【基础算法精讲-学习记录】回溯3

视频学习记录

https://www.bilibili.com/video/BV1mY411D7f6?

• 以模拟某种情况下的全排列为基础的排列型回溯，核心是通过bool列表或者集合记录已走的路径。

例题和课后作业代码记录

46. 全排列

https://leetcode.cn/problems/permutations/description/

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        path = []
        not_on_path = {}
        n = len(nums)
        def dfs(index:int, not_on_path:set):
            if index == n:
                nonlocal ans, path 
                ans.append(path.copy())
                return 
            for num in not_on_path:
                path.append(num)
                dfs(index+1, not_on_path-{num})
                path.pop()
        dfs(0, set(nums))
        return ans

51. N 皇后

https://leetcode.cn/problems/n-queens/description/

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        row = [0]*n 
        ans = []
        row_plus_col = set()
        row_minus_col = set()
        left_col = [True]*n

        def dfs(row_index:int):
            if row_index==n:
                ans.append(["."*col + "Q" + "."*(n-col-1) for col in row])
                return
            
            for col, ok in enumerate(left_col):
                if ok and (not row_index+col in row_plus_col) and (not row_index-col+n in row_minus_col):
                    row[row_index] = col 
                    row_plus_col.add(row_index+col)
                    row_minus_col.add(row_index-col+n)
                    left_col[col] = False
                    dfs(row_index+1)
                    left_col[col] = True
                    row_plus_col.remove(row_index+col)
                    row_minus_col.remove(row_index-col+n)
        dfs(0)
        return ans

52. N 皇后 II

https://leetcode.cn/problems/n-queens-ii/description/

class Solution:
    def totalNQueens(self, n: int) -> int:
        row = [0]*n 
        ans = 0
        row_plus_col = set()
        row_minus_col = set()
        left_col = [True]*n

        def dfs(row_index:int):
            if row_index==n:
                nonlocal ans
                ans += 1
                return
            
            for col, ok in enumerate(left_col):
                if ok and (not row_index+col in row_plus_col) and (not row_index-col+n in row_minus_col):
                    row[row_index] = col 
                    row_plus_col.add(row_index+col)
                    row_minus_col.add(row_index-col+n)
                    left_col[col] = False
                    dfs(row_index+1)
                    left_col[col] = True
                    row_plus_col.remove(row_index+col)
                    row_minus_col.remove(row_index-col+n)
        dfs(0)
        return ans

357. 统计各位数字都不同的数字个数

https://leetcode.cn/problems/count-numbers-with-unique-digits/description/

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        can_use_num = [True]*10
        ans = 0
        # print(can_use_num)
        def dfs(num_index:int, started:bool):
            if num_index == n:
                nonlocal ans 
                ans += 1
                return 
            
            for i in range(10):
                if i == 0 and not started:
                    dfs(num_index+1, started)
                elif can_use_num[i]:
                    can_use_num[i] = False 
                    dfs(num_index+1, True)
                    can_use_num[i] = True 
        dfs(0, False)
        return ans

2850. 将石头分散到网格图的最少移动次数

https://leetcode.cn/problems/minimum-moves-to-spread-stones-over-grid/description/

class Solution:
    def minimumMoves(self, grid: List[List[int]]) -> int:
        froms = []
        tos = []
        for row_index, row in enumerate(grid):
            for col, num in enumerate(row):
                if num == 0:
                    tos.append((row_index, col))
                elif num > 1:
                    froms.append((row_index, col))
        
        n = len(tos)
        ans = inf
        froms_enable = [True]*len(froms)
        def dfs(to_index:int, cur_sum:int):
            if to_index == n:
                nonlocal ans
                ans = cur_sum # 比小环节提前到进入dfs前剪枝
                return 

            to_x, to_y = tos[to_index]
            for i, (f_x, f_y) in enumerate(froms):
                if not froms_enable[i]:
                    continue 
                # print(f_x, f_y, to_x, to_y)
                new_path = cur_sum + abs(f_x-to_x) + abs(f_y-to_y)
                if new_path < ans:
                    grid[f_x][f_y] -= 1
                    if grid[f_x][f_y] == 1:
                        froms_enable[i] = False
                    dfs(to_index+1, new_path)
                    if grid[f_x][f_y] == 1:
                        froms_enable[i] = True 
                    grid[f_x][f_y] += 1
        dfs(0, 0)
        return ans