1089. 复写零
https://leetcode-cn.com/contest/weekly-contest-141/problems/duplicate-zeros/
给你一个长度固定的整数数组 arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意：请不要在超过该数组长度的位置写入元素。
要求：请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。示例 1：
输入：[1,0,2,3,0,4,5,0]
输出：null
解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]示例 2：
输入：[1,2,3]
输出：null
解释：调用函数后，输入的数组将被修改为：[1,2,3]提示：
1 <= arr.length <= 10000
0 <= arr[i] <= 9
遍历数组，判断某位等于零就在该位插入零，并将引索后移一位，最后删除原数组长度后面的内容
class Solution {
public:
void duplicateZeros(vector<int>& arr)
{
int N=arr.size();
for(int i=0;i<N;i++) if(arr[i]==0) arr.insert(arr.begin()+(i++),0);
arr.erase(arr.begin()+N,arr.end());
}
};
1090.受标签影响的最大值
https://leetcode-cn.com/contest/weekly-contest-141/problems/largest-values-from-labels/
我们有一个项的集合，其中第 i 项的值为 values[i]，标签为 labels[i]。
我们从这些项中选出一个子集 S，这样一来：
|S| <= num_wanted
对于任意的标签 L，子集 S 中标签为 L 的项的数目总满足 <= use_limit。
返回子集 S 的最大可能的 和。示例 1：
输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1
输出：9
解释：选出的子集是第一项，第三项和第五项。示例 2：
输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2
输出：12
解释：选出的子集是第一项，第二项和第三项。示例 3：
输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 1
输出：16
解释：选出的子集是第一项和第四项。示例 4：
输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2
输出：24
解释：选出的子集是第一项，第二项和第四项。提示：
1 <= values.length == labels.length <= 20000
0 <= values[i], labels[i] <= 20000
1 <= num_wanted, use_limit <= values.length
将values和labels组合为一个数据num，并按values从大到小排序，用vis记录每个labels的使用次数
对num遍历，如果某位的标签的使用次数小于use_limit，将其values 选出，总计数加一
当总计数等于num_wanted或者遍历结束后，返回结果
class Solution {
public:
static bool cmp(const pair<int,int> a,const pair<int,int> b)
{
return a.first> b.first;
}
int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit)
{
int N=values.size(),ans=0,count=0;
vector<pair<int,int>> num;
int vis[20000+5];
memset(vis,0,sizeof(vis));
for(int i=0;i<N;i++)
{
num.push_back(make_pair(values[i],labels[i]));
// cout<<num[i].first<<" "<<num[i].second<<endl;
}
sort(num.begin(),num.end(),cmp);
// for(int i=0;i<N;i++) cout<<num[i].first<<" "<<num[i].second<<endl;
for(int i=0;i<N;i++)
{
if(count==num_wanted) break;
if(vis[num[i].second]<use_limit)
{
ans+=num[i].first;
vis[num[i].second]++;
count++;
}
}
return ans;
}
};
1091. 二进制矩阵中的最短路径
https://leetcode-cn.com/contest/weekly-contest-141/problems/shortest-path-in-binary-matrix/
在一个 N × N 的方形网格中，每个单元格有两种状态：空（0）或者阻塞（1）。
一条从左上角到右下角、长度为 k 的畅通路径，由满足下述条件的单元格 C_1, C_2, ..., C_k 组成：
相邻单元格 C_i 和 C_{i+1} 在八个方向之一上连通（此时，C_i 和 C_{i+1} 不同且共享边或角）
C_1 位于 (0, 0)（即，值为 grid[0][0]）
C_k 位于 (N-1, N-1)（即，值为 grid[N-1][N-1]）
如果 C_i 位于 (r, c)，则 grid[r][c] 为空（即，grid[r][c] == 0）
返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径，返回 -1 。示例 1：
输入：[[0,1],[1,0]]
输出：2示例 2：
输入：[[0,0,0],[1,1,0],[1,1,0]]
输出：4
提示：
1 <= grid.length == grid[0].length <= 100
grid[i][j] 为 0 或 1
class Solution {
public:
int N,minn=1;
int dr[8][2]={{1,1},{1,0},{0,1},{1,-1},{-1,1},{0,-1},{-1,0},{-1,-1}};
struct Q
{
int x,y;
Q(int x,int y):x(x),y(y){}
};
int bfs(const vector<vector<int>>& grid)
{
Q p(0,0);
queue<Q> res;
res.push(p);
set<int> sq;
sq.insert(0);
while(res.size())
{
p=res.front();
res.pop();
if(p.x==0 &&p.y==0)
{
minn++;
res.push(p);
}
for(int i=0;i<8;i++)
{
int dx=p.x+dr[i][0],dy=p.y+dr[i][1];
if(dx>=N || dx<0 || dy>=N || dy<0 || grid[dy][dx]) continue;
if(sq.count(dx*110+dy)) continue;
// cout<<dx<<" "<<dy<<" "<<minn<<" i="<<i<<" vis"<<vis[dy][dx]<<endl;
if(dx==N-1 && dy==N-1)
{
// cout<<p.x<<" "<<y<<" "<<k<<" vni"<<endl;
return minn;
}
Q t(dx,dy);
sq.insert(dx*110+dy);
res.push(t);
}
if(res.size()==1) break;
}
return -1;
}
int shortestPathBinaryMatrix(vector<vector<int>>& grid)
{
memset(vis,0,sizeof(vis));
N=grid.size();
if(grid[N-1][N-1]==1 || grid[0][0]==1) return -1;
return bfs(grid);
}
};
bfs，用一个set保存每次到达的点，由题目横纵坐标都不超过一百，只需存一个x*110+y即可
要提前判断起点和终点是否为1，若是直接返回-1
1092. 最短公共超序列
https://leetcode-cn.com/contest/weekly-contest-141/problems/shortest-common-supersequence/
给出两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为子序列的最短字符串。如果答案不止一个，则可以返回满足条件的任意一个答案。
（如果从字符串 T 中删除一些字符（也可能不删除，并且选出的这些字符可以位于 T 中的 任意位置），可以得到字符串 S，那么 S 就是 T 的子序列）示例：
输入：str1 = "abac", str2 = "cab"
输出："cabac"
解释：
str1 = "abac" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 的第一个 "c"得到 "abac"。
str2 = "cab" 是 "cabac" 的一个子串，因为我们可以删去 "cabac" 末尾的 "ac" 得到 "cab"。
最终我们给出的答案是满足上述属性的最短字符串。提示：
1 <= str1.length, str2.length <= 1000
str1 和 str2 都由小写英文字母组成。
一开始理解错了，这道题还是要求最长公共子序列。
先用动态规划求出最长公共子序列，dp[i][j]表示str1的前i个字符和str2的前j个字符的最长公共子序列，转移时有两种情况：
1.str1[i]==str2[j] ，此时dp[i][j]=dp[i-1][j-1]+1;
2.否则，dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
然后从后遍历dp，求得字符串ans
class Solution {
public:
string shortestCommonSupersequence(string str1, string str2)
{
int N=str1.size(),M=str2.size();
vector<vector<int>> dp(N+1,vector<int>(M+1,0));
str1=" "+str1;
str2=" "+str2;
for(int i=1;i<=N;i++) for(int j=1;j<=M;j++)
{
if((str1[i]==str2[j])) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
// for(int i=1;i<=N;i++)
// {
// for(int j=1;j<=M;j++) cout<<dp[i][j]<<" ";
// cout<<endl;
// }
string ans="";
int i=N,j=M;
while(i>0 || j>0)
{
if(i==0)
{
ans=str2[j]+ans;
j--;
}
else if(j==0)
{
ans=str1[i]+ans;
i--;
}
else
{
if(str1[i]==str2[j])
{
ans=str1[i]+ans;
i--;
j--;
}
else
{
if(dp[i][j]==dp[i-1][j])
{
ans=str1[i]+ans;
i--;
}
else
{
ans=str2[j]+ans;
j--;
}
}
}
}
return ans;
}
};
