LeetcodeWk188

写在前面

太久没有做过周赛题了,偶尔来做一做,感觉真是越来越菜了

第 188 场周赛

题目

A. 用栈操作构建数组

给你一个目标数组 target 和一个整数 n。每次迭代,需要从 list = {1,2,3..., n} 中依序读取一个数字。

请使用下述操作来构建目标数组 target

  • Push:从 list 中读取一个新元素, 并将其推入数组中。
  • Pop:删除数组中的最后一个元素。
  • 如果目标数组构建完成,就停止读取更多元素。

题目数据保证目标数组严格递增,并且只包含 1n 之间的数字。

请返回构建目标数组所用的操作序列。

题目数据保证答案是唯一的。

示例 1:

1
2
3
4
5
6
输入:target = [1,3], n = 3
输出:["Push","Push","Pop","Push"]
解释:
读取 1 并自动推入数组 -> [1]
读取 2 并自动推入数组,然后删除它 -> [1]
读取 3 并自动推入数组 -> [1,3]

示例 2:

1
2
输入:target = [1,2,3], n = 3
输出:["Push","Push","Push"]

示例 3:

1
2
3
输入:target = [1,2], n = 4
输出:["Push","Push"]
解释:只需要读取前 2 个数字就可以停止。

示例 4:

1
2
输入:target = [2,3,4], n = 4
输出:["Push","Pop","Push","Push","Push"]

提示:

  • 1 <= target.length <= 100
  • 1 <= target[i] <= 100
  • 1 <= n <= 100
  • target 是严格递增的

直接模拟即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public List<String> buildArray(int[] target, int n) {
List<String> ans=new ArrayList<>();
int pos=0;
for(int i=1;i<=n&&pos<target.length;i++){
if(target[pos]==i){
ans.add("Push");
pos++;
}else{
ans.add("Push");
ans.add("Pop");
}
}
return ans;
}
}

B. 形成两个异或相等数组的三元组数目

给你一个整数数组 arr

现需要从数组中取三个下标 ijk ,其中 (0 <= i < j <= k < arr.length)

ab 定义如下:

  • a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
  • b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

注意:^ 表示 按位异或 操作。

请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。

前缀后然后枚举(i,j,k)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int countTriplets(int[] arr) {
int ans=0;
int n = arr.length;
int []sum=new int[n+1];
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]^arr[i-1];
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
for(int k=j;k<=n;k++){
int a= sum[i-1] ^ sum[j-1];
int b= sum[j-1] ^ sum[k];
if(a==b) ans++;
}
}
}
return ans;
}
}

C. 收集树上所有苹果的最少时间

给你一棵有 n 个节点的无向树,节点编号为 0n-1 ,它们中有一些节点有苹果。通过树上的一条边,需要花费 1 秒钟。你从 节点 0 出发,请你返回最少需要多少秒,可以收集到所有苹果,并回到节点 0 。

无向树的边由 edges 给出,其中 edges[i] = [fromi, toi] ,表示有一条边连接 fromtoi 。除此以外,还有一个布尔数组 hasApple ,其中 hasApple[i] = true 代表节点 i 有一个苹果,否则,节点 i 没有苹果。

示例 1:

img

1
2
3
输入:n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
输出:8
解释:上图展示了给定的树,其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。

示例 2:

img

1
2
3
输入:n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]
输出:6
解释:上图展示了给定的树,其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。

示例 3:

1
2
输入:n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false]
输出:0

提示:

  • 1 <= n <= 10^5
  • edges.length == n-1
  • edges[i].length == 2
  • 0 <= fromi, toi <= n-1
  • fromi < toi
  • hasApple.length == n

我们考虑 子问题 跑完cur

如果cur为空,答案显然为1

如果cur这棵子树没有苹果,那么答案为0

如果有苹果,可以分为

  • 只有根有苹果: 实际上答案也是0
  • 其它: 我们继续向下遍历

考虑所有有苹果的儿子子树,我们只需得到对应的消耗步数,然后再加下去上来的两步,如果没有则是0

