LC吐血整理之DFS&BFS篇

2019-09-27 本文已影响0人 amilyxy

200. 岛屿数量

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

DFS:

概念理解

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

实现方法
类似于树的先序遍历
使用堆栈结构-先进后出
实例：寻找迷宫出口（不撞南墙不回头）,目标明确，就是为了找出口
算法思路 python
递归实现 ⬇

'''
假设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

'''
假设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基本操作，有机会再补充

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

127.单词接龙

踩坑记录：

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

1. 循环中谨慎删除列表元素（这个真的是重点，输出死活不对，排查了好久）

>>> 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. 队列的赋值操作

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): 内存地址保持不变

>>> 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)
　注意: 浅拷贝只拷贝了父对象，其子对象是引用，指向统一内存空间 ,详情看下面代码段。
③ 深拷贝：完全拷贝其父对象和子对象

@ 实例源自菜鸟课程
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() 出来的是最左边的元素

>>> 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深度
来了来了，看完题解发现有人跟我思路相差无几哈哈哈，借鉴一下他的深度的记录方法。

'''
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)”

N皇后

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

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

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

# 作者：labuladong
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

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

N皇后II

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

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 全局变量使用：

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变量进行赋值 a[0] = 2则不会有歧义，它是“明确的”，如果把a当作是局部变量的话，它会报KeyError，所以它只能是引用全局的b，因此不需要显式声明global。

所以还是尽量不使用全局变量，不方便调试

(3) global 先声明全局变量

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