TOP100-回溯(二)

2024-03-29 16:36
文章标签 回溯 top100

本文主要是介绍TOP100-回溯(二),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

4.39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。 

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

示例 1:

输入:candidates =[2,3,6,7],target =7
输出:[[2,2,3],[7]]
解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。

示例 2:

输入: candidates = [2,3,5],target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3:

输入: candidates =[2],target = 1
输出: []

提示:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

思路:

本题没有数量要求,可以无限重复,但是有总和的限制,所以间接的也是有个数的限制。因为本题没有组合数量要求,仅仅是总和的限制,所以递归没有层数的限制,只要选取的元素总和超过target,就返回!

代码:

// 剪枝优化
class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(candidates); // 先进行排序backtracking(res, new ArrayList<>(), candidates, target, 0, 0);return res;}public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {// 找到了数字和为 target 的组合if (sum == target) {res.add(new ArrayList<>(path));return;}for (int i = idx; i < candidates.length; i++) {// 如果 sum + candidates[i] > target 就终止遍历if (sum + candidates[i] > target) break;path.add(candidates[i]);backtracking(res, path, candidates, target, sum + candidates[i], i);path.remove(path.size() - 1); // 回溯,移除路径 path 最后一个元素}}
}

Python: 

class Solution:def backtracking(self, candidates, target, total, startIndex, path, result):if total == target:result.append(path[:])returnfor i in range(startIndex, len(candidates)):if total + candidates[i] > target:continuetotal += candidates[i]path.append(candidates[i])self.backtracking(candidates, target, total, i, path, result)total -= candidates[i]path.pop()def combinationSum(self, candidates, target):result = []candidates.sort()  # 需要排序self.backtracking(candidates, target, 0, 0, [], result)return result

5.22. 括号生成

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例 1:

输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]

示例 2:

输入:n = 1
输出:["()"]

提示:

  • 1 <= n <= 8

思路:

回溯法,想象是否成功,通通建立2*n高的树,设置左右标志;加入左括号,则左标志+1,加入右括号,则右标志+1;仅当到达叶子节点时,左右标志也为n,才算做正确的输出。

代码:

class Solution:def generateParenthesis(self, n: int) -> List[str]:if n<=0:return []res = []def dfs(paths,left,right):if left>n or right >left: return#左括号多了,和右括号大于左括号数时,直接拜拜if len(paths) == n*2:res.append(paths)returndfs(paths+'(',left+1,right)dfs(paths+')',left,right+1)dfs('',0,0)return res

6.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 仅由大小写英文字母组成

思路:

思路也应该就是深度优先搜索,然后剪枝。关键点在于:当访问到的位置不是下一个预期值时,直接跳出,然后回溯,不继续下去。

代码:

class Solution {public int m;public int n;public boolean exist(char[][] board, String word) {m=board.length;n=board[0].length;char[] words=word.toCharArray();for(int i =0;i<m;i++){for(int j = 0;j<n;j++){if(dfs(board,words,i,j,0))return true;}}return false;}boolean dfs(char[][] board,char[] word,int i,int j,int k){if(i>=m || i<0 || j>=n || j<0 || board[i][j] != word[k])return false;if(k == word.length-1)return true;board[i][j]='\0';boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);board[i][j] = word[k];return res;}
}

7.131. 分割回文串

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串。返回 s 所有可能的分割方案。

示例 1:

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]

示例 2:

输入:s = "a"
输出:[["a"]]

提示:

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

思路:

1.先写一个函数用于判断是否为回文串
2.要划分出所有的子串,就是通过构建树来完成,而这个过程会用到深度优先搜索dfs(i)这个i是指第i个以后还没有遍历处理,而不是对第i个做操作,子串操作s.substring(start,end+1)
其他内容详见

代码:

