力扣-回溯法

何为回溯法?

在搜索到某一节点的时候,如果我们发现目前的节点(及其子节点)并不是需求目标时,我们回退到原来的节点继续搜索,并且把在目前节点修改的状态还原。
记住两个小诀窍,一是按引用传状态(&),二是所有的状态修改在递归完成后回改。
回溯法修改一般有两种情况,一种是修改最后一位输出,比如排列组合;一种是修改访问标
记,比如矩阵里搜字符串。

46.全排列

46. 全排列
题目

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2:

输入:nums = [0,1]
输出:[[0,1],[1,0]]

示例 3:

输入:nums = [1]
输出:[[1]]

提示:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同​​​​​​​
题解
输出该数组的所有排序组合,我们可以使用回溯法。
首先确定一个位置,然后跟后面的每个位置进行交换。换完之后到下一个位置。然后这一系列步骤结束后,需要将换了的换回来。即回溯法。
class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> ans;back(nums,0,ans);return ans;}void back(vector<int>& nums,int n,vector<vector<int>>& ans){int i;if(n==nums.size()-1)ans.push_back(nums);for(i=n;i<nums.size();i++){swap(nums[i],nums[n]);back(nums,n+1,ans);swap(nums[i],nums[n]);}}
};

77.组合

77. 组合

题目

给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1:

输入:n = 4, k = 2
输出:
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

示例 2:

输入:n = 1, k = 1
输出:[[1]]

提示:

  • 1 <= n <= 20
  • 1 <= k <= n

题解

设定一个count,计算每一个的数量,当count==k时候,就放入数组。这是跟之前不太一样的,之前的是进行排列组合。这个有点像选择排列。

从1-n开始,设置一个额外的数组来存储每一次的结果。count动态变化,将i赋给后count加一,dfs中从(i+1,n)选一个数字。回溯后count--。

class Solution {
public:vector<vector<int>> combine(int n, int k) {vector<vector<int>> ans;vector<int> c(k,0);int count;dfs(n,k,1,ans,c,count);return ans;}void dfs(int n,int k,int level,vector<vector<int>>& ans,vector<int>& c,int& count){int i;if(count==k){ans.push_back(c);return ;}for(i=level;i<=n;i++){c[count++]=i;dfs(n,k,i+1,ans,c,count);--count;}}
};

79.单位搜索

79. 单词搜索

题目

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1:

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true

示例 2:

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出:true

示例 3:

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出:false

提示:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和 word 仅由大小写英文字母组成

题解

类似的套路。

dfs+回溯法,首先定义一个visit,来标记每一次搜索的时候该位置是否被标记过,防止同一个位置被多次访问。

对于一个位置,要进行边界判断,是否越界。接着判断是否已经访问过,是否已经成功找到,是否该位置的字母与目标字母不同。

dfs,往四周搜索。

class Solution {
public:bool exist(vector<vector<char>>& board, string word) {if(board.empty())return false;int m=board.size(),n=board[0].size();vector<vector<bool>> visit(m,vector<bool>(n,false));int i,j;bool find=false;for(i=0;i<m;i++){for(j=0;j<n;j++)back(i,j,board,word,find,visit,0);}return find;}void back(int i,int j,vector<vector<char>>& board,string& word,bool& find,vector<vector<bool>>& visit,int level){if(i<0||i>=board.size()||j<0||j>=board[0].size())return ;if(visit[i][j]||find||board[i][j]!=word[level])return ;if(level==word.size()-1){find=true;return ;}visit[i][j]=true;back(i+1,j,board,word,find,visit,level+1);back(i-1,j,board,word,find,visit,level+1);back(i,j+1,board,word,find,visit,level+1);back(i,j-1,board,word,find,visit,level+1);visit[i][j]=false;}
};

51.N皇后

51. N 皇后

题目

按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1:

输入:n = 4
输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释:如上图所示,4 皇后问题存在两个不同的解法。

示例 2:

输入:n = 1
输出:[["Q"]]

提示:

  • 1 <= n <= 9

题意

N皇后,需要三个标记函数,一个是列,一个是主对角线,另外一个是副对角线。

因为每一行肯定会放一个皇后,一行一行遍历,当成功遍历到最后一行并且成功放好皇后即可。所以不需要设行的标记函数。

这个时候我们可以从第一行开始,按列遍历。判断该列是否为false,该主对角线是否为false,副对角线是否为false。如果是则下一列,如果不是就将该位置置为Q,然后对下一行进行同样的寻找。回溯法,找完后记得将位置和标记函数还原。

这个对角线和副对角线。可以画在坐标上,一个为y=x+b,一个为y=-x+b。

