当前位置： 首页 > article >正文

代码随想录-回溯

article 2025/3/15 6:48:02
  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())
            return
        for i in range(start_index, len(s)):
            subset = s[start_index:i+1]
            if subset != subset[::-1]:
                continue
            else:
                result.append(subset) #result里面其实存的还是i的索引，只不过是有选择地存储
            self.findValue(i+1, s, result, final)
            result.pop()
        return
            
    def partition(self, s: str) -> List[List[str]]:
        start_index = 0
        result = []
        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]:
                    continue
            if nums[i] in used:
                continue
            result.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 = 0
        result = []
        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())
            return
        for i in range(len(nums)):
            if used[i]==True:
                continue
            else:
                result.append(nums[i])
                used[i]=True
                self.findValue(nums,used, result,final)
                result.pop()
                used[i]=False
        return


    def 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 False
        r = row-1
        c = col-1
        #左上对角线
        while r>=0 and c >=0:
            if board[r][c] == "Q":
                return False
            r -=1
            c -=1
        #右上对角线
        r = row-1
        c = col+1
        while r>=0 and c <n:
            if board[r][c] == "Q":
                return False
            r -=1
            c +=1
        return True

    
    def findValue(self, row, board,final,n):
        if row == n:
            final.append(["".join(row) for row in board]) ##注意这里中括号的位置
            return
        for 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]="."
        return


    def solveNQueens(self, n: int) -> List[List[str]]:
        board = [["."]*n for _ in range(n)]
        final = []
        row = 0
        self.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 False
        for r in range(len(board)):
            if board[r][col] == number:
                return False
        left_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 False
        return True


    def 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  #填充完毕，没有地方等于.,返回True

    def 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 True
            
            r, 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] = num
                    rows[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.kler.cn/a/585192.html

相关文章：

  • 如何优雅地将Collection转为Map？
  • 平安养老险广西分公司2025年“3∙15”金融消费者权益教育宣传活动暨南湖公园健步行活动
  • 【C语言】编译和链接详解
  • Redis的缓存雪崩、缓存击穿、缓存穿透与缓存预热、缓存降级
  • 2025-03-15 学习记录--C/C++-PTA 练习3-4 统计字符
  • 【3D视觉学习笔记2】摄像机的标定、畸变的建模、2D/3D变换
  • python如何获取三个小时之前的时间并输出
  • MATLAB 控制系统设计与仿真 - 26
  • python画图文字显示不全+VScode新建jupyter文件
  • 构建分类树（ElementPlus的二级数据模型）
  • [S32K]SPI
  • Python 语言因其广泛的库与框架资源，诸如 `requests`、`BeautifulSoup
  • 证券交易系统的流程
  • pytorch lightning ddp 逆天分配显存方式
  • 关于重构分析查询界面的思考（未完）
  • 基于Hadoop的城市道路交通数据的可视化分析-Flask
  • 前端技巧第五期JavaScript函数
  • C++ 内存管理
  • NFC碰一碰发视频-nfc碰一碰发视频拓客系统 实体商家碰一碰发视频引流获客
  • AI辅助工具-通义灵码