【leetcode52-55图论、56-63回溯】

图论【52-55】

200.岛屿数量

深度优先搜索

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]  # 四个方向，左，右，下，上
        result = 0

        def dfs(x, y):
            for d in dirs:
                nextx = x + d[0]
                nexty = y + d[1]
                if nextx < 0 or nextx >= m or nexty < 0 or nexty >= n:  # 越界了，直接跳过
                    continue
                if not visited[nextx][nexty] and grid[nextx][nexty] == '1':  # 没有访问过的同时是陆地的
                    visited[nextx][nexty] = True
                    dfs(nextx, nexty)
        
        for i in range(m):
            for j in range(n):
                if not visited[i][j] and grid[i][j] == '1':  #没有参观过& 陆地
                    visited[i][j] = True
                    result += 1  # 遇到没访问过的陆地，+1
                    dfs(i, j)  # 将与其链接的陆地都标记上 true

        return result

994.腐烂的句子

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        row, col, time = len(grid), len(grid[0]), 0
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        queue = []
        #把腐烂的橘子加到队列
        for i in range(row):
            for j in range(col):
                if grid[i][j] == 2:
                    queue.append((i, j, time))
        # 广度搜索
        while queue:
            i, j, time = queue.pop(0)
            for di, dj in directions:
                if 0 <= i + di < row and 0 <= j + dj < col and grid[i + di][j + dj] == 1:
                    grid[i + di][j + dj] = 2
                    queue.append((i + di, j + dj, time + 1))
        # 如果仍然有新鲜橘子，返回-1
        for row in grid:
            if 1 in row:
            	return -1

        return time

207.课程表

from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        indegrees = [0 for _ in range(numCourses)]
        adjacency = [[] for _ in range(numCourses)]
        queue = deque()
        # 得到每个节点的入度表，
        for cur, pre in prerequisites:
            indegrees[cur] += 1
            adjacency[pre].append(cur)
        # 得到所有入度为0的节点【没有结点能得到入度为0的节点】
        for i in range(len(indegrees)):
            if not indegrees[i]: 
                queue.append(i)

        # BFS 
        while queue:
            pre = queue.popleft()
            numCourses -= 1
            for cur in adjacency[pre]:
                indegrees[cur] -= 1
                if not indegrees[cur]:
                    queue.append(cur)
        return not numCourses

208.实现True（前缀树）

isWord 表示从根节点到当前节点为止，该路径是否形成了一个有效的字符串。
children 是该节点的所有子节点。

class Node(object):
    def __init__(self):
        self.children = collections.defaultdict(Node)
        self.isword = False
        
class Trie(object):

    def __init__(self):
        self.root = Node()

    def insert(self, word):
        current = self.root
        for w in word:
            current = current.children[w]
        current.isword = True

    def search(self, word):
        current = self.root
        for w in word:
            current = current.children.get(w)
            if current == None:  #路径断了
                return False
        return current.isword

    def startsWith(self, prefix):
        current = self.root
        for w in prefix:
            current = current.children.get(w)
            if current == None:
                return False
        return True

回溯【56-63】

46.全排列

class Solution:
    def permute(self, nums):
        result = []
        self.backtracking(nums, [], [False] * len(nums), result)
        return result

    def backtracking(self, nums, path, used, result):
        if len(path) == len(nums):
            result.append(path[:])
            return
            
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            self.backtracking(nums, path, used, result)
            path.pop()
            used[i] = False

78.子集

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        self.backtracking(nums, 0, [], res)
        return res
    
    def backtracking(self, nums, startindex, path, res):
        res.append(path[:])
        for i in range(startindex, len(nums)):
            path.append(nums[i])
            self.backtracking(nums, i+1, path, res)
            path.pop()

17.电话号码的字母组合

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:

        self.mapping = {2:'abc', 3:'def', 4:'ghi', 
                    5:'jkl',6:'mno',7:'pqrs',8:'tuv',9:'wxyz'}
        res = []
        if len(digits)==0:
            return res
        self.backtracking(digits, 0, [],res)
        return res

    def backtracking(self, digits, startindex, path, res):    
        if len(path) == len(digits):
            res.append(''.join(path))  #将结果转换成str
            return 

        #树宽是mapping[index],树高是len(digits)
        ss = self.mapping[int(digits[startindex])]
        for i in ss:
            path.append(i)
            self.backtracking(digits,startindex+1,path,res)
            path.pop()

39.组合总和

candidate元素不重复，一个元素可以重复选取

'''控制重复选取'''
self.backtracking(candidates, i, path, res, target)

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        self.backtracking(candidates, 0, [],res,target)
        return res
    
    def backtracking(self, candidates, startindex, path, res, target):
        if target == 0:
            res.append(path[:])
            return 

        if target < 0:
            return 
        
        for i in range(startindex, len(candidates)):
            path.append(candidates[i])
            target -=  candidates[i]
            self.backtracking(candidates, i, path, res, target)
            path.pop()
            target += candidates[i]

22.括号生成

什么时候可以向下搜索：

1. 插入数量 < n
2. 左括号插入数量 > 右括号数量

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        self.backtracking(n, 0, 0, '', res)
        return res

    def backtracking(self, n, left, right, path, res):
        if left == n and right == n:
            res.append(path)
            return
        
        if left<n:
            self.backtracking(n, left+1, right, path+'(', res )
        
        if left > right :
            self.backtracking(n, left, right+1, path+')', res)

79.单词搜索

递归参数
当前元素在矩阵 board 中的行列索引 i 和 j ，当前目标字符在 word 中的索引 k 。
：
终止条件

1. 返回 false ： (1) 行或列索引越界 (2) 当前矩阵元素与目标字符不同 或 (3) 当前矩阵元素已访问过
2. 返回 true ： k = len(word) - 1 ，即字符串 word 已全部匹配。

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]: 
                return False
            if k == len(word) - 1: 
                return True

            board[i][j] = ''   #代表当前元素已经访问过，防止反复访问
            res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
            board[i][j] = word[k]
            return res
            
    #遍历i，j，找到word[0]
        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0): #当前在board[i][j],单词在word[k]
                    return True
        return False

131.分割回文串

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res =[]
        self.backtracking(s, 0, [], res)
        return res
    
    def backtracking(self, s, startindex, path, res):
        if startindex == len(s):
            res.append(path[:])
            return
        
        for i in range(startindex, len(s)):
            ss = s[startindex:i+1]
            if ss == ss[::-1]:   #是回文， 再递归
                path.append(ss)
                self.backtracking(s, i+1, path, res )
                path.pop()

51. N 皇后

棋盘的宽度就是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[:])  # 棋盘填满，将当前解加入结果集
            return

        for 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 - 1
        while i >= 0 and j >= 0:
            if chessboard[i][j] == 'Q':
                return False  # 左上方向已经存在皇后，不合法
            i -= 1
            j -= 1

        # 检查 135 度角是否有皇后
        i, j = row - 1, col + 1
        while i >= 0 and j < len(chessboard):
            if chessboard[i][j] == 'Q':
                return False  # 右上方向已经存在皇后，不合法
            i -= 1
            j += 1

        return True  # 当前位置合法