Leetcode Weekly Contest Round 264

唠嗑

就follow up一下最近的进度

最近的一周啊，过的真的是五味杂陈，微软莫名其妙的过了前两轮技术面（指45min全程全部拿来写算法了，八股浓度0，项目浓度0）。然后LEAD面脑抽，还是做题，一个很简单的题目被我愣是想的复杂的要死，脑思路紊乱上手写就更乱了，再限一下时心态崩了，最后没时间了，不能使用哨兵导致下标还处理的稀烂，只能怪我好久不写题了，连最基本的逻辑能力都退化了。🤦我不配了属于是。

在忙着“不务正业”的同时，由于科研训练的缘故，被迫回归正业🤷‍♂️。

从五月背八股刷题干项目干到现在，我都快不知道正业是什么了，虾仁猪心了属于是，好在两位队友队友给力，电路设计和布线基本都是她们做的，我就最后处理了点嵌入式的GPIO，USART通信和中断代码，但是还是痛苦阈值爆表。甚至还能有成品，这是一块步进电机的驱动板，感谢队友全程带菜鸡：

[{"url":"PXL_20211023_135346780.PORTRAIT.jpg","alt":""},{"url":"Picture1.png","alt":""},{"url":"Picture2.png","alt":""},{"url":"Picture3.png","alt":""},{"url":"Picture4.png","alt":""},{"url":"Picture5.jpg","alt":""},{"url":"Picture6.jpg","alt":""},{"url":"Picture7.png","alt":""}]

Load More

BTW，Google Pixel 5的Portrait Mode成像质量真不戳，Pixel老粉很开心（irrelevant，划掉）

鉴于这场比赛我也没打，就抱着康康的心态做做～

听群友说今天的题目很容易又很难，其中T1最难XD，最困难的一次AK了属于是

T1 5906. 句子中的有效单词数

题目

句子仅由小写字母（'a' 到 'z'）、数字（'0' 到 '9'）、连字符（'-'）、标点符号（'!'、'.' 和 ','）以及空格（' '）组成。每个句子可以根据空格分解成 一个或者多个 token ，这些 token 之间由一个或者多个空格 ' ' 分隔。

如果一个 token 同时满足下述条件，则认为这个 token 是一个有效单词：

• 仅由小写字母、连字符和/或标点（不含数字）。
• 至多一个 连字符 '-' 。如果存在，连字符两侧应当都存在小写字母（"a-b" 是一个有效单词，但 "-ab" 和 "ab-" 不是有效单词）。
• 至多一个 标点符号。如果存在，标点符号应当位于 token 的 末尾 。
  这里给出几个有效单词的例子："a-b."、"afad"、"ba-c"、"a!" 和 "!" 。

给你一个字符串 sentence ，请你找出并返回 sentence 中 有效单词的数目 。

示例 1：

输入：sentence = “cat and dog”
输出：3
解释：句子中的有效单词是 “cat”、“and” 和 “dog”

示例 2：

输入：sentence = “!this 1-s b8d!”
输出：0
解释：句子中没有有效单词
“!this” 不是有效单词，因为它以一个标点开头
“1-s” 和 “b8d” 也不是有效单词，因为它们都包含数字

示例 3：

输入：sentence = “alice and bob are playing stone-game10”
输出：5
解释：句子中的有效单词是 “alice”、“and”、“bob”、“are” 和 “playing”
“stone-game10” 不是有效单词，因为它含有数字

示例 4：

输入：sentence = “he bought 2 pencils, 3 erasers, and 1 pencil-sharpener.”
输出：6
解释：句子中的有效单词是 “he”、“bought”、“pencils,”、“erasers,”、“and” 和 “pencil-sharpener.”

提示：

• $1 \leq sentence.length \leq 1000$
• sentence 由小写英文字母、数字（0-9）、以及字符（' '、'-'、'!'、‘.’ 和 ‘,’）组成
• 句子中至少有 1 个 token

题解

裂开了，好恶心。。。

如果需要我们把整个字符串用空格分割成多个字符串，倒也还好，str.trim().split("\\s+")就好了。。。

