代码随想录-回溯

  1. 在处理回溯问题的时候,集合的大小就是多叉树的宽度,因此采用for循环. 注意,这里根节点也会被最终pop,因为如果满足条件就会直接返回,加上后面的pop,导致根节点也会被pop。根本原因是调用回溯的时候,子函数也会进行pop操作,然后再返回,相当于什么也没加。

1. 组合

给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。
输入:n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

  1. 整理比较简单,主要是for循环外面记得加return,final要append result.copy,毕竟result是临时列表
  2. 组合:【1,2】和【2,1】是一样的,因此不能有重复元素。排序:【1,2】和【2,1】是不同的

2. 组合总和III

简单

3. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

  1. 相当于我们现在分阶段处理一个数组,只需要用start_index控制每一阶段,用字典来建立每一阶段for循环的列表即可。

4. 组合总和

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

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

输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]

  1. 主要是没意识到,这个for循环数组的start_index是i而不是i+1

5.组合总和II

给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

  1. 数组中有重复元素,要保证结果中没有重复的结果,比如[1,2,5], [1,2,5]。
  2. 例如[1,1,2],以第一个1开始往下取,那必定包含以第二个1开始往下取的所有结果,就会重复。因此,关键在于,同一层的树,如果相同,就要去重。
  3. 关键在于树层重复的元素怎么找: 树层重复的元素,不是在循环的开头,而且数值和上一个元素相同。
    if i>start_index and nums[i]== nums[i-1]:
    continue

6. 分割回文串

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

示例 1:

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

  1. 一开始不会做,主要是不理解切割的环节。使用start_index作为切割线,当start_index进行到字符串的末尾时,就是结束条件。

  2. result收集多个切割线,然后判断每个切割的是否符合回文。或者,可以在单层判断逻辑里,每个字串就是【start_index, i], 如果符合回文,就把字串放到result, 再对i+1进行递归。也就是说,result不再直接append,而是根据条件判断是否要append字串。

  3. result里面其实存的还是i的索引,只不过是有选择地存储

class Solution:def findValue(self, start_index, s, result, final):if start_index == len(s):final.append(result.copy())returnfor i in range(start_index, len(s)):subset = s[start_index:i+1]if subset != subset[::-1]:continueelse:result.append(subset) #result里面其实存的还是i的索引,只不过是有选择地存储self.findValue(i+1, s, result, final)result.pop()returndef partition(self, s: str) -> List[List[str]]:start_index = 0result = []final = []self.findValue(start_index,s,result,final)return final

7. 复原IP地址

有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 ‘.’ 分隔。

例如:“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址,但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
给定一个只包含数字的字符串 s ,用以表示一个 IP 地址,返回所有可能的有效 IP 地址,这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1:

输入:s = “25525511135”
输出:[“255.255.11.135”,“255.255.111.35”]

  1. 和上面的题目一样的思路,只不过要熟练怎么把整型列表转换为字符串列表
str_list = [ str(i) for i in nums]
  1. 有一个感受,第一个for循环,是树层的遍历,第二个递归,则是树枝的遍历。

8. 子集问题

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1:

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

1.观察树结构的过程,可以发现,这题和上面的分割不一样的是,最终结果是要收集每个中间阶段的结果,因此子集问题没有终止条件
2. 一开始用的分割的方法,但是仔细梳理,这样的结果会是 [1], [2],[3]; [1], [1, 2] ,[3]; [1,2,3]。 会重复一次【1】和[3]

9. 子集问题II

给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的 子集(幂集)。

解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。

示例 1:

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

  1. 和上面一题相比,这里的数组是有重复元素的。如果画二叉树结构可以看出来,需要进行去重;通过画二叉树过程可以看出,去重原理和上面的一样,都是树层去重,即i >start_index and nums[i]==nums[i-1] 为重复元素
  2. 注意!!!!对nums进行排序,否则无法让重复元素站在一起。

10. 递增子序列

给你一个整数数组 nums ,找出并返回所有该数组中不同的递增子序列,递增子序列中至少有两个元素 。你可以按任意顺序返回答案。

数组中可能含有重复元素,如出现两个整数相等,也可以视作递增序列的一种特殊情况。

示例 1:

输入:nums = [4,6,7,7]
输出:[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

  1. 我犯了两个错误,1)这里求子序列,也就是不能sort数组,那就不能用原来的树层去重,而是用used = set()来记录树层是否用过。注意,used数组要放在for循环外面,保证每一树层的used数组互不干扰。
    if i > start_index and nums[i] == nums[i - 1]:
    continue
    2)if len(result) !=0: if nums[i] < result[-1]: continue
    这里注意应该是result[-1]而不是nums[i-1],因为nums[i-1]不一定被放到了result中。
