LeetCode 第292场周赛

题目1：字符串中最大的 3 位相同数字

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

标签

字符串

思路

遍历一遍数组，每次从第 i 个位置截取长度为 3 字符串，然后判断字符串是否符合要求，若符合，则更新结果。

题解

• 题解

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

• 时间复杂度：O(n)，其中 n 为 字符串 num 的长度
• 空间复杂度：O(1)

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：6.4 MB, 在所有 C++ 提交中击败了100.00%的用户

通过测试用例：140 / 140

题目2：统计值等于子树平均值的节点数

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

标签

二叉树、后序遍历、pair

思路

1. 递归函数与返回值
   • 用pair作为返回值记录以当前节点为根的子树的总值与节点个数
   • pair<int,int> getAvgVal(TreeNode* root){}
2. 递归函数出口
   • 如果遇到空节点 返回{0,0}
   • if(root==nullptr) return {0,0};
3. 单层递归逻辑
   • 用l_pair接住遍历过程中左子树的 pair<>;
   • 用r_pair接住遍历过程中右子树的 pair<>;
   • 计算当前节点的 pair<>;
   • 判断当前节点是否符合条件，++ans;
   • 返回当前节点的 pair<>;

题解

• 题解

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int res = 0;
    // 总数，个数
    pair<int, int> getAvgVal(TreeNode* root){
        if(root == nullptr) return {0, 0};
        pair<int, int> pair_l = getAvgVal(root->left);
        pair<int, int> pair_r = getAvgVal(root->right);

        int sum = pair_l.first + pair_r.first + root->val;
        int count = pair_l.second + pair_r.second + 1;

        pair<int, int> cur = {sum, count};
        if(sum / count == root->val) res++;
        return cur;
    }
    int averageOfSubtree(TreeNode* root) {
        pair<int, int> per = getAvgVal(root);
        return res;
    }
};

• 时间复杂度：O(n)，其中 n 为 二叉树中的节点个数
• 空间复杂度：O(1)

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：6.4 MB, 在所有 C++ 提交中击败了100.00%的用户

通过测试用例：140 / 140

题目3：统计打字方案数

统计打字方案数

题目4：检查是否有合法括号字符串路径

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