当前位置: 首页 > news >正文

501、二叉搜索树中的众数

1、题目描述

. - 力扣(LeetCode)

要求:给一个包含重复值的BST,找出并返回BST中的众数(出现频次最高的元素)。

注:如果树中有不止一个众数可以按任意顺序返回,即如果有多个众数多个都要返回。

ps:另外要求不使用额外的空间。

2、分析

分析:看起来还是要求在中序遍历的过程中就记录结果。

(1)在遍历的过程中记录每个数字出现的次数并不断更新,同时维护历史所有的出现过的最大次数的数。

(2)如果最大次数被刷新,就清空向量result并插入最新的众数;如果当前数字出现的次数小于历史最大次数啥都不做;

(3)如果当前数字出现的子树等于历史最大次数则将这个数也插进去。

class Solution {
public:TreeNode* pre = NULL; //记录上一个节点(的数)int max_times = 0;    //记录历史最大出现的次数int cur_times = 0;    //记录当前数字出现的次数vector<int> findMode(TreeNode* root) {vector<int> res;inordertraversal(root, res);return res;}void inordertraversal(TreeNode* root, vector<int>& res){if(root == NULL) return;inordertraversal(root->left, res); //左//中间节点的处理逻辑if(pre != NULL && root->val != pre->val){cur_times = 0;//如果出现新的数字了就直接将当前统计次数清零(随后有自加1)}pre = root; //更新precur_times++; //更新cur_times//超过之前记录的最大出现次数了if(cur_times > max_times){ res.clear();res.push_back(root->val);max_times = cur_times;//没超过只是触及我们也要记录}else if(cur_times == max_times){res.push_back(root->val);}inordertraversal(root->right, res);//右}
};

3、实现代码

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <math.h>using namespace std;struct TreeNode{int val;TreeNode *left;TreeNode *right;TreeNode(): val(0), left(nullptr), right(nullptr){}TreeNode(int x): val(x), left(nullptr), right(nullptr){}TreeNode(int x, TreeNode* left, TreeNode* right): val(x), left(left), right(right){}
};class Solution {
public:TreeNode* pre = NULL; //记录上一个节点(的数)int max_times = 0;    //记录历史最大出现的次数int cur_times = 0;    //记录当前数字出现的次数vector<int> findMode(TreeNode* root) {vector<int> res;inordertraversal(root, res);return res;}void inordertraversal(TreeNode* root, vector<int>& res){if(root == NULL) return;inordertraversal(root->left, res); //左//中间节点的处理逻辑if(pre != NULL && root->val != pre->val){cur_times = 0;//如果出现新的数字了就直接将当前统计次数清零(随后有自加1)}pre = root; //更新precur_times++; //更新cur_times//超过之前记录的最大出现次数了if(cur_times > max_times){ res.clear();res.push_back(root->val);max_times = cur_times;//没超过只是触及我们也要记录}else if(cur_times == max_times){res.push_back(root->val);}inordertraversal(root->right, res);//右}
};int main()
{Solution s1;/*TreeNode node4(1);TreeNode node5(3);TreeNode node3(5);TreeNode* pnode2 = new TreeNode(2, &node4, &node5);TreeNode root(4, pnode2, &node3);
*/TreeNode node3(2);TreeNode* pnode2 = new TreeNode(2, &node3, NULL);TreeNode* pnode1 = new TreeNode(1, NULL, pnode2);vector<int> res = s1.findMode(pnode1);for(int num:res){cout << num << ",";}cout << endl;}

 

相关文章:

501、二叉搜索树中的众数

1、题目描述 . - 力扣&#xff08;LeetCode&#xff09; 要求&#xff1a;给一个包含重复值的BST&#xff0c;找出并返回BST中的众数(出现频次最高的元素)。 注&#xff1a;如果树中有不止一个众数可以按任意顺序返回&#xff0c;即如果有多个众数多个都要返回。 ps&#xff1…...

【洛谷】P2330 [SCOI2005] 繁忙的都市 的题解

