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

代码随想录第二十七天(669、108、538、回溯算法介绍)

669. 修剪二叉搜索树

不能简单地通过递归实现代码,比如:

class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (root == nullptr || root->val < low || root->val > high) return nullptr;root->left = trimBST(root->left, low, high);root->right = trimBST(root->right, low, high);return root;}
};

举例:
在这里插入图片描述
在遍历到0这个结点时,因为0满足递归的第一个条件,所以会直接将0的所有子树删除,但是0的右子树的节点满足[1,3]这个范围.

其实就是要考虑0节点右子树

class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(root==null) return null;if(root.val<low){return trimBST(root.right,low,high);}if(root.val>high){return trimBST(root.left,low,high);}root.left=trimBST(root.left,low,high);root.right=trimBST(root.right,low,high);return root;}
}

108. 将有序数组转换为二叉搜索树

这道题强调平衡,是怕给出了一个升序的数组后,建立的二叉树是这样的:
在这里插入图片描述
如果默认从数组的中间位置开始构建,以中间的节点作为根节点,然后递归的构建左子树和右子树,这个二叉树自然就是平衡的

class Solution {public TreeNode sortedArrayToBST(int[] nums) {if(nums.length==0) return null;return buildTree(nums,0,nums.length-1);}public TreeNode buildTree(int[] nums,int low,int high){if(low>high) return null;int mid=(low+high)/2;TreeNode root=new TreeNode(nums[mid]);root.left=buildTree(nums,low,mid-1);root.right=buildTree(nums,mid+1,high);return root;}
}

注意:
在Java中,由运算结果,由被运算数的最高数据类型决定(float比int类型高)

538. 把二叉搜索树转换为累加树

题中给出的例子:
在这里插入图片描述
根据答案:就是二叉搜索树遍历的顺序是[0,1,2,3,4,5,6,7,8],而累加树遍历的顺序是相反的,从8开始。所以在二叉搜索树上就是按照右中左的遍历顺序

哈哈,看完答案的思路之后自己写的代码,竟然是对的,比答案还简单,真开心!

class Solution {int val=0;//用于存储当前便利的结点之和public TreeNode convertBST(TreeNode root) {if(root==null) return null;root.right=convertBST(root.right);root.val+=val;val=root.val;root.left=convertBST(root.left);return root;}
}

回溯算法

1、回溯函数也就是递归函数,指的都是一个函数。
2、回溯的本质是穷举,穷举所有可能,然后选出我们想要的答案,回溯法并不是什么高效的算法。
3、主要解决的问题种类:
组合问题:N个数里面按一定规则找出k个数的集合
切割问题:一个字符串按一定规则有几种切割方式
子集问题:一个N个数的集合里有多少符合条件的子集
排列问题:N个数按一定规则全排列,有几种排列方式
棋盘问题:N皇后,解数独等等
4、关于组合和排列:
组合是不强调元素顺序的,排列是强调元素顺序
5、模板
习惯是函数起名字为backtracking
回溯算法中函数返回值一般为void

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {处理节点;backtracking(路径,选择列表); // 递归回溯,撤销处理结果}
}

相关文章:

代码随想录第二十七天(669、108、538、回溯算法介绍)

669. 修剪二叉搜索树 不能简单地通过递归实现代码&#xff0c;比如&#xff1a; class Solution { public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (root nullptr || root->val < low || root->val > high) return nullptr;root->left t…...

【Leetcode】设计循环队列

目录 【Leetcode622】设计循环队列 A.链接 B.题目再现 C.解法 【Leetcode622】设计循环队列 A.链接 设计循环队列 B.题目再现 C.解法 其实这题用数组或是链表都能解决&#xff0c;但是如果是用链表的话&#xff0c;那么队列为空的条件和队列满了的条件是一样的&#xff0…...

【Linux】浅谈shell命令以及运行原理

