组内刷题之LeetCode第188周赛解题思路
组内刷题之LeetCode第188周赛解题思路
组内刷题之LeetCode第188周赛解题思路
1.用栈操作构建数组
题目：给你一个目标数组 target 和一个整数 n。每次迭代，需要从 list = {1,2,3..., n} 中依序读取一个数字。
请使用下述操作来构建目标数组 target ：
Push：从 list 中读取一个新元素， 并将其推入数组中。Pop：删除数组中的最后一个元素。如果目标数组构建完成，就停止读取更多元素。题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。
请返回构建目标数组所用的操作序列。
target是递增数组，n是一个数字，每次我们取target中的元素，看看是否轮询到该元素，如果还没有就push与pop，否则只push。
class Solution {
public:
vector<string> buildArray(vector<int>& target, int n) {
vector<string> res;
int i=1;
for(auto elem : target) {
while(i<elem) {
res.push_back("Push");
res.push_back("Pop");
i++;
}
res.push_back("Push");
i++;
}
return res;
}
};
2.形成两个异或相等的三元数组数目
题目：给你一个整数数组 arr 。
现需要从数组中取三个下标 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。
a 和 b 定义如下：
a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1] b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k] 注意：^ 表示 按位异或 操作。
请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。
本题实现：要求a==b，我们可以知道两个相等异或为0，那么a^b=arr[i]...arr[k]=0，实际就是考察i到k区间有多少个j满足从i到k所有元素的异或为0。
class Solution {
public:
int countTriplets(vector<int>& arr) {
int sz = arr.size();
int ans = 0;
/// a^b = arr[i]^arr[i+1]...^arr[k] j的取值总共有k-i种
for (int i=0;i<sz-1;i++) {
int x = arr[i]; // arr[i]
for (int k=i+1;k<sz;k++) {
x^=arr[k]; // arr[i+1]^....arr[k]
if (x == 0) // a==b
ans+=(k-i); // j的取值
}
}
return ans;
}
};
3.收集树上所有苹果的最少时间
题目：给你一棵有 n 个节点的无向树，节点编号为 0 到 n-1 ，它们中有一些节点有苹果。通过树上的一条边，需要花费 1 秒钟。你从 节点 0 出发，请你返回最少需要多少秒，可以收集到所有苹果，并回到节点 0 。
无向树的边由 edges 给出，其中 edges[i] = [fromi, toi] ，表示有一条边连接 from 和 toi 。除此以外，还有一个布尔数组 hasApple ，其中 hasApple[i] = true 代表节点 i 有一个苹果，否则，节点 i 没有苹果。
难点在于，我们一开始需要构建的是一颗无向树，而不是单纯的有向树，该树是多叉的，我们直接dfs从根节点开始遍历即可，并在遍历过程中保证每个节点被访问一次。
class Solution {
private:
map<int,set<int>> m;
set<int> visited;
public:
int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
// 构建无向树，若不这样构建,测试用例过不了。
/**
4
[[0,2],[0,3],[1,2]]
[false,true,false,false]
*/
for(auto node : edges) {
m[node[0]].insert(node[1]);
m[node[1]].insert(node[0]);
}
return dfs(0,hasApple);
}
int dfs(int root,vector<bool>& hasApple) {
int ret = 0;
visited.insert(root); // 根节点访问了
for(auto child : m[root]) { // 访问子节点
if (!visited.count(child)) { // 子节点没有访问过
int tmp = dfs(child,hasApple); // 取到当前子节点与其孩子的结果
ret += tmp;
if (tmp || hasApple[child]) {
ret += 2; // 取到当前根节点及其子节点后关系链组成的结果
}
}
visited.insert(child);
}
return ret;
}
};
4.切披萨的方案数
题目：给你一个 rows x cols 大小的矩形披萨和一个整数 k ，矩形包含两种字符：'A' （表示苹果）和 '.' （表示空白格子）。你需要切披萨 k-1 次，得到 k 块披萨并送给别人。
切披萨的每一刀，先要选择是向垂直还是水平方向切，再在矩形的边界上选一个切的位置，将披萨一分为二。如果垂直地切披萨，那么需要把左边的部分送给一个人，如果水平地切，那么需要把上面的部分送给一个人。在切完最后一刀后，需要把剩下来的一块送给最后一个人。
请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字，请你返回它对 10^9 + 7 取余的结果。
本题实际上考察由二维前缀和所构造的动态规化问题。
需要明确以下信息：
- 如何求二维前缀和？
给定一个n*m大小的矩阵dp，有q次询问，每次询问给定x1,y1,x2,y2四个数，求以(x1,y1)为左上角坐标和(x2,y2)为右下角坐标的子矩阵的所有元素和。注意仍然包含左上角和右下角的元素。
dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1];//因为dp[i-1][j-1]的值被加了两次
我们每次不管是横切，还是竖切，右下角矩阵被保留了，因此可以通过右下角向左上角的遍历方式来求解，这便想到了递归，在每次切的过程中，题目给定切出的每一块披萨包含至少一个苹果，也就是每次一刀下去苹果会减少，因此我们使用上述二维前缀和计算方法快速求取以当前节点为作为右下角矩阵中左上角，求解当前右下角矩阵的苹果个数。
- 递归终止条件：不能再切了呗，也就是k为1，此时只需要根据还有没有苹果来看一下是返回0，还是返回1，
- 剪枝策略：当右下角苹果个数小于k人，那就分配过程中肯定会有人分配为0的苹果，必然失败，直接返回0。
class Solution {
private:
long long dp[55][55][11];
int apple[55][55]; // 右下角矩阵有多少个苹果
int n,m;
int mod = 1e9 + 7;
public:
int ways(vector<string>& pizza, int k) {
memset(dp,-1,sizeof(dp));
memset(apple,0,sizeof(apple));
n = pizza.size();
m = pizza[0].size();
for (int i=n-1;i>=0;i--) {
for (int j=m-1;j>=0;j--) {
apple[i][j] = apple[i][j+1] + apple[i+1][j] - apple[i+1][j+1];
if (pizza[i][j] == 'A') apple[i][j]++;
}
}
return dfs(0,0,k);
}
long long dfs(int x,int y,int k) {
if(dp[x][y][k]!=-1) return dp[x][y][k];
// 已经是最后一个人了，不能切了
if(k==1) {
if (apple[x][y] == 0) return dp[x][y][k]=0;
else return dp[x][y][k]=1;
}
if (apple[x][y]<k) return dp[x][y][k]=0;
long long ans = 0;
// 横着切
for (int i=x+1;i<n;i++) {
// 题目中提到：每一块披萨包含至少一个苹果，那么每次切后苹果少了才满足题意
if(apple[x][y] - apple[i][y] > 0)
ans += dfs(i,y,k-1);
}
// 竖着切
for (int i=y+1;i<m;i++) {
// 题目中提到：每一块披萨包含至少一个苹果，那么每次切后苹果少了才满足题意
if(apple[x][y] - apple[x][i] > 0)
ans += dfs(x,i,k-1);
}
return dp[x][y][k] = ans%mod;
}
};