【算法学习】LCP 44. 开幕式焰火(java / c / c++ / python / go / rust)

二当家的白帽子 2021-10-27 00:35:47
学习 算法 LCP 法学 开幕式

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子 https://le-yi.blog.csdn.net/ 博客原创~



LCP 44. 开幕式焰火:

「力扣挑战赛」开幕式开始了,空中绽放了一颗二叉树形的巨型焰火。
给定一棵二叉树 root 代表焰火,节点值表示巨型焰火这一位置的颜色种类。请帮小扣计算巨型焰火有多少种不同的颜色。

样例 1

输入:
root = [1,3,2,1,null,2]
输出:
3
解释:
焰火中有 3 个不同的颜色,值分别为 1、2、3

样例 2

输入:
root = [3,3,3]
输出:
1
解释:
焰火中仅出现 1 个颜色,值为 3

提示

  • 1 <= 节点个数 <= 1000
  • 1 <= Node.val <= 1000

分析

  • 翻译一下题意就是看整个树里一共有几种不同的值。
  • 所以考察了2个方面的知识点,一个是二叉树数据结构,一个是统计计数。
  • 最容易想到的是用Set之类的数据结构。
  • 循环和递归都可以。
  • 提示中已经给定了节点值的范围,所以可以使用数组这种底层数据结构去替代Set等数据结构。
  • 在遍历树的过程中判断计数,或者在最后再对计数的数据结构遍历计数,这两种方式都可以,在遍历树中判断计数受节点的数量影响,在最后再遍历计数数据结构计数受节点值取值范围影响。

题解

java

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {

public int numColor(TreeNode root) {

int ans = 0;
boolean[] flag = new boolean[1001];
dfs(root, flag);
for (boolean f : flag) {

if (f) {

ans++;
}
}
return ans;
}
private void dfs(TreeNode root, boolean[] flag) {

if (root != null) {

flag[root.val] = true;
dfs(root.left, flag);
dfs(root.right, flag);
}
}
}

c

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
int numColor(struct TreeNode *root) {

int ans = 0;
bool flag[1001] = {
false};
dfs(root, flag);
for (int i = 1; i < 1001; ++i) {

if (flag[i]) {

ans++;
}
}
return ans;
}
void dfs(struct TreeNode *root, bool *flag) {

if (root) {

flag[root->val] = true;
dfs(root->left, flag);
dfs(root->right, flag);
}
}

c++

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
class Solution {

public:
int numColor(struct TreeNode *root) {

int ans = 0;
bool flag[1001] = {
false};
dfs(root, flag);
for (bool f : flag) {

if (f) {

ans++;
}
}
return ans;
}
void dfs(struct TreeNode *root, bool *flag) {

if (root != nullptr) {

flag[root->val] = true;
dfs(root->left, flag);
dfs(root->right, flag);
}
}
};

python

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def numColor(self, root: TreeNode) -> int:
ans = 0
flag = [False] * 1001
def dfs(n):
if n:
flag[n.val] = True
dfs(n.left)
dfs(n.right)
dfs(root)
for f in flag:
if f:
ans += 1
return ans

go

/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
func numColor(root *TreeNode) int {

ans := 0
var flag [1001]bool
var dfs func(*TreeNode)
dfs = func(n *TreeNode) {

if n == nil {

return
}
flag[n.Val] = true
dfs(n.Left)
dfs(n.Right)
}
dfs(root)
for i := 1; i < 1001; i++ {

if flag[i] {

ans++
}
}
return ans
}

rust

// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn num_color(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
let mut ans = 0;
let mut flag = vec![false; 1001];
Solution::dfs(root, &mut flag);
flag.into_iter().for_each(|f| {
if f { ans += 1; }
});
ans
}
fn dfs(root: Option<Rc<RefCell<TreeNode>>>, flag: &mut Vec<bool>) {
if let Some(root) = root {
let root = root.borrow();
flag[root.val as usize] = true;
Solution::dfs(root.left.clone(), flag);
Solution::dfs(root.right.clone(), flag);
}
}
}

在这里插入图片描述


原题传送门:https://leetcode-cn.com/problems/sZ59z6/