class Solution:def findValue(self, start_index, nums, result, final):if len(result) >= 2:final.append(result.copy())used = set()for i in range(start_index, len(nums)):if len(result) !=0:if nums[i] < result[-1]:continueif nums[i] in used:continueresult.append(nums[i])used.add(nums[i])self.findValue(i+1, nums, result, final)result.pop()return def findSubsequences(self, nums: List[int]) -> List[List[int]]:start_index = 0result = []final = []self.findValue(start_index, nums, result, final)return final

11. 全排列

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

示例 1:

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

  1. 解题思路是一样的,只不过排列问题的特殊点在于,used数组是全局的,而不是每层都是新的。这一点可以通过画二叉树图验证。由于是全局的used数组,因此在pop之后,还要设置used为False。
  2. 由于没有重复元素,相当于只使用树枝去重就可以了。而树枝是从上到下的,因此used是全局的
class Solution:def findValue(self, nums, used, result, final):if len(result) == len(nums):final.append(result.copy())returnfor i in range(len(nums)):if used[i]==True:continueelse:result.append(nums[i])used[i]=Trueself.findValue(nums,used, result,final)result.pop()used[i]=Falsereturndef permute(self, nums: List[int]) -> List[List[int]]:used = [False] * len(nums)result = []final = []self.findValue(nums,used,result,final)return final

12. 全排列II

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

示例 1:

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

  1. 由于多了重复元素,除了树枝去重外,还需要进行树层去重,每一层新建一个set()然后set.add()。注意树层去重,pop后并不会剔除,因为该层确定了之后不能再用这个元素。树枝去重则不同,需要进行False还原,因为下一个树枝还是会用到这些元素。

13. N皇后

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

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

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

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

  1. 开始完全没有思路。主要是前面的题目都是给定一个一维数组,然后按照条件来输出结果。但是这里是二维数组,需要额外使用一个row来指定循环的层数。
  2. 不能这样初始化二维数组,要用一个真值
board = [[]*n for _ in range(n)]#错误
board = [[.]*n for _ in range(n)] #正确
  1. 由于是逐层选择,每次只需要对上一层的元素进行去重就可以了。分别对先前行的同一列,左上角和右上角进行去重Q
class Solution:def isValid(self, board, row, col,n):for i in range(row):if board[i][col] == "Q":return Falser = row-1c = col-1#左上对角线while r>=0 and c >=0:if board[r][c] == "Q":return Falser -=1c -=1#右上对角线r = row-1c = col+1while r>=0 and c <n:if board[r][c] == "Q":return Falser -=1c +=1return Truedef findValue(self, row, board,final,n):if row == n:final.append(["".join(row) for row in board]) ##注意这里中括号的位置returnfor col in range(n):board[row][col]="Q"if self.isValid(board, row, col,n):self.findValue(row+1, board, final,n)board[row][col] ="."else:board[row][col]="."returndef solveNQueens(self, n: int) -> List[List[str]]:board = [["."]*n for _ in range(n)]final = []row = 0self.findValue(row, board, final,n)return final

14. 解数独

1.和N皇后相比,N皇后一行只填一个,但是数独一行填N个,因此维度更高。关键在于,用了两个for循环,一个是列的for循环,挑选当前行的每一列的元素,一个是k的for循环,让当前元素选择n次。
2. isValid函数,先检查这个位置放是不是合法,如果合法就放下。
3. 使用了i的for循环,主要是考虑到如果某一行的数组全都是满的,如果没有i的for循环,就需要用

return self.findValue(board, row + 1, n) 
class Solution:def isValid(self, row, col, board, number):if number in board[row]:return Falsefor r in range(len(board)):if board[r][col] == number:return Falseleft_col = col- ((col)%3)left_row = row-((row%3))for r in range(left_row, left_row+3):for c in range(left_col, left_col+3):if board[r][c] == number:return Falsereturn Truedef findValue(self, board,n):for i in range(n):for j in range(n):if board[i][j] == ".":for k in range(1,10):if self.isValid(i,j,board,str(k)):#预判填了k之后board是否合法board[i][j] = str(k)result = self.findValue(board,n)if result:return True #下一级确定没问题,直接向上返回,跳出循环#如果下一级返回的是False,那恢复为.,自动进入下一个k循环,如果到了k的末尾,会自动返回False,因此不用额外设置条件            else:board[i][j] = "."return False        return True  #填充完毕,没有地方等于.,返回Truedef solveSudoku(self, board: List[List[str]]) -> None:"""Do not return anything, modify board in-place instead."""n = len(board)self.findValue(board,n)

上面的代码超时了:

  1. 对每一行建立一个列表,存储已经填充的数字;对每一列也建立一个列表,存储已经填充的数字;对每一个box建立一个列表,存储已经填充的数字
  2. 建立一个待处理的事务列表,存储需要填充数字的坐标信息。
