dfs

1、递归DFS：访问节点，将该节点标记为已访问，同时对根节点的邻接结点中未访问过的结点递归调用DFS

2、非递归DFS：取栈顶元素（不出栈），找到栈顶元素的一个未被访问过的邻接结点（注意是一个就行，不需要所有邻接结点入 栈，与BFS不同），访问、标记为已访问并入栈，直到栈顶元素的所有邻接结点都被访问过，栈顶元素出栈，直到栈空

DFS 适用于找到起始节点到目标节点的路径，但不一定是最短路径。它通过递归的方式深入探索图的分支，因此对于深
度较小的图或树， DFS 通常表现较好。

1
2
3
4
5
6
7
8
9
10
11
# 图的DFS遍历 递归
def dfs(graph, start, visited):
    # 访问当前节点
    print(start, end=' ')
    # 标记当前节点为已访问
    visited[start] = True
    # 遍历当前节点的邻居节点
    for neighbor in graph[start]:
        # 如果邻居节点未被访问，则继续深度优先搜索
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 图的DFS遍历 非递归
'''DFS的非递归实现方式相比于BFS应该说大同小异，只是把queue换成了stack而已，stack具有后进先出LIFO(Last Input First Output)的特性，DFS的操作步骤如下：

- 1、把起始点放入stack；
- 2、重复下述3步骤，直到stack为空为止：
  - 从stack中访问栈顶的点；
  - 找出与此点邻接的且尚未遍历的点，进行标记，然后全部放入stack中；
  - 如果此点没有尚未遍历的邻接点，则将此点从stack中弹出。'''
def dfs(graph, start):
    stk = [start] # 使用栈来记录遍历路径
    visited = set([start]) # 标记节点是否已访问的集合
    while stk:
        node = stk[-1]
        print(node, end=' ')
        for neighbor in graph[node]:
            if neighbor not in visited:
                stk.append(neighbor)
                visited.add(neighbor)
                break
        else: stk.pop() #只有没有break时，才会执行else
           	
1
2
3
4
5
6
7
8
# 二叉树的DFS遍历 递归
def dfs_binary_tree(root):
    if root is None:
        return
    print(root.val, end=' ')
    dfs_binary_tree(root.left)
    dfs_binary_tree(root.right)
#根据print的位置可以实现先序、中序、后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 二叉树的DFS遍历 非递归
def dfs_binary_tree(root):
    if root is None:
        return

    stk = [root]
    while stk:
        node = stk[-1]
        print(node.val, end=' ')
        if node.left:
            queue.append(node.left)
        elif node.right:
            queue.append(node.right)
        else: stk.pop() #没有根节点

bfs

BFS：采用队列的数据结构，取队列首元素，将该节点标记为已访问，将该节点的未被访问过且不在队列中的邻接结点加入队列中。

BFS 适用于找到起始节点到目标节点的最短路径。它通过逐层遍历图的节点，从而保证找到的路径是最短的。在需要寻找最短路径的情况下， BFS 是更好的选择。Dijkstra算法就是bfs思想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from collections import deque
# 图的BFS遍历
def bfs(graph, start):
    # 使用队列来记录遍历路径
    queue = deque([start])
    # 标记节点是否已访问的集合
    visited = set([start])

    while queue:
        node = queue.popleft()
        print(node, end=' ')

        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from collections import deque
# 二叉树的BFS遍历
def bfs_binary_tree(root):
    if root is None:
        return

    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.val, end=' ')
        #此处加上for循环，可实现层级遍历
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

二分法

1
2
3
index1 = bisect(ls, x)   #第1个参数是列表，第2个参数是要查找的数，返回值为索引
index2 = bisect_left(ls, x) #bisect_left返回大于等于，其他两个返回大于
index3 = bisect_right(ls, x)

djs算法

最短路径算法-迪杰斯特拉(Dijkstra)算法

基本思想和BFS相同

  1. 通过Dijkstra计算图G中的最短路径时，需要指定一个起点D(即从顶点D开始计算)。
  2. 此外，引进两个数组S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点D的距离)。
  3. 初始时，数组S中只有起点D；数组U中是除起点D之外的顶点，并且数组U中记录各顶点到起点D的距离。如果顶点与起点D不相邻，距离为无穷大。
  4. 然后，从数组U中找出路径最短的顶点K，并将其加入到数组S中；同时，从数组U中移除顶点K。接着，更新数组U中的各顶点到起点D的距离。
  5. 重复第4步操作，直到遍历完所有顶点。

image-20240322112953423

例题-到达目的地的方案数

你在一个城市里，城市由 n 个路口组成，路口编号为 0 到 n - 1 ，某些路口之间有 双向 道路。输入保证你可以从任意路口出发到达其他任意路口，且任意两个路口之间最多有一条路。

给你一个整数 n 和二维整数数组 roads ，其中 roads[i] = [ui, vi, timei] 表示在路口 ui 和 vi 之间有一条需要花费 timei 时间才能通过的道路。你想知道花费 最少时间 从路口 0 出发到达路口 n - 1 的方案数。

