递归搜索回溯综合练习(十五题)

目录

1.找出所有子集的异或总和再求和 

2.全排列2 

3.电话号码的字母组合

4.括号生成

 5.组合

 6.目标和

1.path作为全局变量

2.path用于传参

7.组合总和

方法一:按照每个空选什么数字进行递归

 方法二:按照每个数字选几个进行递归

8.字母大小写全排列

9.优美的排列

 10.N皇后问题

 11.有效的数独

12.解数独

13.单词搜索

14.黄金矿工

15.不同路径3


1.找出所有子集的异或总和再求和 

1863. 找出所有子集的异或总和再求和 - 力扣(LeetCode)

        它的决策树是这样子的,也是每个节点都作为一个结果,没有边界条件。 因为异或运算具有重复相消除的性质,因此我们回溯的时候只需要再异或一次即可 

class Solution {
public:int mysum = 0;int path;int subsetXORSum(vector<int>& nums) {dfs(nums,0);return mysum;}void dfs(vector<int>& nums, int pos){mysum += path;for(int i = pos; i < nums.size(); i++){path ^= nums[i];dfs(nums, i + 1);path ^= nums[i];}}
};

2.全排列2 

.LCR 084. 全排列 II - 力扣(LeetCode)

class Solution {
public:vector<vector<int>> ret;vector<int> path;int check[9];vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());dfs(nums, 0);return ret;}void dfs(vector<int> nums, int pos){if(pos == nums.size()){ret.push_back(path);return;}for(int i = 0; i < nums.size(); i++){if(check[i] == true || (i != 0 && nums[i] == nums[i-1] && check[i-1] == false))continue;else{path.push_back(nums[i]);check[i] = 1;dfs(nums,pos + 1);path.pop_back();check[i] = 0;}}}
};

3.电话号码的字母组合

17. 电话号码的字母组合 - 力扣(LeetCode)

这道题主要是考虑一下数字和字符的映射关系,我们弄一个数组把字符装进去就可以了

class Solution {
public:string hash[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};string path;vector<string> ret;vector<string> letterCombinations(string digits) {if(digits.size() == 0)return ret;dfs(digits, 0);return ret;}void dfs(string & digits, int pos){if(pos == digits.size()){ret.push_back(path);return;}for(auto ch: hash[digits[pos] -'0']){path.push_back(ch);dfs(digits, pos + 1);path.pop_back();}}
};

4.括号生成

LCR 085. 括号生成 - 力扣(LeetCode)

整体代码只需要看一次深搜是怎么样的,就怎么样写就行 ,比如看最左侧那列

class Solution {
public:int left,right;string path;vector<string> ret;vector<string> generateParenthesis(int n) {dfs(n);return ret;}void dfs(int n){if(right == n){ret.push_back(path);return;}//leftleft++;if(left <= n){path += '(';dfs(n);path.pop_back();}left--;right++;if(right <= left){path += ')';dfs(n);path.pop_back();}right--;}
};

 5.组合

 LCR 080. 组合 - 力扣(LeetCode)

只要递归的时候从下一个位置递归,自然就进行了剪枝 ,即这里的  dfs(n,k,i+1);

class Solution {
public:vector<int> path;vector<vector<int>> ret;vector<vector<int>> combine(int n, int k) {dfs(n,k, 1);return ret;}void dfs(int n,int k, int pos){if(path.size() == k){ret.push_back(path);return;}for(int i = pos; i <= n; i++){path.push_back(i);dfs(n,k,i+1);path.pop_back();}}
};

