leetcode 搜索算法

在图的基本算法中，最初需要接触的就是图的遍历算法，根据访问节点的顺序，可分为广度优先搜索（BFS）和深度优先搜索（DFS）。

BFS

BFS 广度优先搜索的搜索过程是一层一层地进行遍历，每层遍历都以上一层遍历的结果作为起点，遍历一个距离能访问到的所有节点。需要注意的是，遍历过的节点不能再次被遍历。

第一层：
0 -> {6,2,1,5};

第二层：
6 -> {4}
2 -> {}
1 -> {}
5 -> {3}

第三层：
4 -> {}
3 -> {}

上述过程可知：是反复从新节点出发进行遍历操作。

每一轮遍历的节点都与根节点路径长度相同。设 d_i 表示第 i 个节点与根节点的路径长度，可以推导出结论：对于先遍历的节点 i 与后遍历的节点 j，有 d_i<=d_j。
利用上述结论，可以求解最短路径 最优解 问题：第一次遍历到目的节点，其所经过的路径为最短路径，如果继续遍历，之后再遍历到目的节点，所经过的路径就不是最短路径。

在程序实现 BFS 时需要考虑以下问题：

• 队列：用来存储每一轮遍历的节点。
• 标记：对于已经遍历的节点，需要标记，避免重复遍历。

DFS

深度优先搜索在得到一个新节点时立马对新节点进行遍历：
从节点 0 出发开始遍历，得到到新节点 6 时，立马对新节点 6 进行遍历，得到新节点 4；
如此反复以这种方式遍历新节点，直到没有新节点了，此时返回。返回到根节点 0 的情况是，继续对根节点 0 进行遍历，得到新节点 2，然后继续以上步骤。

从一个节点出发，使用 DFS 对一个图进行遍历时，能够遍历到的节点都是从初始节点可达的，DFS 常用来求解 可达性 问题。

在程序实现 DFS 时需要考虑以下问题：

• 栈：用来存储当前节点信息，当遍历新节点返回时能够继续遍历当前节点。也可以使用递归栈。
• 标记：对已经遍历过的节点进行标记。

Backtracking

回溯法属于 DFS ，主要用于求解 排列组合 问题。
在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

因为 Backtracking 不是立即就返回，而要继续求解，因此在程序实现时，需要注意对元素的标记问题：

• 在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复访问该元素；
• 但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素。

一般看到所有的组合问题，则用回溯法

Letter Combinations of a Phone Number

Leetcode : 17. Letter Combinations of a Phone Number(Medium)

思路：运用 DFS

def letterCombinations(self, digits):
    if not digits:
        return []
    
    dict = {'2': ['a', 'b', 'c'],
            '3': ['d', 'e', 'f'],
            '4': ['g', 'h', 'i'],
            '5': ['j', 'k', 'l'],
            '6': ['m', 'n', 'o'],
            '7': ['p', 'q', 'r', 's'],
            '8': ['t', 'u', 'v'],
            '9': ['w', 'x', 'y', 'z']}
    
    def dfs(d, string):
        if not d:
            res.append(string)
            return
        
        num = d[0]
        rest_num = d[1:]
        for char in dict[num]:
            dfs(rest_num, string+char)
            
    res = []
    dfs(digits, '')
    return res

Generate Parentheses

Leetcode : 22. Generate Parentheses(Medium)

