【上岸算法福利发放】LeetCode Weekly Contest 188 解题报告
No.1 用栈操作构建数组
★解题思路
既然题目保证有解, 那么就按照 target 的顺序依次构造了. 如果从 list 种获取的数比正在构造的当前 target 中的数要小, 那么就直接 Pop 出去.
代码展示
class Solution {
public List<String> buildArray(int[] target, int n) {
List<String> res = new ArrayList<>();
int now = 1;
for (int num : target) { // 依次构造 num
while (num > now) { // 不想等, 则直接弹出
res.add("Push");
res.add("Pop");
now++;
}
res.add("Push"); // 此时 now == num
now++;
}
return res;
}
}
No.2 形成两个异或相等数组的三元组数目 ★解题思路，方法一
异或的区间和也可以通过两个前缀和异或得到, 比如 [start, end] 区间的异或和就等于 prefix[end] ^ prefix[start - 1], 其中 prefix[i] = arr[0] ^ arr[1] ^ ... ^arr[i] (当 start == 0 时无需再异或 prefix[start - 1], 区间和直接就是 prefix[end]) 求出异或的前缀和数组, 然后枚举所有的三元组 (i, j, k)，时间复杂度: o(n^3)
代码展示
class Solution {
public int countTriplets(int[] arr) {
if (arr.length == 0) {
return 0;
}
int[] prefix = new int[arr.length];
prefix[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
prefix[i] = prefix[i - 1] ^ arr[i];
}
int res = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
for (int k = j; k < arr.length; k++) {
if (xorSum(i, j - 1, prefix) == xorSum(j, k, prefix)) {
res++;
}
}
}
}
return res;
}
private int xorSum(int start, int end, int[] prefix) {
return start == 0 ? prefix[end] : prefix[end] ^ prefix[start - 1];
}
}
★解题思路，方法二
我们可以避免完全枚举三元组, 而是用一个 Map 来记录某一个异或和出现的次数. 详见代码注释.
时间复杂度 o(n^2)
代码展示
class Solution {
public int countTriplets(int[] arr) {
if (arr.length == 0) {
return 0;
}
int[] prefix = new int[arr.length];
prefix[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
prefix[i] = prefix[i - 1] ^ arr[i];
}
int res = 0;
for (int j = 1; j < arr.length; j++) {
// 计算每一个 i 对应的 [i, j) 的异或和
// count[sum] 表示这些异或和中 sum 出现的次数
Map<Integer, Integer> count = new HashMap<>();
for (int i = 0; i < j; i++) {
int xs = xorSum(i, j - 1, prefix);
count.put(xs, count.getOrDefault(xs, 0) + 1);
}
// 计算每一个 k 对应的 [j, k] 的异或和
// 直接通过 count 就可以得知该异或和在 [i, j) 中出现的次数
for (int k = j; k < arr.length; k++) {
res += count.getOrDefault(xorSum(j, k, prefix), 0);
}
}
return res;
}
private int xorSum(int start, int end, int[] prefix) {
return start == 0 ? prefix[end] : prefix[end] ^ prefix[start - 1];
}
}
No.3 收集树上所有苹果的最少时间
★解题思路
想象我们收集苹果的过程: 当前站在树根, 只有某棵子树中含有苹果时, 我们才走到对应的子节点上.
所以整体需要两次 DFS, 第一次统计出以每个节点为根的子树上是否有苹果, 第二次即收集苹果的过程.
代码展示
class Solution {
private boolean[] subTreeHasApple;
private List<List<Integer>> neighbors;
private List<Boolean> hasApple;
public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
subTreeHasApple = new boolean[n];
this.hasApple = hasApple;
// 构造邻接表, 方便 DFS, neighbors[i] 表示与 i 相邻的所有点
neighbors = new ArrayList<>();
for (int i = 0; i < n; i++) {
neighbors.add(new ArrayList<>());
}
// 树是无向图, 所以未必 [from, to] 中 from 一定是父亲
for (var edge : edges) {
neighbors.get(edge[0]).add(edge[1]);
neighbors.get(edge[1]).add(edge[0]);
}
getSubTreeHasApple(-1, 0);
return getAnswer(-1, 0);
}
private int getAnswer(int father, int current) {
int res = 0;
for (int next : neighbors.get(current)) {
if (next != father && subTreeHasApple[next]) {
// 走到 next 需要 1 步
// 从 next 收集需要 getAnswer() 步
// 再从 next 走回 current, 还需要 1 步
res += getAnswer(current, next) + 2;
}
}
return res;
}
private void getSubTreeHasApple(int father, int current) {
if (hasApple.get(current)) {
subTreeHasApple[current] = true;
}
for (int next : neighbors.get(current)) {
if (next != father) {
getSubTreeHasApple(current, next);
subTreeHasApple[current] |= subTreeHasApple[next];
}
}
}
}
No.4 切披萨的方案数 ★解题思路
动态规划问题
该问题每次都把上边或左边的给别人, 所以剩下的一定是原 pizza 中的以 (i, j) 为左上角的, 以 (n - 1, m - 1) 为右下角的 pizza. 所以状态可以用左上角坐标 (i, j) 来表示
定义状态: f[i][j][k] 表示剩下的 pizza 的左上角坐标为 (i, j), 还需要切出去 k 块时, 有多少方案
状态转移: f[i][j][k] = sum{ f[ni][j][k - 1] } + sum{ f[i][nj][k - 1] } 其中 i < ni, j < nj 并且要保证切出去的那一块有苹果
边界状态: f[i][j][0] = 1 或 0 取决于以 (i, j) 为左上角的 pizza 中有无苹果
代码展示
class Solution {
String[] pizza;
private int[][] rowSum, colSum;
private int[][][] f;
public int ways(String[] pizza, int k) {
this.pizza = pizza;
int n = pizza.length;
int m = pizza[0].length();
// 计算两个前缀和数组, 方便快速得知切下来的 pizza 中是否有苹果
rowSum = new int[n][m]; // rowSum[i][j] 表示 (i, j) 位置之后的行内的苹果数
colSum = new int[n][m]; // colSum[i][j] 表示 (i, j) 位置之下的列内的苹果数
for (int i = 0; i < n; i++) {
rowSum[i][m - 1] = pizza[i].charAt(m - 1) == 'A' ? 1 : 0;
for (int j = m - 2; j >= 0; j--) {
rowSum[i][j] = rowSum[i][j + 1] + (pizza[i].charAt(j) == 'A' ? 1 : 0);
}
}
for (int i = 0; i < m; i++) {
colSum[n - 1][i] = pizza[n - 1].charAt(i) == 'A' ? 1 : 0;
for (int j = n - 2; j >= 0; j--) {
colSum[j][i] = colSum[j + 1][i] + (pizza[j].charAt(i) == 'A' ? 1 : 0);
}
}
// 初始化所有未计算的状态为 -1
f = new int[n][m][k];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
Arrays.fill(f[i][j], -1);
}
}
// 记忆化搜索
return dp(0, 0, k - 1);
}
private int dp(int x, int y, int k) {
if (f[x][y][k] >= 0) {
return f[x][y][k];
}
// 边界状态
if (k == 0) {
for (int i = x; i < pizza.length; i++) {
if (rowSum[i][y] > 0) {
return f[x][y][k] = 1;
}
}
return f[x][y][k] = 0;
}
// 状态转移: 枚举切下来的是哪一块即可
long res = 0;
// 横着切
for (int nx = x + 1, apples = 0; nx < pizza.length; nx++) {
apples += rowSum[nx - 1][y];
// 切下来的部分中苹果数量大于 0 才进行转移
if (apples > 0) {
res += dp(nx, y, k - 1);
res %= 1000000007;
}
}
// 竖着切
for (int ny = y + 1, apples = 0; ny < pizza[0].length(); ny++) {
apples += colSum[x][ny - 1];
if (apples > 0) {
res += dp(x, ny, k - 1);
res %= 1000000007;
}
}
return f[x][y][k] = (int)res;
}
}
创作新主题