LeetCode-Weekly Contest 141

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;
    }
};