leetcode 第 292 场周赛题解

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

字符串

思路：判断如果三个相同则更新一下答案，取一个最大值。

代码：

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

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

DFS遍历

思路：dfs遍历树，dfs返回两个参数，子树的总权值和节点总个数。如果当前节点满足则ans++；

代码：

/**
 * 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 ans=0;
    
    pair<int,int> dfs(TreeNode* root){
        if(root==NULL) return {0,0};
        int sum=root->val;
        int cnt=1;
        auto z=dfs(root->left);
        sum+=z.first;
        cnt+=z.second;
        z=dfs(root->right);
        sum+=z.first;
        cnt+=z.second;
        if(sum/cnt==root->val) ans++;
        return {sum,cnt};
    }
    int averageOfSubtree(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

6058. 统计打字方案数

递推+双指针

思路：其实就是一个递推式，比如2222，固定最前面，答案=a开头剩余三个2+b开头剩余两个2+c开头剩余1一个2。

四个字母的同理。所以预处理一下递推取模,双指针滑动窗口取相同数的区间长度。

代码：

typedef long long ll;
const int N=100010;
const int mod=1e9+7;
class Solution {
public:
    int a[N],b[N];
    void init(){
        a[1]=1,a[2]=2,a[3]=4;
        for(int i=4;i<=100000;i++){
            a[i]=((a[i-1]%mod+a[i-2]%mod)%mod+a[i-3]%mod)%mod;
            a[i]%=mod;
        }
        b[1]=1,b[2]=2,b[3]=4,b[4]=8;
        for(int i=5;i<=100000;i++){
            b[i]=(((b[i-1]%mod+b[i-2]%mod)%mod+b[i-3]%mod)%mod+b[i-4]%mod)%mod;
            b[i]%=mod;
        }
    }
    int countTexts(string s) {
        init();
        int n=s.size();
        long long ans=1;
        for(int i=0;i<n;i++){
            int j=i;
            while(s[j]==s[i]&&j<n) j++;
            if(s[i]=='9'||s[i]=='7'){
                ans=(ans%mod*b[j-i]%mod)%mod;
            }else{
                ans=(ans%mod*a[j-i]%mod)%mod;
            }
            i=j-1;
        }
        return (int)ans;
    }
};

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

括号序列+DP

思路：

$d p [i] [j] [k]$ 表示从前i,j个中选，k个左括号合法.

由当前 $d p [i] [j] [k]$ 状态推到前一个状态：向右或者向下走,如果没有越界，遇到右括号，k–,遇到左括号k++。如果大于等于0，说明在这一过程是合法的。最终k==0，说明整个路径有合法的。

代码：

class Solution {
    
public:
    bool dp[105][105][201];//dp[i][j][k]表示从前i,j个中选，k个左括号合法
    bool hasValidPath(vector<vector<char>>& s) {
        if(s[0][0]=='(') dp[0][0][1]=true;
        else return false;
        int n=s.size(),m=s[0].size();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                for(int k=0;k<200;k++){
                    if(dp[i][j][k]){
                        if(j+1<m){
                            int l=k;
                            if(s[i][j+1]==')') l--;
                            else l++;
                            if(l>=0) dp[i][j+1][l]=true;
                        }
                        if(i+1<n){
                            int l=k;
                            if(s[i+1][j]==')') l--;
                            else ++l;
                            if(l>=0) dp[i+1][j][l]=true;
                        }
                    }
                }
            }
        }
        return dp[n-1][m-1][0];
    }
};