Leetcode第264场周赛

fighting小王子 2021-10-24

258

程序员们，节日快乐！今天的周赛第一题模拟，有个点卡了一下，不细心；第二题直接暴力搜；第三题分析出一般表达式后直接dfs；第四题拓扑排序。这次的特点就是第三、四题难度有降低。

keywords：模拟；暴搜；dfs；拓扑排序

5906. 句子中的有效单词数

【题目描述】

简而言之：判断单词。包含数字的一定不是单词，中间有标点的也不是合法单词，包含多个连字符，或者连字符出现在首尾也不合法。

【思路】

简单模拟，串长只有1000，数据量并不大。做题的时候有个细节没注意到，导致有三个测试点就是过不了。连字符两侧都必须是小写字母，如"a-b"是合法单词，但是"a-,"这就不合法了，细节要注意。

另外，这种判断条件较多的题，代码实现上，把判断模块抽出来是一个不错的做法，这样遇到不满足条件的情况直接 return false，后续不需要管了，省了很多标志变量等信息的设置，代码可以简化不少。不过，这只能说是一个帮助解题写代码的技巧，轻松了你累了操作系统，实际工程项目中需要权衡。

【代码】

class Solution {
public:
    bool judge(string s){
        int len =  s.size();
        int k = 0;
        for(int i = 0; i < len; i ++){
            if(s[i] >= '0' || s[i] <= '9') 
                return false;
            else if(s[i] == ',' || s[i] == '.' || s[i] == '.'){
                if(i != len - 1)
                    return false;
            }
            else if(s[i] == '-'){
                if(i==0 || i == len-1) 
                    return false;
                k++;
                if(k>=2) 
                    return false;
            }
        }
        return true;
    }


    int countValidWords(string sen) {
        int i = 0, cnt = 0;
        string tmp="";
        while(i < sen.size()){
            if(sen[i] == ' ' || i == sen.size() - 1){
                if(i == sen.size() - 1 && sen[i] != ' ') tmp += sen[i];
                if(tmp.size() > 0 && judge(tmp))
                    cnt ++;
                tmp="";
            }
            tmp += sen[i];
            i++;
        }
        return cnt;
    }
};
复制

5907. 下一个更大的数值平衡数

【题目描述】

【思路】

平衡数的概念很好理解。n最大是10^6，比它大的最小的平衡数是1224444。不超过10^7，暴力枚举就行。枚举n+1到1224444之间所有数，每个数单独判断是否是平衡数，复杂度o(n)。

暴力枚举其实并不是一个优秀的做法，但竞赛中如果判断出了暴力可以过，那暴力的写法个人认为是可取的。暴力虽然不优雅，但它不需要你多思考，代码基本可以一气呵成。当然这只针对是现场想思路的情况，倘若有现成模板可以用就不用考虑暴力了。另外，确实可以发现题目涉及的平衡数并不多，全写出来，打表查，代码速度很快。但有个问题，列出这些平衡数的思考过程似乎要比暴搜更加复杂，或者得写一份求平衡数的代码先获取到所有平衡数，个人觉得此处暴搜更合适。

【代码】

class Solution {
public:
    bool judge(int n){
        vector<int> cnt(10 , 0);
        while(n)
        {
            cnt[n % 10] ++;
            n /= 10;
        }
        for(int i = 0; i < 10; i ++)
            if(cnt[i] != 0 &&cnt[i] != i) return false;
        return true;
    }
    int nextBeautifulNumber(int n) {
        for(int i = n + 1; i <= 1224444; i ++){
            if(judge(i))
                return i;
        }
        return -1;
    }
};
复制

5908. 统计最高分的节点数目

【题目描述】

【思路】

首先得稍微推一推这个分数怎么算，抽象出统一的表达式。很明显，删除一个节点后，剩下左子树（如果有的话）、右子树（如果有的话）、以及父节点那边部分（如果有的话），分数也就是左*右*父节点部分。父节点部分的节点数=n-左-右-1，这也显然。所以分数=左*右*(n-1-左-右)。左、右分别指左右子树的节点数噢。接下来关键的就是如何求左右子树数量，这就直接dfs可以解决。

代码说明：代码里有些地方初始定义的是int，理论上应该没问题，但是实际测试的时候计算分数时出现爆int的情况，所以改成了long long。其次，具体计算分数那行代码，每个部分都与1取了个max，1是乘法的幺元，不影响结果。如果某个节点没有左子树，左子树节点数是0，这部分不应该参与运算，但我们使用了统一的表达式就要保证这个0不会影响结果。

【代码】

struct node
{
    int left = -1;
    int right = -1;
};
class Solution {
public:
    long long int ln[100010],rn[100010];
    node tree[100010];
    int dfs(int root)
{
        if(root == -1) return 0;
        int l = dfs(tree[root].left);
        int r = dfs(tree[root].right);
        ln[root] = l;
        rn[root] = r;
        return l + r + 1;
    }


    int countHighestScoreNodes(vector<int>& parents) {
        long long n = parents.size() , maxn = 0, maxcnt = 0;
        int root = -1; 
        for(int i = 0; i < n; i ++)
        {
            int p = parents[i];
            if(p == -1){
                root = i;
                continue;
            }
            if(tree[p].left == -1) 
                tree[p].left = i;
            else 
                tree[p].right = i;
        }
        dfs(root);
        for(int i = 0; i < n; i ++)
        {
            long long t = max(1ll , (n - 1 - ln[i] - rn[i])) * max(ln[i] , 1ll) * max(1ll , rn[i]);
            if( t >= maxn)
            {
                if(t == maxn)
                    maxcnt ++;
                else{
                    maxn = t;
                    maxcnt = 1;
                }
            }
        }
        return maxcnt;
    }
};
复制

5909. 并行课程 III

【题目描述】

【思路】

求AOV网表示的工程的最早结束时间。直接拓扑排序就行。每个节点最早结束时间是和它有（指向它的）边的节点中最晚结束时间加上自己的耗时。所以，边拓扑排序，边更新节点的最早结束时间。

【代码】‍

class Solution {
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        vector<vector<int> > g(n + 1,vector<int>());
        vector<int> d(n + 1);
        vector<int> ans(n + 1);
        for(auto &x : relations){
            g[x[0]].push_back(x[1]);
            d[x[1]] ++;
        }
        queue<int> q;
        for(int i = 1; i <= n; i ++){
            if(d[i] == 0){
                q.push(i);
                ans[i] = time[i - 1]; 
            }
        }
        while( !q.empty()){
            int front = q.front();
            q.pop();
            for( auto &x : g[front]){
                d[x] --;
                if(d[x] == 0)
                    q.push(x);
                ans[x] = max(ans[x] , ans[front] + time[x - 1]);
            }
        }
        int maxn=-1;
        for(auto &x : ans)
            maxn = max(maxn , x);
        return maxn;
    }
};
复制

数据库

文章转载自fighting小王子，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

Leetcode第264场周赛

5906. 句子中的有效单词数

5907. 下一个更大的数值平衡数

5908. 统计最高分的节点数目

5909. 并行课程 III

评论

相关阅读