2022-03-11

很迷惑，这个题看的不太懂，直接cv看官方了。

class Solution {
      List<Integer>[] children;
       long maxScore = 0;
 
      int cnt = 0;
    int n;

    public int countHighestScoreNodes(int[] parents) {
         n=parents.length;

// 每一个节点的子树以自身根的子树的大小
 
// DFS()
 children = new List[n];
   
    for(int i=0;i<n;i++){
       children[i]=new ArrayList<Integer>();
    }
     int i=1;
    
    for(int parent:parents){
        if(parent==-1){
            continue;
        }
      children[parent].add(i);
    i++;
    }
  
    int[] res=new int[n];

    // for(int j=0;j<n;j++){
    //     //    System.out.println(children[j][0]);
    //     //       System.out.println(children[j][1]);
    //   res[j]=Math.max(DFS(children[j][0],0),DFS(children[j][1],0))+1;
    //    System.out.println(res[j]);
       
    // }
    dfs(0);
    return cnt;

    
  


    }
     public int dfs(int node) {
        long score = 1;
        int size = n - 1;
        for (int c : children[node]) {
            int t = dfs(c);
            score *= t;
            size -= t;
        }
        if (node != 0) {
            score *= size;
        }
        if (score == maxScore) {
            cnt++;
        } else if (score > maxScore) {
            maxScore = score;
            cnt = 1;
        }
        return n - size;
    }


    // public int DFS(int i,int count){
    //     if(i==-1){
    //         return 0;
    //     }
    //     if(children[i][0]==-1 && children[i][1]==-1){
    //         return count;
    //     } 
    //   return  DFS(children[i][0],count+1)+DFS(children[i][1],count+1);
// }
        
        // int count_left=0,count_right=0;

    
        
        // return Math.max(count_left,count_right);
    
}

前缀树：65最短的单词编码：

class Solution {

    public int minimumLengthEncoding(String[] words) {
        // 好像确实有点像前缀树
      Arrays.sort(words, (s1,s2)-> s2.length()-s1.length());
      Tribe tree=new Tribe();
      int len=0;
      



    for(String text:words){
        boolean flag=false;
     Tribe node=tree;
        char[] text_arr=text.toCharArray();
        for(int i=text_arr.length-1;i>=0;i--){
            int index=text_arr[i]-'a';
            Tribe temp=node.children[index];
            
       if(temp==null){
           flag=true;
         temp=new Tribe();
         node.children[index]=temp;
       }
       node=temp;
        }
       if(flag) len+=text_arr.length+1;

       
    }
    return len;


    }
}
  class Tribe{
      Tribe[] children;
  
      public Tribe(){
          this.children=new Tribe[26];
   
      }
  }