Leetcode 第 292 场周赛 题解

Leetcode 第 292 场周赛 题解

1. 字符串中最大的 3 位相同数字

手速题

class Solution {
public:
    string largestGoodInteger(string num) {
        char t = 0;
        for (int i = 0; i + 3 - 1 < num.length(); ++i) {
            if (num[i] == num[i + 1] && num[i + 1] == num[i + 2]) {
                t = max(t, num[i]);
            }
        }
        if (t == 0) {
            return "";
        }
        return ""s + t + t + t;
    }
};

2. 统计值等于子树平均值的节点数

DFS 即可，过程中记录子树大小和总和。

class Solution {
    using ll = long long;
    int count = 0;
    
    std::pair<ll, ll> dfs(TreeNode* root) {
        if (root == nullptr) return {0, 0};

        ll value = root->val;
        ll size = 1;

        auto [lx, ly] = dfs(root->left);
        auto [rx, ry] = dfs(root->right);

        value += lx + rx;
        size += ly + ry;

        if (value / size == root->val) {
            ++count;
        }

        return {value, size};
    }
public:
    int averageOfSubtree(TreeNode *root) {
        count = 0;
        dfs(root);
        return count;
    }
};

3. 统计打字方案数

简单的统计方案数 dp。考虑 $dp[i]$ 代表前 $i$ 项的打字方案数，显然可以从 $dp[i - j]$ 中转移过来，其中 $s[i - j: i]$ 只有一种字母。转移状态的多少自然由该数字能表示多少字母决定，时间复杂度 $O(n)$。

const int MOD = 1e9 + 7;
const int cnt[10] = {0, 0, 3, 3, 3, 3, 3, 4, 3, 4};
const int N = 1e5 + 5;

int dp[N];
class Solution {
public:
    int countTexts(string pressedKeys) {
        memset(dp, 0, sizeof(dp));

        int n = pressedKeys.size();

        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            int key = pressedKeys[i - 1] - '0';
            for (int j = 0; j < cnt[key] && i - j >= 1; ++j) {
                if (pressedKeys[i - j - 1] - '0' == key) {
                    dp[i] = (0LL + dp[i] + dp[i - j - 1]) % MOD;
                } else {
                    break;
                }
            }
        }

        return dp[n];
    }
};

4. 检查是否有合法括号字符串路径

简单的记忆化搜索，只需要保证搜索过程中，左括号 ( 的数量大于等于右括号 ) 的数量即可。注意递归的终止条件。时间复杂度 $O(NM(N+M))$

const int N = 105;
char dp[N][N][4 * N];

class Solution {
    int n, m;
    vector<vector<char>> grid;

    bool dfs(int x, int y, int offset) {
        if (x >= n || y >= m) return false;

        if (offset < 0) return false;

        int delta = grid[x][y] == '(' ? 1 : -1;
        if (x == n - 1 && y == m - 1) {
            return offset + delta == 0;
        }

        if (dp[x][y][offset] != -1) {
            return dp[x][y][offset];
        }

        bool ans = false;
        ans |= dfs(x + 1, y, offset + delta);
        ans |= dfs(x, y + 1, offset + delta);
        return dp[x][y][offset] = ans;
    }
public:
    bool hasValidPath(vector<vector<char>>& grid) {
        memset(dp, -1, sizeof(dp));

        this->n = grid.size();
        this->m = grid[0].size();
        this->grid = grid;

        return dfs(0, 0, 0);
    }
};