但是每个单词需要满足的条件还是多的吓人了，建议刀了我

class Solution {
    public int countValidWords(String sentence) {
        int res = 0;
        String [] words = sentence.strip().split("\\s+");
        for (String word: words){
            boolean ok = true;

            //----不能有数字
            for (int i = 0; i < word.length(); i ++){
                if (Character.isDigit(word.charAt(i)) == true){
                    ok = false;
                    break;
                }
            }

            //----至多一个连字符，连字符两侧应该都是小写字母
            int a = 0;
            for (int i = 0; i < word.length(); i ++){
                if (word.charAt(i) == '-'){
                    a ++;
                    if (a > 1){
                        ok = false;
                        break;
                    }
                }
            }
            if (a == 1){
                for (int i = 0; i < word.length(); i ++){
                    if (word.charAt(i) == '-'){
                        if ((0 <= i - 1 && Character.isLowerCase(word.charAt(i - 1)) && i + 1 < word.length() && Character.isLowerCase(word.charAt(i + 1))) == false){
                            ok = false;
                        }
                        break;
                    }
                }

            }

            //----至多一个标点符号
            int sign_cnt = 0;
            for (int i = 0; i < word.length(); i ++){
                if (word.charAt(i) == '!' || word.charAt(i) == ',' || word.charAt(i) == '.'){
                    sign_cnt ++;
                    if (sign_cnt > 1){
                        ok = false;
                        break;
                    }
                }
            }
            if (sign_cnt == 1){
                if ((word.charAt(word.length() - 1) == '!' || word.charAt(word.length() - 1) == ',' || word.charAt(word.length() - 1) == '.') == false){
                    ok = false;
                }
            }

            if (ok == true){
                res ++;
            }
        }

        return res;
    }
}

后来又看了看题解评论区，真行啊，又骗我学正则表达式😪

import java.util.regex.Pattern;
class Solution {
    // 正则表达式解法
    // + 号代表前面的字符必须至少出现一次（1次或多次）
    // * 号代表前面的字符可以不出现，也可以出现一次或者多次（0次、或1次、或多次）
    // ? 问号代表前面的字符最多只可以出现一次（0次、或1次）
    // $ 匹配输入字符串结尾的位置
    private static final String pattern = "^(([a-z]+[-]?[a-z]+)|([a-z]*))[!.,]?$";
    public int countValidWords(String sentence) {
        int cnt = 0;
        String[] tokens = sentence.split(" ");
        for (String token : tokens) {
            if (Pattern.matches(pattern, token) && token.length() != 0) {
                cnt++;
            }
        }
        return cnt;
    }
}

//作者：crushallproblems
//链接：https://leetcode-cn.com/problems/number-of-valid-words-in-a-sentence/solution/qing-xi-de-mo-ni-jie-fa-zheng-ze-biao-da-g18h/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

正则表达式的坑以后再填吧，弟弟学不动了

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

题目

如果整数 x 满足：对于每个数位 d ，这个数位 恰好 在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。

给你一个整数 n ，请你返回 严格大于 n 的 最小数值平衡数 。

示例 1：

输入：n = 1
输出：22
解释：
22 是一个数值平衡数，因为：

• 数字 2 出现 2 次

这也是严格大于 1 的最小数值平衡数。

示例 2：

输入：n = 1000
输出：1333
解释：
1333 是一个数值平衡数，因为：

• 数字 1 出现 1 次。

• 数字 3 出现 3 次。

这也是严格大于 1000 的最小数值平衡数。
注意，1022 不能作为本输入的答案，因为数字 0 的出现次数超过了 0 。

示例 3：

输入：n = 3000
输出：3133
解释：
3133 是一个数值平衡数，因为：

• 数字 1 出现 1 次。

• 数字 3 出现 3 次。

这也是严格大于 3000 的最小数值平衡数。

提示：

$0 \leq n \leq 10^6$

题解

暴力解即可～