如果cur就是树根,那么不用考虑+2,因为不会下去上来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
vector<int> e[100000];
vector<bool> val;
int DFS(int cur){
if(e[cur].size()==0) return val[cur] ? 2 : 0;
int ret=0;
for(auto v : e[cur]) ret+=DFS(v);
if(cur==0) return ret;
if(val[cur]&&ret==0) return 2;
else if(!val[cur]&&ret==0) return 0;
return ret+2;
}
int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
if(n==1) return 0;
val=hasApple;
for(int i=0;i<n;i++) e[i].clear();
for(auto lis : edges){
int a=lis[0];
int b=lis[1];
e[a].push_back(b);
}
return DFS(0);
}
};

D. 切披萨的方案数

给你一个 rows x cols 大小的矩形披萨和一个整数 k ,矩形包含两种字符: 'A' (表示苹果)和 '.' (表示空白格子)。你需要切披萨 k-1 次,得到 k 块披萨并送给别人。

切披萨的每一刀,先要选择是向垂直还是水平方向切,再在矩形的边界上选一个切的位置,将披萨一分为二。如果垂直地切披萨,那么需要把左边的部分送给一个人,如果水平地切,那么需要把上面的部分送给一个人。在切完最后一刀后,需要把剩下来的一块送给最后一个人。

请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字,请你返回它对 10^9 + 7 取余的结果。

示例 1:

img

1
2
3
输入:pizza = ["A..","AAA","..."], k = 3
输出:3
解释:上图展示了三种切披萨的方案。注意每一块披萨都至少包含一个苹果。

示例 2:

1
2
输入:pizza = ["A..","AA.","..."], k = 3
输出:1

示例 3:

1
2
输入:pizza = ["A..","A..","..."], k = 1
输出:1

提示:

  • 1 <= rows, cols <= 50
  • rows == pizza.length
  • cols == pizza[i].length
  • 1 <= k <= 10
  • pizza 只包含字符 'A''.'

直接使用记忆化搜索即可

注意状态的表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
int MOD=1000000007;
int mk=0;
int [][][]dp=null;
int [][]sum;
int DFS(int dep,int a,int b,int c,int d){
if(dp[a][b][dep]!=-1) return dp[a][b][dep];
int all = sum[a-1][b-1] + sum[c][d] - sum[c][b-1] - sum[a-1][d];
int ret=0;
if(dep==mk) {
for(int i=a;i<c;i++){
int val = sum[i][d] + sum[a-1][b-1] - sum[i][b-1] -sum[a-1][d];
if(val>0 && val < all) ret++;
}
for(int j=b;j<d;j++){
int val = sum[c][j] + sum[a-1][b-1] -sum[a-1][j] - sum[c][b-1];
if(val>0 && val < all) ret++;
}
dp[a][b][dep]=ret;
return ret;
}
for(int i=c-1;i>=a;i--){
int val = sum[i][d] + sum[a-1][b-1] - sum[i][b-1] -sum[a-1][d];
if(val > 0&& val <all )ret= (ret+ DFS(dep+1,i+1,b,c,d))%MOD;
}
for(int j=d-1;j>=b;j--){
int val = sum[c][j] + sum[a-1][b-1] -sum[a-1][j] - sum[c][b-1];
if(val > 0 && val < all) ret = (ret + DFS(dep+1,a,j+1,c,d))%MOD;
}
dp[a][b][dep]=ret;
return ret;
}
public int ways(String[] pizza, int k) {
mk=k-1;
int a=1;
int b=1;
int n=pizza.length;
int m=pizza[0].length();
char [][]mp=new char[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++) mp[i][j]=pizza[i].charAt(j);
}
sum=new int[n+1][m+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int x= mp[i-1][j-1]=='A' ? 1 : 0;
sum[i][j]= x + sum[i-1][j] + sum[i][j-1]- sum[i-1][j-1];
}
}
dp=new int[n+1][m+1][k+1];
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
for(int dep=0;dep<=k;dep++) dp[i][j][dep]=-1;
}
}
if(mk==0){
if(sum[n][m] > 0) return 1;
else return 0;
}
return DFS(1,a,b,n,m);
}
}

总结

太久没做了,还是有些生疏了,第三题写了好久,然后第四题脑抽了写了更久