代码随想录|Day20|二叉树09|669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树
669. 修剪二叉搜索树
思路:利用二叉搜索树的性质,对于每个节点,判断其是否在区间内:
- 如果节点值 < low,则此节点和其左子树都不在范围内
- 如果节点值 > high,则此节点和其右子树都不在范围内
- 如果 low < 节点值 < high,则保留此节点,但需要递归修建其左右子树
class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:if not root:return None# 如果节点小于low,返回右子树修剪的结果if root.val < low:return self.trimBST(root.right, low, high)# 如果节点大于high,返回左子树修剪的结果elif root.val > high:return self.trimBST(root.left, low, high)# 如果节点在区间内,递归修建左右子树else:root.left = self.trimBST(root.left, low, high)root.right = self.trimBST(root.right, low, high)return root
108.将有序数组转换为二叉搜索树
思路:我们知道,按照中序遍历一个二叉搜索树将获得一个递增数组。因此我们可以将数组二分,中间元素所谓根节点,左边元素作为左子树,右边元素作为右子树,递归下去可以构成平衡二叉搜索树。
class Solution:def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:def helper(left, right):if left > right:return Nonemid = (left + right) // 2root = TreeNode(nums[mid])root.left = helper(left, mid - 1)root.right = helper(mid + 1, right)return rootreturn helper(0, len(nums)-1)
538.把二叉搜索树转换为累加树
什么是累加树?
指在二叉搜索树(BST)的基础上进行转换得到的一种特殊形式的树。在累加树中,每个节点的值被替换为原始二叉搜索树中所有大于该节点值的节点值之和加上该节点自身的值。
思路:我们从最大值开始累加,因此遍历顺序是元素从大到小。我们可以使用反向中序遍历来实现:右中左。
class Solution:def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:self.sum = 0def traverse(node):if not node:return# 反向中序遍历:右 -> 根 -> 左traverse(node.right)self.sum += node.valnode.val = self.sumtraverse(node.left)traverse(root)return root相关文章:
代码随想录|Day20|二叉树09|669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树
669. 修剪二叉搜索树 思路:利用二叉搜索树的性质,对于每个节点,判断其是否在区间内: 如果节点值 < low,则此节点和其左子树都不在范围内如果节点值 > high,则此节点和其右子树都不在范围内如果 low &…...
开源的java 代码分析库介绍
本文将为您详细讲解开源的 Java 代码分析库,以及如何安装这些库、它们的特性、区别和应用场景。Java 社区提供了多种代码分析工具,这些工具可以帮助您在 Java 应用程序中进行代码质量评估、性能分析、安全检查等功能。 1. CheckStyle 安装 - 通过…...
基于udp协议的网络通信(windows客户端版+简易聊天室版),重定向到终端
目录 和windows通信 引入 思路 WSADATA 代码 运行情况 简单的聊天室 思路 重定向 代码 terminal.hpp -- 重定向函数 服务端 客户端 运行情况 和windows通信 引入 linux和windows都需要联网,虽然他们系统设计不同,但网络部分一定是相同的,所以套接字也是一样的 这…...
Qt+FFmpeg+opengl从零制作视频播放器-7.OpenGL播放视频
在上一节Qt+FFmpeg+opengl从零制作视频播放器-6.视频解码中,我们学到了如何将视频数据解码成YUV原始数据,并且保存到本地,最后使用工具来播放YUV文件。 本节使用QOpenGLWidget来渲染解码后的YUV视频数据。 首先简单介绍QOpenGLWidget的使用。 QOpenGLWidget类是用于渲染O…...
用两个栈实现简单的四则运算
题目要求:给定一个字符串如“12*3”,没有括号,要求利用栈的知识来处理结果算出答案 我的思路:建立两个栈,一个存放数据,一个存放符号,再定义一个结构体做为操作的主体,然后制作几个函数&#x…...
<个人笔记>数论
1.快速幂 (1)求解问题: 给定 n组 ai,bi,pi求 aibi mod pi 的值。 (2)主要思想:任何一个数(b),可以被 n 个 2k 相加获得。 即 b 2k1 2k2 2k3 … 2logb。 快速幂模板: typedef long long LL;LL qmi(int a,int b,int p){LL re…...
CMS垃圾收集
初始标记 需要暂停所有的其他线程,但这个阶段会很快完成。它的目的是标记所有的根对象,以及被根对象直接引用的对象,以及年轻代指向老年代的对象,不会遍历对象关系,单线程执行。 并发标记阶段 不需要暂停应用线程&a…...
Incorrect DECIMAL value: ‘0‘ for column ‘‘ at row -1
用mysql插入数据的时候,报了上面的错误。 语句类似:INSERT INTO t_aa(c1,c2,c3,a1,a2,a3) SELECT t1,t2,t3,b1,b2,b3 FROM ( SELECT, t1,t2,t3 cast(ifnull(d1,0)as decimal(8,1) b1, cast(ifnull(d2,0) as decimal(8,1) b2, …...
Vue3组件通信的方式
1、父给子传 — props 父组件 <template><h1>父</h1><Son :value"number" /><button click"add">点我加1</button> </template><script setup> import Son from ./son.vue;import { ref } from vue; le…...
双场板功率型GaN HEMT中用于精确开关行为的电容建模
来源:Capacitance Modeling in Dual Field-Plate Power GaN HEMT for Accurate Switching Behavior (TED 16年) 摘要 本文提出了一种基于表面电势的紧凑模型,用于描述具有栅极和源极场板(FP)结构的AlGaN/GaN高电子迁移率晶体管(…...
UE4_AI_行为树_行为树快速入门指南
声明:学习笔记。 在 行为树快速入门指南 中,你将学会如何创建一个敌方AI,该AI看到玩家后会做出反应并展开追逐。当玩家离开视线后,AI将在几秒钟后(这可根据你的需求进行调整)放弃追逐,并在场景中…...
c++ 面试100个题目中的编程题目
88、下列程序的运行结果是? #include <stdlib.h> #include <stdio.h> #include <string.h> #include <iostream> const char* str = "vermeer"; using namespace std; int main(){ const char* pstr = str;cout << "The add…...
C++初阶:类与对象(尾篇)
目录 1. 构造函数与初始化列表1.1 对象的创建与构造函数的初始化1.2 初始化列表及构造函数存在的意义1.3 explicit关键字与构造函数的类型转换 2. static成员变量与static成员函数2.1 static成员变量2.2 static成员函数 3. 日期类流插入操作符的重载与友元3.1 友元3.2 友元函数…...
Spring状态机简单实现
一、什么是状态机 状态机,又称有限状态自动机,是表示有限个状态以及在这些状态之间的转移和动作等行为的计算模型。状态机的概念其实可以应用的各种领域,包括电子工程、语言学、哲学、生物学、数学和逻辑学等,例如日常生活中的电…...
WebServer -- 面试题(下)
👂 夏风 - Gifty - 单曲 - 网易云音乐 目录 🌼前言 🎂面试题(下) 4)HTTP报文解析 为什么要用状态机 状态转移图画一下 https 协议为什么安全 https 的 ssl 连接过程 GET 和 POST 的区别 5)数据库注册登录 登…...
企业微信如何接入第三方应用?
1.登录企业微信管理后台:https://work.weixin.qq.com/wework_admin 2.点击创建应用; 3. 此时可以看到已经创建好的应用,并且生成应用的唯一id(agentId) 4. 第三方应用申请域名 (举例&…...
JAVA后端编码的主键字段存储为什么倾向于使用雪花算法
1.背景 最近有人问,什么是雪花算法,为什么使用雪花算法不使用数据库UUID,基于此,写一个说明。 2.简介 (1)雪花算法,英文名为snowflake,翻译过来就是是雪花,所以叫雪花…...
Rust 深度学习库 Burn
一、概述 Burn 它是一个新的综合动态深度学习框架,使用 Rust 构建的,以极高的灵活性、计算效率和可移植性作为其主要目标。 Rust Burn 是一个以灵活性、高性能和易用性为核心设计原则工具,主打就是灵活性 、高性能 及易用性。 二、Rust B…...
C语言-存储期2.0
静态存储期 在数据段中分配的变量,统统拥有静态存储期,因此也都被称为静态变量。这里静态的含义,指的是这些变量的不会因为程序的运行而发生临时性的分配和释放,它们的生命周期是恒定的,跟整个程序一致。 静态变量包含…...
计算机网络面经八股-HTTP请求报文和响应报文的格式?
请求报文格式: 请求行(请求方法URI协议版本)请求头部空行请求主体 请求行:GET /sample.jsp HTTP/1.1 表示使用 GET 方法请求 /sample.jsp 资源,并使用 HTTP/1.1 协议。请求头部:包含多个字段,…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
Admin.Net中的消息通信SignalR解释
定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...
