每日一题补题记录14

题记录14"/>

每日一题补题记录14

3.11

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

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

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

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

首先我们要建立一张表或者一张图，然后根据节点来分类处理，如果当前节点是根节点，那么所有的连通分量数目就是当前节点的子节点数目（也就是子连通分量个数）；如果当前节点不是根节点，还要加上其父亲所在连通分量，期间我们要处理每个连通分量大小。

一个可行的计算方法是，我们要统计每个节点做根节点对应子树的大小，只有父亲节点所在连通分量要特殊处理，只要用总的结点数减去两个子连通分量再减去该节点（1）即可得到，再计算分数就可以了。

class Solution {//注意到树的长度，如果三个子树均分，那么相乘就会爆int，所以分数用long,别的不需要long maxScore;int n,maxCount;//记录这棵树List<Integer>[]tree;public int countHighestScoreNodes(int[] parents) {//变量初始化n=parents.length;maxScore=0;maxCount=0;tree=new List[n];for(int i=0;i<n;i++){tree[i]=new ArrayList<>();}//记录树for(int i=0;i<n;i++){int p=parents[i];//特殊情况if(p!=-1)tree[p].add(i);}//DFSdfs(0);return maxCount;}//计算以Node为根的子树内结点数目int dfs(int Node) {long score = 1;//记录包括自己在内这棵树的节点总数int sum = 1;for (int num : tree[Node]) {//子树的节点个数int t = dfs(num);//计算当前节点分数score *= t;sum += t;}//只要不是根节点，就要考虑其父节点所在联通分量if (Node != 0) {score *= n - sum;}//分数计算完成，对比当前最高分//若相同，增加最高分数目if (score==maxScore) {maxCount++;//刷新最高分数//重置最高分数目} else if (score>maxScore) {maxScore = score;maxCount = 1;}//返回本子树结点数目return sum;}
}

3.12

590. N 叉树的后序遍历

给定一个 n 叉树的根节点 root ，返回 其节点值的 后序遍历 。

n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

dfs+递归后序遍历

class Solution {List<Integer>ans;public List<Integer> postorder(Node root) {ans=new ArrayList<>();dfs(root,ans);return ans;}void dfs(Node root,List<Integer>ans){if(root==null)return;for(Node node:root.children){dfs(node,ans);}ans.add(root.val);}
}

3.13

393. UTF-8 编码验证

给定一个表示数据的整数数组 data ，返回它是否为有效的 UTF-8 编码。

UTF-8 中的一个字符可能的长度为 1 到 4 字节，遵循以下的规则：

对于 1 字节 的字符，字节的第一位设为 0 ，后面 7 位为这个符号的 unicode 码。
对于 n 字节 的字符 (n > 1)，第一个字节的前 n 位都设为1，第 n+1 位设为 0 ，后面字节的前两位一律设为 10 。剩下的没有提及的二进制位，全部为这个符号的 unicode 码。
这是 UTF-8 编码的工作方式：

注意：输入是整数数组。只有每个整数的 最低 8 个有效位 用来存储数据。这意味着每个整数只表示 1 字节的数据。

这个题目要确定false的四种情况：

1.单字符长度>4(首字符11111以上)

2.首字符10开头

3.非首字符不以10开头

4.剩余空间不够

我们用一个count函数来记录当前首字节对应的字符所占字节数，可以处理1、2两种情况，不符合返回-1，然后根据count值处理，单字节的count=1，继续往后遍历，多字节的还要往后处理count-1个字节，确定都符合条件3，如果这个过程中越界就违反了4，返回false，这样逻辑就完整了。

class Solution {public boolean validUtf8(int[] data) {int n=data.length;int i=0;while(i<n){int cnt=count(data[i]);//字符数错误if(cnt==-1)return false;//单字节字符，直接跳过if(cnt==1){i++;continue;}//首先去掉当前这个字符cnt--;//处理后面的n-1个字节while (cnt-- > 0) {//往后遍历i++;//如果越界，直接返回falseif (i >= data.length) {return false;}int x = data[i];//检验每一位的开头是否符合10开头if ((x & 0b11000000) != 0b10000000) {return false;}}//处理完最后一个还得++i++;}return true;}//统计是几字节字符int count(int x) {//0开头，一字节if ((x & 0b10000000) == 0) {return 1;}//110开头，二字节if ((x & 0b11100000) == 0b11000000) {return 2;}//1110开头，三字节if ((x & 0b11110000) == 0b11100000) {return 3;}//11110开头，四字节if ((x & 0b11111000) == 0b11110000) {return 4;}return -1;}
}