【数据结构】回溯算法公式化解题 leetcode经典题目带刷:全排列、组合、子集
目录
- 回溯算法
- 一、什么是回溯算法
- 1、基本思想:
- 2、一般步骤:
- 二、题目带练
- 1、全排列
- 2、组合
- 3、子集
- 三、公式总结
回溯算法
一、什么是回溯算法
回溯算法(Backtracking Algorithm)是一种解决组合问题、排列问题、选择问题等一类问题的常用算法。它通过尝试所有可能的选择来找到问题的解,当发现当前选择不符合要求时,就回溯到之前的状态,然后尝试其他的选择。
1、基本思想:
- 从问题的起始点开始,进行尝试,每次选择一个可能的路径。
- 如果发现当前选择无法达到解决问题的目标,就回退到上一个状态,尝试其他的选择。
- 不断地重复上述过程,直到找到解决问题的路径,或者遍历完所有可能的选择。
2、一般步骤:
- 确定问题的解空间和约束条件。
- 从解空间中选择一个可能的选择,进入下一步。
- 判断当前选择是否符合约束条件,如果符合,继续深入尝试下一步;如果不符合,回退到上一步。
- 重复上述步骤,直到找到解,或者遍历完所有可能的选择。
二、题目带练
1、全排列
题目地址
分析:
看到这道题的描述,不难想到,如果我们要找出所有的排列方式,就要遍历n次数组,每次选择一个不重复元素排列在上次循环选择的元素后面,那这就出现了一个问题:怎么对一个数组遍历n次?
显然这是不太可能实现的,因为n是不确定的,但是我们可以换一种思路,通过深度来代表遍历次数,也就是我们常说的回溯算法。
根据题意,我们应当设递归出口为 当前递归的深度 == 数组的长度if(depth == nums.length)
,同时保存当前的排列方式到集合中。ans.add(new ArrayList<>(path));
每次递归的过程中我们需要遍历一次数组for(int i = 0; i < nums.length; i++)
,判断当前的元素是否被使用过if(used[i])
,如果没被使用那么就将其记录下来,并且标记为使用过,继续进入递归path.add(nums[i]); used[i] = true;。
当这次递归结束时dfs(nums,depth + 1,used);,
撤销当前元素的使用标记,并且移除记录的集合。path.remove(path.size() - 1); used[i] = false;
效果就是调用方法后,先选择元素1path.add(nums[0]); used[0] = true;
,再次调用方法记录深度+1dfs(nums,depth + 1,used);
,此时发现1已经被选择过了,开始选择2path.add(nums[1]); used[1] = true;
,调用递归,深度+1dfs(nums,depth + 1,used);
,同理1,2被标记为使用过的元素,继续选择3path.add(nums[2]); used[2] = true;
,然后递归结束。这里会退回到深度为2的那次选择,因为2之后还有别的元素可以选择,选择3后发现只有2可以选了,首选项为1的递归结束,依次类推得到所有排列方式。
代码如下:
class Solution {public List<List<Integer>> ans = new ArrayList<>();public List<Integer> path = new ArrayList<>();public List<List<Integer>> permute(int[] nums) {boolean[] used = new boolean[nums.length];dfs(nums,0,used);return ans;}public void dfs(int[] nums,int depth,boolean[] used){if(depth == nums.length){ans.add(new ArrayList<>(path));return;}for(int i = 0; i < nums.length; i++){if(used[i]){continue;}path.add(nums[i]);used[i] = true;dfs(nums,depth + 1,used);path.remove(path.size() - 1);used[i] = false;}}
}
2、组合
题目地址
分析:
这道题与全排列的区别在于,全排列需要全部选择,而这道题不一定要全部选择,并且每个组合只能有一次,所以面对这道题,我们不能按照和之前同样的思路去解,因为无法排除同样组合的组合顺序问题。
那么我们要如何作出改动呢?
其实很简单,我们只需要让每次循环的起始值变为当前的深度即可,同时也不需要判断是否使用过了,因为我们只会向后找,不会从前开始往后找了。
class Solution {List<Integer> temp = new ArrayList<Integer>();List<List<Integer>> ans = new ArrayList<List<Integer>>();public List<List<Integer>> combine(int n, int k) {dfs(1, n, k);return ans;}public void dfs(int depth, int n, int k) {if (temp.size() == k) {ans.add(new ArrayList<Integer>(temp));return;}for(int i = depth;i <= n;i++){temp.add(i);dfs(i + 1, n, k);temp.remove(temp.size() - 1);}}
}
3、子集
题目地址
分析:
大家看这道题可能会发现,是不是和组合有点相似?区别在哪呢,区别在于子集的选择长度不一定是n,而是[0,n]。
其实我们只需要每次回溯都记录一次结果就好了。
class Solution {List<Integer> list = new ArrayList<>();List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {dfs(0,nums);return result;}public void dfs(int current, int[] nums){result.add(new ArrayList<>(list));if(current == nums.length){return;}for(int i = current; i < nums.length; i++){list.add(nums[i]);dfs(i + 1, nums);list.remove(list.size() - 1);}}
}
三、公式总结
如果认真看完的朋友可以发现,对于这种基础的回溯题目,我们都可以通过循环+回溯来解决问题,只需要根据具体问题来更改我们的循环条件即可。
当然这么做不一定是最好的,还有许多可以优化的地方,只是说大部分情况可以通过这种循环的方式来解决问题。
相关文章:
【数据结构】回溯算法公式化解题 leetcode经典题目带刷:全排列、组合、子集
目录 回溯算法一、什么是回溯算法1、基本思想:2、一般步骤: 二、题目带练1、全排列2、组合3、子集 三、公式总结 回溯算法 一、什么是回溯算法 回溯算法(Backtracking Algorithm)是一种解决组合问题、排列问题、选择问题等一类问…...
WPF基础入门-Class3-WPF数据模板
WPF基础入门 Class3:WPF数据模板 1、先在cs文件中定义一些数据 public partial class Class_4 : Window{public Class_4(){InitializeComponent();List<Color> test new List<Color>();test.Add(new Color() { Code "Yellow", Name &qu…...
js将搜索的关键字加颜色
js将搜索的关键字加颜色 使用正则匹配关键字并加入span标签,页面渲染时使用v-html渲染即可 // 文本框内容 let searchCont 测试;const reg new RegExp((${searchCont.value}), g); let data 图片保存测试A; data data.replace(reg, <span style"color:…...
Docker安装Oracle数据库打开、链接速度很慢
问题: 使用Docker安装Oracle数据库打开、链接速度很慢,明显的在在转圈严重影响效率。 解决: 排查到DNS时,发现宿主机DNS配置清空后,通过JDBC连接目标Oracle数据库速度很快 进入容器中进行测试,发现清空DNS…...
学生分班查询系统的创建与使用指南
开学季,负责分班工作的老师们又面临一个难题:如何公布分班结果?将结果放在学校官网上可能会让很多无关人员看到,而不放则会导致家长们纷纷打电话来询问。那么,有没有一种方法可以让家长们自行查看分班结果呢࿱…...
全套解决方案:基于pytorch、transformers的中文NLP训练框架,支持大模型训练和文本生成,快速上手,海量训练数据!
全套解决方案:基于pytorch、transformers的中文NLP训练框架,支持大模型训练和文本生成,快速上手,海量训练数据! 1.简介 目标:基于pytorch、transformers做中文领域的nlp开箱即用的训练框架,提…...
ffmpeg
文章目录 libavcodec实现 libavformat实现libavfilter实现 libswscale实现对比libavfilter图像处理libswscale vs libyuvlibavutil 命令行工具ffmpeg例子 ffprobe例子 FFmpeg 是一个由 C 语言编写的开源跨平台音视频处理工具集,它具有模块化的架构。下面是 FFmpeg 的…...
CH03_代码的坏味道(下)
循环语句(Loops) 从最早的编程语言开始,循环就一直是程序设计的核心要素。如今,函数作为一等公民已经得到了广泛的支持,因此我们可以使用以管道取代循环(231)管道操作(如filter和ma…...
journal日志导致服务器磁盘满
背景 ubuntu 18.04服务器磁盘突然100% 一查/var/log/journal目录占了14G 清理 要清理 journal 日志,可以使用以下步骤: 运行以下命令来查看 journal 日志的使用情况: journalctl --disk-usage这将显示 journal 日志的当前使用情况&#x…...
“Go程序员面试笔试宝典”复习便签
一.逃逸分析 1.1逃逸分析是什么? 逃逸分析,主要是Go编译器用来决定变量分配在堆或者栈的手段。 区分于C/C手动管理内存分配,Go将这些工作交给了编译器。 1.2逃逸分析有什么作用 解放程序员。程序员不需要手动指定指针分配内存。 灵活的…...
数组的度(指数组里任一元素出现频数的最大值)
题目: 给定一个非空且只包含非负数的整数数组 nums,数组的 度 的定义是指数组里任一元素出现频数的最大值。 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组,返回其长度。 示例 1: 输入:nums …...
scala array类型参数
在Scala中,数组(Array)是一种用于存储相同类型元素的数据结构。数组可以用于保存基本数据类型和自定义数据类型的元素。当定义数组类型参数时,您通常是在函数、类或方法签名中使用它们。以下是一些有关Scala数组类型参数的示例&am…...
构建 NodeJS 影院预订微服务并使用 docker 部署(03/4)
一、说明 构建一个微服务的电影网站,需要Docker、NodeJS、MongoDB,这样的案例您见过吗?如果对此有兴趣,您就继续往下看吧。 你好社区,这是🏰“构建 NodeJS 影院微服务”系列的第三篇文章。本系列文章演示了…...
html写一个向flask_socketio发送消息和接收消息并显示在页面上
以下是一个简单的HTML页面,它包含一个输入框、一个发送按钮和一个显示区域。用户可以在输入框中输入消息,点击发送按钮,然后这个消息会被发送到 Flask-SocketIO 服务器。当服务器回应消息时,它会在页面的显示区域显示出来。 <…...
C#使用.Net Core进行跨平台开发
使用 .NET Core 进行跨平台开发是一种灵活的方法,可以在多个操作系统上运行 C# 应用程序。以下是在 C# 中使用 .NET Core 进行跨平台开发的一般步骤: 安装 .NET Core SDK: 在开始之前,需要安装适用于操作系统的 .NET Core SDK。可…...
Java“牵手”天猫店铺所有商品API接口数据,通过店铺ID获取整店商品详情数据,天猫API申请指南
天猫商城是一个网上购物平台,售卖各类商品,包括服装、鞋类、家居用品、美妆产品、电子产品等。天猫商品详情可以帮助消费者更好的了解宝贝信息,从而做出购买决策。同时,消费者也可以通过商品详情了解其他买家对宝贝的评价…...
php输入post过滤函数,入库出库,显示
第一部分 php输入post过滤函数 function GLOBAL_POST($str) {$str_origin$str; if (empty($str)) return false;$str str_replace( /, "", $str);//替换关键词 $str str_replace("\\", "", $str); $str str_replace(">", &…...
matlab-对数据集加噪声并实现tsne可视化
matlab-对数据集加噪声并实现tsne可视化 最近才知道,原来可以不用模型,也能实现对数据集数据的可视化。 **一、**以COIL-100数据集为例子。 问题: 前提:首先对COIL-100数据集根据角度0-175和180-255,分别划分成C1,C…...
【BASH】回顾与知识点梳理(三十八)
【BASH】回顾与知识点梳理 三十八 三十八. 源码概念及简单编译38.1 开放源码的软件安装与升级简介什么是开放源码、编译程序与可执行文件什么是函式库什么是 make 与 configure什么是 Tarball 的软件如何安装与升级软件 38.2 使用传统程序语言进行编译的简单范例单一程序&#…...
Sql注入攻击的三种方式
SQL注入是指web应用程序对用户输入数据的合法性没有判断或过滤不严,攻击者可以在web应用程序中事先定义好的查询语句的结尾上添加额外的SQL语句,在管理员不知情的情况下实现非法操作,以此来实现欺骗数据库服务器执行非授权的任意查询,从而进一步得到相应的数据信息。SQL 注…...
dockerfile部署前端vue打包的dist文件实战
背景:一般前端开发后会将打包后的dist文件交由我们部署,部署的方式有很多,这里提供一种思路 在服务器的路径下新建一个目录,在目录中新建Dockerfile,编辑这个文件 FROM nginxCOPY ./dist /home/front COPY nginx.con…...
[技术杂谈]MobaXterm中文乱码编码问题一种解决方法
今日使用mobaxterm连接树莓派发现安装出现乱码,看不清文字是什么。最最简单方式是ssh设置终端字体,具体步骤为: 1. 右键会话,点击编辑会话 2.在以下画面点击终端字体设置 3.选择编码:GBK或者ISO-8859-1...
mac os M1 安装并启动 postgreSQL 的问题
Homebrew 安装 postgreSQL brew install postgresql启动 brew services start postgresql但报错: uninitialized constant Homebrew::Service::System解决方案 brew doctor按照 brew doctor 中的建议进行操作,如果不行,如下: h…...
如何使用Wireshark进行网络流量分析?
如何使用Wireshark进行网络流量分析。Wireshark是一款强大的网络协议分析工具,可以帮助我们深入了解网络通信和数据流动。 1. 什么是Wireshark? Wireshark是一个开源的网络协议分析工具,它可以捕获并分析网络数据包,帮助用户深入…...
抖音web主页视频爬虫
需要抖音主页视频爬虫源码的发私信,小偿即可获得长期有效的采集程序。 比构造 s_v_web_id 验证滑块的方法更快,更稳定。...
常用的jar包【maven坐标格式】
文章目录 🐒个人主页🏅JavaEE系列专栏📖前言:🏨mysql加载启动项jar包🦓mybatis加载启动项jar包 🐒个人主页 🏅JavaEE系列专栏 📖前言: 本篇博客主要以介绍常…...
【分布式】VMware FT概要
讨论了1primary 1backup的情况,比较好理解, 6.824中以该论文为例,介绍了分布式系统中复制的概念,复制的方式。以下简要讲述一些关键点,来源于MIT6.824课程,翻译版本 https://mit-public-courses-cn-transl…...
江西南昌电气机械三维测量仪机械零件3d扫描-CASAIM中科广电
精密机械零部件是指机械设备中起到特定功能的零件,其制造精度要求非常高。这些零部件通常由金属、塑料或陶瓷等材料制成,常见的精密机械零部件包括齿轮、轴承、螺丝、活塞、阀门等。精密机械零部件的制造需要高精度的加工设备和工艺,以确保其…...
MySQL三大日志(binlog、redo log和undo log)详解
1.redo log redo log是InnoDB存储引擎层的日志,又称重做日志文件。 用于记录事务操作的变化,记录的是数据修改之后的值,不管事务是否提交都会记录下来 redo log包括两部分:一个是内存中的日志缓冲(redo log buffer),另…...
七大排序算法详解
1.概念 1.排序的稳定性 常见的稳定的排序有三种:直接插入排序,冒泡排序,归并排序 对于一组数据元素排列,使用某种排序算法对它进行排序,若相同数据之间的前后位置排序后和未排序之前是相同的,我们就成这种…...
[docker][WARNING]: Empty continuation line found in:
报警内容: 下面展示一些 内联代码片。 //执行 sudo docker build ubuntu:v1.00 . [WARNING]: Empty continuation line found in:出现上述错误原因为18行多了一个 " \" 符号,去除即可...
探工业互联网的下一站!腾讯云助力智造升级
引言 数字化浪潮正深刻影响着传统工业形态。作为第四次工业革命的重要基石,工业互联网凭借其独特的价值快速崛起,引领和推动着产业变革方向。面对数字化时代给产业带来的机遇与挑战,如何推动工业互联网的规模化落地,加速数字经济…...
SpringBoot上传文件的实现与优化
一、什么是文件上传? 文件上传是指客户端将本地的文件通过HTTP协议发送到服务器端的过程。文件上传是Web开发中常见的功能之一,例如用户可以上传头像、照片、视频、文档等各种类型的文件。文件上传涉及到客户端和服务器端的交互,需要考虑文件…...
学习python可以做什么?有前景么
Python被热门领域广泛应用 学习者就业优势明显! 说到Python的优势,就不得不提这句玩笑话:Python除了不会生孩子,其他的都会。 Web开发、网络爬虫、数据分析、人工智能、自动化、云计算、网络编程、游戏开发等领域,统…...
还不知道怎么提示LLM?ChatGPT提示入门
文章目录 简介:什么是人工智能?什么是提示过程?为什么会出现这样的差异? 为什么需要提示过程?1) 文章摘要2) 数学问题求解 如何进行提示过程?角色提示:多范例提示:无范例提示单范例提…...
反射机制-体会反射的动态性案例(尚硅谷Java学习笔记)
// 举例01 public class Reflect{ // 静态性 public Person getInstance(){return new Person(); }// 动态性 public T<T> getInstance(String className) throws Exception{Calss clzz Class.forName(className);Constructor con class.getDeclaredConstructor();con…...
uniapp离线打包apk - Android Studio
uniapp 离线打包 基于uni-app的andiord 离线打包 开发工具及所需要的jar包1.将下载的App离线SDK解压打开,找到HBuilder-Integrate-AS ,在Android Studio打开2.打开HBuilder X,发行->原生app本地打包->生成本地打包app资源3.在“HBuil…...
cuda面试准备(一),架构调试
1 cuda架构 硬件方面 SP (streaming Process) ,SM (streaming multiprocessor) 是硬件(GPUhardware) 概念。而thread,block,grid,warp是软件上的(CUDA) 概念 SP:最基本的处理单元,streaming processor,也称为CUDA core,最后具体的指令和任务都是在SP上处理的。GPU进行并行…...
docker containers logs清理
容器的磁盘占用 每次创建一个容器时,都会有一些文件和目录被创建,例如: /var/lib/docker/containers/ID目录,如果容器使用了默认的日志模式,他的所有日志都会以JSON形式保存到此目录下。 /var/lib/docker/overlay2 目…...
Ubuntu安装RabbitMQ
一、安装 更新系统软件包列表: sudo apt update安装RabbitMQ的依赖组件和GPG密钥: sudo apt install -y curl gnupg curl -fsSL https://github.com/rabbitmq/signing-keys/releases/download/2.0/rabbitmq-release-signing-key.asc | sudo gpg --dearmo…...
Vue3获取当前环境信息
获取.env.development和.env.production内的信息及环境信息 在业务逻辑文件中可以通过 import.meta.env的方式获取,例如: const { MODE, VITE_APP_BASE_API} import.meta.env在vite.config.js中获取: import { defineConfig, loadEnv } f…...
Linux 系统 diff 文件比较命令详解
diff 命令用于比较两个文件或目录之间的差异。它会逐行比较文件的内容,并且在不同的行上显示不同之处。下面是 diff 命令的使用方法和选项: 基本语法: diff [选项] 文件1 文件2常见选项: -c 或 --context:显示上下文…...
【负载均衡】Nacos简单入门
Nacos简单入门 快速安装 在Nacos的GitHub页面,提供有下载链接,可以下载编译好的Nacos服务端或者源代码: 下载完压缩包之后,放在任意目录下面进行解压: GitHub主页:https://github.com/alibaba/nacos G…...
实验一 ubuntu 网络环境配置
ubuntu 网络环境配置 【实验目的】 掌握 ubuntu 下网络配置的基本方法,能够通过有线网络连通 ubuntu 和开发板 【实验环境】 ubuntu 14.04 发行版FS4412 实验平台 【注意事项】 实验步骤中以“$”开头的命令表示在 ubuntu 环境下执行,以“#”开头的…...
ubuntu can应用开发环境搭建指南
sudo apt-get update sudo apt-get install can-utils libsocketcan-dev can数据发送这个采用来自网上的一段代码进行测试: can_send.c代码内容如下: /* 1. 报文发送程序 */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <…...
全流程R语言Meta分析核心技术高阶应用
查看原文>>>全流程R语言Meta分析核心技术高阶应用 目录 专题一、Meta分析的选题与检索 专题二、Meta分析与R语言数据清洗及统计方法 专题三、R语言Meta分析与作图 专题四、R语言Meta回归分析 专题五、R语言Meta诊断分析 专题六、R语言Meta分析的不确定性 专题…...
windows下安装使用git-lfs克隆大文件
下载安装git-lfs工具 首先去git-lfs这里,下载相应平台的工具,我下载的windows版本,非安装版本,直接配置到系统环境变量里 执行以下命令验证是否成功 git lfs install 克隆数据集 这样自动会下载里边的大文件 git clone https:/…...
Node.js下载安装及环境配置教程
一、进入官网地址下载安装包 https://nodejs.org/zh-cn/download/ 选择对应你系统的Node.js版本,这里我选择的是Windows系统、64位 Tips:如果想下载指定版本,点击【以往的版本】,即可选择自己想要的版本下载 二、安装程序 &a…...
半导体低压热氧工艺中的真空度精密控制解决方案
摘要:在目前的各种半导体材料热氧化工艺中,往往需要对正负压力进行准确控制并对温度变化做出快速的响应,为此本文提出了热氧化工艺的正负压力控制解决方案。解决方案的核心是基于动态平衡法分别对进气和排气流量进行快速调节,具体…...
TCP的可靠性之道:确认重传和流量控制
TCP 全称为 Transmission Control Protocol(传输控制协议),是一种面向连接的、可靠的、基于字节流的传输层通信协议,其中可靠性是相对于其他传输协议的优势点。TCP 为了确保数据传输的可靠性主要做了以下几点: 发送确…...