所以b=y-x,为了使b>0,因此我们加上n。另外一个为y+x。

class Solution {
public:vector<vector<string>> solveNQueens(int n) {vector<vector<string>> ans;if(n==0)return {};vector<string> board(n,string(n,'.'));vector<bool> c(n,false),l(2*n-1,false),r(2*n-1,false);back(n,ans,board,c,l,r,0);return ans;}void back(int n,vector<vector<string>>& ans,vector<string>& board,vector<bool>& c,vector<bool>& l,vector<bool>& r,int row){if(row==n){ans.push_back(board);return ;}int i;for(i=0;i<n;i++){if(c[i]||l[row-i+n]||r[row+i]){continue;}board[row][i]='Q';c[i]=l[row-i+n]=r[row+i]=true;back(n,ans,board,c,l,r,row+1);board[row][i]='.';c[i]=l[row-i+n]=r[row+i]=false;}}
};

总结

对于回溯法,首先找到边界条件以及结束的条件。一般为设置的i等于行数。

边界条件一般为不要越界。

一般还需要设置标记函数。然后一行一行进行访问或者一个位置一个位置的访问,访问过的标记函数置为true。接着继续下一个或者下一行(一般是递归)。然后结束后还原上面的标记函数以及board(一般会设置一个作为答案)。符合的就push_back到ans数组中去。

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

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

相关文章

什么是面向对象编程

什么是面向对象编程&#xff1f;&#xff08;OOP&#xff09; ● 面向对象编程是一种基于对象概念的编程范式&#xff1b;&#xff08;所谓的编程范式&#xff0c;就是代码风格&#xff0c;我们“如何”编写和组织代码&#xff09;&#xff1b; ● 我们使用对象来模拟&#xf…

[C++] STL :stackqueue详解 及 模拟实现

标题&#xff1a;[C] STL &#xff1a;stack&&queue详解 水墨不写bug 目录 &#xff08;一&#xff09;stack简介 &#xff08;二&#xff09;queue简介 &#xff08;三&#xff09;容器适配器 &#xff08;四&#xff09;stack和queue的模拟实现 /*** …

LabVIEW从测试曲线中提取特征值

在LabVIEW中开发用于从测试曲线中提取特征值的功能时&#xff0c;可以考虑以下几点&#xff1a; 数据采集与处理&#xff1a; 确保你能够有效地采集和处理测试曲线数据。这可能涉及使用DAQ模块或其他数据采集设备来获取曲线数据&#xff0c;并在LabVIEW中进行处理和分析。 特…

lvs集群、NAT模式和DR模式、keepalive

目录 lvs集群概念 集群的类型&#xff1a;三种类型 系统可靠性指标 lvs集群中的术语 lvs的工作方式 NAT模式 lvs的工具 算法 实验 数据流向 步骤 一 、调度器配置&#xff08;test1 192.168.233.10&#xff09; 二、RS配置&#xff08;nginx1和nginx2&#xff09;…

Python那些优质可视化工具!

作者&#xff1a;Lty美丽人生 https://blog.csdn.net/weixin_44208569 本次分享10个适用于多个学科的Python数据可视化库&#xff0c;其中有名气很大的也有鲜为人知的&#xff01; 1、matplotlib 两个直方图 matplotlib 是Python可视化程序库的泰斗。经过十几年它任然是Pytho…

王牌站士Ⅴ--mysql9.0发布向量类型糊弄了事

前言 MySQL在本月发布了9.0大版本&#xff0c;作为一个老用户&#xff0c;忍不住关注了一下&#xff0c;简单说下这次大版本更新。 2023年&#xff0c;AI爆火&#xff0c;带动了向量数据库赛道。当下几乎所有主流 DBMS 都已经提供向量数据类型支持 —— MySQL 除外。 大家原…

【vue教程】二. Vue特性原理详解

目录 回顾本章涵盖知识点Vue 实例和选项创建 Vue 实例Vue 实例的选项 Vue 模板语法插值表达式指令v-bindv-modelv-on 自定义指令创建自定义指令在模板中使用自定义指令自定义指令的钩子函数自定义指令的实例演示 指令注册局部注册指令过滤器 数据绑定和响应式原理响应式数据绑定…

【CUDA|CUDNN】安装

every blog every motto: You can do more than you think. https://blog.csdn.net/weixin_39190382?typeblog 0. 前言 显卡驱动安装参考之前的文章 cuda、cudnn 安装 1. cuda 安装 访问https://developer.nvidia.com/cuda-toolkit-archive 选择需要的版本&#xff1a;h…

css实现渐进中嵌套渐进的方法