class Solution:def solveSudoku(self, board: List[List[str]]) -> None:# 预存行、列、3×3 子方格的已填数字rows, cols, boxes = [set() for _ in range(9)], [set() for _ in range(9)], [set() for _ in range(9)]empty_cells = []  # 存储所有空白格的位置# **预处理**: 记录 board 里的数字,同时找到所有 "."for r in range(9):for c in range(9):if board[r][c] == ".":empty_cells.append((r, c))  # 记录空白格子else:num = board[r][c]rows[r].add(num)cols[c].add(num)boxes[(r // 3) * 3 + (c // 3)].add(num) #每个box存放9个数字# **回溯填充数独**def backtrack(index: int) -> bool:if index == len(empty_cells):  # **所有空白填完,返回 True**return Truer, c = empty_cells[index]  # 获取下一个空白格的位置box_id = (r // 3) * 3 + (c // 3)  # 计算当前格子属于哪个 3×3 方块for k in range(1, 10):num = str(k)if num not in rows[r] and num not in cols[c] and num not in boxes[box_id]:  # **判断是否可填**board[r][c] = numrows[r].add(num)cols[c].add(num)boxes[box_id].add(num)if backtrack(index + 1):  # **递归填下一个空白格**return True  # **成功填充数独**# **回溯**board[r][c] = "."rows[r].remove(num)cols[c].remove(num)boxes[box_id].remove(num)return False  # **如果 1-9 都无法填入,则回溯**backtrack(0)  # **从第 0 个空白格开始填**

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

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

相关文章

【C++项目实战】校园公告搜索引擎:完整实现与优化指南

&#x1f3ac; 个人主页&#xff1a;谁在夜里看海. &#x1f4d6; 个人专栏&#xff1a;《C系列》《Linux系列》《算法系列》 ⛰️ 道阻且长&#xff0c;行则将至 目录 &#x1f4da;一、项目概述 &#x1f4d6;1.项目背景 &#x1f4d6;2.主要功能 &#x1f4d6;3.界面展…

大数据技术之Spark优化

第 1 章 Spark 性能调优 问:spark 优化 第一句:我们可以从性能,算子,shuffle 过程以及 jvm 四个方面展开优化。 1 常规性能调优 1.1 常规性能调优一:最优资源配置 Spark 性能调优的第一步,就是为任务分配更多的资源,在一定范围内,增加资源的分配与性能的提升是成正…

【 Manus平替开源项目】

文章目录 Manus平替开源项目1 OpenManus1.1 简介1.2 安装教程1.3 运行 2 OWL2.1 简介2.2 安装教程2.3 运行 3 OpenHands&#xff08;原OpenDevin&#xff09;3.1 简介3.2 安装教程和运行 Manus平替开源项目 1 OpenManus 1.1 简介 开发团队: MetaGPT 核心贡献者&#xff08;5…

《Java SQL 操作指南:深入理解 Statement 用法与优化》

在 Java 数据库编程中&#xff0c;Statement 是用于执行 SQL 语句的接口&#xff0c;允许程序与数据库进行交互。本文将详细介绍 Statement 的基本概念、常见用法以及 PreparedStatement 和 CallableStatement 等相关接口。 1. Statement 基本介绍 Statement 接口继承了 AutoC…

FFMPEG录制远程监控摄像头MP4

手绘效果图 上图是录制功能的HTML前端页面&#xff0c;录制功能和解码视频放在一起。录制功能关键是录制(开始录制按钮)、停止录像按钮。当点击“录制”的时候则会开始录制MP4文件, 当点击停止的时候就会停止录制MP4。经过录制后&#xff0c;则会生成MP4,并放到我的RV1126的/tm…

数据类型及sizeof,进制转换

其实数据类型可以讲很多内容&#xff0c;这里看情况需要讲多久吧。 本篇基本都是理论。 目录 数据类型的分类 基本数据类型 构造数据类型 指针类型 空类型 计算数据类型或变量所占用的内存字节数 基本语法 进制转换 二进制 二进制的概念 二进制与十进制的转换 十六进…

网络安全之tcpdump工具

引言 wireshark是一款非常不错的抓包软件&#xff0c;在图形化界面占绝对统治地位&#xff1b;尽管其在字符界面下有些许选项可供使用&#xff0c;但终究不太方便&#xff0c;下面我再介绍一款NB的终端抓包工具 tcpdump 1、混杂模式 linux的网卡有混杂模式一说&#xff0c;当开…

建筑管理(2): 施工承包模式,工程监理,质量监督

文章目录 一. 施工承包模式1. 施工总承包模式1.1 施工总承包的特点1.2 施工总承包模式中的承包方 2. 平行承包模式3. 联合体与合作体承包模式 二. 工程监理1. 强制实行监理的工程范围1.1 国家重点建设工程1.2 大中型公用事业工程(重点)1.3 成片开发建设的住宅小区工程1.4 必须实…