思路：括号的长度是 2n，在 [1, 2n] 之间，左括号的数量必定是小于等于右括号的数量，但右括号的数量小于左括号的数量时，则终止递归。
因此用 DFS， left 代表左括号的数量，right 代表右括号的数量，如果左括号有剩余，就在结果上 + ‘(‘。

def generateParenthesis(self, n):
    res = []
    def dfs(left, right, string):
        if right < left:
            return 
        if left == 0 and right == 0:
            res.append(string)
        if left > 0:
            dfs(left-1, right, string + '(')
        if right > 0:
            dfs(left, right-1, string + ')')
    dfs(n, n, '')
    return res

Combination Sum

Leetcode : 39. Combination Sum(Medium)

思路：用 DFS，要注意的是每次循环遍历需要从当前位置之后开始遍历，否则会出现重复计算。
且 arr 不能用 arr.append, 会造成两种问题：

• 若在 dfs 的参数中用 arr.append, 相当于是 arr = arr.append, 执行后发现 arr 的类型变为了 NoneType。 因为 append 会修改 arr 本身，并且返回 None，不能把返回值再赋值给 a。
• 若在调用 dfs 之前，单独用 arr.append(cans[i])，会一直往 arr 里面加元素。
  因此需要用 arr+[cans[i]] 来追加元素。

def combinationSum(self, candidates, target):
    res = []
    def dfs(cans, tar, start, arr):
        if tar < 0:
            return 
        if tar == 0:
            res.append(arr)
            return 
        for i in range(start, len(cans)):
            if cans[i] <= tar:
                dfs(cans, tar-cans[i], i, arr+[cans[i]])
    
    dfs(candidates, target, 0, [])
    return res

Combination Sum II

Leetcode : 40. Combination Sum II(Medium)

思路：由于一个数字用多次，因此递归时要从 cans[i+1:] 开始

def combinationSum2(self, candidates, target):
    res = []
    def dfs(cans, tar, start, arr):
        if tar < 0:
            return 
        if tar == 0 and arr not in res:
            res.append(arr)
            return 
        for i in range(len(cans)):
            if cans[i] <= tar:
                dfs(cans[i+1:], tar-cans[i], i+1, arr+[cans[i]])
    candidates = sorted(candidates)
    dfs(candidates, target, 0, [])
    return res

Combination Sum III

Leetcode : 216. Combination Sum III(Medium)

def combinationSum3(self, k, n):
    res = []
    nums = [i for i in range(1, 10)]
    
    def dfs(nums, target, arr):
        if target < 0:
            return 
        if target == 0 and len(arr) == k and sorted(nums) not in res:
            res.append(arr)
            return
        for i in range(len(nums)):
            dfs(nums[i+1:], target-nums[i], arr + [nums[i]])
    
    dfs(nums, n, [])
    return res

Permutations

Leetcode : 46. Permutations(Medium)

数组元素不重复，排列组合。

def permute(self, nums):
    res = []
    def dfs(n, arr):
        if not n:
            res.append(arr)
            return 
        for i in range(len(n)):
            dfs(n[:i]+n[i+1:], arr+[n[i]])
        
    dfs(nums, [])
    return res

备注：不要用 pop()，会改变原数组，导致最后数组为空，直接 n[:i]+n[i+1:] 表示删除第 i 个数

Permutations II

Leetcode : 47. Permutations II(Medium)

数组元素重复，排列组合。

直接在上一题的基础上添加条件 if not n and arr not in res，会超时。
为了提交效率，可以先对 nums 排序，那么相同的元素会在一起，在遍历时，如果遇到相同的元素，其结果会和之前的元素相同，就不要重复递归了。由于添加了元素是否重复的判断，那么得到的 arr 便也不会重复了，因此 if not n 后面不用再接着判断 arr 是否存在于 res 中。

def permuteUnique(self, nums):=
    res = []
    def dfs(n, arr):
        if not n:
            res.append(arr)
            return 
        for i in range(len(n)):
            if i > 0 and n[i] == n[i-1]:
                continue
            dfs(n[:i]+n[i+1:], arr+[n[i]])
            
    nums.sort()
    dfs(nums, [])
    return res

N-Queens

Leetcode : 51. N-Queens(Hard)

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

N 皇后问题，需要使得任意两个皇后不能处于同一行、同一列或同一斜线上，打印出所有的解法。
思路：可以一行一行的，从左到右尝试皇后的摆放，若有冲突，则回溯。
可以使用一维数组简化摆放，例 a[0] = 2，表示第 1 行的第 2 列摆放皇后，这样可以无需判断两个皇后是否会处于同一行。
需要定义一个 check(i, j) 函数来判断 (i, j) 是否可以摆放皇后。

• 不在同一列
• 不在同一斜线，即若有两个皇后的位置为 (i1, j1) 和 (i2, j2), 不能有 (i1-i2) == (j1-j2) 的情况

def solveNQueens(self, n):
    """
    :type n: int
    :rtype: List[List[str]]
    """
    def check(i, j): # 判断第 i 个皇后能否放在第 j 列，由于是一行一行的放置，因此也就是能否放在第 i 行的第 j 列
        for k in range(i): # 与前 i-1 行进行比较 
            if board[k] == j or abs(k-i) == abs(board[k]-j): # 判断是否会和第 k 行的皇后在同一列或同一对角线
                return False
        return True
        
    def dfs(col, arr):
        if col == n:
            res.append(arr)
            return 
        for j in range(n): # 一行行的放皇后，每行的每列开始尝试
            if check(col, j): # 如果第 col 行的 第 j 列可以放置
                board[col] = j
                s = '.' * n # 初始化需要打印的结果
                dfs(col+1, arr+[s[:j]+'Q'+s[j+1:]])
    
    res = []
    board = [-1 for i in range(n)] # 初始化棋盘
    dfs(0, []) # 从第 0 行开始摆放棋子
    return res

N-Queens II

Leetcode : 52. N-Queens II(Hard)

上一题是输出所有的解决方案，该题只需要输出解决方案的个数

直接调用上一题的结果，输出长度即可。或者把 res 直接变为计数，提高效率。

def totalNQueens(self, n):
       def check(i, j):
           for k in range(i):
               if board[k] == j or abs(board[k]-j) == abs(k-i):
                   return False
           return True
       
       def dfs(col):
           if col == n:
               self.res += 1
               return 
           for j in range(n):
               if check(col, j):
                   board[col] = j
                   dfs(col+1)
       
       self.res = 0
       board = [-1 for i in range(n)]
       dfs(0)
       return self.res

Combinations

Leetcode : 77. Combinations(Medium)

def combine(self, n, k):
    res = []
    nums = [i for i in range(1, n+1)]
    def dfs(nums, k, arr):
        if len(arr) == k and sorted(arr) not in res:
            res.append(arr)
            return 
        for i in range(len(nums)):
            dfs(nums[i+1:], k, arr+[nums[i]])
            
    dfs(nums, k, [])
    return res

Subsets

Leetcode : 78. Subsets(Medium)

def subsets(self, nums):
    res = []
    def dfs(nums, arr):
        res.append(arr)
        for i in range(len(nums)):
            dfs(nums[i+1:], arr+[nums[i]])
    
    dfs(sorted(nums), [])
    return res

Subsets II

Leetcode : 90. Subsets II(Medium)

nums 变为包含重复数字，其余与上题一样。
只需要在 res.append(arr) 之前添加判断条件 if arr not in res 即可。

Word Search

Leetcode : 79. Word Search(Medium)

思路： 先找到第一个字母的位置，再从此位置上下左右 去 DFS，要注意的是已经访问过的节点需要标记，否则之后会再访问到该节点。并且在遍历完之后需要把该节点改回原来的值，不然可能有其他的路径到达 word，board 的节点值不能改变。

def exist(self, board, word):
    """
    :type board: List[List[str]]
    :type word: str
    :rtype: bool
    """
    n = len(board)
    m = len(board[0])
    visited = [[False for _ in range(m)] for _ in range(n)]
    
    def dfs(i, j, k): # 找第 k 个字母
        if k == len(word):
            return True
        if i-1 >= 0 and not visited[i-1][j] and board[i-1][j] == word[k]: # 向上
            visited[i-1][j] = True
            if dfs(i-1, j, k+1):
                return True
            visited[i-1][j] = False
        if j-1 >= 0 and not visited[i][j-1] and board[i][j-1] == word[k]: # 向左
            visited[i][j-1] = True
            if dfs(i, j-1, k+1):
                return True
            visited[i][j-1] = False
        if i+1 < n and not visited[i+1][j] and board[i+1][j] == word[k]: # 向下
            visited[i+1][j] = True
            if dfs(i+1, j, k+1):
                return True
            visited[i+1][j] = False
        if j+1 < m and not visited[i][j+1] and board[i][j+1] == word[k]: # 向右
            visited[i][j+1] = True
            if dfs(i, j+1, k+1):
                return True
            visited[i][j+1] = False
                 
    for i in range(n):
        for j in range(m):
            if board[i][j] == word[0]:
                visited[i][j] = True
                if dfs(i, j, 1):
                    return True
                visited[i][j] = False
    return False

Restore IP Addresses

Leetcode : 93. Restore IP Addresses(Medium)

Given a string containing only digits, restore it by returning all possible valid IP address combinations.
Input: “25525511135”
Output: [“255.255.11.135”, “255.255.111.35”]

思路：合法 IP 地址分为四部分，每个部分的长度为 1-3 位， 大小为 0-255 之间

def restoreIpAddresses(self, s):
    if len(s) > 12:
        return []
    res = []
    def dfs(s, ip):
        if not s and len(ip) == 4:
            res.append('.'.join(ip)) 
            return 
        for i in range(1, 4): 
            if i <= len(s):
                number = int(s[:i]) # 此处为了防止出现两位数以上，0 开头的情况。
                if number <= 255 and str(number) == s[:i]:
                    dfs(s[i:], ip+[s[:i]])
    dfs(s, [])
    return res

Palindrome Partitioning

Leetcode : 131. Palindrome Partitioning (Medium)

所有可能的结果：回溯法

def partition(self, s):
    self.is_palindorm = lambda s : s == s[::-1]
    res = []        
    def dfs(s, palindorm):
        if not s:        	
            res.append(palindorm)
            return
        for i in range(len(s)):
            if self.is_palindorm(s[:i+1]):
                dfs(s[i+1:], palindorm + [s[:i+1]])
    dfs(s, [])
    return res

搜索练习

Word Ladder

Leetcode : 127. Word Ladder (Medium)

思路： 用队列保存每个能够有效变换的字符串，再遍历这个字符串的每个字符，将其每个字符变为 26 个字母中的任意一个，并保证新生成的 newWord ！= 原来的 word，如果 newWord 在 wordList 中，就把该 newWord 从 wordSet 中删除，并将 queue 的长度 +1, 最后的终止条件是有一个 word == endWord，此时返回长度，若到最后都没有找到这个 word，则返回 0。

使用到队列 queue 是因为需要先进先出，先变换到的词应该要先进行下一次变换，若 pop() 最后一个，可能会是新加进去的元素，这个时候已经进行了新的改变。

改进：

1. 若直接用 wordList 会超时，而 set 比 list 快很多，因此将 wordList 转为 set。
2. 替换字母时不需要用到 26个字母，只需要用到 wordList 中包含的字母即可，先得到所有不同的字母 alphas = set(‘’.join(wordList))

def ladderLength(self, beginWord, endWord, wordList):
    if endWord not in wordList or not wordList:
        return 0
    wordSet = set(wordList)
    alphas = set(''.join(wordSet))
    queue = [[beginWord, 1]]
    while queue:
        word, length = queue.pop(0)
        if word == endWord:
            return length
        for i in range(len(word)):
            for c in alphas:
                newWord = word[:i] + c + word[i+1:]
                if newWord in wordSet and newWord != word:
                    wordSet.remove(newWord)
                    queue.append([newWord, length+1])
    return 0

Surrounded Regions

Leetcode : 130. Surrounded Regions (Medium)

思路：从边缘开始搜索，即搜索第一行和最后一行，第一列和最后一列，遇到 ‘O’，就搜索 ‘O’ 周围每条边的元素，并将 ‘O’ 置换为 ‘D’，这样的话边缘上的 ‘O’ 及与边缘相连的 ‘O’ 都会被置换为 ‘D’， 而内部被围住的 ‘O’ 并没有发生改变。 再遍历一遍 board，将 ‘O’ 全部变为 ‘X’，将 ‘D’ 全部变为 ‘O’。

def solve(self, board):
    if not board:
        return
    n = len(board)
    m = len(board[0])
    
    def dfs(i, j):
        if i < 0 or i >= n or j < 0 or j >= m or board[i][j] != 'O':
            return 
        board[i][j] = 'D'
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)
        
    for j in range(m): # 第0行和最后一行
        if board[0][j] == 'O':
            dfs(0, j)
        if board[n-1][j] == 'O':
            dfs(n-1, j)
    
    for i in range(n): # 第0列和最后一列
        if board[i][0] == 'O':
            dfs(i, 0)
        if board[i][m-1] == 'O':
            dfs(i, m-1)
    
    for i in range(n):
        for j in range(m):
            if board[i][j] == 'D':
                board[i][j] = 'O'
            else:
                board[i][j] = 'X'

Clone Graph

Leetcode : 133. Clone Graph (Medium)

Number of Islands

Leetcode : 200. Number of Islands (Medium)

思路： 和 130 类似，遍历一遍矩阵，遇到 ‘1’ 之后，就搜索 ‘1’ 周围的元素，并将 ‘1’ 变为 ‘0’，主函数中每调用一次 dfs，说明出现了一个新的 island，则让 cnt+1

def numIslands(self, grid):
    if not grid:
        return 0
    cnt = 0
    n = len(grid)
    m = len(grid[0])
    
    def dfs(i, j):
        if i < 0 or i >= n or j < 0  or j >= m or grid[i][j] != '1':
            return 
        grid[i][j] = '0'
        dfs(i-1, j)
        dfs(i+1, j)
        dfs(i, j+1)
        dfs(i, j-1)
    
    for i in range(n):
        for j in range(m):
            if grid[i][j] == '1':
                dfs(i, j)
                cnt += 1
    return cnt

Course Schedule

Leetcode : 207. Course Schedule (Medium)