讨论/题目交流/🏆 第 170 场力扣周赛/
🏆 第 170 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 解码字母到整数映射
5 分 - 子数组异或查询
5 分 - 获取你好友已观看的视频
7 分 - 让字符串成为回文串的最少插入次数

展开讨论

哭脸, 第四题太简单了根本不符合hard的。
倒是我第三题map不熟练坑死我了, 前一百都没进。

一点发答案。

T1: 简单的一个扫描题。按照‘#’分割即可。 注意两点。第一, ‘#’前的一定是两位数字, 第二, 最后没有'#‘那一段也需要解析。

class Solution {
public:
    
    char single[10]={' ', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'};
    
    string freqAlphabets(string s) {
        int lastSharp = -1;
        
        int n = s.length();
        
        string ans = "";
        
        for(int i = 0; i < n; i++){
            if(s[i] == '#'){
                for(int j = lastSharp + 1; j < i - 2; j++){
                    ans = ans + single[s[j] - '0'];
                }
                
                int h = s[i - 2] - '0';
                int l = s[i - 1] - '0';
                
                int cid = h * 10 + l + 'a' - 1;
                
                ans = ans + (char)cid;
                
                lastSharp = i;
            }
        }
        
        if(lastSharp < n - 1){
            for(int j = lastSharp + 1; j < n; j++){
                    ans = ans + single[s[j] - '0'];
            }
        }
        
        return ans;
    }
};

时间复杂度: O(N)O(N)
空间复杂度: O(1)O(1) 额外仅需要常数空间。

T2: 只需要知道xor有一个性质就好了。 即 $ a xor b xor b = a $ 即可。 另外xor也有交换律, 所以直接前缀 xor sum就可以了。

class Solution {
public:
    
    int *prefix;
    
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        int n = arr.size();
        prefix = (int *)malloc(sizeof(int) * (n + 1));
        
        prefix[0] = 0;
        for(int i = 0; i < n; i++){
            prefix[i + 1] = prefix[i] ^ arr[i];
        }
        
        vector<int>ans;
        ans.clear();
        
        int m = queries.size();
        
        for(int i = 0; i < m; i++){
            int x = queries[i][0], y = queries[i][1];
            int ret = prefix[y + 1] ^ prefix[x];
            
            ans.push_back(ret);
        }
        
        return ans;
    }
};

时间复杂度: O(N)O(N)
空间复杂度: O(N)O(N) 需要额外前缀和数组。

T3: 读懂题了很简单。 实际上就是取BFS层次遍历后第levellevel层所有节点。 将其看过的影片全部加起来就可以了。 这个使用map维护即可。

struct myVideos{
    string name;
    int val;
    
    bool operator <(myVideos other){
        return val < other.val || (val == other.val && name < other.name);
    }
};

class Solution {
public:
    
    static const int maxn = 10003;
    
    int q[maxn], vis[maxn], dist[maxn];
    
    myVideos vi[maxn];
    
    
    map<string, int> videos;
    
    vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
        int n = watchedVideos.size();
        
        int front, rear;
        front = rear = 1;
        vis[id] = 1;
        dist[id] = 0;
        q[rear++] = id;
        
        
        while(front != rear){  //BFS
            int i = q[front++];
            for(int k = 0; k < friends[i].size(); k++){
                int j = friends[i][k];
                if(!vis[j]){
                    vis[j] = 1;
                    q[rear++] = j;
                    dist[j] = dist[i] + 1;
                    
                    if(dist[j] == level){
                        for(int u = 0; u < watchedVideos[j].size(); u++){
                            videos[watchedVideos[j][u]] += 1;
                        }
                    }
                }
            }
        }
        
        vector<string>ans;
        
        int cnt = 0;
        for(auto &v : videos){
            vi[cnt].name = v.first;
            vi[cnt].val = v.second;
            cnt++;
        }
        
        sort(vi, vi + cnt);
        for(int i = 0; i < cnt; i++){
            ans.push_back(vi[i].name);
        }

        return ans;
    }
};

时间复杂度: O(N+M)O(N + M)
空间复杂度: O(N+M)O(N + M)

其中 NN为人数, MM为所有影片数。

T4: 简单的dp. 在我看来甚至没有T3难。 个人是第二个就做了这个题。

想象一个字符串ss, 如果想要把其变成回文串, 则对其任何一个字符, 其对称位置上可以需要有一个字符。 该操作等价于下面的操作。

  1. 在字符串开头删去一个字符, 记操作数 + 1;
  2. 在字符串结尾删去一个字符, 记操作数 + 1;
  3. 若字符串开头和结尾字符相同, 则同时从开头和结尾删去一个字符, 操作数不变。

现给出一个字符串's', 将其用上述方法删除到空串的最小操作次数。

依此, 可以写出动态规划方程。

$ f(s) = f(s[1...n-2]) (if s[0] == s[n - 1]) f(s) = 1 + min(f(s[0...n-2], f(s[1...n-1])))$

代码如下:

class Solution {
public:
    
    static const int maxn = 512;
    
    int dp[maxn][maxn];
    
    int calc(string &s, int x, int y){
        if(x >= y)return 0;
        
        if(dp[x][y] > -1)return dp[x][y];
        
        int ret = y - x + 1;
        if(s[x] == s[y])ret = min(ret, calc(s, x+1, y-1));
        ret = min(ret, 1 + calc(s, x+1, y));
        ret = min(ret, 1 + calc(s, x, y-1));
        
        return dp[x][y] = ret;
    }
    
    int minInsertions(string s) {
        
        memset(dp, -1, sizeof(dp));
        
        int n = s.length();
        
        int ans = calc(s, 0, n - 1);
        
        return ans;
    }
};

这道题数据量很小,即使不加记忆化搜索也能过。
按照加上记忆化搜索的结果来看。

时间复杂度: O(N2)O(N^2)
空间复杂度: O(N2)O(N^2)
其中NN为给定字符串的长度。

如有缺漏,敬请指正。

另外, 请允许我给leetcode官方给一个建议。
在这种力扣周赛中出的题目, 建议数据范围可以开的区分度更强一些。 象本次周赛有同学反应出T2可以用暴力优化过, 但这显然不是出题人的本意。 这道题难度为Medium即需要用效率较高的算法通过。

标程时间复杂度 建议数据规模下限 建议数据规模上限
O(n!)O(n!) 8 10
O(3n)O(3^n) 8 12
O(2n)O(2^n) 12 24
O(n4)O(n^4) 50 100
O(n3)O(n^3) 200 500
O(n2logn)O(n^2logn) 782 1536
O(n2)O(n^2) 2000 1e4
O(nn)O(n \sqrt{n}) 5e4 1e5
O(nlogn)O(nlogn) 2e5 5e5
O(n)O(n) 1e6 1e7
O(logn)O(logn) 1e9 1e18

按照以上建议扩大部分题目数据规模更能达到比赛效果。

2
展开全部 12 讨论