class Solution {
    public int nextBeautifulNumber(int n) {
        for(int i = n + 1; i <= Integer.MAX_VALUE; i++){
            if(isChecked(i)){
                return i;
            }
        }
        return -1;
    }
    public boolean isChecked(int n){
        int[] cnt = new int[10];
        String str = Integer.toString(n);
        int len = str.length();
        for(int i = 0; i < len; i++){
            cnt[(int)(str.charAt(i) - '0')]++;
        }
        for(int i = 0; i < 10; i++){
            if(cnt[i] != 0){
                if(cnt[i] != i) return false;
            }
        }
        return true;
    }
}

当然评论区里的人才个个说话都好听，既然数据量不是很大，指$10^6$不是很大，打表人永不为奴了属于是

class Solution {
    public int nextBeautifulNumber(int n) {
        if (n<1) {
            return 1;
        }else if (n<22) {
            return 22;
        } else if (n<122) {
            return 122;
        }else if(n<212){
            return 212;
        }else if(n<221){
            return 221;
        }else if(n<333){
            return 333;
        }else if(n<1333){
            return 1333;
        }else if(n<3133){
            return 3133;
        }else if(n<3313){
            return 3313;
       
        }else if(n<3331){
            return 3331;
        }else if(n<4444){
            return 4444;
        }else if(n<14444){
            return 14444;
        }else if(n<22333){
            return 22333;
        }else if(n<23233){
            return 23233;
        }else if(n<23323){
            return 23323;
        }else if(n<23332){
            return 23332;
        }else if(n<32233){
            return 32233;
        }else if(n<32323){
            return 32323;
        }else if(n<32332){
            return 32332;
        }else if(n<33223){
            return 33223;
        }else if(n<33232){
            return 33232;
        }else if(n<33322){
            return 33322;
        }else if(n<41444){
            return 41444;
        }else if(n<44144){
            return 44144;
        }else if(n<44414){
            return 44414;
        }else if(n<44441){
            return 44441;
        }else if(n<55555){
            return 55555;   
        }else if(n<122333){
            return 122333;
        }else if(n<123233){
            return 123233;
        }else if(n<123323){
            return 123323;
        }else if(n<123332){
            return 123332;
        }else if(n<132233){
            return 132233;
        }else if(n<132323){
            return 132323;
        }else if(n<132332){
            return 132332;
        }else if(n<133223){
            return 133223;
        }else if(n<133232){
            return 133232;
        }else if(n<133322){
            return 133322;
        }else if(n<155555){
            return 155555;
        }else if(n<212333){
            return 212333;
        }else if(n<213233){
            return 213233;
        }else if(n<213323){
            return 213323;
        }else if(n<213332){
            return 213332;
        }else if(n<221333){
            return 221333;
        }else if(n<223133){
            return 223133;
        }else if(n<223313){
            return 223313;
        }else if(n<223331){
            return 223331;
        }else if(n<224444){
            return 224444;
        }else if(n<231233){
            return 231233;
        }else if(n<231323){
            return 231323;
        }else if(n<231332){
            return 231332;
        }else if(n<232133){
            return 232133;
        }else if(n<232313){
            return 232313;
        }else if(n<232331){
            return 232331;
        }else if(n<233123){
            return 233123;
        }else if(n<233132){
            return 233132;
        }else if(n<233213){
            return 233213;
        }else if(n<233231){
            return 233231;
        }else if(n<233312){
            return 233312;
        }else if(n<233321){
            return 233321;
        }else if(n<242444){
            return 242444;
        }else if(n<244244){
            return 244244;
        }else if(n<244424){
            return 244424;
        }else if(n<244442){
            return 244442;
        }else if(n<312233){
            return 312233;
        }else if(n<312323){
            return 312323;
        }else if(n<312332){
            return 312332;
        }else if(n<313223){
            return 313223;
        }else if(n<313232){
            return 313232;
        }else if(n<313322){
            return 313322;
        }else if(n<321233){
            return 321233;
        }else if(n<321323){
            return 321323;
        }else if(n<321332){
            return 321332;
        }else if(n<322133){
            return 322133;
        }else if(n<322313){
            return 322313;
        }else if(n<322331){
            return 322331;
        }else if(n<323123){
            return 323123;
        }else if(n<323132){
            return 323132;
        }else if(n<323213){
            return 323213;
        }else if(n<323231){
            return 323231;
        }else if(n<323312){
            return 323312;
        }else if(n<323321){
            return 323321;
        }else if(n<331223){
            return 331223;
        }else if(n<331232){
            return 331232;
        }else if(n<331322){
            return 331322;
        }else if(n<332123){
            return 332123;
        }else if(n<332132){
            return 332132;
        }else if(n<332213){
            return 332213;
        }else if(n<332231){
            return 332231;
        }else if(n<332312){
            return 332312;
        }else if(n<332321){
            return 332321;
        }else if(n<333122){
            return 333122;
        }else if(n<333212){
            return 333212;
        }else if(n<333221){
            return 333221;
        }else if(n<422444){
            return 422444;
        }else if(n<424244){
            return 424244;
        }else if(n<424424){
            return 424424;
        }else if(n<424442){
            return 424442;
        }else if(n<442244){
            return 442244;
        }else if(n<442424){
            return 442424;
        }else if(n<442442){
            return 442442;
        }else if(n<444224){
            return 444224;
        }else if(n<444242){
            return 444242;
        }else if(n<444422){
            return 444422;
        }else if(n<515555){
            return 515555;
        }else if(n<551555){
            return 551555;
        }else if(n<555155){
            return 555155;
        }else if(n<555515){
            return 555515;
        }else if(n<555551){
            return 555551;
        }else if(n<666666){
            return 666666;
        }
            return 1224444;
    }
}

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