版权声明
本文为[二当家的白帽子]所创,转载请带上原文链接,感谢
https://le-yi.blog.csdn.net/article/details/120606909

  1. python编写程序, 先输入一组10个元素,再输出数组中比平均值小的所有奇数。
  2. 《用python写网络爬虫》完整版+源码
  3. python中的小问题,友友们来看一下
  4. python自定义函数CircleArea求圆面积
  5. 判断年月日问题python 不知道自己哪里写错了
  6. 关于Python语言表达的问题
  7. Python代码阅读(第23篇):将变量名称转换为短横线连接式命名风格
  8. Python 用ARIMA、GARCH模型预测分析股票市场收益率时间序列
  9. 云计算开发:Python3-encode()方法详解
  10. python编写程序自动计算个人总分平均分各科最高最低平均分
  11. 在不同python版本下的python代码可以集成到一个应用中吗?
  12. 吹弹牛皮之Unity 工具制作常用交互bat ini python
  13. 手动新建和pycharm新建Djagno项目时候,Django项目的文件夹和虚拟环境文件夹venv的位置有所不同
  14. python课提的求解答一下,是什么意思
  15. python画图X轴太密集了,为什么加了代码也没用
  16. 用PYTHON实现EXCEL数据改动的cell高亮显示
  17. Python Type Hints 从入门到实践
  18. 求一个python大大( •︠ˍ•︡ )(想哭)如果可以的话可以开课,我可以去听课
  19. 真香!值得收藏的30道Python练手题(附详细答案)
  20. django+uwsgi+nginx 前后端分离部署配置
  21. 用python实现千图成像工具,快给你的男/女神弄一张吧~
  22. python csv中dwlimiter用不了,有没有大咖能解释一下
  23. 新手学Python要打好哪些基础?从软件安装到全面基础讲解,就它了!
  24. Python中字符串子串的输出
  25. python判断是否一个序列是超增序列
  26. Python爬虫框架的读取和创建
  27. python对数据框中两列进行判断, 得到新的列的
  28. Python做一个模仿文本进度条的编程
  29. python 中使用MS SQL问题 怎样解决
  30. python有没有类似传送门功能的代码,,就是比如这边运行完然后输入一些指令然后可以跳转到程序里的某个地方
  31. Python基操教学!不会?(熟能生巧)
  32. python画图,有没有初学者的代码
  33. 朋友股票亏惨了,我一怒用Python爬取了证券最新数据
  34. 被称之为永远的神!就这6个Python爬虫开源项目?
  35. python Qtreeview 如何选择子行,选择第一行下面的行数
  36. Python随机生成100个1~200之间的不重复数字
  37. 关于#python#的问题,请各位专家解答!
  38. Python编写程序先输入一组10个元素,再输入数组中比平均值小的所有奇数
  39. Ubuntu终端下安装Python需要import的库
  40. 为什么下载pandas和xlwings运行不了,出现No system module pywintypes(系统查不到pywin32具体位置)(又不能重新下载pywin32)
  41. python求带我脱离苦海,哎_
  42. Python 数据分析里面轴的问题
  43. python初学者,请问使用openpyxl库读取文件后出现图片中的报错要怎么解决?
  44. 大学毕业论文写有关python
  45. 授人以鱼吧友友python编写程序自动计算个人总分平均分各科最高最低平均分
  46. python怎么将四行代码换成一行啊
  47. 用Python如何编写啊 真不会啊?
  48. 这个布尔变化怎么做啊(Python
  49. PYTHON求集合交集需要用户手动输入集合名
  50. Python运行哈姆雷特词频统计时出错(如图),是哪方面的问题?
  51. 【Python表白代码合集】”我还是很喜欢你,像风走了八千里,不问归期”!!
  52. python实现学生信息管理系统(含代码)
  53. wxpython中如何按键停止死循环?
  54. python 类的问题?不懂这种方法的作用?不是继承那是什么作用?
  55. Python 题目不会写 求帮助!
  56. Python,turtle制图,要求使用for,while编写
  57. Python题目不会 求帮助! 谢谢您!
  58. Python题目不会!求帮助!
  59. Python这个看不太懂,,大神们帮个忙
  60. 安装拓展库pandas失败怎么解决