 6.目标和

LCR 102. 目标和 - 力扣(LeetCode)

1.path作为全局变量

class Solution {
public:int ret = 0;int path = 0;int aim;int findTargetSumWays(vector<int>& nums, int target) {aim = target;dfs(nums, 0);return ret;}void dfs(vector<int>& nums ,int pos){if(pos == nums.size()){if(path == aim)ret++;return;}path += nums[pos];dfs(nums, pos + 1);path -= nums[pos];path -= nums[pos];dfs(nums, pos + 1);path += nums[pos];}
};

2.path用于传参

这里因为参数本身的性质,就不需要恢复现场

(当全局变量为int类型时,我们可以把它放进参数里面)

class Solution {
public:int ret = 0;int aim;int findTargetSumWays(vector<int>& nums, int target) {aim = target;int path = 0;dfs(nums, 0 , path);return ret;}void dfs(vector<int>& nums, int pos, int path){if(pos == nums.size()){if(path == aim)ret++;return;}dfs(nums, pos + 1, path + nums[pos]);dfs(nums, pos + 1, path - nums[pos]);}
};

7.组合总和

 39. 组合总和 - 力扣(LeetCode)

方法一:按照每个空选什么数字进行递归

因为一个元素可以无限次数地去用,因此递归到下一层的时候仍然可以从当前位置开始继续 

 即dfs(candidates, i); 

临界条件是tmp >= target,要是等于的话可以加入ret,否则直接return即可

class Solution {
public:vector<vector<int>> ret;vector<int> path;int tmp;int target;vector<vector<int>> combinationSum(vector<int>& candidates, int _target) {target = _target;dfs(candidates,0);return ret;}void dfs(vector<int>& candidates,int pos){if(tmp >= target){if(tmp == target){ret.push_back(path);}return;}for(int i = pos; i < candidates.size(); i++){path.push_back(candidates[i]);tmp += candidates[i];dfs(candidates, i);path.pop_back();tmp -= candidates[i];}}
};

 方法二:按照每个数字选几个进行递归

        值得注意的是,这里的恢复现场要等这个数字的选择全部结束后再一次性恢复。因为例如选两个,它就是在选一个的基础上再进行选择的

class Solution {
public:vector<vector<int>> ret;vector<int> path;int tmp;int target;vector<vector<int>> combinationSum(vector<int>& candidates, int _target) {target = _target;dfs(candidates,0);return ret;}void dfs(vector<int>& candidates,int pos){if(tmp >= target){if(tmp == target){ret.push_back(path);}return;}if(pos == candidates.size())return;for(int i = 0; i * candidates[pos] <= target; i++){if(i) {path.push_back(candidates[pos]);tmp += candidates[pos];}dfs(candidates, pos + 1);}for(int i = 1; i * candidates[pos] <= target; i++){path.pop_back();tmp -= candidates[pos];}}
};

8.字母大小写全排列

784. 字母大小写全排列 - 力扣(LeetCode)

        这里依照每个位置改变和不改变的分类方式去写代码,但是只有字母字符才能改变,条件判断一下即可 

class Solution {
public:string path;vector<string> ret;vector<string> letterCasePermutation(string s) {dfs(s,0);return ret;}void dfs(string s, int pos){if(pos == s.size()){ret.push_back(path);return;}//不改变path.push_back(s[pos]);dfs(s,pos + 1);path.pop_back();//改变if(s[pos] < '0' || s[pos] > '9'){path.push_back(change(s[pos]));dfs(s,pos + 1);path.pop_back();} }char change(char ch){if(islower(ch))return toupper(ch);else return tolower(ch);}
};

 这里则是按照数字和字母的分类去写代码,数字不改变,字母字符有改变和不改变两种状态

class Solution {
public:string path;vector<string> ret;vector<string> letterCasePermutation(string s) {dfs(s,0);return ret;}void dfs(string s, int pos){if(pos == s.size()){ret.push_back(path);return;}if(s[pos] < '0' || s[pos] > '9'){path.push_back(change(s[pos]));dfs(s,pos + 1);path.pop_back();path.push_back(s[pos]);dfs(s,pos + 1);path.pop_back();} else{path.push_back(s[pos]);dfs(s,pos + 1);path.pop_back();}}char change(char ch){if(islower(ch))return toupper(ch);else return tolower(ch);}
};

9.优美的排列

