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  # 当前位置合法

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

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

相关文章

Vue的前世今生与安装配置

vue的前世今生 Vue.js是一个流行的前端JavaScript框架&#xff0c;用于构建用户界面与单页应用程序&#xff08;SPA&#xff09;。它的诞生和发展可以概括为以下几个重要阶段&#xff1a; 初创阶段&#xff1a;Vue由中国人尤雨溪&#xff08;Evan You&#xff09;创建于2014年…

目标检测+车道线识别+追踪

一种方法&#xff1a; 车道线检测-canny边缘检测-霍夫变换 一、什么是霍夫变换 霍夫变换&#xff08;Hough Transform&#xff09;是一种在图像处理和计算机视觉中广泛使用的特征检测技术&#xff0c;主要用于识别图像中的几何形状&#xff0c;尤其是直线、圆和椭圆等常见形状…

Mysql数据库-DQL查询

Mysql数据库-DQL基本查询 1 DQL基本查询1.1 基础查询1.2 WHERE子句1&#xff09;算术运算符2&#xff09;逻辑运算符3&#xff09;比较运算符A&#xff09;BETWEEN... AND ...B&#xff09;IN(列表)C&#xff09;NULL值判断 4&#xff09;综合练习 2 DQL高级查询2.1 LIKE 模糊查…

JavaWeb后端——HTTP协议/Tomcat

HTTP HTTP协议&#xff1a;无状态&#xff0c;对事务处理没有记忆能力。每次请求-响应都是独立的。后一次请求不会记录前一次请求数据。缺点&#xff1a;多次请求之间不能共享数据&#xff0c;优点&#xff1a;速度快。 HTTP协议请求报文&#xff1a; HTTP协议响应报文&#x…

HarmonyOS入门--配置环境 + IDE汉化

文章目录 下载安装DevEco Studio配置环境先认识DevEco Studio界面工程目录工程级目录模块级目录 app.json5module.json5main_pages.json通知栏预览区 运行模拟器IED汉化 下载安装DevEco Studio 去官网下载DevEco Studio完了安装 配置环境 打开已安装的DevEco Studio快捷方式…

linux 环境安装配置

安装java17 1.下载安装包 wget https://download.oracle.com/java/17/latest/jdk-17_linux-x64_bin.tar.gz 2.解压到自定义目录/usr/local/java mkdir /usr/local/java tar zxvf jdk-17_linux-x64_bin.tar.gz -C /usr/local/java 3.配置环境变量 echo export PATH$PATH:/…

stm32之GPIO寄存器

文章目录 1 背景2 GPIO寄存器的类型2.1 端口配置寄存器2.2 设置/清除寄存器和位清除寄存器 3 总结 1 背景 C51单片机在进行数据的输入输出时&#xff0c;是直接操作与外部引脚关联的内部寄存器&#xff0c;例如&#xff0c;当设置P2_1为0时&#xff0c;就是将外部引脚的P21引脚…

LeetCode.2908. 元素和最小的山形三元组 I

题目 2908. 元素和最小的山形三元组 I 分析 首先&#xff0c;看到这道题&#xff0c;第一反应就是暴力方法&#xff0c;三层for循环&#xff0c;枚举每一种情况&#xff0c;代码如下 class Solution {public int minimumSum(int[] nums) {int min Integer.MAX_VALUE;for(i…

【详细讲解PostCSS如何安装和使用】

&#x1f308;个人主页:程序员不想敲代码啊&#x1f308; &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家&#x1f3c6; &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d; 希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提…

GPU算力池管理工具Determined AI部署与使用教程(2024.03)

1. 概念 1.1 什么是Determined&#xff1f; Determined AI 是一个全功能的深度学习平台&#xff0c;兼容 PyTorch 和 TensorFlow。它主要负责以下几个方面&#xff1a; 分布式训练&#xff1a;Determined AI 可以将训练工作负载分布在多个 GPU&#xff08;可能在多台计算机上…

Untiy 布局控制器Aspect Ratio Fitter

Aspect Ratio Fitter是Unity中的一种布局控制器组件&#xff0c;用于根据指定的宽高比来调整包含它的UI元素的大小。实际开发中&#xff0c;它可以确保UI元素保持特定的宽高比&#xff0c;无论UI元素的内容或父容器的大小如何变化。 如图为Aspect Ratio Fitter组件的基本属性&…

开源 OLAP 及其在不同场景下的需求

目录 一、开源 OLAP 综述 二、OLAP场景思考 2.1 面向客户的报表 2.2 面向经营的报表 2.3 末端运营分析 2.4 用户画像 2.5 订单分析 2.6 OLAP技术需求思考 三、开源数据湖/流式数仓解决方案 3.1 离线数仓体系——Lambda架构 3.2 实时数据湖解决方案 3.3 实时分析解决…

Spark基于DPU Snappy压缩算法的异构加速方案

一、总体介绍 1.1 背景介绍 Apache Spark是专为大规模数据计算而设计的快速通用的计算引擎&#xff0c;是一种与 Hadoop 相似的开源集群计算环境&#xff0c;但是两者之间还存在一些不同之处&#xff0c;这些不同之处使 Spark 在某些工作负载方面表现得更加优越。换句话说&am…

Android开发 --- Android12外部存储权限问题

1.问题 Android 11中强制启用Scoped Storage是为了更好地保护用户的隐私&#xff0c;以及提供更加安全的数据保护。拥有对整个SD卡的读写权限&#xff0c;在Android 11上被认为是一种非常危险的权限&#xff0c;同时也可能会对用户的数据安全造成比较大的影响。Android12使用如…

html安装及入门

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、简单介绍一下前端三大件开发工具 二、安装VSCode三、VSCode相关配置1.汉化2.live server3.使用前 总结 提示&#xff1a;以下是本篇文章正文内容&#xff0c;下…

【热门话题】Yarn:新一代JavaScript包管理器的安装与使用

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 Yarn&#xff1a;新一代JavaScript包管理器的安装与使用引言一、Yarn的安装1. 系…

探索多种数据格式:JSON、YAML、XML、CSV等数据格式详解与比较

title: 探索多种数据格式&#xff1a;JSON、YAML、XML、CSV等数据格式详解与比较 date: 2024/3/28 17:34:03 updated: 2024/3/28 17:34:03 tags: 数据格式JSONYAMLXMLCSV数据交换格式比较 1. 数据格式介绍 数据格式是用于组织和存储数据的规范化结构&#xff0c;不同的数据格…

腾讯云邮件推送功能有哪些?如何有效使用?

腾讯云邮件推送如何设置&#xff1f;怎么用邮件推送做高效营销&#xff1f; 腾讯云作为业界领先的云服务提供商&#xff0c;其邮件推送功能在便捷性、稳定性和安全性上都有着出色的表现。那么&#xff0c;腾讯云邮件推送功能究竟有哪些呢&#xff1f;让AokSend来探个究竟。 腾…

Mac添加和关闭开机应用

文章目录 mac添加和关闭开机应用添加开机应用删除/查看 mac添加和关闭开机应用 添加开机应用 删除/查看 打开&#xff1a;系统设置–》通用–》登录项–》查看登录时打开列表 选中打开项目&#xff0c;点击“-”符号

第十二届蓝桥杯物联网试题(省赛)

思路&#xff1a; 这个考了一个RTC的配置&#xff0c;RTC我只配过一次&#xff0c;所以有些生疏&#xff0c;还是不能大意&#xff0c;一些偏僻的考点还是要多练&#xff0c;在获取RTC时间的时候也遇到一些bug,这个后续会用一篇博客将最近遇到的BUG都总结一下 主要的难点还是…