前言&#xff1a;上篇博文把linux下的基本指令讲解完了。本期我们聊聊Linux下【shell】命令及其运行原理。 目录 Shell的基本概念与作用 原理图展示 shell命令执行原理 Shell的基本概念与作用 Linux严格意义上说的是一个操作系统&#xff0c;我们称之为“核心&#xff08;ker…...

【shell脚本】nginx服务管理及存活检测脚本实战

前言 今天终于敢说自己是csdn万粉博主了&#xff0c;感谢大家的厚爱&#xff0c;我会继续输出更多优质的好文章&#xff0c;一起学习。 座右铭&#xff1a; 先努力让自己发光&#xff0c;再帮助更多的人。 &#x1f3e0; 个人主页&#xff1a;我是沐风晓月 &#x1f9d1; 个人…...

web服务器—nginx

一、nginx介绍Nginx(“engine x”)是一款是由俄罗斯的程序设计师Igor Sysoev所开发高性能的 Web和 反向代理服务器&#xff0c;也是一个 IMAP/POP3/SMTP 代理服务器。和apache一样&#xff0c;都是web服务器软件&#xff0c;因为其性能优异&#xff0c;所以被广大运维喜欢。又因…...

网络安全工具大合集

还是一句话&#xff0c;功夫再高&#xff0c;也怕菜刀首先&#xff0c;恭喜你发现了宝藏。本文章集成了全网优秀的开源攻防武器项目&#xff0c;包含&#xff1a;信息收集工具&#xff08;自动化利用工具、资产发现工具、目录扫描工具、子域名收集工具、指纹识别工具、端口扫描…...

什么是SHA256?比特币是如何应用SHA256算法的?

SHA 256算法是一种具有确定性的单向哈希函数 算法是执行操作的一系列步骤或过程 哈希函数是种数学函数&#xff0c;输入的长度任意&#xff0c;但是输出长度固定&#xff0c;可以理解为文件的数字指纹&#xff0c;同一个输入值&#xff0c;总是得相同的输出 SHA256&#xff0…...

JDK20正式发布了GA版本,短期维护支持,以及JDK21预览

最近&#xff0c;Oracle发布了JDK20&#xff0c;相比对于Java开发者来说&#xff0c;JDK的发版是比较收关注的事情了&#xff0c;小简也来和大家一起了解了解JDK20发生了什么变化呢&#xff1f; 首先&#xff0c;JDK20是一个短周期版本&#xff0c;有6个月的维护时间&#xff0…...

.NET/C#/GC与内存管理(含深度解析)

详情请看参考文章&#xff1a;.NET面试题解析(06)-GC与内存管理 - 不灬赖 - 博客园 (cnblogs.com)一、对象创建及生命周期一个对象的生命周期简单概括就是&#xff1a;创建>使用>释放&#xff0c;在.NET中一个对象的生命周期&#xff1a;new创建对象并分配内存对象初始化…...

Java开发 | 内部类 | 静态内部类 | 非静态内部类 | 匿名内部类

目录 1.内部类 1.1内部类的简单创建 1.2内部类的分类 1.2.1普通内部类 1.2.2静态内部类 1.3匿名内部类 1.4局部内部类 1.内部类 内部类就是一是一个类里面装着另外一个类&#xff0c;就像俄罗斯套娃一样。最外层的类我们叫外部类&#xff0c;内层的类我们叫内部类。 1…...

Portal认证

Portal认证Portal认证简介Portal认证协议Portal认证方式Portal认证流程Portal认证用户下线Portal认证简介 定义&#xff1a; Portal认证通常也称作Web认证&#xff0c;一般将Portal认证网站成为门户网站。用户上网时&#xff0c;必须在门户网站进行认证&#xff0c;如果没有认…...

论文解读:ChangeFormer | A TRANSFORMER-BASED SIAMESE NETWORK FOR CHANGE DETECTION