class Solution {private String s;private final List<List<String>> res = new ArrayList<>();private final List<String> path = new ArrayList<>();//路径变量public List<List<String>> partition(String s) {this.s=s;//首先给字符串赋值//开始回溯(递归寻找)dfs(0,0);return res; }private boolean isHuiWen(int left, int right){while(left<right)if(s.charAt(left++)!=s.charAt(right--))return false;return true;}//i后面的还没处理,从Start开始private void dfs(int i, int  start){if(i==s.length()){res.add(new ArrayList<>(path));//说明这个已经完成了,复制return;}//不选i与i+1之间的逗号if(i < s.length() - 1)dfs(i+1,start);// 选 i 和 i+1 之间的逗号(把 s[i] 作为子串的最后一个字符)//要对于检查回文的部分做操作,也就是把s[i]作为字符串的最后一个字符,//需要判断从start到iif(isHuiWen(start,i)){path.add(s.substring(start,i+1));//切割子串,第i+1不算入//判断下一个字符作为头dfs(i+1,i+1);path.remove(path.size()-1);//恢复现场}}}

8.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

思路:

首先,抄来回溯的模板:

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

 递归函数参数:

依然是定义全局变量二维数组result来记录最终的结果。

参数n是棋盘的大小,然后用row来记录当前遍历到了棋盘的第几层

这部分代码是:

result=[[]*n]*n
def backtrak(n , row , chessboard):#chessboard为棋盘

我们是逐行去寻找的,因此可以想到当当前遍历行数row为第n行时,回溯到了终点。因此回溯终点为:

if row == n :result.push_back(chessboard)return

单层搜索的逻辑:

递归深度其实就是row控制棋盘的行,每一层里for循环的col控制棋盘的列,一行一列决定了皇后的位置。
每次都是从新的一行开始搜索,因此都是从0开始

代码如下:

for(int col = 0; col < n ; col++){if(isValid(row,col,chessboard,n))chessboard[row][col] = 'Q';backtrack(n,row+1,chessboard);chessboard[row][col] = '.';    
}

验证是否合法的逻辑是:

1.不能同行
2.不能同列
3.不能同斜线(45度和135度)

代码:

bool isVaild(int row,int col, vector<string>& chessboard , int n){for(int i= 0;i < row ; i++){//同一列if(chessboard[i][col]=='Q')return false;}//45度检查for(int i= row-1 ,int j =col-1;i >=0 && j >=0 ; i--,j--){if(chessboard[i][j]=='Q')return false;    }//135度检查for(int i= row-1 ,int j =col+1;i >=0 && j < n  ; i--,j++){if(chessboard[i][j]=='Q')return false;  }return true;}

 总结来说:

棋盘的宽度就是for循环的长度,递归的深度就是棋盘的高度,这样就可以套进回溯法的模板里了

代码:

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:result = []  # 存储最终结果的二维字符串数组chessboard = ['.' * n for _ in range(n)]  # 初始化棋盘self.backtracking(n, 0, chessboard, result)  # 回溯求解return [[''.join(row) for row in solution] for solution in result]  # 返回结果集def backtracking(self, n: int, row: int, chessboard: List[str], result: List[List[str]]) -> None:if row == n:result.append(chessboard[:])  # 棋盘填满,将当前解加入结果集returnfor col in range(n):if self.isValid(row, col, chessboard):chessboard[row] = chessboard[row][:col] + 'Q' + chessboard[row][col+1:]  # 放置皇后self.backtracking(n, row + 1, chessboard, result)  # 递归到下一行chessboard[row] = chessboard[row][:col] + '.' + chessboard[row][col+1:]  # 回溯,撤销当前位置的皇后def isValid(self, row: int, col: int, chessboard: List[str]) -> bool:# 检查列for i in range(row):if chessboard[i][col] == 'Q':return False  # 当前列已经存在皇后,不合法# 检查 45 度角是否有皇后i, j = row - 1, col - 1while i >= 0 and j >= 0:if chessboard[i][j] == 'Q':return False  # 左上方向已经存在皇后,不合法i -= 1j -= 1# 检查 135 度角是否有皇后i, j = row - 1, col + 1while i >= 0 and j < len(chessboard):if chessboard[i][j] == 'Q':return False  # 右上方向已经存在皇后,不合法i -= 1j += 1return True  # 当前位置合法

这篇关于TOP100-回溯(二)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/859095

相关文章

回溯——9.全排列

力扣题目链接 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 示例: 输入: [1,2,3]输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 解题思路 问题建模:题目要求给出一个数组的所有排列组合,属于典型的全排列问题,这可以用回溯法来解决。回溯法通过递归的方式,依次将数组中的每个元素放入排列中,直到生成

全球AI产品Top100排行榜

Web Top50的榜单里,AIGC类型的应用占比52%,遥遥领先。AIGC类型包括图像、视频、音乐、语音等的内容生成和编辑。音乐生成应用Suno在过去六个月中的排名跃升最为显著,从第36位上升至第5位。排名第二大类是通用对话/AI聊天/角色扮演类型的应用,占比20%,包括常见的ChatGPT、Claude、Character.ai等。其他是AI写作(8%)、AI搜索/问答(6%)、Agent/

风控系统之指标回溯,历史数据重跑

个人博客:无奈何杨(wnhyang) 个人语雀:wnhyang 共享语雀:在线知识共享 Github:wnhyang - Overview 回顾 默认你已经看过之前那篇风控系统指标计算/特征提取分析与实现01,Redis、Zset、模版方法。 其中已经介绍了如何利用redis的zset结构完成指标计算,为了方便这篇文章的介绍,还是在正式开始本篇之前回顾一下。 时间窗口 zset

165-Stamps【回溯】

回溯 给h和k的意思是在k种邮票中选h个邮票 基本的连续邮资问题 15226160 165 Stamps Accepted C++ 0.062 2015-03-27 07:21:37 #include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 2

回溯——8.递增子序列

力扣题目链接 给定一个整型数组, 你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是2。 示例: 输入: [4, 6, 7, 7]输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]] 说明: 给定数组的长度不会超过15。数组中的整数范围是 [-100,100]。给定数组中

【代码随想录|回溯part04】

代码随想录|回溯part04 1、46.全排列2、47.全排列 II3.问题 总结 python 1、46.全排列 46.全排列 class Solution:def permute(self, nums):result = []self.backtracking

代码随想录算法训练营第十九天| 回溯理论、77. 组合、216. 组合总和Ⅲ、17. 电话号码的字母组合

今日内容 回溯的理论基础leetcode. 77 组合leetcode. 216 组合总和Ⅲleetcode. 17 电话号码的字母组合 回溯理论基础 回溯法也叫回溯搜索法,它是一种搜索的方式,而且只要有递归就会有回溯,回溯就是递归的副产品。 回溯说到底并不是什么非常高深的搜索方式,本质上仍然是穷举,穷举所有可能然后选择出我们要的答案。剪枝会使回溯法更加高效一点,但改变不了回溯本质就是穷举

算法打卡 Day28(回溯算法)-组合总数 + 组合总数 Ⅱ+ 电话号码的字母组合

文章目录 Leetcode 17-电话号码的字母组合题目描述解题思路 Leetcode 39-组合总数题目描述解题思路 Leetcode 216-组合总数 Ⅲ题目描述解题思路 Leetcode 17-电话号码的字母组合 题目描述 https://leetcode.cn/problems/letter-combinations-of-a-phone-number/descrip

【递归、回溯专题(三)】记忆化搜索题集

文章目录 1. 斐波那契数2. 不同路径2. 不同路径3. 最长递增子序列4. 猜数字大小II 1. 斐波那契数 斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n > 1 给定 n

栈回溯

首先必须明确一点也是非常重要的一点,栈是向下生长的,所谓向下生长是指从内存高地址->低地址的路径延伸,那么就很明显了,栈有栈底和栈顶,那么栈顶的地址要比栈底低。对x86体系的CPU而言,其中: ---> 寄存器ebp(base pointer )可称为“帧指针”或“基址指针”,其实语意是相同的。 ---> 寄存器esp(stack pointer)可称为“ 栈指针”。 要知道的是: ---