题目链接： Leetcode Weekly Contest 264

1、2047. Number of Valid Words in a Sentence

难度：Easy

代码：

class Solution {
    public int countValidWords(String sentence) {
        int j=0;
        while(j<sentence.length()&&sentence.charAt(j)==' '){
            j++;
        }
        sentence=sentence.substring(j);
        String[] str=sentence.split("\\s+");
        //System.out.println(str.length);
        int res=0;
        for(String s:str){
            //System.out.println(s);
            char[] a=s.toCharArray();
            boolean flag=true;
            int hyphen=0;
            for(int i=0;i<a.length;i++){
                if(hyphen>=2){
                    flag=false;
                    break;
                }
                if(a[i]>='0'&&a[i]<='9'){
                    flag=false;
                    break;
                }
                if(a[i]=='-'){
                    hyphen++;
                    if(i==0||i==a.length-1||a[i-1]>'z'||a[i-1]<'a'||a[i+1]>'z'||a[i+1]<'a'){
                        flag=false;
                        break;
                    }
                    
                }
                if((a[i]=='!'||a[i]=='.'||a[i]==',')&&(i!=a.length-1)){
                    flag=false;
                    break;
                }
            }
            if(flag){
                res++;
            }
        }
        return res;
    }
}

2、2048. Next Greater Numerically Balanced Number

难度：Medium

思路：

暴力把1e6内所有的平衡数求出来，比1e6大的最小平衡数是1224444。

代码：

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

3、2049. Count Nodes With the Highest Score

难度：Medium

思路：

参考高赞回答，用DFS求解。

代码

class Solution {
    public int countHighestScoreNodes(int[] parents) {
        int n=parents.length;
        List<List<Integer>> children=new ArrayList<>();
        for(int i=0;i<n;i++){
            children.add(new ArrayList<>());
        }
        for(int i=1;i<n;i++){
            children.get(parents[i]).add(i);
        }
        int[] numNodes=new int[n];//numNodes[i]表示以i为根节点的子树共有多少个节点
        dfs(0,children,numNodes);
        long maxScore=0L;
        long[] score=new long[n];//score[i]表示移除节点i的得分
        for(int i=0;i<n;i++){
            int remain=n-numNodes[i];//移除掉以i为根节点后还剩下的节点个数
            if(remain>0){
                score[i]=remain;
            }
            else{
                score[i]=1;
            }
            for(int child:children.get(i)){
                score[i]*=numNodes[child];
            }
            maxScore=Math.max(maxScore,score[i]);
        }
        int count=0;
        for(long s:score){
            if(s==maxScore){
                count++;
            }
        }
        return count;
    }
    public int dfs(int node,List<List<Integer>> children,int[] numNodes){
        int numChild=0;
        for(int child:children.get(node)){
            if(numNodes[child]>0){
                numChild+=numNodes[child];
            }
            else{
                numChild+=dfs(child,children,numNodes);
            }
        }
        numNodes[node]=numChild+1;//加上自己本身
        return numNodes[node];
    }
}