On the shoulders of giants.

biweekly-contest-17

解压缩编码列表

给你一个以行程长度编码压缩的整数列表 nums 。

考虑每相邻两个元素 [a, b] = [nums[2*i], nums[2*i+1]] (其中 i >= 0 ),每一对都表示解压后有 a 个值为 b 的元素。

请你返回解压后的列表。

示例:

输入:nums = [1,2,3,4]
输出:[2,4,4,4]

提示:

  • 2 <= nums.length <= 100
  • nums.length % 2 == 0
  • 1 <= nums[i] <= 100
题解

模拟即可。

时间复杂度:\(O(n)\)

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

矩阵区域和

给你一个 m * n 的矩阵 mat 和一个整数 K ,请你返回一个矩阵 answer ,其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和: 

  • i - K <= r <= i + K, j - K <= c <= j + K 
  • (r, c) 在矩阵内。

示例 1:

输入:mat = [[1,2,3],[4,5,6],[7,8,9]], K = 1
输出:[[12,21,16],[27,45,33],[24,39,28]]

示例 2:

输入:mat = [[1,2,3],[4,5,6],[7,8,9]], K = 2
输出:[[45,45,45],[45,45,45],[45,45,45]]

提示:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n, K <= 100
  • 1 <= mat[i][j] <= 100
题解

用记录型的美学暴力,时间复杂度可达: \(O(nmk)\)

用二维前缀和预处理,时间复杂度可达:\(O(nm)\)

但这里就直接使用暴力枚举,时间复杂度:\(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>> ret(n, vector<int> (m));
        for(int i = 0; i < n; i++) {
            int x1 = max(0, i - K), x2 = min(n - 1, i + K);
            for(int j = 0; j < m; j++) {
                int y1 = max(0, j - K), y2 = min(m - 1, j + K);
                int sum = 0;
                for(int x = x1; x <= x2; x++) {
                    for(int y = y1; y <= y2; y++) {
                        sum += mat[x][y];
                    }
                }
                ret[i][j] = sum;
            }
        }
        return ret;
    }
};

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

给你一棵二叉树,请你返回满足以下条件的所有节点的值之和:

  • 该节点的祖父节点的值为偶数。(一个节点的祖父节点是指该节点的父节点的父节点。)

如果不存在祖父节点值为偶数的节点,那么返回 0

示例:

输入:root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
输出:18
解释:图中红色节点的祖父节点的值为偶数,蓝色节点为这些红色节点的祖父节点。

提示:

  • 树中节点的数目在 1 到 10^4 之间。
  • 每个节点的值在 1 到 100 之间。
题解

DFS ,记录父亲节点和祖先节点,然后遍历二叉树,并更新答案。

时间复杂度:\(O(n)\)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int result = 0;
    void dfs(TreeNode* x, TreeNode* y, TreeNode* p) {
        if(p == NULL) return;
        if(x != NULL && x->val % 2 == 0) {
            result += p->val;
        }
        dfs(y, p, p->left);
        dfs(y, p, p->right);
    }
    int sumEvenGrandparent(TreeNode* root) {
        dfs(NULL, NULL, root);
        return result;
    }
};

不同的循环子字符串

给你一个字符串 text ,请你返回满足下述条件的 不同 非空子字符串的数目:

  • 可以写成某个字符串与其自身相连接的形式。

例如,abcabc 就是 abc 和它自身连接形成的。

示例 1:

输入:text = "abcabcabc"
输出:3
解释:3 个子字符串分别为 "abcabc" , "bcabca" 和 "cabcab" 。

示例 2:

输入:text = "leetcodeleetcode"
输出:2
解释:2 个子字符串为 "ee" 和 "leetcodeleetcode" 。

提示:

  • 1 <= text.length <= 2000
  • text 只包含小写英文字母。
题解

设计 Hash 函数,然后枚举子串,判断是否可以串联。

这里 Hash 函数使用无符号整型处理相当于模 \(2^{64}\) 下运算。

不使用 Hash ,时间复杂度:\(O(n^3)\)

使用 Hash ,时间复杂度:\(O(n^2)\)

# define ULL unsigned long long
const int N = 2E4, BASE = 233;
class Solution {
private:
    set<ULL> s;
    ULL sum[N], p[N];
public:
    ULL check(int x, int y) {
        return sum[y] - sum[x - 1];
    }
    int distinctEchoSubstrings(string text) {
        int n = text.length();
        s.clear();
        sum[1] = 0, p[0] = 1;
        for(int i = 1; i <= n; i++) {
            p[i] = p[i - 1] * BASE;
            sum[i] = sum[i - 1] * BASE + text[i - 1];
        }
        for(int i = 1; i <= n; i++) {
            ULL HashCode = 0;
            for(int j = i; j <= n; j++) {
                HashCode = HashCode * BASE + text[j - 1];
                int l = j - i + 1, x = j + 1, y = j + l;
                // s1:[i,j] s2:[x,y]
                if(check(i, j) * p[l] == check(x, y)) {
                    s.insert(HashCode);
                }
            }
        }
        return s.size();
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注