请返回花费 最少时间 到达目的地的 路径数目 。由于答案可能很大，将结果对 109 + 7 取余 后返回。

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
30
31
32
33
class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        #不能用*定义矩阵，否者列表元素的内存地址相同
        #a = [[float('inf')] * n] * n  #inf表示无穷大
        a = [[float('inf') for _ in range(n)] for _ in range(n)]   
        #a[x][y]表示x节点到y节点的距离，如果给定了，则为d，如果没给定，则为inf
        for x,y,d in roads:
            a[x][y] = d     
            a[y][x] = d
        dis = [float('inf')] * n   #dis[x]表示0到x节点的最短距离
        dis[0] = 0   #0节点到0节点的距离为0
        f = [0] * n     #表示0到x节点共有f[x]种最短路径
        f[0] = 1      #默认0到0节点有一种路径
        done = [False] * n   #表示节点是否已计算最短距离
        while True:
            x = -1  #重置x，以便进行遍历
            #找出x节点邻点的最小dis[y]
            for i,do in enumerate(done):
                if not do and (x<0 or dis[i]<dis[x]):  
                    x = i
            if x == n-1:   #当所有的节点都done了
                return f[-1]   #输出n-1节点最短路径数
            dx = dis[x]     #减少循环中调用dis[x]的次数
            for y,d in enumerate(a[x]):   #将x节点的邻点y的dis(y)确认
                new_dis = dx + d    #从0到x再到y
                #如果从x走更短，更改dis[y]，并且令f[y]=f[x]
                if new_dis < dis[y]:   
                    dis[y] = new_dis
                    f[y] = f[x]
                #如果从x走的长度一样，则y节点的最短路径加上f[x]条
                elif new_dis == dis[y]:   
                    f[y] = (f[y] + f[x]) % 1_000_000_007
            done[x] = True   #x节点已完成，标记为done

image-20240322113207394

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
30
#堆优化 Dijkstra（适用于稀疏图）
class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        g = [[] for _ in range(n)]  # 邻接表
        for x, y, d in roads:
            g[x].append((y, d))
            g[y].append((x, d))

        dis = [inf] * n
        dis[0] = 0
        f = [0] * n
        f[0] = 1
        h = [(0, 0)]
        while True:
            dx, x = heappop(h)
            if x == n - 1:
                # 不可能找到比 dis[-1] 更短，或者一样短的最短路了（注意本题边权都是正数）
                return f[-1]
            if dx > dis[x]:
                continue
            for y, d in g[x]:  # 尝试更新 x 的邻居的最短路
                new_dis = dx + d
                if new_dis < dis[y]:
                    # 就目前来说，最短路必须经过 x
                    dis[y] = new_dis
                    f[y] = f[x]
                    heappush(h, (new_dis, y))
                elif new_dis == dis[y]:
                    # 和之前求的最短路一样长
                    f[y] = (f[y] + f[x]) % 1_000_000_007

有限状态机

有限状态机（Finite-state machine, FSM），又称有限状态自动机，简称状态机，是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。

img

有限状态机模型

image-20240322112008154

例题-有效数字

有效数字（按顺序）可以分成以下几个部分：

若干空格
一个 小数 或者 整数
（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数
若干空格
小数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（‘+’ 或 ‘-’）
下述格式之一：
至少一位数字，后面跟着一个点 ‘.’
至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
一个点 ‘.’ ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（‘+’ 或 ‘-’）
至少一位数字

部分有效数字列举如下：[“2”, “0089”, “-0.1”, “+3.14”, “4.”, “-.9”, “2e10”, “-90E3”, “3e+7”, “+6e-1”, “53.5e93”, “-123.456e789”]
部分无效数字列举如下：[“abc”, “1a”, “1e”, “e3”, “99e2.5”, “–6”, “-+3”, “95a54e53”]
给你一个字符串 s ，如果 s 是一个 有效数字 ，请返回 true 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#有限状态自动机。先定义状态，再画出状态转移图，最后编写代码即可。
class Solution:
    def validNumber(self, s: str) -> bool:
        states = [
            { ' ': 0, 's': 1, 'd': 2, '.': 4 }, # 0. start with 'blank'
            { 'd': 2, '.': 4 } ,                # 1. 'sign' before 'e'
            { 'd': 2, '.': 3, 'e': 5, ' ': 8 }, # 2. 'digit' before 'dot'
            { 'd': 3, 'e': 5, ' ': 8 },         # 3. 'digit' after 'dot'
            { 'd': 3 },                         # 4. 'digit' after 'dot' (‘blank’ before 'dot')
            { 's': 6, 'd': 7 },                 # 5. 'e'
            { 'd': 7 },                         # 6. 'sign' after 'e'
            { 'd': 7, ' ': 8 },                 # 7. 'digit' after 'e'
            { ' ': 8 }                          # 8. end with 'blank'
        ]
        p = 0                           # start with state 0
        for c in s:
            if '0' <= c <= '9': t = 'd' # digit
            elif c in "+-": t = 's'     # sign
            elif c in "eE": t = 'e'     # e or E
            elif c in ". ": t = c       # dot, blank
            else: t = '?'               # unknown
            if t not in states[p]: return False
            p = states[p][t]
        return p in (2, 3, 7, 8)