 526. 优美的排列 - 力扣(LeetCode)

class Solution {
public:int ret = 0;int n;int check[16];int countArrangement(int _n) {n = _n;dfs(1);return ret;}void dfs(int pos){if(pos == n + 1){ret++;return;}for(int i = 1; i <= n; i++){if(check[i] == 0 && (i % pos == 0 || pos % i == 0)){check[i] = 1;dfs(pos + 1);check[i] = 0;}}}
};

 10.N皇后问题

51. N 皇后 - 力扣(LeetCode)

        我们只需要注意剪枝的判断条件即可,我们引入一个坐标系,使用row和i(这里的i实际上就是col)的函数对应关系来标记对角线上是否有皇后。在相减产生负数的时候我们可以同时加上n。 

class Solution {
public:bool col[10];bool dig1[20];bool dig2[20];vector<string> pathret;vector<vector<string>> ret;int n;vector<vector<string>> solveNQueens(int _n) {n = _n;dfs(0);return ret;}void dfs(int row){if(row == n){ret.push_back(pathret);}for(int i = 0; i < n; i++){if(col[i] == 0 && dig1[row - i + n] == 0 && dig2[row + i] == 0){string tmp;for(int j = 0; j < n; j++){if(j == i)tmp.push_back('Q');else tmp.push_back('.');}pathret.push_back(tmp);col[i] = 1 ;dig1[row - i + n] =  1 ;dig2[row + i] = 1;dfs(row + 1);pathret.pop_back();col[i] = 0 ;dig1[row - i + n] =  0 ;dig2[row + i] = 0;}}}
};

 11.有效的数独

  36. 有效的数独 - 力扣(LeetCode)

本题作为解数独前置题目。

本题的关键是剪枝策略,我们用三个数组来表示某行,某列,某个小的3*3方格中有没有某个数字

class Solution {
public:bool row[9][10];bool col[9][10];bool grid[3][3][10];bool isValidSudoku(vector<vector<char>>& board) {for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){if(board[i][j] == '.')continue;else{int num = board[i][j]-'0';if(row[i][num] || col[j][num] || grid[i/3][j/3][num])return false;else{row[i][num] = col[j][num] = grid[i/3][j/3][num] = 1;}}}}return true;}
};

12.解数独

37. 解数独 - 力扣(LeetCode)

这题的决策树和其它题目没有本质不同

我们的思路是遍历全部的格子,遇到‘.’ 就往里面依次尝试填入数字。

但是有可能填到最后发现这种策略是不行的,因此我们需要让函数有一个返回值帮助我们判断。

当正确填完,就会依次一轮轮返回true。

 如果在某种填法下我们发现这种填法最终是不行的,那么我们返回false被最上层接收时,会进行恢复路径,即 board[i][j] = '.';
                            row[i][num] = col[j][num] = grid[i/3][j/3][num] = false;

当某个空位1-9填入后都不行,那么我们就返回false,说明上层的填值出现了问题。

当我们遍历完所有格子出了循环,那么说明成功填完了,我们就返回true。

class Solution {
public:bool row[9][10];bool col[9][10];bool grid[3][3][10];void solveSudoku(vector<vector<char>>& board) {for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){if(board[i][j] == '.')continue;else{int num = board[i][j]-'0';row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;}}}dfs(board);}bool dfs(vector<vector<char>>& board){for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){if(board[i][j] == '.'){for(int num = 1; num <= 9; num++){if(!row[i][num] && !col[j][num] && !grid[i/3][j/3][num]){board[i][j] = num + '0';row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;if(dfs(board))return true;board[i][j] = '.';row[i][num] = col[j][num] = grid[i/3][j/3][num] = false;}}return false;}}}return true;}
};

13.单词搜索

79. 单词搜索 - 力扣(LeetCode)

决策树

 这题和解数独那题类似,都需要返回值判断这种情况行不行。

我们首先找到首字符然后进入dfs。在这里我们需要遍历上下左右四个位置来找到下一个位置。为了避免重复遍历,我们仍然需要一个标记数组check【】【】。

