代码随想录——回溯

系列文章目录

代码随想录——回溯


文章目录

  • 系列文章目录
    • 概述
    • 组合
      • 组合
      • 组合III
      • 电话号码的字母组合
      • 组合总和
      • 组合总和II
    • 分割
      • 分割回文串
      • ** 复原ip地址
    • 子集
      • 子集
      • 子集II


概述

回溯的本质就是递归遍历,但在完成某一条路之后会撤回到上一层,然后重新选择另一条路继续遍历,是一个比较低效的算法,能进行提升的方式就是剪枝。

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

在这里插入图片描述

组合

组合

链接:https://leetcode.cn/problems/combinations/description/

vector<vector < int > > 作为最终返回的结果,vector < int >作为每一小项,中止条件是vector< int > == k,注意在递归过程中n,k是不变的,所以必须引入一个递增index来去重。

剪枝方法:

  1. 已经选择的元素个数:path.size();
  2. 还需要的元素个数为: k - path.size();
  3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1,开始遍历

组合III

链接:https://leetcode.cn/problems/combination-sum-iii/description/

与前一个组合几乎一样,但中止条件需要加一个total == k的判断。

电话号码的字母组合

链接:https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/

中止条件是单个项的size等于digits的size,一开始我以为要双循环,即digits遍历和单个数字对应的字母遍历,但其实不需要,因为digits一定是顺序往后取的,所以只需要定义一个index,每层递归+1即可。
ps:在leetcode由char转变为int的方法是减去 ‘0’

