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

力扣-回溯法

何为回溯法?

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

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数组中去。

相关文章:

力扣-回溯法

何为回溯法&#xff1f; 在搜索到某一节点的时候&#xff0c;如果我们发现目前的节点&#xff08;及其子节点&#xff09;并不是需求目标时&#xff0c;我们回退到原来的节点继续搜索&#xff0c;并且把在目前节点修改的状态还原。 记住两个小诀窍&#xff0c;一是按引用传状态…...

240713_昇思学习打卡-Day25-LSTM+CRF序列标注(4)

240713_昇思学习打卡-Day25-LSTMCRF序列标注&#xff08;4&#xff09; 最后一天咯&#xff0c;做第四部分。 BiLSTMCRF模型 在实现CRF后&#xff0c;我们设计一个双向LSTMCRF的模型来进行命名实体识别任务的训练。模型结构如下&#xff1a; nn.Embedding -> nn.LSTM -&…...

python requests关闭https校验

python requests关闭https校验 import requests# 关闭SSL验证 requests.get(https://***.com, verifyFalse)...

PG大会周五于杭州举办;Pika发布4.0;阿里云MySQL上线Zero-ETL集成能力

重要更新 1. PostgreSQL中国技术大会举行12日&#xff08;周五&#xff09;于杭州举办&#xff0c;是PostgreSQL社区年度的大会&#xff0c;举办地点&#xff1a;杭州君尚云郦酒店&#xff08;杭州市上城区临丁路1188号&#xff09;&#xff0c;感兴趣的可以考虑现场参加 ( [1]…...

虚拟机vmware网络设置

一、网络分类 打开vmware workstation网络编辑器可以知道有三种网络类型&#xff0c;分别是&#xff1a;桥接模式、nat模式、仅主机模式。 1、桥接模式 桥接模式是将主机网卡与虚拟机虚拟的网卡利用虚拟网桥进行通信。在桥接的作用下, 类似于把物理主机虚拟为一个交换机, 所有设…...

数学建模国赛入门指南

文章目录 认识数学建模及国赛认识数学建模什么是数学建模&#xff1f;数学建模比赛 国赛参赛规则、评奖原则如何评省、国奖评奖规则如何才能获奖 国赛赛题分类及选题技巧国赛赛题特点赛题分类 国赛历年题型及优秀论文 数学建模分工技巧数模必备软件数模资料文献数据收集资料收集…...

Java基础之集合

集合和数组的类比 数组: 长度固定可以存基本数据类型和引用数据类型 集合: 长度可变只能存引用数据类型存储基本数据类型要把他转化为对应的包装类 ArrayList集合 ArrayList成员方法 添加元素 删除元素 索引删除 查询 遍历数组...

深度学习和NLP中的注意力和记忆

深度学习和NLP中的注意力和记忆 文章目录 一、说明二、注意力解决了什么问题&#xff1f;#三、关注的代价#四、机器翻译之外的关注#五、注意力&#xff08;模糊&#xff09;记忆&#xff1f;# 一、说明 深度学习的最新趋势是注意力机制。在一次采访中&#xff0c;现任 OpenAI 研…...

自用的C++20协程学习资料

C20的一个重要更新就是加入了协程。 在网上找了很多学习资料&#xff0c;看了之后还是不明白。 最后找到下面这些资料总算是讲得比较明白&#xff0c;大家可以按照顺序阅读&#xff1a; 渡劫 C 协程&#xff08;1&#xff09;&#xff1a;C 协程概览C20协程原理和应用...

【C++】优先级队列(底层代码解释)

一. 定义 优先级队列是一个容器适配器&#xff0c;他可以根据不同的需求采用不同的容器来实现这个数据结构&#xff0c;优先级队列采用了堆的数据结构&#xff0c;默认使用vector作为容器&#xff0c;且采用大堆的结构进行存储数据。 &#xff08;1&#xff09;在第一个构造函数…...

华为模拟器防火墙配置实验(二)

