上上周的周赛了...

一如既往的双题选手...每次复盘都要拖好久🤐

2264. Largest 3-Same-Digit Number in String

Analysis

找出子串中最大的 3 位数，且这个 3 位数，必须各数位相等。

Code

当时提交的代码：

class Solution {
public:
    string largestGoodInteger(string num) {
        vector<string> nums;
        int len = num.length();
        for(int i = 0; i < len - 2; i++) {
            if(num[i] == num[i + 1] && num[i] == num[i + 2]) nums.push_back(num.substr(i, 3));
        }
        int size = nums.size();
        sort(nums.begin(), nums.end());
        if(size == 0) return "";
        else return nums[size - 1];
    }
};

现在再看，写的麻烦了一点，改简单一点：

class Solution {
public:
    string largestGoodInteger(string num) {
        string ans = "";
        int len = num.length();
        for(int i = 0; i < len - 2; i++) {
            if(num[i] == num[i + 1] && num[i] == num[i + 2]) {
                string tmp = num.substr(i, 3);
                if(tmp > ans) ans = tmp;
            }
        }
        return ans;
    }
};

2265. Count Nodes Equal to Average of Subtree

Analysis

统计出所有结点的值与以对应结点为根结点的树的结点值之和的平均值相等的结点数目...读起来相当拗口，不过题目意思就是如此。

Code

当时做的时候没什么好想法，就是把所有结点构成的树的结点和都算出来，求出平均值，再进行比较，这样做时间复杂度很高，勉强通过。这是当时提交的代码：

class Solution {
public:
    int averageOfSubtree(TreeNode* root) {
        if(!root->left && !root->right) return 1;
        queue<TreeNode*> q1;
        q1.push(root);
        int cnt = 0;
        while(!q1.empty()) {
            TreeNode *node = q1.front(); q1.pop();
            queue<TreeNode*> q2;
            q2.push(node);
            int sum = 0, nodecnt = 0;
            while(!q2.empty()) {
                TreeNode *tmp = q2.front(); q2.pop();
                sum += tmp->val;
                nodecnt++;
                if(tmp->left) q2.push(tmp->left);
                if(tmp->right) q2.push(tmp->right);
            }
            if(sum / nodecnt == node->val) cnt++;
            if(node->left) q1.push(node->left);
            if(node->right) q1.push(node->right);
        }
        return cnt;
    }
};

遍历思路是 bfs 的思路，用 dfs 也能实现类似的思路，不再写了。
现在要考虑一下，能不能边计算，边判定。从题目的示例来分析，所有的叶子结点都是满足条件的，非叶子结点才需要判定。而完成判定需要两个条件，一是知道以当前结点为子树的结点值之和，而是这颗子树的结点总数。按照 dfs 的思路，如果一开始判断的是叶结点，然后再将值返回给非叶结点，这样就不用重复计算了。也就是说，每次需要返回两个值，一个是子树所有结点值之和，而是结点的数量。

class Solution {
public:
    pair<int, int> dfs(TreeNode *root, int &ans) {
        if(root == nullptr) {
            return {0, 0};
        }
        pair<int, int> left, right;
        left = dfs(root->left, ans);
        right = dfs(root->right, ans);
        int sum = left.first + right.first + root->val;
        int cnt = left.second + right.second + 1;
        if(sum / cnt == root->val) ans++;
        return {sum, cnt};
    }
    int averageOfSubtree(TreeNode* root) {
        int ans = 0;
        dfs(root, ans);
        return ans;
    }
};

注意在 averageOfSubtree 这个函数中，忽略掉了 dfs 的返回值，实际项目中可别这样写。
回头再看这个题目，dfs 的思路跟后序遍历很像，整体的思路跟树形 dp 也很像。

2266. Count Number of Texts

Analysis

题目信息有点多，大致意思就是给一串代表九宫格键盘按键顺序的字符串，算出这个字符串可以被解码成多少种可能。

Code

这个题当时想了挺久的，但是没想出来，属于是有思路，但是思路又不是那么完全的那种题目。
当时的思路是，按照数字分类，也就是 7 和 9 一类，剩下的一类，然后分割字符串，一个一个找出所有的连续且字符都相等的子串。因为 7 和 9 最多按 4 下，其他数字最多按 3 下，所以计算出对应的可能，然后依次乘起来，就是总的可能数，同时别忘了取余。但是，看到示例 2 又想到了数字可能出现很多次，那这样统计就不对了，思路就搁浅了...