题目

给你一棵根节点为 0 的 二叉树 ，它总共有 n 个节点，节点编号为 0 到 n - 1 。同时给你一个下标从 0 开始的整数数组 parents 表示这棵树，其中 parents[i] 是节点 i 的父节点。由于节点 0 是根，所以 parents[0] == -1 。

一个子树的 大小 为这个子树内节点的数目。每个节点都有一个与之关联的 分数 。求出某个节点分数的方法是，将这个节点和与它相连的边全部 删除 ，剩余部分是若干个 非空 子树，这个节点的 分数 为所有这些子树 大小的乘积 。

请你返回有 最高得分 节点的 数目 。

示例 1:

输入：parents = [-1,2,0,2,0]
输出：3
解释：

• 节点 0 的分数为：3 * 1 = 3

• 节点 1 的分数为：4 = 4

• 节点 2 的分数为：1 * 1 * 2 = 2

• 节点 3 的分数为：4 = 4

• 节点 4 的分数为：4 = 4

最高得分为 4 ，有三个节点得分为 4 （分别是节点 1，3 和 4 ）。

示例 2：

输入：parents = [-1,2,0]
输出：2
解释：

• 节点 0 的分数为：2 = 2

• 节点 1 的分数为：2 = 2

• 节点 2 的分数为：1 * 1 = 1

最高分数为 2 ，有两个节点分数为 2 （分别为节点 0 和 1 ）。

提示：

• n == parents.length
• $2 \leq n \leq 10^5$
• parents[0] == -1
• 对于 i != 0 ，有 $0 \leq parents[i] \leq n - 1$
• parents 表示一棵二叉树。

题解

全程唯一亮点：做乘法可能溢出，干，WA了捉了半天虫，发现是long的问题🤦‍♂️

另外捉个题目的小虫，貌似是树就可了，二叉树还真不需要😂

对于树上的任意一个节点而言，当我们进行分离的时候他的各个子树都会被分离出来，也就是子树的节点数相乘即可，至于顶头的另外一部分我们直接拿总结点数去减掉节点和其包含的所有子树即可，毕竟大家都在一棵树里面，不存在其他特殊情况。

class Solution {
    long max = -1;
    int cnt = 1;
    public int countHighestScoreNodes(int[] parents) {
        int n = parents.length;
        List<List<Integer>> child = new ArrayList<>();
        for(int i = 0; i < n; i++){
            child.add(new ArrayList<Integer>());
        }
        for(int i = 1; i < n; i++){
            child.get(parents[i]).add(i);
        }
        dfs(child, 0, n);
        return cnt;
    }
    public int dfs(List<List<Integer>> child, int node, int n){
        int res = 0;
        long cur = 1L;
        for(int x: child.get(node)){
            int ch = dfs(child, x, n);
            cur *= (ch == 0) ? 1 : ch;
            res += ch;
        }
        res++;
        cur *= (n - res == 0)? 1: (n - res);
        //System.out.println(node + " " + cur);
        if(cur > max){
            max = cur;
            cnt = 1;
        }else if(cur == max){
            cnt++;
        }
        return res;
    }
}

