[数据结构与算法] LeetCode 第 292 场周赛

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> LeetCode 第 292 场周赛 -> 正文阅读

[数据结构与算法]LeetCode 第 292 场周赛

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

题目大意
给定一个字符串num，问其中连续出现三次且最大的三位数是多少（包含前导0）。
思路
一个个的找，找到了就更新一下答案。
代码

class Solution {
public:
    string largestGoodInteger(string num) {
        int ans=-1;
        int n=num.size();
        num+="-1";
        int tim=1;
        for(int i=1;i<=n;i++)
        {
            if(tim==3 && num[i-1]-'0'>ans) 
            {
                ans=num[i-1]-'0';
            }
            if(num[i]!=num[i-1]) tim=1;
            else tim++;
        }
        // cout<<endl<<ans<<endl;
        if(ans==-1) return "";
        else
        {
           if(ans==0) return "000";
            else{
                string s = std::to_string(ans*100+ans*10+ans);
                           return s; 
            }
        }  
    }
};

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

题目大意
给定一颗树（树的结构已经存在了root中），问有多少个节点的权值=他的子树的权值的平均值（平均值=ceil(子树权值和/子树节点数)）。
思路
dfs一遍，同时记录子树权值和，和字数的节点数，通过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 {
int ans=0,num=0;
pair<int,int> dfs(TreeNode* u)
{
    if(u==NULL) return make_pair(0,0);
    int temp=u->val;
    int nm=1;
    pair<int,int> x=dfs(u->left);
    pair<int,int> y=dfs(u->right);
    temp+=x.first;
    temp+=y.first;
    nm+=x.second;
    nm+=y.second;
    if(temp/nm==u->val) ans++;
    // cout<<u->val<<" "<<temp<<" "<<nm<<" "<<ans<<endl;
    return make_pair(temp,nm);
}

public:
    int averageOfSubtree(TreeNode* root) {
        dfs(root);
        return ans; 
    }
};

6058. 统计打字方案数

题目大意

现在一个手机通过2-9来输出英文字母，每个键敲几次就会输出这个键上排在第几的字母。现在Alice发给Bob一串数字序列，问这个数字序列对应多少种字母序列。
思路
首先不同的数字之间方案数不相干扰，即统计每一段连续的相等的数字的方案数，然后用乘法原理将每一段方案相乘。
那么，怎么统计一段连续相等字母的方案呢？可以发现是一个变形的斐波那契问题。对于7和9而言： $f [i] = f [i ? 1] + f [i ? 2] + f [i ? 3] + f [i ? 4]$ 。对于其他数字而言： $f [i] = f [i ? 1] + f [i ? 2] + f [i ? 3]$ 即可。
代码

class Solution {
public:
    int countTexts(string pressedKeys) {
        int n=pressedKeys.size();
        pressedKeys+="0";
        long long ans=1;
        const long long mod=1000000007;
        long long f[n+10],g[n+10];
        f[0]=1;f[1]=1;f[2]=2;f[3]=4;
        g[0]=1;g[1]=1;g[2]=2;g[3]=4;g[4]=6;
        for(int i=4;i<=n;i++) f[i]=(f[i-1]+f[i-2]+f[i-3])%mod;
        for(int i=4;i<=n;i++) g[i]=(g[i-1]+g[i-2]+g[i-3]+g[i-4])%mod;
        int tim=1;
        for(int i=0;i<n;i++)
        {
            if(pressedKeys[i]!=pressedKeys[i+1])
            {
                if(pressedKeys[i]=='7' || pressedKeys[i]=='9') ans=(ans*g[tim])%mod;
                else ans=(ans*f[tim])%mod;
                tim=1;
            }
            else
            {
                tim++;
            }
        }
        return (int)ans;
    }
};

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

题目大意
给定一个 $n\times m$ 的格子,每个格子是’(‘或者’)'，问存不存在一天从(0,0)走到(n-1,m-1)的路径，使得上面的括号序列是合法的（合法的定义：左右括号是匹配的）。
思路
dp:
f[i][j][k]表示第（i,j）位置上左括号比右括号多k个是否可行。显然我们要保证每时每刻k>=0，即左括号的个数永远大于等于右括号才有可能为真。最后答案是f[n-1][m-1][0]。
代码

class Solution {
public:
    bool hasValidPath(vector<vector<char>>& mp) {
        bool f[105][105][205]={false}; //要初始化一下false 要不然也不知道为什么会出错
        int n=mp.size(),m=mp[0].size();
        if(mp[0][0]=='(') f[0][0][1]=true;
        else return false;

        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                for(int k=0;k<200;k++)
                    if(f[i][j][k])
                    {
                        if(i+1<n)
                        {
                            if(mp[i+1][j]=='(') f[i+1][j][k+1]=true;
                            else if(k-1>=0) f[i+1][j][k-1]=true;
                        }
                        if(j+1<m)
                        {
                            if(mp[i][j+1]=='(') f[i][j+1][k+1]=true;
                            else if(k-1>=0) f[i][j+1][k-1]=true;
                        }
                    }
        return f[n-1][m-1][0];
    }
};