[LeetCode热门100题]|137,260,268,面试17.19

1、137 只出现一次数字|| 1、题目描述 137 只出现一次数字||https://leetcode.cn/problems/single-number-ii/description/ 给你一个整数数组 nums &#xff0c;除某个元素仅出现 一次 外&#xff0c;其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。 你…

MySQL中有哪几种锁?

大家好&#xff0c;我是锋哥。今天分享关于【MySQL中有哪几种锁&#xff1f;】面试题。希望对大家有帮助&#xff1b; MySQL中有哪几种锁&#xff1f; 1000道 互联网大厂Java工程师 精选面试题-Java资源分享网 在MySQL中&#xff0c;锁是用来控制并发访问的机制&#xff0c;确…

外贸企业可以申请网络专线吗?

在对外业务不断扩大的情况下&#xff0c;外贸企业对网络的需求愈发迫切。稳定、快速的网络连接不仅是企业开展国际业务的基础&#xff0c;更是提升竞争力的关键。外贸企业是否可以申请网络专线&#xff1f;如何选择适合的外贸网络专线服务&#xff1f;本文将为您详细解答。 网络…

python笔记2

变量&#xff1a;含义 一个容器&#xff0c;计算机当中的存储空间。 可以理解为一个用于标识或引用数据的名字或标签。 作用&#xff1a; 可以通过定义一个变量来给需要使用多次的数据命名&#xff0c;就像一个标签一样。下次需要使用这个数据时&#xff0c;只需要通过这个变…

【算法】动态规划

⭐️个人主页&#xff1a;小羊 ⭐️所属专栏&#xff1a;Linux 很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~ 目录 持续更新中...1、常规动态规划Fibonacci数列杨辉三角最小花费爬楼梯孩子们的游戏 2、背包问题3、最长公共子序列4、最长递增子序列…

ECU BootLoader开发——Flash编程

我是穿拖鞋的汉子&#xff0c;魔都中坚持长期主义的汽车电子工程师。 老规矩&#xff0c;分享一段喜欢的文字&#xff0c;避免自己成为高知识低文化的工程师&#xff1a; 简单&#xff0c;单纯&#xff0c;喜欢独处&#xff0c;独来独往&#xff0c;不易合同频过着接地气的生活…

NetLink内核套接字案例分析

一、基础知识 Netlink 是 Linux 系统中一种内核与用户空间通信的高效机制&#xff0c;而 Netlink 消息是这种通信的核心载体。它允许用户态程序&#xff08;如网络配置工具、监控工具&#xff09;与内核子系统&#xff08;如网络协议栈、设备驱动&#xff09;交换数据&#xff…

Linux 配置静态 IP

一、简介 在 Linux CentOS 系统中默认动态分配 IP 地址&#xff0c;每次启动虚拟机服务都是不一样的 IP&#xff0c;因此要配置静态 IP 地址避免每次都发生变化&#xff0c;下面将介绍配置静态 IP 的详细步骤。 首先先理解一下动态 IP 和静态 IP 的概念&#xff1a; 动态 IP…

开源:LMDB 操作工具:lmcmd

目录 什么是 LMDB为什么编写 lmcmd安装方法如何使用 连接数据库命令列表 小结 1. 什么是 LMDB LMDB&#xff08;Lightning Memory-Mapped Database&#xff09;是一种高效的键值存储数据库&#xff0c;基于内存映射&#xff08;memory-mapping&#xff09;技术&#xff0c;提供…

进程管理:前后台切换

前后台切换 [rootxxx ~]# yum install -y xclock #安装xclock&#xff08;这里是用来解释前后台&#xff09; [rootxxx ~]# xclock -update 1 #前台运行&#xff08;如果把1改成2&#xff0c;就是秒针两秒走动一次&#xff09; [rootxxx ~]# xclock -update 1…

【CF】Day6——Codeforces Round 942 (Div. 2) BC + Codeforces Round 941 (Div. 2) C

B. Coin Games 题目&#xff1a; 思路&#xff1a; 虽然标签是博弈论&#xff0c;但我感觉更像一个找规律的思维题 由于题目告诉我们每次只能选U&#xff0c;那我们不妨来考虑选U会造成什么情况&#xff08;以下都为选中间U&#xff09; ①.UUU -3*U 此时选了U会导致两侧…

视频推拉流EasyDSS案例分析:互联网直播/点播技术与平台创新应用

随着互联网技术的快速发展&#xff0c;直播/点播平台已成为信息传播和娱乐的重要载体。特别是在电视购物领域&#xff0c;互联网直播/点播平台与技术的应用&#xff0c;不仅为用户带来了全新的购物体验&#xff0c;也为商家提供了更广阔的营销渠道。传统媒体再一次切实感受到了…