LC吐血整理之DFS&BFS篇

Posted on | In
人生苦短 我学python

所有题解方法请移步 github-Leecode_summary

200. 岛屿数量

三个字：不会做，没有什么好的思路，虽然理解了题目的意思，但是真的没法用程序表达出来，也是一种绝望啊~ 话不多说，直接进入题解，讲一讲学到的知识吧:　参考资料：Flood Fill 今日份重要的Tips:
以下针对的都是无向图，且图已经用邻接矩阵表示。

DFS:

  • 概念理解

    DFS(Deep First Search) 深度优先搜索：是一种用于遍历或者搜索树和图的算法，属于盲目搜索。@wiki 　　沿着树的深度遍历树的节点，尽可能深的搜索树的分支，如果没有节点可以搜索，将回溯到发现该节点的“源节点”，直到访问完从源节点可达到的所有节点。(递归下去，回溯上来) 　　此刻若发现还有未访问的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

  • 实现方法
    类似于树的先序遍历 使用堆栈结构-先进后出 实例：寻找迷宫出口（不撞南墙不回头）,目标明确，就是为了找出口
  • 算法思路 python
    递归实现 ⬇
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    '''
    假设graph大小为m*n 
    graph[i][j]: 情况一：有值   比如 1:可访问单元  0：该单元不可访问 
                 情况二：无值（所有单元均可访问，也就是迷宫没有障碍物）
    marked[m][n]: 用于标记graph上哪些点走过
    directions: 用于实现左上右下的移动
    state(graph[i][j]) = S：graph[i][j]满足某种状态/条件S
    '''
    directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    def solution(graph):
        marked = [[0 for _ in range(m)] for ) in range(n)]     
        # 图不连通需要遍历整张图
        for i in range(m):
            for j in range(n):
                //相应dfs条件//
                dfs(graph, marked, i, j)
    def dfs(graph, marked, i, j):
        marked[new_i][new_j] = 1
        if state(graph[i][j]) = S：
         // 相应处理
         # 接下来进行DFS搜索
        for direc in directions:
            new_i = i+direc[0]
            new_j = j+direc[1]
            if (0<=new_i<m) and (0<=new_j<n) and not marked[new_i][new_j] and graph[new_i][new_j] == 1：
                dfs(graph, marked, new_i, new_j)
                # marked[new_i][new_j] = 1 是否需要这一步视情况而定
    实际上递归非常消耗内存，如果graph过大，容易发生溢出，DFS也可用stack实现queue.append() queue.pop()先进后出，具体可参考BFS

BFS:

  • 概念理解

    BFS(Breath First Search) 广度优先搜索：搜索树和图的算法，也是一种盲目搜素。@wiki 　　BFS从树的宽度遍历树的节点

  • 实现方法
    类似树的层次遍历
    使用队列结构（先进先出）
    实例：寻找迷宫出口的最短路径 ，大范围搜索

  • 算法思路 python 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    '''
    假设graph大小为m*n 
    graph[i][j]: 情况一：有值   比如 1:可访问单元  0：该单元不可访问 
                 情况二：无值（所有单元均可访问，也就是迷宫没有障碍物）
    marked[m][n]: 用于标记graph上哪些点走过
    directions: 用于实现左上右下的移动
    state(graph[i][j]) = S：graph[i][j]满足某种状态/条件S
    '''
    from collections import deque    # deque：双向队列
    def bfs(graph, marked):
        marked = [[0 for _ in range(m)] for ) in range(n)]     
        # 如果图不连通，仅靠一次搜索无法遍历整张图，需要外循环（14-17可删）
        for i in range(m):
            for j in range(n):
                //相应 graph[i][j]条件//
                //相应处理//
                queue = deque()
                queue.append((i, j))    # 从队列右侧添加
                marked[i][j] = 1      #  进队列就标记已访问
                while queue:
                    x, y = queue.popleft()
                    if state(graph[i][j]) = S: 
                      //相关处理//
                    for direc in directions:
                        new_x = x + direc[0]
                        new_y = y + direc[1]
                        if (0<=new_x<m) and (0<=new_y<n) and not marked[new_x][new_y] and graph[new_x][new_y] == 1：
                            queue.append((new_x, new_y))
                            marked[new_x][new_y] = 1

    IDDFS:

  • 概念理解

    IDDFS(iterative deepening depth-first search (IDS or IDDFS)) 是对状态空间的搜索策略，它重复地运行一个有深度限制的DFS，每次运行结束后，增加深度并迭代，直到找到目标状态。@wiki 　　IDDFS 与BFS有同样的时间复杂度，而空间复杂度远优。（这一点也可以从第130题体现出来）
    　　IDDFS 第一次访问节点的累积顺序是广度优先的。

  • 实现方法
    迭代过程中记录深度
    贴几个帖子看看吧，时间有限，我也不深究了
    迭代深化深度优先搜索（IDDFS）