T4 5909. 并行课程 III

题目

给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n 。同时给你一个二维整数数组 relations ，其中 relations[j] = [prevCoursej, nextCoursej] ，表示课程 prevCoursej 必须在课程 nextCoursej 之前 完成（先修课的关系）。同时给你一个下标从 0 开始的整数数组 time ，其中 time[i] 表示完成第 (i+1) 门课程需要花费的 月份 数。

请你根据以下规则算出完成所有课程所需要的 最少 月份数：

如果一门课的所有先修课都已经完成，你可以在 任意 时间开始这门课程。
你可以 同时 上 任意门课程 。
请你返回完成所有课程所需要的 最少 月份数。

注意：测试数据保证一定可以完成所有课程（也就是先修课的关系构成一个有向无环图）。

示例 1:

输入：n = 3, relations = [[1,3],[2,3]], time = [3,2,5]
输出：8
解释：上图展示了输入数据所表示的先修关系图，以及完成每门课程需要花费的时间。
你可以在月份 0 同时开始课程 1 和 2 。
课程 1 花费 3 个月，课程 2 花费 2 个月。
所以，最早开始课程 3 的时间是月份 3 ，完成所有课程所需时间为 3 + 5 = 8 个月。

示例 2：

输入：n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]
输出：12
解释：上图展示了输入数据所表示的先修关系图，以及完成每门课程需要花费的时间。
你可以在月份 0 同时开始课程 1 ，2 和 3 。
在月份 1，2 和 3 分别完成这三门课程。
课程 4 需在课程 3 之后开始，也就是 3 个月后。课程 4 在 3 + 4 = 7 月完成。
课程 5 需在课程 1，2，3 和 4 之后开始，也就是在 max(1,2,3,7) = 7 月开始。
所以完成所有课程所需的最少时间为 7 + 5 = 12 个月。

提示：

• $1 \leq n \leq 5 * 10^4$
• $0 \leq relations.length \leq min(n * (n - 1) / 2, 5 * 10^4)$
• $relations[j].length == 2$
• $1 \leq prevCoursej, nextCoursej \leq n$
• prevCoursej != nextCoursej
• 所有的先修课程对 [prevCoursej, nextCoursej] 都是 互不相同 的。
• $time.length == n$
• $1 \leq time[i] \leq 10^4$
• 先修课程图是一个有向无环图。

题解

初看，好像是拓扑？实际一写，哇，还真是拓扑，那没事了

裸拓扑板子题

最关键的问题就是每个上级节点的值最小也要取到下级节点中的最大值来进行计算，也就是你必须等到下级节点中最晚的结束了才能开始自己的课程。

class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        List<List<Integer>> neighbours = new ArrayList<>();
        int[] indegrees = new int[n + 1];
        for(int i = 0; i <= n; i++){
            neighbours.add(new ArrayList<Integer>());
        }
        for(int[] relation: relations){
            indegrees[relation[1]]++;
            neighbours.get(relation[0]).add(relation[1]);
        }
        int[] res = new int[n + 1];
        Queue<Integer> queue = new ArrayDeque<>();
        for(int i = 1; i <= n; i++){
            if(indegrees[i] == 0){
                queue.offer(i);
                res[i] = time[i - 1];
            }
        }
        while(!queue.isEmpty()){
            int cur = queue.poll();
            for(int x: neighbours.get(cur)){
                res[x] = Math.max(res[x], res[cur] + time[x - 1]);
                if(--indegrees[x] == 0){
                    queue.offer(x);
                }
            }
        }
        int max = 0;
        for(int i = 1; i <= n; i++) max = Math.max(max, res[i]);
        return max;
    }
}

笑死，但是没完全笑死，这么一看最难的还真是T1。属实牛批。