跳到主要内容

第 292 场周赛

Problem A - 字符串中最大的 3 位相同数字​

方法一：暴力​

  • 时间复杂度 O(∣S∣)\mathcal{O}(|S|)。
  • 空间复杂度 O(1)\mathcal{O}(1)。
参考代码（Python 3）
class Solution:
    def largestGoodInteger(self, num: str) -> str:
        ans = ''
        n = len(num)
        for i in range(n - 2):
            if num[i] == num[i + 1] == num[i + 2]:
                ans = max(ans, num[i])
        return ans * 3

Problem B - 统计值等于子树平均值的节点数​

方法一：DFS​

  • 时间复杂度 O(N)\mathcal{O}(N)。
  • 空间复杂度 O(H)\mathcal{O}(H)，其中 HH 表示树高。
参考代码（C++）
class Solution {
    int ans;
    
    pair<int, int> dfs(TreeNode *root) {
        if (root == nullptr)
            return make_pair(0, 0);
        
        int sum = root->val;
        int cnt = 1;
        auto [ls, lc] = dfs(root->left);
        auto [rs, rc] = dfs(root->right);
        sum += ls + rs;
        cnt += lc + rc;
        if (sum / cnt == root->val)
            ans++;
        
        return make_pair(sum, cnt);
    }
public:
    int averageOfSubtree(TreeNode* root) {
        ans = 0;
        dfs(root);
        return ans;
    }
};

Problem C - 统计打字方案数​

方法一：动态规划​

  • 时间复杂度 O(∣S∣)\mathcal{O}(|S|) 。
  • 空间复杂度 O(∣S∣)\mathcal{O}(|S|)，可以进一步优化到 O(1)\mathcal{O}(1)。
参考代码（Python 3）
class Solution:
    def countTexts(self, pressedKeys: str) -> int:
        d = [3] * 10
        d[7] = d[9] = 4
        MOD = 1000000007
        dp = [1]
        n = len(pressedKeys)
        for i in range(n):
            v = int(pressedKeys[i])
            curr = 0
            for j in range(d[v]):
                if i < j or pressedKeys[i - j] != pressedKeys[i]:
                    break
                curr += dp[i - j]
            curr %= MOD
            dp.append(curr)
        return dp[-1]

Problem D - 检查是否有合法括号字符串路径​

方法一：动态规划​

  • 时间复杂度 O(NM(N+M))\mathcal{O}(NM(N+M))，可以利用 bitset 进一步优化。
  • 空间复杂度 O(NM(N+M))\mathcal{O}(NM(N+M))，可以利用 bitset 进一步优化。
参考代码（C++）
class Solution {
public:
    bool hasValidPath(vector<vector<char>>& grid) {
        if (grid[0][0] == ')')
            return false;
        
        int n = grid.size(), m = grid[0].size();
        vector<vector<unordered_set<int>>> v(n, vector<unordered_set<int>>(m));
        v[0][0].insert(1);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                int c = grid[i][j] == '(' ? 1 : -1;
                if (i > 0)
                    for (int k : v[i - 1][j])
                        if (k + c >= 0)
                            v[i][j].insert(k + c);
                if (j > 0)
                    for (int k : v[i][j - 1])
                        if (k + c >= 0)
                            v[i][j].insert(k + c);
            }
        
        return v[n - 1][m - 1].count(0);
    }
};