动态规划

动态规划解题框架

若确定给定问题具有重叠子问题和最优子结构，那么就可以使用动态规划求解。总体上看，求解可分为四步：

状态定义： 构建问题最优解模型，包括问题最优解的定义、有哪些计算解的自变量；
初始状态： 确定基础子问题的解（即已知解），原问题和子问题的解都是以基础子问题的解为起始点，在迭代计算中得到的；
转移方程： 确定原问题的解与子问题的解之间的关系是什么，以及使用何种选择规则从子问题最优解组合中选出原问题最优解；
返回值： 确定应返回的问题的解是什么，即动态规划在何处停止迭代；
完成以上步骤后，便容易写出对应的解题代码。

1
2
3
4
5
6
7
# 求第 n 个斐波那契数
def fibonacci(n):
    if n == 0: return 0       # 若求 f(0) 则直接返回 0
    a, b = 0, 1               # 初始化 f(0), f(1)
    for i in range(2, n + 1): # 状态转移求取 f(2), f(3), ..., f(n) 
        a, b = b, a + b
    return b                  # 返回 f(n)

双指针

分治算法

回溯

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def quicksort(nums,l,r):
    #只有一个值时，无需排序
    if l >= r: return
    #以i为哨兵节点，nums[l]为基准数
    i, j = l, r
    while i < j:
        #外循环终止条件无法影响内循环，所以内循环也要加i<j
        while i < j and nums[j] >= nums[l]: j -= 1
        while i < j and nums[i] <= nums[l]: i += 1
        nums[i], nums[j] = nums[j], nums[i] #i,j都停住时交换i,j的值
    nums[i], nums[l] = nums[i], nums[l] #i,j重合时交换i,l的值
    # 递归左（右）子数组执行哨兵划分
    quciksort(nums,l,i-1)
    quciksort(nums,i+1,r)

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def merge_sort(nums, l, r):
    # 终止条件
    if l >= r: return
    # 递归划分数组
    m = (l + r) // 2
    merge_sort(nums, l, m)
    merge_sort(nums, m + 1, r)
    # 合并子数组
    tmp = nums[l:r + 1]       # 暂存需合并区间元素
    i, j = 0, m - l + 1       # 两指针分别指向左/右子数组的首个元素
    for k in range(l, r + 1): # 遍历合并左/右子数组
        if i == m - l + 1:
            nums[k] = tmp[j]
            j += 1
        elif j == r - l + 1 or tmp[i] <= tmp[j]:
            nums[k] = tmp[i]
            i += 1
        else:
            nums[k] = tmp[j]
            j += 1

# 调用
nums = [3, 4, 1, 5, 2, 1]
merge_sort(0, len(nums) - 1)

贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解 。

贪心算法不是对所有问题都能得到体最优解，关键是整贪心策略的选择

贪心算法一般按如下步骤进行：

①建立数学模型来描述问题

②把求解的问题分成若干个子问题

③对每个子问题求解，得到子问题的局部最优解

④把子问题的解局部最优解合成原来解问题的一个解

单调栈

滑动窗口

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    #快速幂
    def Pow(self, x: float, y: int) -> float:
        res = 1
        while y:
            #可以再往上乘一个
            if y & 1: 
                res = res * x % mod
            #叠加
            x = x * x % mod 
            #减少乘次数
            y = y >> 1 
        return res
        
    def Power(self , base: float, exponent: int) -> float:
        #处理负数次方
        if exponent < 0:
            base = 1 / base
            exponent = -exponent
        res = 1.0
        return self.Pow(base, exponent)

递归

递：自上而下，用参数或数组向下传递

归，自下而上，用返回值

1026. 节点与其祖先之间的最大差值

给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。

（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#递+最大最小值
class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        res = 0
        def dfs(root, mn, mx):
            if not root: 
                nonlocal res
                res = max(res, mx - mn)
                return       
            mn = min(mn, root.val)
            mx = max(mx, root.val)          
            dfs(root.left, mn, mx)
            dfs(root.right, mn, mx)
        dfs(root, root.val, root.val)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#归+最大最小值
class Solution:
    def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
        res = 0
        def dfs(root):
            if not root: 
                return inf, -inf
            l_mn, l_mx = dfs(root.left)
            r_mn, r_mx = dfs(root.right)
            mn = min(root.val, l_mn, r_mn)
            mx = max(root.val, l_mx, r_mx)
            nonlocal res
            res = max(res, root.val-mn, mx-root.val)          
            return mn, mx
        dfs(root)
        return res