看了下别人的题解，发现这是个字符串和 dp 结合的题（完全没往 dp 上想...），数字需要分类的想法倒是没错。其实，当时思考这个题的时候，应该察觉到了前面的选择会影响后面的选择，这也就是 dp 的特点。
这个人的题解把这个题的 dp 思路说的很清楚，这里不赘述了。

class Solution {
public:
    int countTexts(string pressedKeys) {
        int mod = 1e9 + 7;
        int len = pressedKeys.length();
        vector<long long> dp(len);
        dp[0] = 1;
        for(int i = 1; i < len; i++) {
            dp[i] = dp[i - 1];
            if(pressedKeys[i] == pressedKeys[i - 1]) {
                dp[i] += i >= 2 ? dp[i - 2] : 1;
                if(i >= 2 && pressedKeys[i] == pressedKeys[i - 2]) {
                    dp[i] += i >= 3 ? dp[i - 3] : 1;
                    if((pressedKeys[i] == '7' || pressedKeys[i] == '9') 
                        && i >= 3 && pressedKeys[i] == pressedKeys[i - 3]) {
                        dp[i] += i >= 4 ? dp[i - 4] : 1; 
                    }
                }
            }
            dp[i] %= mod;
        }
        return dp[len - 1];
    }
};

回头再看这道题，首先的问题是没意识到是 dp，再者就是这个状态转移方程可能写不出来，原因可能是没做过类似的字符串 + dp 的题（上周那个困难题还没搞懂啊...）。仔细想想，这个题的 dp 思路与跳台阶、青蛙过河本质上是一样的，都是一维 dp 的思路，只是这个题需要考虑一下字符的不同情况。
再回到题目中，上面的思路中，$dp[i]$ 代表的就是以 $pressedKeys[i]$ 结尾的可能数，这样做可能会使 $dp[i - k], k = 2, 3, 4$ 不存在。所以需要将 $dp[i]$ 的定义修改成以 $pressedKeys[i - 1]$ 结尾的可能数，就可以避开这个问题了，这个细节，以后思考 dp 类问题的时候千万不要忘了。

class Solution {
public:
    int countTexts(string pressedKeys) {
        int mod = 1e9 + 7;
        int len = pressedKeys.length();
        vector<long long> dp(len + 1);
        dp[0] = 1, dp[1] = 1;
        for(int i = 2; i <= len; i++) {
            dp[i] = dp[i - 1];
            if(pressedKeys[i - 1] == pressedKeys[i - 2]) {
                dp[i] += dp[i - 2];
                if(i >= 3 && pressedKeys[i - 1] == pressedKeys[i - 3]) {
                    dp[i] += dp[i - 3];
                    if((pressedKeys[i - 1] == '7' || pressedKeys[i - 1] == '9') 
                        && i >= 4 && pressedKeys[i - 1] == pressedKeys[i - 4]) {
                        dp[i] += dp[i - 4]; 
                    }
                }
            }
            dp[i] %= mod;
        }
        return dp[len];
    }
};

类似的，一维 dp 还可以通过滚动数组的思想来解决，就不写了...

最后一个题，又要想很久了，明天再写...

又拖了几天~

2267. Check if There Is a Valid Parentheses String Path

Analysis

同样是能读懂题意，但是不知道如何下手的题目...只能学习一下大佬们的思路了。

Code

参考思路：DP。

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<vector<bool>>> f;
        for(int i = 0; i < n; i++) {
            f.push_back(vector<vector<bool>>());
            for(int j = 0; j < m; j++) {
                f.back().push_back(vector<bool>(n + m));
            }
        }
        f[0][0][1] = true;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                int t = grid[i][j] == '(' ? 1 : -1;
                for(int k = 0; k < n + m; k++) {
                    int kk = k - t;
                    if(kk < 0 || kk >= n + m) continue;
                    if(i > 0) f[i][j][k] = f[i][j][k] || f[i - 1][j][kk];
                    if(j > 0) f[i][j][k] = f[i][j][k] || f[i][j - 1][kk];
                }
            }
        }
        return f[n - 1][m - 1][0];
    }
};