一.实验拓扑 二.实验要求 1&#xff0c;DMZ区内的服务器&#xff0c;办公区仅能在办公时间内&#xff08;9&#xff1a;00 - 18&#xff1a;00&#xff09;可以访问&#xff0c;生产区的设备全天可以访问. 2&#xff0c;生产区不允许访问互联网&#xff0c;办公区和游客区允许…...

group 与查询字段

需求 每周周一&#xff0c;统计菜单在过去一周&#xff0c;点击次数&#xff0c;和点击人数&#xff08;同一个人访问多次按一次计算&#xff09; 表及数据 日志表 CREATE TABLE t_data_log ( id varchar(50) NOT NULL COMMENT 主键id, operation_object varchar(500) DE…...

PlantUML 教程:绘制时序图

绘制时序图是 PlantUML 的一个强大功能&#xff0c;下面是详细的 PlantUML 时序图教程&#xff0c;帮助你理解如何使用它来创建清晰的时序图。 基本概念 时序图&#xff08;Sequence Diagram&#xff09;用于展示对象之间的交互以及它们之间的消息传递顺序。它主要由以下元素…...

自定义ViewGroup-流式布局FlowLayout(重点:测量和布局)

效果 child按行显示&#xff0c;显示不下就换行。 分析 继承ViewGrouponDraw()不重写&#xff0c;使用ViewGroup的测量-重点 &#xff08;测量child、测量自己&#xff09;布局-重点 &#xff08;布局child&#xff09; 知识点 执行顺序 构造函数 -> onMeasure() -> …...

C++的入门基础(二)

目录 引用的概念和定义引用的特性引用的使用const引用指针和引用的关系引用的实际作用inlinenullptr 引用的概念和定义 在语法上引用是给一个变量取别名&#xff0c;和这个变量共用同一块空间&#xff0c;并不会给引用开一块空间。 取别名就是一块空间有多个名字 类型& …...

显示产业如何突破芯片短板

尽管中国在显示IC领域面临一定的不足&#xff0c;但新技术的不断涌现为中国企业提供了重要的发展机遇。随着手机、平板电脑和液晶电视对显示屏性能要求的不断提高&#xff0c;显示驱动IC也必须相应地发展&#xff0c;向更高分辨率、更大尺寸和更低功耗的方向迈进。例如&#xf…...

STM32HAL库+ESP8266+cJSON+微信小程序_连接华为云物联网平台

STM32HAL库ESP8266cJSON微信小程序_连接华为云物联网平台 实验使用资源&#xff1a;正点原子F407 USART1&#xff1a;PA9P、A10&#xff08;串口打印调试&#xff09; USART3&#xff1a;PB10、PB11&#xff08;WiFi模块&#xff09; DHT11&#xff1a;PG9&#xff08;采集数据…...

debian或Ubuntu中开启ssh允许root远程ssh登录的方法

debian或Ubuntu中开启ssh允许root远程ssh登录的方法 前因&#xff1a; 因开发需要&#xff0c;需要设置开发板的ssh远程连接。 操作步骤如下&#xff1a; 安装openssh-server sudo apt install openssh-server设置root用户密码&#xff1a; sudo passwd root允许root用户…...

C++《日期》实现

C《日期》实现 头文件实现文件 头文件 在该文件中是为了声明函数和定义类成员 using namespace std; class Date {friend ostream& operator<<(ostream& out, const Date& d);//友元friend istream& operator>>(istream& cin, Date& d);//…...

【面试题】MySQL(第三篇)

目录 1. MySQL中如何处理死锁&#xff1f; 2. MySQL中的主从复制是如何实现的&#xff1f; 3. MySQL中的慢查询日志是什么&#xff1f;如何使用它来优化性能&#xff1f; 4.存储过程 一、定义与基本概念 二、特点与优势 三、类型与分类 四、创建与执行 五、示例 六、总…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

镜像里切换为普通用户

如果你登录远程虚拟机默认就是 root 用户&#xff0c;但你不希望用 root 权限运行 ns-3&#xff08;这是对的&#xff0c;ns3 工具会拒绝 root&#xff09;&#xff0c;你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案&#xff1a;创建非 roo…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...