重点：

  • DFS
  • BFS
  • 拓扑排序
  • 单元最短路径（迪杰斯特拉算法）
  • 染色问题

    模板

    Bellman-ford算法

例题

1. 课程表

描述
image.png
思路
组成的有向图，有环就说明无法完成。

  • DFS
  • 拓扑排序

代码
Java代码-拓扑排序：

  1. class Solution {
  2.     public boolean canFinish(int numCourses, int[][] prerequisites) {
  3.         int[] inDegrees = new int[numCourses];
  4.         List<List<Integer>> adj = new ArrayList<>();
  5.         Queue<Integer> queue = new LinkedList<>();
  7.         for (int i = 0; i < numCourses; i++) 
  8.             adj.add(new ArrayList<>());
  10.         for (int[] cp : prerequisites) {
  11.             inDegrees[cp[0]]++;
  12.             adj.get(cp[1]).add(cp[0]);
  13.         }
  15.         for(int i = 0; i < numCourses; i++)
  16.             if(inDegrees[i] == 0) {
  17.                 queue.add(i);
  18.             }
  20.         while(!queue.isEmpty()) {
  21.             int pre = queue.poll();
  22.             numCourses--;
  23.             for (int cur : adj.get(pre)) {
  24.                 if (--inDegrees[cur] == 0) {
  25.                     queue.add(cur);
  26.                 }
  27.             }
  28.         }
  29.         return numCourses == 0;
  30.     }
  31. }

Python拓扑排序：

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        import collections
        indegree = [0] * numCourses
        graph = collections.defaultdict(list)
        for pre in prerequisites:
            indegree[pre[0]] += 1
            graph[pre[1]].append(pre[0])

        q = []
        for i in range(numCourses):
            if indegree[i] == 0:
                q.append(i)

        while q:
            cur = q.pop(0)
            numCourses -= 1
            for nbr in graph[cur]:
                indegree[nbr] -= 1
                if indegree[nbr] == 0:
                    q.append(nbr)
        return numCourses == 0

Python代码-DFS:

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        def dfs(graph, visited, i):
            visited[i] = 1
            for nbr in graph[i]:
                if visited[nbr] == 1:
                    return True
                else:
                    if dfs(graph, visited, nbr):
                        return True
            visited[i] = 2


        graph = collections.defaultdict(list)
        for pre in prerequisites:
            graph[pre[1]].append(pre[0])
        visited = [0] * numCourses
        hasCycle = False
        for i in range(numCourses):
            if visited[i] == 0:
                hasCycle = dfs(graph, visited, i)
                if hasCycle:
                    break
        return not hasCycle

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        edges = collections.defaultdict(list)
        visited = [0] * numCourses
        result = list()
        valid = True

        for info in prerequisites:
            edges[info[1]].append(info[0])

        def dfs(u: int):
            nonlocal valid
            visited[u] = 1
            for v in edges[u]:
                if visited[v] == 0:
                    dfs(v)
                    if not valid:
                        return
                elif visited[v] == 1:
                    valid = False
                    return
            visited[u] = 2
            result.append(u)

        for i in range(numCourses):
            if valid and not visited[i]:
                dfs(i)

        return valid

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/course-schedule/solution/ke-cheng-biao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Java代码-DFS：

class Solution {
    boolean valid = true;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();

        for (int i = 0; i < numCourses; i++) 
            adj.add(new ArrayList<>());

        for (int[] cp : prerequisites) {
            adj.get(cp[1]).add(cp[0]);
        }

        int[] visited = new int[numCourses];

        for (int i = 0; i < numCourses; i++) {
            if (valid && visited[i] == 0) {
                dfs(adj, visited, i);
            }
        }

        return valid;
    }
    public void dfs(List<List<Integer>> adj, int[] visited, int i) {
        visited[i] = 1;
        for (int nbr : adj.get(i)) {
            if (visited[nbr] == 1) {
                valid = false;
            }
            if (visited[nbr] == 0) {
                dfs(adj, visited, nbr);
            }
        }
        visited[i] = 2;
    }
}

2. 头条笔试-最小删除次数

描述
一个字符串可能包含”0010”，删除其中字符使字符串不包含”0010”，求最少删除次数。
输入样例：

2
0010ABCDEFAB24566
1001

输出样例：

1
0

思路

  • 最少删除次数，最少转换次数，最短距离，通常都是BFS

image.png
代码
Python代码：

t = int(input())
for _ in range(t):
    s = input()
    q = [(s, 0)]
    visted = set()
    while q:
        cur, step = q.pop(0)
        if "0010" not in cur:
            print(step)
            break
        target_index = cur.index("0010")
        for i in range(target_index, target_index + 4):
            new_str = cur[:i] + cur[i+1:]
            if new_str not in visted:
                q.append((new_str, step + 1))
                visted.add(new_str)

3. AcWing 173. 矩阵距离

给定一个N行M列的01矩阵A，A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为：

dist(A[i][j],A[k][l])=|i−k|+|j−l|
输出一个N行M列的整数矩阵B，其中：

B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1⁡dist(A[i][j],A[x][y])
输入格式
第一行两个整数n,m。
接下来一个N行M列的01矩阵，数字之间没有空格。
输出格式
一个N行M列的矩阵B，相邻两个整数之间用一个空格隔开。
数据范围
1≤N,M≤1000
输入样例：

3 4
0001
0011
0110

输出样例：

3 2 1 0
2 1 0 0
1 0 0 1

思路

  • BFS
  • 最短路径

代码
Python代码：

import collections
n, m = map(int, input().split())

g = []
for _ in range(n):
    g.append(list(input()))

dist = [[-1] * (m) for _ in range(n)]
q = collections.deque()

for i in range(n):
    for j in range(m):
        if g[i][j] == "1":
            q.append([i, j])
            dist[i][j] = 0

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

while q:
    x, y = q.popleft()
    for i in range(4):
        newx = x + dx[i]
        newy = y + dy[i]
        if 0 <= newx < n and 0 <= newy < m and dist[newx][newy] == -1:
            q.append([newx, newy])
            dist[newx][newy] = dist[x][y] + 1
for i in range(len(dist)):
    print(" ".join(map(str, dist[i])))

4. lc 1553. 吃掉 N 个橘子的最少天数

image.png
思路

  • BFS
  • 哈希表减少搜索空间

代码
Python代码：

class Solution:
    def minDays(self, n: int) -> int:
        def extend(dist, x):
            if x in d:
                return 
            d[x] = dist + 1
            q.append(x)
        import collections
        if n == 1:
            return 1
        q = collections.deque()
        d = {}
        d[n] = 0
        q.append(n)
        while q:
            cur = q.popleft()
            if cur == 0:
                return d[cur]
            extend(d[cur], cur - 1)
            if cur % 2 == 0:
                extend(d[cur], cur // 2)
            if cur % 3 == 0:
                extend(d[cur], cur // 3)
        return -1;

Java代码：

class Solution {
    Map<Integer, Integer> d = new HashMap<>();
    Queue<Integer> q = new LinkedList<>();
    public int minDays(int n) {
        q.offer(n);
        d.put(n, 0);
        while (!q.isEmpty()) {
            int cur = q.poll();
            if (cur == 0) {
                return d.get(cur);
            }
            extend(d.get(cur), cur - 1);
            if (cur % 2 == 0) {
                extend(d.get(cur), cur / 2);
            }
            if (cur % 3 == 0) {
                extend(d.get(cur), cur / 3);
            }
        }
        return -1;
    }
    public void extend(int dist, int x) {
        if (d.containsKey(x)){
            return;
        }
        d.put(x, dist + 1);
        q.offer(x);
    }
}