当前位置: 首页 > 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;希望和大家一起进…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...