总结

两种搜索方法都属于盲目搜索，都不是很难，理解之后就好好的做下面的题吧，不要看题解啦 !

130.被围绕的区域

不得不说，总结一下DFS和BFS还是挺有用的，今天做题很迅速 (假的，今天是的是队列去存储 ‘X’2‘O’ 的单元格。
今日份的small Tips: 关于deque基本操作，有机会再补充 

1
2
3
4
5
6
7
8
9
# deque 为双向队列
from collections import deque
queue = deque()
# 在双向队列的右边/左边添加
queue.append() / queue.appendleft()
# 删除所有queue元素
queue.clear()
# 在双向队列的右边/左边删除并返回一个元素
queue.pop() / queue.popleft()

127.单词接龙

踩坑记录：

是这样的，刚开始看到关键词-“找 最短 转换序列”，瞬间想到用BFS求最短路径去做，但在做的过程中发现用队列BFS方法似乎没办法轻松的求深度，也就是这个最短路径到底是多短，后来尝试了记录每一层的进队列出队列数去计算深度，写是写出来了，无奈运行第30个测试用例的时候超出时长限制，我太难了… 　　踩了几个坑，对BFS有更深的了解：

1. 循环中谨慎删除列表元素（这个真的是重点，输出死活不对，排查了好久）
1
2
3
4
5
6
7
8
9
10
11
>>> a = [1,2,3,4]
>>> for i in a:           /   for i in a[::-1]:
...        a.remove(i)            a.remove(i)
...        print(a)               print(a) 
[2, 3, 4]    
[2, 3]
期望输出：# 其实是期望来一个删一个
[2, 3, 4]
[3, 4]
[4]
[]
  • 解决方案： 　　1. 定义一个空列表用来保存for循环中需要删除的值，出循环之后统一remove()
    　　2. 倒序删除（推荐！）
2. 队列的赋值操作
1
2
3
4
5
6
7
8
queue = deque()
queue_next = deque()
for i in range(5):
    queue.append(i)
queue_next = queue
queue_next:  deque([0, 1, 2, 3, 4])
queue.pop()
queue_next:  deque([0, 1, 2, 3])

以上涉及到一个问题：Python中对象的赋值、浅拷贝、深拷贝
① python中，赋值是建立对象的引用 　　不可变数据类型(Numbers、String、Tuple): 赋值后如果更改变量，会创建一个新值，同时改变内存地址。 　　可变数据类型(List、Dict): 内存地址保持不变

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> a = "amilyxy"  / a = ["amilyxy"]
>>> b = a
>>> id(b)   
139863454833944
>>> id(a)   
139863454833944
>>> b +=" go!"  /  b .append(" go!")
 'amilyxy go!'  /  ['amilyxy', ' go!']
>>> a
"amilyxy"  /  ['amilyxy', ' go!']
>>> id(b)   
139863455613104  / ab一样
>>> id(a)   
139863454833944

② 浅拷贝：浅拷贝创建新对象，内容是原对象的引用
　三种形式：切片b = a[:] 、copy() b = a.copy()、工厂函数b = list(a)
　注意: 浅拷贝只拷贝了父对象，其子对象是引用，指向统一内存空间 ,详情看下面代码段。
③ 深拷贝：完全拷贝其父对象和子对象 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@ 实例源自菜鸟课程
import copy
a = [1, 2, 3, 4, ['a', 'b']] #原始对象
 
b = a                       #赋值，传对象的引用
c = copy.copy(a)            #对象拷贝，浅拷贝
d = copy.deepcopy(a)        #对象拷贝，深拷贝
 
a.append(5)                 #修改对象a
a[4].append('c')            #修改对象a中的['a', 'b']数组对象
 
a = [1, 2, 3, 4, ['a', 'b', 'c'], 5]
b = [1, 2, 3, 4, ['a', 'b', 'c'], 5]
c = [1, 2, 3, 4, ['a', 'b', 'c']]
d = [1, 2, 3, 4, ['a', 'b']]
  • 解决方案
    　　1. 使用copy()或者deepcopy() 　　2. 重新声明
3. 关于python中set()

① python中set和dict是一个无序不重复元素集
② set.add() 插入位置是不定 ③ set.pop() 出来的是最左边的元素

1
2
3
4
5
6
7
>>> a = "amilyxy"
>>> b = set(a)
{'i', 'a', 'm', 'x', 'y', 'l'}
>>> b.add("hello")
{'i', 'a', 'm', 'hello', 'x', 'y', 'l'}
>>> b.pop()
'i'

今日份的Tips：

  • Tips-1：BFS深度
    来了来了，看完题解发现有人跟我思路相差无几哈哈哈，借鉴一下他的深度的记录方法。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    '''
    state(graph[i][j]) = S：graph[i][j]满足某种状态/条件S
    '''
    def bfs():
        queue = deque()
        queue.append(begin)
        depth = 1
        while queue:
            n = len(queue)
            for _ in range(n):
                temp= queue.popleft()
                if state(graph[i][j]) = S:
                    // 相应处理
                //all_node = 搜索该节点下层所有节点
                // queue.append(all_node)
            depth += 1
            return 0

  • Tips-2：TimeComplexity ① 简直amazing，上面说了我的方法一直超时，也是没有考虑到list和set中x in s操作时间复杂度问题。
    ② list、set、dict、queue 时间复杂度指路→TimeComplexity
    总而言之：“判断值是否存在，一定不要用list，时间复杂度为O(n)，而set和dict由于用hash实现，时间复杂度为O(1)”

51.N皇后

首先在这里引用一下某个题解的总结
解决一个回溯问题，实际上就是一个决策树的遍历过程，需要思考三个问题：

1.路径： 也就是已经做出的选择
2.选择列表： 当前可做的选择
3.结束条件： 达到决策树底层或者结点满足某个条件

回溯框架：核心是for循环里面的递归，在递归之前「做选择」，在递归调用之后「撤销选择」 

1
2
3
4
5
6
7
8
9
10
11
# 作者：labuladong
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

其实这个题还有一个关键，就是如何判别攻击位置（横竖肯定知道，主要是主对角线和次对角线的关系
main diagonal = col - row
subdiagonal = col+row

52.N皇后II

本来不打算写这个的，但是做题的时候用到了全局变量，找不到定义就很难受，举个栗子：
(1) 局部变量大家都知道用： 

1
2
3
4
5
6
7
8
9
10
def  outter():
    a = 1  # a = [1]
    def inner():
      a = 3  # a[0] = 3
      print("the inner a is:", a)
    inner()
    print("the outter a is :", a)
>>> outter()
the inner a is: 3    # the inner a is: 3  
the outter a is : 1  # the outter a is: 3

(2) python 全局变量使用： 

1
2
3
4
5
6
7
8
9
def  outter():
    a = 1  # a =[3,2]
    def inner():
      a += 1  # a.append(4)
    inner()
    print("the outter a is :", a)
>>> outter()
Traceback (most recent call last):   # a=[3,2,4]
UnboundLocalError: local variable 'a' referenced before assignment

注意，当a为list、set、dict的时候，却不会报错
原因：参考(1)

  • 普通变量如果在函数中赋值a = 3会有歧义，因为它既可以是表示引用全局变量a，也可以是创建一个新的局部变量，所以在python中，默认它的行为是创建局部变量，除非显式声明global。
  • 对list/set/dict变量进行赋值a[0] = 2则不会有歧义，它是“明确的”，如果把a当作是局部变量的话，它会报KeyError，所以它只能是引用全局的b，因此不需要显式声明global。

还是尽量不要使用全局变量吧，不方便调试。

(3) global 先声明全局变量 

1
2
3
4
5
6
7
8
9
10
def  outter():
    global a
    a = 1
    def inner():
      global a
      a += 1
    inner()
    print("the outter a is :", a)
>>> outter()
the outter a is : 2