解数独那题是遍历完九个数字之后,如果找不到填入的数字那么这种情况不行,返回false。

这题则是遍历完四个位置之后,如果找不到就返回false。每找四周的一个位置都需要重复标记check数组,恢复路径。(这里注意要定义新的变量不能直接改x和y,否则会影响到其它位置)

最终的判断条件是 if(pos == s.size())return true;

class Solution {
public:bool check[10][10];int m, n;bool exist(vector<vector<char>>& board, string word) {m = board.size();n = board[0].size();for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(board[i][j] == word[0]){check[i][j] = true;if(dfs(board,i,j,word,1))return true;check[i][j]= false;}}}return false;}int dx[4] = {0 , 0, -1, 1};int dy[4] = {1 , -1 ,0 , 0};bool dfs(vector<vector<char>>& board, int x, int y, string s, int pos){if(pos == s.size())return true;for(int k = 0; k < 4; k++){int i = x + dx[k];int j = y + dy[k];if(i >= 0 && i < m && j >=0 && j < n && check[i][j] == false && board[i][j] == s[pos]){check[i][j] = true;if(dfs(board,i,j,s,pos+1))return true;check[i][j] = false;}}return false;}
};

14.黄金矿工

1219. 黄金矿工 - 力扣(LeetCode)

找到一个非零位置我们就去深度优先去找,因此在大框架里面我们需要遍历一次数组。

仍然需要一个check数组标记是否遍历 ,和单词搜索一样,我们是遍历上下左右四格。

因为这个函数最后一定会走到终点,所以我们不需要返回值来标记情况。

我们用一个参数来记录 金矿的和 这样就不需要恢复现场了。

等到我们从上下左右四格都出来,说明已经走到死路了,这时候把tmpsum加入我们的ret数组即可

class Solution {
public:int check[15][15];int m, n;int dx[4] = {0 , 0, -1, 1};int dy[4] = {1 , -1 ,0 , 0};vector<int> ret;int getMaximumGold(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();for(int i = 0; i < m; i++){for(int j = 0; j < n ; j++){if(grid[i][j]){check[i][j] = true;dfs(grid, i, j, grid[i][j]);check[i][j] = false;}}}int maxret = 0;for(int i = 0; i < ret.size(); i++){if(ret[i] >= maxret)maxret = ret[i];}return maxret;}void dfs(vector<vector<int>>& grid, int x, int y,int tmpsum){for(int k = 0; k < 4; k++){int i = x + dx[k];int j = y + dy[k];if(i >= 0 && i < m && j >=0 && j < n && check[i][j] == false && grid[i][j]){check[i][j] = true;dfs(grid,i,j,tmpsum + grid[i][j]);check[i][j] = false;}}ret.push_back(tmpsum);}
};

15.不同路径3

980. 不同路径 III - 力扣(LeetCode)

代码与黄金矿工等非常类似。我们只需要标记我们遍历一次需要走的步数作为终止条件即可。

我们通过一次遍历,把数字为0或者2的部分加入aimcount即可。

class Solution {
public:int check[25][25];int m, n;int dx[4] = {0 , 0, -1, 1};int dy[4] = {1 , -1 ,0 , 0};int aimcount = 0;int pathcount = 0;int ret = 0;int uniquePathsIII(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();int initx;int inity;for(int i = 0; i < m; i++){for(int j = 0; j < n ; j++){if(grid[i][j] == 0|| grid[i][j] == 2){aimcount++;}else if(grid[i][j] == 1 ){initx = i;inity = j;}}}check[initx][inity] = true;dfs(grid,initx, inity);return ret;}void dfs(vector<vector<int>>& grid, int x, int y){if(grid[x][y] == 2){if(pathcount == aimcount)ret++;return;}for(int k = 0; k < 4; k++){int i = x + dx[k];int j = y + dy[k];if(i >= 0 && i < m && j >=0 && j < n && check[i][j] == false && grid[i][j] != -1){check[i][j] = true;pathcount++;dfs(grid,i,j);pathcount--;check[i][j] = false;}}}
};

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

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