num[digits[index] - '0'

组合总和

链接:https://leetcode.cn/problems/combination-sum/description/
中止条件为当总和相等时push进result并return,总和超过target时直接人return;注意这道题也是不能重复的,一般不能重复的都需要加入index来保证起始位置。

组合总和II

链接:https://leetcode.cn/problems/combination-sum-ii/description/
这道题不重复的核心点在于,同层的数不能够重选,例如[1,1,2,2,5],第一层选了1,第二层还是可以继续选1,因为两者不是同层的。但如果第一层的第一个1用完了,又选了第二个1,这就重复了,所以只需要加一个判断条件:

            if (i > index && candidates[i] == candidates[i - 1]) {continue;}

这里的核心点在于ℹi > index,因为index是本层的第一个数,必然不可能重复,所以要从index下一个开始判断,此时如果第二个数和第一个数是相同的,则属于同层重复选择,直接continue;

分割

分割回文串

https://leetcode.cn/problems/palindrome-partitioning/description/
每切下来一个子字符串,就相当于是在一层做了选择,这样就可以套上回溯算法的模板。中止条件是起始切割位置到了字符串的最后一位,额外再写一个回文判断函数。、
注意:leetcode里常用的切割字符串函数substr,第一个参数是起始位置,第二个参数是要切割的长度。

string str = s.substr(index,i - index + 1);

** 复原ip地址

https://leetcode.cn/problems/restore-ip-addresses/description/
这道题一直做错,能接受的方法是,将切割每一个子字符串进行判断,符合标准后放入vector备用,个数达到4个并且index也等于s.size()之后,再拼接放入最终的result里。
注意:string转为int直接用stoi函数

return stoi(s) <= 255;

字符串的增加和删改不能用-=和+=,要用insert和erase。

子集

子集

https://leetcode.cn/problems/subsets/description/
这道题唯一要注意的点是子集的大小是不固定的,所以不能在中止条件里面将子集添加到结果里,每一次循环都要添加,所以放在递归的开头。中止条件是index == s.size()。

子集II

https://leetcode.cn/problems/subsets-ii/description/
这题和之前组合的去重思路一模一样,在子集的基础上,首先对nums进行sort保证是递增的,然后进行判断去掉本层重复的选择。

if(i > index && nums[i] == nums[i - 1]) continue;

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/238007.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

章鱼网络 2023 年全回顾|暨12月进展报告

2023年&#xff0c;章鱼网络轻装上阵&#xff0c;身处加密行业的低谷中砥砺前行。 12月17日&#xff0c;经过整整1年时间的开发和打磨&#xff0c;章鱼网络在重磅上线 Octopus 2.0&#xff0c;即 $NEAR Restaking 和 NEAR-IBC&#xff0c;获得了社区和市场的一致认可&#xff…

Elasticsearch 快速入门指南【总结记录】

本文将介绍一些基本概念&#xff0c;帮助您快速入门使用Elasticsearch。 一、概述 ES用来解决什么问题&#xff1f;Elasticsearch是解决海量数据&#xff08;已经存在的数据&#xff09;全文检索的不二只选。 Elasticsearch是一个基于Java语言开发&#xff0c;建立在开源搜索…

java SSM物业管理系统myeclipse开发mysql数据库springMVC模式java编程计算机网页设计

一、源码特点 java SSM物业管理系统是一套完善的web设计系统&#xff08;系统采用SSM框架进行设计开发&#xff0c;springspringMVCmybatis&#xff09;&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和 数据库&#xff0c;系统主要采用B/…

PCL 大地坐标转空间直角坐标(C++详细过程版)

目录 一、算法原理二、代码实现三、结果展示四、测试数据本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫与GPT生成的文章。 一、算法原理 二、代码实现 头文件及读取保存函数见:PCL 空间直角坐标转大地坐标(直接求解法C…

基于传统机器学习模型算法的项目开发详细过程

1 场景分析 1.1 项目背景 描述开发项目模型的一系列情境和因素&#xff0c;包括问题、需求、机会、市场环境、竞争情况等 1.2. 解决问题 传统机器学习在解决实际问题中主要分为两类&#xff1a; 有监督学习&#xff1a;已知输入、输出之间的关系而进行的学习&#xff0c;从而…

大数据StarRocks(六) :Catalog

StarRocks 自 2.3 版本起支持 Catalog&#xff08;数据目录&#xff09;功能&#xff0c;实现在一套系统内同时维护内、外部数据&#xff0c;方便您轻松访问并查询存储在各类外部源的数据。 1. 基本概念 内部数据&#xff1a;指保存在 StarRocks 中的数据。 外部数据&#xf…

【Python】使用pyinstaller打包为Windows平台的xxx.exe方法步骤

pyinstaller 是一个用于将 Python 代码打包成独立可执行文件的工具&#xff0c;它可以将 Python 代码打包成 Windows、Linux、Mac 等平台的可执行文件&#xff0c;方便用户在不同环境中运行。 pyinstaller用法&#xff1a; 1.安装pyinstaller库&#xff0c;这里以PyCharm环境为…

在CentOS中,对静态HTTP服务的性能监控

在CentOS中&#xff0c;对静态HTTP服务的性能监控和日志管理是确保系统稳定运行和及时发现潜在问题的关键。以下是对这一主题的详细探讨。 性能监控 使用工具监控&#xff1a;top、htop、vmstat、iostat等工具可以用来监控CPU、内存、磁盘I/O等关键性能指标。这些工具可以实时…

vscode打开c_cpp_properties.json文件的一种方式

步骤一 点击win32 步骤二 点击json 自动生成了

一、MOJO环境部署和安装

以Ubuntu系统为例。 安装mojo-CLI curl https://get.modular.com | MODULAR_AUTHmut_fe303dc5ca504bc4867a1db20d897fd8 sh - 安装mojo SDK modular auth mojo modular auth install mojo 查看mojo版本号 mojo --version 输入mojo指令&#xff0c;进入交互编程窗口

单例模式---JAVA

目录 “饿汉”模式 完整代码 “懒汉”模式 完整代码 单例模式&#xff1a;保证某个类在程序中只存在唯一一份实例, 而不会创建出多个实例。 单例模式可以通过实例创建的时间来分为两种&#xff1a;“饿汉”和“懒汉”模式。 “饿汉”模式 所谓的“饿汉”模式实则就是在类…

【JAVA】在 Queue 中 poll()和 remove()有什么区别

&#x1f34e;个人博客&#xff1a;个人主页 &#x1f3c6;个人专栏&#xff1a;JAVA ⛳️ 功不唐捐&#xff0c;玉汝于成 目录 前言 正文 poll() 方法&#xff1a; remove() 方法&#xff1a; 区别总结&#xff1a; 结语 我的其他博客 前言 在Java的Queue接口中&…

【期末考试】数据库综合复习宝典

目录 第一章 数据库系统概述 第二章 关系代数 第四章 关系数据库理论 第五章 数据库设计 第六章 数据库管理系统 第八章 事务管理 第一章 数据库系统概述 1.1三级模式 ①外模式&#xff1a;它为特定的应用程序或用户群体提供了一个数据视图&#xff0c;这个视图是独立于…

VS code的使用介绍

VS code的使用介绍 简介下载和安装常用的插件使用教程快捷键 集成Git未找到 Git。请安装 Git&#xff0c;或在 "git.path" 设置中配置。操作步骤打开文件夹初始化仓库文件版本控制状态提交文件到git打开git操作栏位 好用的插件ChineseDraw.io Integration实体关系 Gi…

webpack的性能优化(二)——减少打包体积

优化webpack性能时&#xff0c;主要集中在两个方面&#xff1a;优化构建后的结果和优化构建时的速度。前一篇文章已经介绍了如何通过webpack的分包来优化构建后的结果。而在本篇文章中&#xff0c;我们将从减少打包体积的角度来探讨。 1.通过CDN链接引入第三方库 CDN是指通过相…

Linux------进程的初步了解

目录 一、什么是进程 二、进程的标识符pid 三、getpid 得到进程的PID 四、kill 终止进程 五、父进程与子进程 六、目录中的进程 一、什么是进程 在windows中&#xff0c;我们查看进程很简单&#xff0c;打开任务管理器&#xff0c;就可以看到在运行的进程。这里我们还可以…

【用法总结】无障碍AccessibilityService

一、背景 本文仅用于做学习总结&#xff0c;转换成自己的理解&#xff0c;方便需要时快速查阅&#xff0c;深入研究可以去官网了解更多&#xff1a;官网链接点这里 之前对接AI语音功能时&#xff0c;发现有些按钮&#xff08;或文本&#xff09;在我没有主动注册唤醒词场景…

原生js实现拖拽效果

<!DOCTYPE html> <html> <head> <style> #mydiv { width: 200px; height: 200px; background-color: red; position: absolute; cursor: move; } </style> | </head> <body> <div id"mydiv">拖拽我…

PostgreSQL认证考试PGCA、PGCE、PGCM

PostgreSQL认证考试PGCA、PGCE、PGCM 【重点&#xff01;重点&#xff01;重点&#xff01;】PGCA、PGCE、PGCM 直通车快速下正&#xff0c;省心省力&#xff0c;每2个月一次考试 PGCE考试通知 &#xff08;2024&#xff09; 一、考试概览 &#xff08;一&#xff09; 报名要…

k8s存储卷之动态

动态pv需要两个组件 1、卷插件&#xff0c;k8s本身支持的动态pv创建不包含NFS&#xff0c;需要声明和安装一个外部插件 Provisioner 存储分配器&#xff0c;动态创建pv&#xff0c;然后根据pvc的请求自动绑定和使用 2、StorageClass&#xff0c;用来定义pv的属性&#xff0c…