这是我们想要的实现效果&#xff1a; 思路&#xff1a; 1.有一个底色的背景渐变 2.需要几个小的块级元素做绝对定位通过渐变filter模糊来实现 注意&#xff1a;这里的采用的定位方法&#xff0c;所以在内部的元素一律要使用绝对定位&#xff0c;否则会出现层级的问题&…

面试经验之谈

优质博文&#xff1a;IT-BLOG-CN ​通常面试官会把每一轮面试分为三个环节&#xff1a;① 行为面试 ② 技术面试 ③ 应聘者提问 行为面试环节 面试开始的5~10分钟通常是行为面试的时间&#xff0c;面试官会参照简历和你的自我介绍了解应聘者的过往经验和项目经历。由于面试官…

Hangfire发布托管到iis无法正常执行任务

本文以windowsServer2012R2iis8示例。 当我们设置了一个后台周期性任务后发布到iis&#xff0c;如果出现网站间隔时间较长没有用户去访问&#xff0c;这是iis可能就会自动回收导致Hangfire服务停止&#xff0c;导致我们的后台任务终止执行&#xff0c;直到进来一个请求&#xf…

基于全国产复旦微JFM7K325T+ARM人工智能数据处理平台

复旦微可以配合的ARM平台有&#xff1a;RK3588/TI AM62X/ NXP IMX.8P/飞腾FT2000等。 产品概述 基于PCIE总线架构的高性能数据预处理FMC载板&#xff0c;板卡采用复旦微的JFM7K325T FPGA作为实时处理器&#xff0c;实现各个接口之间的互联。该板卡可以实现100%国产化。 板卡具…

window下tqdm进度条

原代码是linux下运行&#xff0c;修改后可在window下运行。 #ifndef TQDM_H #define TQDM_H#include <chrono> #include <ctime> #include <numeric> #include <ios> #include <string> #include <cstdlib> #include <iostream> #i…

系统吃swap问题排查

目录 背景 问题 分析并解决 1.控制线程数 2.更换IO组件 3.Linux进程信息文件分析 总结加餐 参考文档 背景 隔壁业务组系统是简单的主从结构&#xff0c;写索引的服务(主)叫primary&#xff0c; 读索引并提供搜索功能的服务(从)叫replica。业务线同步数据并不是平滑的&…

【新书速递】使用MATLAB进行雷达系统分析和设计(第四版)(2022)

来源&#xff1a;公众号高山防务 一、目录 目录 1雷达定义和术语 1.1雷达系统分类和波段 1.1.1高频&#xff08;HF&#xff09;和甚高频&#xff08;VHF&#xff09;雷达&#xff08;A和B波段&#xff09; 1.1.2超高频&#xff08;UHF&#xff09;雷达&#xff08;C波段&am…

【学习css1】flex布局-页面footer部分保持在网页底部

中间内容高度不够屏幕高度撑不开的页面时候&#xff0c;页面footer部分都能保持在网页页脚&#xff08;最底部&#xff09;的方法 1、首先上图看显示效果 2、奉上源码 2.1、html部分 <body><header>头部</header><main>主区域</main><foot…

循环结构(一)——for语句【互三互三】

文章目录 &#x1f341; 引言 &#x1f341; 一、语句格式 &#x1f341; 二、语句执行过程 &#x1f341; 三、语句格式举例 &#x1f341;四、例题 &#x1f449;【例1】 &#x1f680;示例代码: &#x1f449;【例2】 【方法1】 &#x1f680;示例代码: 【方法2】…

通过git将文件push到github 远程仓库

1.先git clone 代码地址 git clone htttp://github.com/用户名/test.git 2. 添加文件 例如&#xff1a;touch 1.txt 3.将文件添加到暂存区 git add 1.txt 4.提交 git commit -m "commit 1.txt" 5.与远程仓库建立关联 git remote add 远程仓库名 远程仓库…

华为浏览器,Chrome的平替,插件无缝连接

文章目录 背景插件书签 背景 不知道各位小伙伴有没有这样的痛点&#xff0c;办公电脑、家里的电脑还有手机、平板等&#xff0c;收藏了一个网址或者在手机上浏览了某个网页&#xff0c;保存起来&#xff0c;可是一换平台或者换个电脑&#xff0c;在想要浏览之前收藏的东西&…

Elasticsearch 8 支持别名查询

在 Elasticsearch 8 中&#xff0c;使用 Java 高级 REST 客户端进行别名管理的过程与之前的版本类似&#xff0c;但有一些API细节上的变化。以下是如何使用 Java 和 Elasticsearch 8 进行别名操作的例子&#xff1a; 引入依赖 确保你的项目中包含了 Elasticsearch 的高级 RES…