相关文章

JWT实现单点登录

文章目录 JWT实现单点登录JWT 简介存在问题及解决方案登录流程后端程序实现前端保存Tokenstore存放信息的缺点及解决 校验流程&#xff1a;为gateway增加登录校验拦截器 另一种单点登录方法&#xff1a;Token&#xff0b;Redis实现单点登录 JWT实现单点登录 登录流程&#xff…

qt-QtQuick笔记之常见项目类简要介绍

qt-QtQuick笔记之常见项目类简要介绍 code review! 文章目录 qt-QtQuick笔记之常见项目类简要介绍1.QQuickItem2.QQuickRectangle3.QQuickImage4.QQuickText5.QQuickBorderImage6.QQuickTextInput7.QQuickButton8.QQuickSwitch9.QQuickListView10.QQuickGridView11.QQuickPopu…

循环神经网络(RNN)+pytorch实现情感分析

目录 一、背景引入 二、网络介绍 2.1 输入层 2.2 循环层 2.3 输出层 2.4 举例 2.5 深层网络 三、网络的训练 3.1 训练过程举例 1&#xff09;输出层 2&#xff09;循环层 3.2 BPTT 算法 1&#xff09;输出层 2&#xff09;循环层 3&#xff09;算法流程 四、循…

Autosar-Os是怎么运行的?(多核系统运行)

写在前面&#xff1a; 入行一段时间了&#xff0c;基于个人理解整理一些东西&#xff0c;如有错误&#xff0c;欢迎各位大佬评论区指正&#xff01;&#xff01;&#xff01; 目录 1.Autosar多核操作系统 1.1多核启动过程 1.2多核运行过程 1.2.1核间任务同步 1.2.2Counte…

【C语言练习题】正弦函数

题目&#xff1a; 根据麦克劳林公式计算正弦值。 输入格式 x ε 注&#xff1a;x 为角(弧度)&#xff0c;ε 为计算精度。 输出格式 y 注&#xff1a;y 为 x 的正弦值&#xff0c;输出 6 位小数。 输入样例1 0.5235987755982989 0.00000001输出样例1 0.500000输入样例2 314.68…

GBase 8a 9.5.3.27 DBlink配置---源端GBase

原理图 1.目标端集群将数据请求由gcluster的5258端口发送至dblink的9898端口 2.Dblink将请求由9898端口转发至源端集群的5258端口 3.源端数据库将接收的请求生成执行计划&#xff0c;由gcluster的5258端口下发至各gnode的5050端口 4.源端的5050端口接收到执行计划进行查询&…

二次封装的方法

二次封装 我们开发中经常需要封装一些第三方组件&#xff0c;那么父组件应该怎么传值&#xff0c;怎么调用封装好的组件原有的属性、插槽、方法&#xff0c;一个个调用虽然可行&#xff0c;但十分麻烦&#xff0c;我们一起来看更简便的方法。 二次封装组件&#xff0c;属性怎…

*胡闹厨房*

前期准备 详细教程 一、创建项目 1、选择Universal 3D,创建项目 2、删除预制文件Readme:点击Remove Readme Assets,弹出框上点击Proceed 3、Edit-Project Setting-Quality,只保留High Fidelity 4、打开 Assets-Settings ,保留URP-HighFidelity-Renderer 和 URP-High…

Effective Objective-C 2.0 读书笔记—— objc_msgSend

Effective Objective-C 2.0 读书笔记—— objc_msgSend 文章目录 Effective Objective-C 2.0 读书笔记—— objc_msgSend引入——静态绑定和动态绑定OC之中动态绑定的实现方法签名方法列表 其他方法objc_msgSend_stretobjc_msgSend_fpretobjc_msgSendSuper 尾调用优化总结参考文…

Three.js实战项目02:vue3+three.js实现汽车展厅项目

