力扣-第-292-场周赛

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string largestGoodInteger(string num) {
      if(num.find("999")!=-1) return "999";
      if(num.find("888")!=-1) return "888";  
      if(num.find("777")!=-1) return "777";  
      if(num.find("666")!=-1) return "666";  
      if(num.find("555")!=-1) return "555";  
      if(num.find("444")!=-1) return "444";  
      if(num.find("333")!=-1) return "333";  
      if(num.find("222")!=-1) return "222";  
      if(num.find("111")!=-1) return "111";
              if(num.find("000")!=-1) return "000"; 
        return "";


    }
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 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 {
    int cnt=0;
    struct no{
        int sum=0,num=0;
        };
    no dfs(TreeNode* fa)
    {
        if(!fa) return {0,0};
        no ls=dfs(fa->left);
        no rs=dfs(fa->right);
        if ((ls.sum + rs.sum + fa->val) / (ls.num + rs.num+1) == fa->val) cnt++;
        return { ls.sum + rs.sum + fa->val,ls.num + rs.num + 1 };
        
    }
public:
    int averageOfSubtree(TreeNode* root) {
        dfs(root);
        
        return cnt;
    }
};

6058. 统计打字方案数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    const int mod=1e9+7;
    const int maxx=1e5+5;
    long long dp1[100005],dp2[100005];
    void pr()
    {
        for(int i=0;i<maxx;i++) dp1[i]=dp2[i]=0;
        
        dp1[1]=1,dp1[2]=2,dp1[3]=4;
        for(int i=4;i<maxx;i++) dp1[i]=dp1[i-1]+dp1[i-2]+dp1[i-3],dp1[i]%=mod;
        
        dp2[1]=1,dp2[2]=2,dp2[3]=4,dp2[4]=8;
        for(int i=5;i<maxx;i++) dp2[i]=dp2[i-1]+dp2[i-2]+dp2[i-3]+dp2[i-4],dp2[i]%=mod;

    }
public:
    int countTexts(string pressedKeys) {
        int l=pressedKeys.size();
        if(l==0||l==1) return 1;
        
        
        pr();  
        long long ans=1;
        int ll=0,rr=0,cnt=0;
        while(rr<l)
        {
            cnt=0;
            while(rr<l&&pressedKeys[ll]==pressedKeys[rr])
            {
                rr++,cnt++;
            }
            if(pressedKeys[ll]=='7'||pressedKeys[ll]=='9') ans*=dp2[cnt],ans%=mod;
            else ans*=dp1[cnt],ans%=mod;
            ll=rr;
        }
    
    return ans;}
    
};

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

用vis[x][y][cnt]记录走过的状态,走过的就不走了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
bool flag = 0;
int n, m;
bool vis[105][105][205] = { 0 };
int st[2][2] = { {0,1},{1,0} };
    inline void dfs(int cnt, int x, int y, vector<vector<char>>& grid) {

        if (grid[x][y] == '(') cnt++;
        else cnt--;
        if(cnt<0) return;
        if (flag) return;
        if (x == n - 1 && y == m - 1)
        {
            flag |= cnt == 0;
            return;
        }


        if (vis[x][y][cnt]) 
        return;
        vis[x][y][cnt] = 1;
        int xx, yy;
        for (int i = 0; i < 2 ; i++)
        {
            xx = x + st[i][0], yy = y + st[i][1];
            if (xx < n && yy < m)
                dfs(cnt, xx, yy, grid);
        }
    }
public:
    bool hasValidPath(vector<vector<char>>& grid) {
        n = grid.size();
        if (!n) return 0;
        m = grid[0].size();
        if ((m + n+1) % 2 || grid[n - 1][m - 1] == '(' || grid[0][0] == ')') return 0;
        dfs(0, 0, 0, grid);
        return flag;
    }
};