讨论/题目交流/🐱 第 17 场夜喵双周赛/
🐱 第 17 场夜喵双周赛

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

image.png

3 分 - 解压缩编码列表
4 分 - 矩阵区域和
5 分 - 祖父节点值为偶数的节点和
7 分 - 不同的循环子字符串

展开讨论

5143. 解压缩编码列表

按照题意模拟即可:顺序读取给定的压缩后列表 numsnums,每次读取两个数字,分别设为 a,ba, b。那么原序列中就放进去 aa 个 bb,直至读取结束。

class Solution {
public:
    vector<int> decompressRLElist(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans;
        
        for (int i = 0; i < n; i += 2){
            for (int k = 0; k < nums[i]; k++)
                ans.push_back(nums[i + 1]);
        }
        
        return ans;
    }
};

5144. 矩阵区域和

因为数据范围比较小:1≤n,m,K≤1001\leq n, m, K \leq 100,暴力模拟的复杂度为 O(nmK2)O(nmK^2),所以可以放心开冲,直接四重循环模拟即可。

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int K) {
        int n = mat.size(), m = mat[0].size();
        vector<vector<int> > ans;
        
        for (int i = 0; i < n; i++){
            vector<int> row;
            for (int j = 0; j < m; j++){
                int sum = 0;
                for (int p = max(0, i - K); p < min(n, i + K + 1); ++p)
                    for (int q = max(0, j - K); q < min(m, j + K + 1); ++q)
                        sum += mat[p][q];
                row.push_back(sum);
            }
            ans.push_back(row);
        }
        
        return ans;
        
    }
};

5145. 祖父节点值为偶数的节点和

这道题目考察二叉树的遍历…一点和平时不同的地方就是,访问到某一个节点的时候,需要直到它的祖父(父亲的父亲)节点的值。在 DFS 的时候,在记录父亲节点的值的同时再记录祖父节点的值即可。

class Solution {
public:
    int sum = 0;
    
    void dfs(TreeNode *rt, int fa, int gfa){
        if (rt == NULL) return;
        if (gfa != -1 && gfa % 2 == 0) sum += rt->val;
        dfs(rt->left, rt->val, fa);
        dfs(rt->right, rt->val, fa);
    }
    
    int sumEvenGrandparent(TreeNode* root) {
        sum = 0;    
        dfs(root, -1, -1);
        return sum;
    }
};

5146. 不同的循环子字符串

这道题目的题意感觉有一点点绕,说白了就是给你一个字符串 texttext,你需要找到它所有的形如 AAAA 的不同子串,并返回数量。(AA 可以是字符也可以是一个字符串)

数据范围并不大:1≤n≤20001\leq n \leq 2000,所以支持我们暴力枚举每一个可能的子串进行检查,但检查的复杂度需要被控制在 O(1)O(1) 级别。(Emmm,好像 Log 也行,不过这个 Log 没啥意义)

这时候就需要一个科技叫做字符串哈希,即设定一个小质数 CC ,并令 Hash[i]=∑k=1iCi−k×text[i]Hash[i] = \sum_{k=1}^i C^{i-k} \times text[i](其中 texttext 下标从 1 开始)。那么取出 text[p,q]text[p, q] 一段的哈希值则为:

Hash[q]−Hash[p−1]=∑i=pqCq−i×text[i]\begin{aligned} Hash[q] - Hash[p - 1] = \sum_{i=p}^q C^{q-i}\times text[i] \end{aligned}

对于另一段与 text[p,q]text[p, q] 相同的字串 text[a,b]text[a, b],它的哈希值则为:∑i=abCb−i×text[i]\sum_{i=a}^b C^{b-i}\times text[i],如果这两段相同,那么他们之间仅相差 Cq−bC^{q-b} 倍。那么检查 text[p,q]text[p, q] 与 text[a,b]text[a, b] 是否相同,仅需要将相差的倍数乘上去,然后判断哈希值是否相同即可。
当然,HashHash 数组肯定会很大,所以我们要在模意义下进行运算和比较。

#define ULL unsigned long long
const int MAXN = 2000 + 50;
const ULL CHASH = 37;
ULL hCode[MAXN], hSqr[MAXN];

class Solution {
public:
    set<ULL> table;
    int distinctEchoSubstrings(string text) {
        table.clear();
        int n = text.size();
        
        hCode[0] = 0;
        hSqr[0] = 1;
        for (int i = 1; i <= n; i++) {
            hCode[i] = hCode[i - 1] * CHASH + text[i - 1];
            hSqr[i] = hSqr[i - 1] * CHASH;
        }
        
        for (int i = 1; i <= n; i++){
            ULL curCode = 0;
            for (int j = i; j <= n; j++){
                curCode = curCode * CHASH + text[j - 1];
                int len = (j - i + 1);
                int x = j + 1, y = j + len;
                if (y > n) break;
                ULL left = (hCode[j] - hCode[i - 1]) * hSqr[len];
                ULL right = hCode[y] - hCode[x - 1];
                if (left == right) table.insert(curCode);
            }
        }
        
        return table.size();
    }
};
9
展开全部 18 讨论