文章目录 实战项目02项目预览项目创建初始化项目模型加载与展厅灯光加载汽车模型设置灯光材质设置完整项目下载实战项目02 项目预览 完整项目效果: 项目创建 创建项目: pnpm create vue安装包: pnpm add three@0.153.0 pnpm add gsap初始化项目 修改App.js代码&#x…

Elasticsearch 性能测试工具 Loadgen 之 001——部署及应用详解

在现代软件开发中&#xff0c;性能测试是确保应用程序稳定性和响应速度的关键环节。 今天&#xff0c;我们就来深入了解一款国产化功能强大的 Elasticsearch 负载测试工具——INFINI Loadgen。 一、INFINI Loadgen 简介 Github地址&#xff1a;https://github.com/infinilabs/l…

Python从0到100(八十五):神经网络-使用迁移学习完成猫狗分类

前言: 零基础学Python:Python从0到100最新最全教程。 想做这件事情很久了,这次我更新了自己所写过的所有博客,汇集成了Python从0到100,共一百节课,帮助大家一个月时间里从零基础到学习Python基础语法、Python爬虫、Web开发、 计算机视觉、机器学习、神经网络以及人工智能…

(1)SpringBoot入门+彩蛋

SpringBoot 官网(中文)&#xff1a;Spring Boot 中文文档 Spring Boot是由Pivotal团队提供的一套开源框架&#xff0c;可以简化spring应用的创建及部署。它提供了丰富的Spring模块化支持&#xff0c;可以帮助开发者更轻松快捷地构建出企业级应用。Spring Boot通过自动配置功能…

C语言从入门到进阶

视频&#xff1a;https://www.bilibili.com/video/BV1Vm4y1r7jY?spm_id_from333.788.player.switch&vd_sourcec988f28ad9af37435316731758625407&p23 //枚举常量 enum Sex{MALE,FEMALE,SECRET };printf("%d\n", MALE);//0 printf("%d\n", FEMALE…

MacOS安装Docker battery-historian

文章目录 需求安装battery-historian实测配置国内源相关文章 需求 分析Android电池耗电情况、唤醒、doze状态等都要用battery-historian&#xff0c; 在 MacOS 上安装 battery-historian&#xff0c;可以使用 Docker 进行安装runcare/battery-historian:latest。装完不需要做任…

公式与函数的应用

一 相邻表格相乘 1 也可以复制 打印标题

DeepSeek学术写作测评第二弹:数据分析、图表解读,效果怎么样?

我是娜姐 迪娜学姐 &#xff0c;一个SCI医学期刊编辑&#xff0c;探索用AI工具提效论文写作和发表。 针对最近全球热议的DeepSeek开源大模型&#xff0c;娜姐昨天分析了关于论文润色、中译英的详细效果测评&#xff1a; DeepSeek学术写作测评第一弹&#xff1a;论文润色&#…

MongoDB平替数据库对比

背景 项目一直是与实时在线监测相关&#xff0c;特点数据量大&#xff0c;读写操作大&#xff0c;所以选用的是MongoDB。但按趋势来讲&#xff0c;需要有一款国产数据库可替代&#xff0c;实现信创要求。选型对比如下 1. IoTDB 这款是由清华大学主导的开源时序数据库&#x…

动手学深度学习-卷积神经网络-3填充和步幅

目录 填充 步幅 小结 在上一节的例子&#xff08;下图&#xff09; 中&#xff0c;输入的高度和宽度都为3&#xff0c;卷积核的高度和宽度都为2&#xff0c;生成的输出表征的维数为22。 正如我们在 上一节中所概括的那样&#xff0c;假设输入形状为nhnw&#xff0c;卷积核形…

简易CPU设计入门:控制总线的剩余信号(二)

项目代码下载 请大家首先准备好本项目所用的源代码。如果已经下载了&#xff0c;那就不用重复下载了。如果还没有下载&#xff0c;那么&#xff0c;请大家点击下方链接&#xff0c;来了解下载本项目的CPU源代码的方法。 CSDN文章&#xff1a;下载本项目代码 上述链接为本项目…