【洛谷】P2330 [SCOI2005] 繁忙的都市 的题解 题目传送门 题解 水最小生成树&#xff0c;发现可以水一堆黄题qaq 这题显然就是求最大边权最小的生成树&#xff0c;而用 Kruskal 很容易证明这就是最小生成树&#xff0c;考虑一下这个算法每次取的都是不构成环的最小边即可&a…...

第18场小白入门赛(蓝桥杯)

第 18 场 小白入门赛 6 武功秘籍 考察进制理解。 对于第 i i i 位&#xff0c;设 b i t i x bit_ix biti​x &#xff0c;每一位的最大值是 b j b_j bj​ &#xff0c;也就是说每一位是 b j 1 b_j1 bj​1 进制 &#xff0c;那么第 i i i 位的大小就是 x ∑ j i 1…...

Redission · 可重入锁(Reentrant Lock)

前言 Redisson是一个强大的分布式Java对象和服务库&#xff0c;专为简化在分布式环境中的Java开发而设计。通过Redisson&#xff0c;开发人员可以轻松地在分布式系统中共享数据、实现分布式锁、创建分布式对象&#xff0c;并处理各种分布式场景的挑战。 Redisson的设计灵感来…...

初阶C语言-指针

1.指针是什么&#xff1f; 理解指针的两个要点&#xff1a; 1.指针是内存中一个最小单元的编号&#xff0c;也就是地址 2.口头语中说的指针&#xff0c;通常是指指针变量&#xff0c;是用来存放内存地址的变量 总结&#xff1a;指针就是地址&#xff0c;口语中说的指针通常是指…...

论文笔记:微表情欺骗检测

整理了AAAI2018 Deception Detection in Videos 论文的阅读笔记 背景模型实验可视化 背景 欺骗在我们的日常生活中很常见。一些谎言是无害的&#xff0c;而另一些谎言可能会产生严重的后果。例如&#xff0c;在法庭上撒谎可能会影响司法公正&#xff0c;让有罪的被告逍遥法外。…...

智能家居有哪些产品?生活中常见的人工智能有哪些?

智能家居有哪些产品? 1、智能照明设备类&#xff1a;智能开关、智能插座、灯控模块、智能空开、智能灯、无线开关。 2、家庭安防类&#xff1a;智能门锁、智能摄像机、智能猫眼、智能门铃。 3、智能传感器类&#xff1a;烟雾传感器、可燃气体传感器、水浸传感器、声光报警器…...

洗车行软件系统有哪些 佳易王洗车店会员管理系统操作教程#洗车店会员软件试用版下载

一、前言 【试用版软件下载可点击本文章最下方官网卡片】 洗车行软件系统有哪些 佳易王洗车店会员管理系统操作教程#洗车店会员软件试用版下载 洗车管理软件应用是洗车业务的得力助手&#xff0c;实现会员管理及数据统计一体化&#xff0c;助力店铺高效、有序运营。 洗车项…...

【Java】springboot 项目中出现中文乱码

在刚创建的springboot项目中&#xff0c;出现乱码&#xff0c;跟走着解决一下 1、Ctrl Shift S 打开idea设置&#xff0c;根据图片来&#xff0c;将③④这三个地方都修改为UTF-8 2、返回配置查看&#xff0c;解决...

开放式耳机是什么意思?漏音吗?开放式的运动蓝牙耳机推荐

目前运动耳机市场主要分为入耳式、骨传导和开放式三类。入耳式耳机占比30%-40%&#xff0c;虽目前占比较大&#xff0c;但因在运动场景下有闷塞感、出汗不适、屏蔽外界环境音带来安全隐患等缺点&#xff0c;占比会逐渐下降。 骨传导耳机占比也为30%-40%&#xff0c;其不堵塞耳…...

如何优雅的处理NPE问题?

1.什么是NPE&#xff1f; NPE&#xff0c;即NullPointerException&#xff0c;是开发中最常见的问题之一&#xff0c;有必要知道如何正确地处理NPE。 对于 Java 开发者来说&#xff0c;null 是一个令人头疼的类型&#xff0c;一不小心就会发生 NPE &#xff08;空指针&#xf…...

