A 题链接
给你一个目标数组 target 和一个整数 n. 每次迭代, 需要从 list = {1,2,3..., n} 中依序读取一个数字.
请使用下述操作来构建目标数组 target :
Push: 从 list 中读取一个新元素, 并将其推入数组中.
Pop: 删除数组中的最后一个元素.
如果目标数组构建完成, 就停止读取更多元素.
题目数据保证目标数组严格递增, 并且只包含 1 到 n 之间的数字.
请返回构建目标数组所用的操作序列.
题目数据保证答案是唯一的.
示例 1
输入: target = [1,3], n = 3
输出:["Push","Push","Pop","Push"]
解释:
读取 1 并自动推入数组 -> [1]
读取 2 并自动推入数组, 然后删除它 -> [1]
读取 3 并自动推入数组 -> [1,3]
示例 2:
输入: target = [1,2,3], n = 3
输出:["Push","Push","Push"]
示例 3:
输入: target = [1,2], n = 4
输出:["Push","Push"]
解释: 只需要读取前 2 个数字就可以停止.
提示:
- 1 <= target.length <= 100
- 1 <= target[i] <= 100
- 1 <= n <= 100
target 是严格递增的
- class Solution {
- public:
- // 正常判断是否需要在 target 数组中存储, 同时如果足够了即可 break
- vector<string> buildArray(vector<int>& target, int n) {
- vector<string>v;
- int len = target.size();
- int j = 0;
- for(int i = 1;i <=n ;++i){
- if(j == len)break;
- if(i == target[j]){
- v.push_back("Push");
- ++j;
- }
- else{
- v.push_back("Push");
- v.push_back("Pop");
- }
- }
- return v;
- }
- };
[B 题](https://leetcode-cn.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/)
给你一个整数数组 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)$ 的数目.
示例 1:
输入: arr = [2,3,1,6,7]
输出: 4
解释: 满足题意的三元组分别是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4)
示例 2:
输入: arr = [1,1,1,1,1]
输出: 10
示例 3:
输入: arr = [2,3]
输出: 0
思路:
arr[i]...arr[j-1]的异或结果可以转化为(arr[0]...arr[j-1])(arr[0]...^arr[i-1]), 因为相同的值异或为 0, 而异或一个 0 是不影响原结果的. 因此事先计算出会用到的异或结果, 用数组 dp 保存.
- class Solution {
- public:
- int countTriplets(vector<int>& a) {
- int n = a.size();
- vector<int> s(n+1);
- for (int i = 1; i <= n; ++ i)
- s[i] = s[i-1]^a[i-1];
- int ret = 0;
- for (int i = 1; i <= n; ++ i)
- for (int j = i+1; j <= n; ++ j)
- for (int k = j; k <= n; ++ k)
- {
- if ((s[j-1]^s[i-1]) == (s[k]^s[j-1])) ret ++;
- }
- return ret;
- }
- };
[C 题](https://leetcode-cn.com/problems/minimum-time-to-collect-all-apples-in-a-tree/)
给你一棵有 n 个节点的无向树, 节点编号为 0 到 n-1 , 它们中有一些节点有苹果. 通过树上的一条边, 需要花费 1 秒钟. 你从 节点 0 出发, 请你返回最少需要多少秒, 可以收集到所有苹果, 并回到节点 0 .
无向树的边由 edges 给出, 其中 edges[i] = [fromi, toi] , 表示有一条边连接 from 和 toi . 除此以外, 还有一个布尔数组 hasApple , 其中 hasApple[i] = true 代表节点 i 有一个苹果, 否则, 节点 i 没有苹果.
示例 1:
输入: 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:
输入: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]
输出: 6
解释: 上图展示了给定的树, 其中红色节点表示有苹果. 一个能收集到所有苹果的最优方案由绿色箭头表示.
思路:
只要那个节点是 true, 向上一直将父节点同化, 那么路径就等于: 每两个连接 (子, 父都为 true) 的点的那条线 x 2 后的和
- class Solution {
- public:
- int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
- int i,res=0;
- // 若子节点为 true, 则父节点同化为 true
- for(i=edges.size()-1; i>=0; i--)
- if(hasApple[edges[i][1]]==true)
- hasApple[edges[i][0]]=true;
- // 收集苹果的路径即为所有节点为 true 的拓扑图的所有连线 * 2
- for(i=0; i<edges.size(); i++)
- if(hasApple[edges[i][1]]==true) res +=2;
- return res;
- }
- };
D 题
给你一个 rows x cols 大小的矩形披萨和一个整数 k , 矩形包含两种字符: 'A' (表示苹果)和 '.' (表示空白格子). 你需要切披萨 k-1 次, 得到 k 块披萨并送给别人.
切披萨的每一刀, 先要选择是向垂直还是水平方向切, 再在矩形的边界上选一个切的位置, 将披萨一分为二. 如果垂直地切披萨, 那么需要把左边的部分送给一个人, 如果水平地切, 那么需要把上面的部分送给一个人. 在切完最后一刀后, 需要把剩下来的一块送给最后一个人.
请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数. 由于答案可能是个很大的数字, 请你返回它对 10^9 + 7 取余的结果.
示例 1:
输入: pizza = ["A..","AAA","..."], k = 3
输出: 3
解释: 上图展示了三种切披萨的方案. 注意每一块披萨都至少包含一个苹果.
示例 2:
输入: pizza = ["A..","AA.","..."], k = 3
输出: 1
示例 3:
输入: pizza = ["A..","A..","..."], k = 1
输出: 1
- 1 <= rows, cols <= 50
- rows == pizza.length
- cols == pizza[i].length
- 1 <= k <= 10
pizza 只包含字符'A' 和 '.' .
思路:
本题是统计切割方案数, 一看就是使用 dp, 怎么来思考呢?
首先我们考虑存在的状态数:
毫无疑问, 披萨被切成 k 块肯定是状态之一.
而如何表示当前剩余部分的披萨呢? 题中说把左边和上边给一个人, 可以知道, 右下部分总是会剩余下来.
所以可以记录左上角的位置来表示剩余的披萨.
因此一个三维数组可以做为 dp 数组: dp[i][j][k]
i,j 表示披萨剩余部分的左上角, k 表示当前披萨被切成 k 块
初始状态显而易见, 由于只有一块, 没有切, 左上角为(0,0), 所以 dp[0][0][1]=1
状态转移
知道初始状态后, 我们就要开始进行状态转移了~
首先让我们来考虑怎么从一块变成两块
披萨:
A..
AAA
...
由于我们知道可以水平切和垂直切, 左上角为(i,j), 一刀切下去, 可以从 k 变成 k+1
因此, 我们可以穷举每个状态水平切和垂直切的所有切法, 来得到 k+1 的状态.
因为每切一次得到的剩余披萨左上角都不同, 所以不会出现重复.
首先水平切:
左上角为(0,0),k=1
- A.. A..
- +++ AAA
- AAA +++
- ... ...
剩余部分: 左上角为(1,0),k=2 剩余部分: 左上角为(2,0),k=2 (不合理)
有这两种切法, 很清楚看出来, 第二种切法是不可以的, 因为下面那一部分不存在 A, 不符合题意.
如何判断剩余和切出来的披萨存不存在 A, 我们先记下这个问题, 后面会提到.
所以可以得到水平切的状态转移方程:
记原来的左上角为(i,j), 新的左上角为(x,y)
- if(两部分都存在 A){
- dp[x][y][k+1]+=dp[i][j][k]
- }
垂直切是和水平切一样的, 就不说了.
解决存在 A 的问题
我们如何判断切开后的两块披萨是否存在 A 呢?
方法 1: 直接暴力求解, 我不知道会不会超时, 我没有试, 有兴趣可以写一下.
方法 2: 利用数学知识, 计算出来对应披萨块中 A 的数量, 假如数量大于 0, 则存在 A
方法 3: 别的方法, 假如有人愿意分享更简单的, 可以在评论分享, 大家一起进步
我使用方法 2, 所以就写一下方法 2:
用数组 num[i][j]表示以 (0,0) 为左上角,(i,j)为右下角的披萨块中包含的 A 数量
上例中:
- num:
- 1 1 1
- 2 3 4
- 2 3 4
怎么计算 num 数组使用简单的 dp 和数学知识就可以了, 这里就不再赘述.
通过 num 数组和获得披萨块的左上角和右下角就可以轻易地算出 A 的个数:
这个大家肯定都会, 就举个例子吧, 就是简单的数学关系:
例: 计算以 (1,0) 为左上角,(2,2)为右下角的披萨块 A 数目:
num[2][2]-num[0][2]-num[2][-1]+num[0][-1];
下标中出现 - 1 的 num 值都用 0 代替: 所以为 4-1-0-0=3
看不懂的可以直接看代码如何计算 A 数目, 一看就明白了
- #define ll long long int
- class Solution {
- public:
- const ll mod=1e9+7;
- int ways(vector<string>& pizza, int k) {
- int row=pizza.size(),col=pizza[0].length();
- // 计算 num
- vector<vector<int>> num(row,vector<int>(col,0));
- if(pizza[0][0]=='A') num[0][0]=1;
- for(int i=1;i<row;i++) num[i][0]=num[i-1][0]+(pizza[i][0]=='A');
- for(int i=1;i<col;i++) num[0][i]=num[0][i-1]+(pizza[0][i]=='A');
- for(int i=1;i<row;i++) for(int j=1;j<col;j++)
- num[i][j]=num[i-1][j]+num[i][j-1]-num[i-1][j-1]+(pizza[i][j]=='A');
- // 初始化 dp
- vector<vector<vector<ll>>> dp(row,vector<vector<ll>>(col,vector<ll>(k+1,0)));
- dp[0][0][1]=1;
- // 从 k=2 开始填充
- for(int x=2;x<=k;x++){
- for(int i=0;i<row;i++){
- for(int j=0;j<col;j++){
- //dp 为 0 代表不存在这种情况
- if(dp[i][j][x-1]==0)
- continue;
- // 穷举水平切
- for(int z=i+1;z<row;z++){
- if(hasA(num,i,j,z-1,col-1) && hasA(num,z,j,row-1,col-1)){
- dp[z][j][x]+=dp[i][j][x-1];
- dp[z][j][x]%=mod;
- }
- }
- // 穷举垂直切
- for(int z=j+1;z<col;z++){
- if(hasA(num,i,j,row-1,z-1) && hasA(num,i,z,row-1,col-1)){
- dp[i][z][x]+=dp[i][j][x-1];
- dp[i][z][x]%=mod;
- }
- }
- }
- }
- }
- // 计算答案
- ll ans=0;
- for(int i=0;i<row;i++){
- for(int j=0;j<col;j++){
- ans+=dp[i][j][k];
- }
- ans%=mod;
- }
- return ans;
- }
- // 计算存在 A 吗
- bool hasA(vector<vector<int>>& num,int sr,int sc,int er,int ec){
- int num1=0,num2=0,num3=0,res;
- if(sr!=0 && sc!=0) num1=num[sr-1][sc-1];
- if(sr!=0) num2=num[sr-1][ec];
- if(sc!=0) num3=num[er][sc-1];
- return num[er][ec]-num2-num3+num1>0;
- }
- };
来源: https://www.cnblogs.com/RioTian/p/12863004.html