论文地址&#xff1a;https://arxiv.org/pdf/2201.01293.pdf 项目代码&#xff1a;https://github.com/wgcban/ChangeFormer 发表时间&#xff1a;2022 本文提出了一种基于transformer的siamese网络架构&#xff08;ChangeFormer&#xff09;&#xff0c;用于一对共配准遥感图…...

Redis 内存优化技巧

这次跟大家分享一些优化神技如何用更少的内存保存更多的数据&#xff1f;我们应该从 Redis 是如何保存数据的原理展开&#xff0c;分析键值对的存储结构和原理。从而继续延展出每种数据类型底层的数据结构&#xff0c;针对不同场景使用更恰当的数据结构和编码实现更少的内存占用…...

【java】笔试强训Day2【​倒置字符串​与排序子序列】

目录 ⛳选择题 1.A 派生出子类 B &#xff0c; B 派生出子类 C &#xff0c;并且在 java 源代码有如下声明&#xff1a; 2.下面代码将输出什么内容&#xff1a;&#xff08; &#xff09; 3.阅读如下代码。 请问&#xff0c;对语句行 test.hello(). 描述正确的有&…...

【Linux】基础IO(一) :文件描述符,文件流指针,重定向

&#x1f34e;作者&#xff1a;阿润菜菜 &#x1f4d6;专栏&#xff1a;Linux系统编程 码字不易&#xff0c;请多多支持&#x1f618;&#x1f618; 这是目录重新认识文件系统内部的文件操作我们C语言的文件操作系统内部的文件操作OS一般会如何让用户给自己传递标志位的&#x…...

【C语言】通讯录的实现(静态版)

【C语言】通讯录的实现(静态版一.前言1.前期准备a.菜单实现b.联系人结构体的构建c.菜单选项的功能d.#define 的定义2.功能的实现a.初始化通讯录b.增加联系人c.显示通讯录d.查找联系人e.修改联系人d.删除联系人3. 总代码test.ccontact.ccontact.h一.前言 本文将会用c语言实现一…...

IDEA一键构建Docker镜像

效果 Idea右击Dockerfile文件&#xff0c;直接在服务器构建docker镜像 开整 1、下载docker插件 2、编写Dockerfile文件 # 基础镜像 FROM openjdk:8-jdk-alpine # 工作目录 WORKDIR /opt/apps/gateway/logs/ # 文件拷贝,把target目录下的jar报拷贝到镜像的/APP/目录下 ADD…...

QT的使用3:鼠标事件

鼠标事件0 事件1 需求2 查看控件的事件处理函数3 UI设计4 新建一个类&#xff0c;继承QLabel5 对已有对象进行类型提升6 重写事件处理函数7 项目进一步拓展&#xff08;1&#xff09;获取鼠标按键&#xff08;2&#xff09;鼠标移动&#xff08;3&#xff09;显示多个按键&…...

线程安全之单例模式

文章目录前言一.什么是单例模式二.在java中的单例模式2.1 饿汉式的介绍2.2 懒汉式的介绍三 懒汉式的单例模式,线程不安全的解决方式3.1 造成线程不安全的原因3.2 解决方案3.3 总结前言 这篇文章,我们会介绍一下单例模式,但这里的单例模式,不是我们所说的设计模式,当然听到设计…...

“二分”带来“十分”快感——二分思想的奥秘解析

文章目录无处不在的二分思想二分查找惊人的查找速度二分查找的递归与非递归实现1.循环退出条件2.mid的取值3.low和high的更新最后说一句&#x1f431;‍&#x1f409;作者简介&#xff1a;大家好&#xff0c;我是黑洞晓威&#xff0c;一名大二学生&#xff0c;希望和大家一起进…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...

ui框架-文件列表展示

ui框架-文件列表展示 介绍 UI框架的文件列表展示组件&#xff0c;可以展示文件夹&#xff0c;支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项&#xff0c;适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...

内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献

Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译&#xff1a; ### 胃肠道癌症的发病率呈上升趋势&#xff0c;且有年轻化倾向&#xff08;Bray等人&#xff0c;2018&#x…...