k8s 中存储之 NFS 卷

目录 1 NFS 卷的介绍 2 NFS 卷的实践操作 2.1 部署一台 NFS 共享主机 2.2 在所有k8s节点中安装nfs-utils 2.3 部署nfs卷 2.3.1 生成 pod 清单文件 2.3.2 修改 pod 清单文件增加 实现 NFS卷 挂载的 参数 2.3.3 声明签单文件并查看是否创建成功 2.3.4 在 NFS 服务器 创建默认发布…...

Redis中BitMap实现签到与统计连续签到功能

服务层代码 //签到Overridepublic Result sign() {//1.获取当前登录的用户Long userId UserHolder.getUser().getId();//获取日期LocalDateTime now LocalDateTime.now();//拼接keyString keySuffix now.format(DateTimeFormatter.ofPattern(":yyyyMM"));String …...

【Spring】“请求“ 之传递 JSON 数据

文章目录 JSON 概念JSON 语法JSON 的语法JSON 的两种结构 JSON 字符串和 Java 对象互转JSON 优点传递 JSON 对象 JSON 概念 JSON&#xff1a;JavaScript Object Notation【JavaScript 对象表示法】 JSON 就是一种数据格式&#xff0c;有自己的格式和语法&#xff0c;使用文本…...

文心一言 VS 讯飞星火 VS chatgpt (359)-- 算法导论24.3 1题

一、在图 24-2上运行Dijkstra算法&#xff0c;第一次使用结点 s s s作为源结点&#xff0c;第二次使用结点 z z z作为源结点。以类似于图 24-6 的风格&#xff0c;给出每次while循环后的 d d d值和 π π π值&#xff0c;以及集合 S S S中的所有结点。如果要写代码&#xff0c…...

Redis-预热雪崩击穿穿透

预热雪崩穿透击穿 缓存预热 缓存雪崩 有这两种原因 redis key 永不过期or过期时间错开redis 缓存集群实现高可用 主从哨兵Redis Cluster开启redis持久化aof&#xff0c;rdb&#xff0c;尽快恢复集群 多缓存结合预防雪崩&#xff1a;本地缓存 ehcache redis 缓存服务降级&…...

jvisualvm学习

系列文章目录 JavaSE基础知识、数据类型学习万年历项目代码逻辑训练习题代码逻辑训练习题方法、数组学习图书管理系统项目面向对象编程&#xff1a;封装、继承、多态学习封装继承多态习题常用类、包装类、异常处理机制学习集合学习IO流、多线程学习仓库管理系统JavaSE项目员工…...

Gazebo环境下开源UAV与USV联合仿真平台

推荐一个ROS2下基于Gazebo环境的开源UAV与USV联合仿真平台。平台是由两个开源项目共同搭建的。首先是UAV仿真平台&#xff0c;是基于PX4官方仿真平台&#xff08;https://docs.px4.io/main/en/sim_gazebo_gz&#xff09;&#xff1b;其次是USV仿真平台&#xff0c;是基于VRX仿真…...

Linux进程调度和进程切换

并行&#xff08;Parallel&#xff09; 含义&#xff1a;并行是指多个任务在同一时刻同时执行。 硬件要求&#xff1a;需要多个处理器&#xff08;如多核CPU&#xff09;或者多台计算设备来实现&#xff0c;这些执行单元能够真正地同时处理不同的任务。例如&#xff0c;一个具…...

机器学习基本上就是特征工程——《特征工程训练营》

作为机器学习流程的一部分&#xff0c;特征工程是对数据进行转化以提高机器学习性能的艺术。 当前有关机器学习的讨论主要以模型为中心。更应该关注以数据为中心的机器学习方法。 本书旨在介绍流行的特征工程技术&#xff0c;讨论何时以及如何运用这些技术的框架。我发现&…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

MySQL:分区的基本使用

目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区&#xff08;Partitioning&#xff09;是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分&#xff08;分区&#xff09;可以独立存储、管理和优化&#xff0c;…...