IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 游戏开发 -> 力扣解法汇总2049-统计最高分的节点数目 -> 正文阅读

[游戏开发]力扣解法汇总2049-统计最高分的节点数目

原题链接:力扣


描述:

给你一棵根节点为 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 <= n <= 105
parents[0] == -1
对于?i != 0?,有?0 <= parents[i] <= n - 1
parents?表示一棵二叉树。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-nodes-with-the-highest-score
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:

* 解题思路:
* 这题长度10^5,那么时间复杂度一定不能超过O(NlgN),目标还是往O(N)靠拢。
* 我的想法是构建一个一个的Node节点,每个节点包含left,right,parent的id,以及leftNum和rightNum的数量。
* 第一步,我们构建所有的节点,用map记录。方便根据id查找该节点。
* 第二步,我们遍历数组,根据parent分别给parentNode的left和right赋值,以及给node节点的parent赋值。
* 第三步,从根节点开始递归遍历,找到left的节点数量leftNum,right的节点数量rightNum.如果某个节点的leftNum>0,则证明计算过,无需重复计算。其实应该也不会出现重复计算的场景,毕竟是从上向下有序的。
* 第四步,再次遍历数组。获取对应的node节点。因为我们有其leftNum,rightNum,则可以计算出parentNum。则value=leftNum*rightNum*parentNum;
* 第五步,如果value>maxvalue,则maxvaluenum=1。如果value==maxvalue,则maxvaluenum++。最终返回maxvaluenum即可

代码:

public class Solution2049 {

    public int countHighestScoreNodes(int[] parents) {
        Map<Integer, Node> map = new HashMap<>();//1,2
        for (int i = 0; i < parents.length; i++) {
            Node node = new Node();
            node.value = i;
            map.put(i, node);
        }
        for (int i = 0; i < parents.length; i++) {
            int parent = parents[i];
            Node parentNode = map.get(parent);
            if (parentNode == null) {
                continue;
            }
            if (parentNode.left == -1) {
                parentNode.left = i;
                continue;
            }
            parentNode.right = i;

            Node node = map.get(i);
            node.parent = parent;
        }
        int num = searchList(map.get(0), map);
        long maxValue = 0;
        int maxValueNum = 0;
        for (int i = 0; i < parents.length; i++) {
            Node node = map.get(i);
            long leftNum = node.leftNum;
            long rightNum = node.rightNum;
            long topNum = num - leftNum - rightNum - 1;
            topNum = topNum == 0 ? 1 : topNum;
            leftNum = leftNum == 0 ? 1 : leftNum;
            rightNum = rightNum == 0 ? 1 : rightNum;
            long value = leftNum * rightNum * topNum;
            if (value > maxValue) {
                maxValueNum = 1;
                maxValue = value;
            } else if (value == maxValue) {
                maxValueNum++;
            }
        }
        return maxValueNum;
    }

    private int searchList(Node node, Map<Integer, Node> map) {
        int leftNum = 0;
        int rightNum = 0;
        if (node.left >= 0) {
            if (node.leftNum > 0) {
                leftNum = node.leftNum;
            } else {
                leftNum = searchList(map.get(node.left), map);
            }
        }
        if (node.right >= 0) {
            if (node.rightNum > 0) {
                rightNum = node.rightNum;
            } else {
                rightNum = searchList(map.get(node.right), map);
            }
        }
        node.leftNum = leftNum;
        node.rightNum = rightNum;
        return leftNum + rightNum + 1;
    }


    static class Node {
        int value = -1;
        int leftNum = 0;
        int rightNum = 0;
        int parent = -1;
        int left = -1;
        int right = -1;

    }

}

  游戏开发 最新文章
6、英飞凌-AURIX-TC3XX: PWM实验之使用 GT
泛型自动装箱
CubeMax添加Rtthread操作系统 组件STM32F10
python多线程编程:如何优雅地关闭线程
数据类型隐式转换导致的阻塞
WebAPi实现多文件上传,并附带参数
from origin ‘null‘ has been blocked by
UE4 蓝图调用C++函数(附带项目工程)
Unity学习笔记(一)结构体的简单理解与应用
【Memory As a Programming Concept in C a
上一篇文章      下一篇文章      查看所有文章
加:2022-03-12 17:53:59  更:2022-03-12 17:57:40 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/25 13:20:03-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计