蓝桥杯 第十一天 回溯法(2)

目录

1.93. 复原 IP 地址 - 力扣(LeetCode) (leetcode-cn.com)

2.78. 子集 - 力扣(LeetCode) (leetcode-cn.com)

3.90. 子集 II - 力扣(LeetCode) (leetcode-cn.com)

4.491. 递增子序列 - 力扣(LeetCode) (leetcode-cn.com)

5.46. 全排列 - 力扣(LeetCode) (leetcode-cn.com)

6.47. 全排列 II - 力扣(LeetCode) (leetcode-cn.com)

7.51. N 皇后 - 力扣(LeetCode) (leetcode-cn.com)

8.37. 解数独 - 力扣(LeetCode) (leetcode-cn.com)


1.93. 复原 IP 地址 - 力扣(LeetCode) (leetcode-cn.com)

切割问题

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        results=[]
        def dfs(rest,times,path):
            if times==4:
                if not rest:
                    results.append(path[:-1])
                return
            for i in range(1,len(rest)+1):
                if rest[:i]=='0' or (rest[0]!='0' and 0<int(rest[:i])<=255):
                    dfs(rest[i:],times+1,path+rest[:i]+'.')
            return
        dfs(s,0,"")
        return results
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        results=[]
        def dfs(s,index,path,times):
            if times==4:
                if index==len(s):
                    results.append(path[:-1])
                return
            for i in range(index,len(s)):
                if s[index:i+1]=='0' or (s[index]!='0' and 0<int(s[index:i+1])<=255):
                    dfs(s,i+1,path+s[index:i+1]+'.',times+1)
            return
        dfs(s,0,"",0)
        return results

2.78. 子集 - 力扣(LeetCode) (leetcode-cn.com)

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        results=[]
        def dfs(rest,path):
            if path not in results:
                results.append(path)
            if not rest:
                return
            for i in range(len(rest)):
                dfs(rest[i+1:],path+rest[:i+1])
                dfs(rest[i+1:],path)
        dfs(nums,[])
        return results
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        results=[]
        def dfs(nums,index,path):
            results.append(path)
            for i in range(index,len(nums)):
                dfs(nums,i+1,path+[nums[i]])
        dfs(nums,0,[])
        return results

3.90. 子集 II - 力扣(LeetCode) (leetcode-cn.com)

for循环后面的第一句话,堪称防重复的精髓

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        results=[]
        nums.sort()
        def dfs(nums,index,path):
            results.append(path)
            for i in range(index,len(nums)):
                if i>index and nums[i]==nums[i-1]:
                    continue
                dfs(nums,i+1,path+[nums[i]])
        dfs(nums,0,[])
        return results

4.491. 递增子序列 - 力扣(LeetCode) (leetcode-cn.com)

用哈希表防止重复

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        results=[]
        def dfs(nums,index,path):
            if len(path)>=2:
                results.append(path)
            if index==len(nums):
                return
            hashtable=[0 for i in range(-101,101)]
            for i in range(index,len(nums)):
                # if i>index and nums[i]==nums[i-1]:
                #     continue
                if hashtable[nums[i]]!=0:
                    continue
                if not path:
                    hashtable[nums[i]]+=1
                    dfs(nums,i+1,path+[nums[i]])
                else:
                    if nums[i]>=path[-1]:
                        hashtable[nums[i]]+=1
                        dfs(nums,i+1,path+[nums[i]])
            return
        dfs(nums,0,[])
        return results

5.46. 全排列 - 力扣(LeetCode) (leetcode-cn.com)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        results=[]
        hashtable=[False for i in range(len(nums))]
        def dfs(nums,path):
            if len(path)==len(nums):
                results.append(path)
                return
            for i in range(len(nums)):
                if not hashtable[i]:
                    hashtable[i]=True
                    dfs(nums,path+[nums[i]])
                    hashtable[i]=False
            return
        dfs(nums,[])
        return results

6.47. 全排列 II - 力扣(LeetCode) (leetcode-cn.com)

一个很奇妙的bug,出现在localhash那里

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        results=[]
        hashtable=[False for i in range(len(nums))]
        def dfs(nums,path):
            if len(path)==len(nums):
                results.append(path)
                return
            localhash=[False for i in range(-11,11)]
            for i in range(len(nums)):
                if localhash[nums[i]]==True:
                    continue
                if not hashtable[i]:
                    localhash[nums[i]]=True
                    hashtable[i]=True
                    dfs(nums,path+[nums[i]])
                    hashtable[i]=False
            return
        dfs(nums,[])
        return results

7.51. N 皇后 - 力扣(LeetCode) (leetcode-cn.com)

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        result=[]
        table=[-1 for i in range(n)]
        
        def check(row,col):
            if col in table:
                return False
            for i in range(row):
                if abs(row-i)==abs(col-table[i]):
                    return False
            return True
        def dfs(level,path):
            nonlocal result
            if level==n:
                result.append(path)
                return
            for i in range(n):
                if check(level,i):
                    currow="."*i+"Q"+"."*(n-i-1)
                    table[level]=i
                    dfs(level+1,path+[currow])
                    table[level]=-1
        dfs(0,[])
        return result

8.37. 解数独 - 力扣(LeetCode) (leetcode-cn.com)

大型N皇后

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def backtrack(board):
            for i in range(len(board)):  #遍历行
                for j in range(len(board[0])):  #遍历列
                    if board[i][j] != ".": continue
                    for k in range(1,10):  #(i, j) 这个位置放k是否合适
                        if isValid(i,j,k,board):
                            board[i][j] = str(k)  #放置k
                            if backtrack(board): return True  #如果找到合适一组立刻返回
                            board[i][j] = "."  #回溯,撤销k
                    return False  #9个数都试完了,都不行,那么就返回false
            return True  #遍历完没有返回false,说明找到了合适棋盘位置了
        def isValid(row,col,val,board):
            for i in range(9):  #判断行里是否重复
                if board[row][i] == str(val):
                    return False
            for j in range(9):  #判断列里是否重复
                if board[j][col] == str(val):
                    return False
            startRow = (row // 3) * 3
            startcol = (col // 3) * 3
            for i in range(startRow,startRow + 3):  #判断9方格里是否重复
                for j in range(startcol,startcol + 3):
                    if board[i][j] == str(val):
                        return False
            return True
        backtrack(board)

上一篇:redis慢日志查询


下一篇:FastAPI-7-参数额外的校验