图论#

#

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

1
2
3
4
5
6
7
输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

1
2
3
4
5
6
7
输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3
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
func numIslands(grid [][]byte) (ans int) {
    m, n := len(grid), len(grid[0])
    var dfs func(int, int)
    dfs = func(i, j int) {
        // 出界，或者不是 '1'，就不再往下递归
        if i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1' {
            return
        }
        grid[i][j] = '2' // 插旗！避免来回横跳无限递归
        dfs(i, j-1)      // 往左走
        dfs(i, j+1)      // 往右走
        dfs(i-1, j)      // 往上走
        dfs(i+1, j)      // 往下走
    }

    for i, row := range grid {
        for j, c := range row {
            if c == '1' { // 找到了一个新的岛
                dfs(i, j) // 把这个岛插满旗子，这样后面遍历到的 '1' 一定是新的岛
                ans++
            }
        }
    }
    return
}
  1. 这是个无向图，然后上下左右走一走
  2. 用插旗的方法，遍历过的地方标记为2，这样子第一次遍历的地方就是1
  3. 相当于二维数组的直接两层for循环遍历

#

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

  • 值 0 代表空单元格；
  • 值 1 代表新鲜橘子；
  • 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

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
34
35
36
37
38
39
40
41
42
43
44
type pair struct{
	x , y int
}

var directions = []pair{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

func orangesRotting(grid [][]int)int{
	m, n := len(grid) , len(grid[0])
	
	fresh := 0
	queue := []pair{}
	for i, row := range grid {
		for j, x := range row {
			if x == 1 {
				fresh ++ 
			}else if x == 2 {
				queue = append(queue, pair{i, j})
			}	
		}
	}
	
	ans := 0 
	for fresh > 0 && len(queue) > 0{
		ans ++ 
		tmp := queue
		queue = []pair{}
		for _ , p := range tmp{
			for _ , d := range directions{
				i , j := p.x + d.x , p.y + d.y
				if i >= 0 && j >= 0 && i < m && j < n && grid[i][j] == 1{
					grid[i][j] = 2
					fresh -- 
					queue = append(queue, pair{i, j})
				}
			}
		}
	}
	
	if fresh > 0 {
		return -1 
	}
	
	return ans 
}
  1. 这道题很明显是bfs的模板，像外部扩散的模型
  2. 老规矩 上下左右扩散一次 –> 也就是遍历一次
  3. 两层for循环直接遍历
  4. 使用一个队列来标记是否腐烂

小结：#

前面两题都是无向图的典例：有这么一些共同的特征：

  1. 上下左右遍历
  2. 两层for循环直接遍历
  3. 需要用 0 - 1 - 2 来标记状态

#

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

  • 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

1
2
3
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
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
34
35
36
37
38
39
40
41
42
43
44
// dfs
func canFinish(numCourses int, prerequisites [][]int) bool {
	// 初始化变量
	adjacency := make(map[int][]int)  // 邻接表，键是图中所有课程节点，值是该课程的所有直接依赖的后序课程
	courseStatus := make(map[int]int) // 映射表，键是图中的节点，值是该节点的状态，值的状态分为3种，0：该节点未被访问、1：该节点在本次dfs中被访问过、2：该节点被其他次dfs访问过

	// 遍历先决条件，更新邻接表和入度表，将某课程的后序课程加入邻接表中
	for _, prerequisite := range prerequisites {
		adjacency[prerequisite[1]] = append(adjacency[prerequisite[1]], prerequisite[0])
	}

	// 定义递归函数
	var dfs func(int) bool
	dfs = func(course int) bool {
		// 1.终止条件：
		// 当节点状态为1，说明该节点在本次dfs中遇到了2次，即图中是存在环的，且该节点是环中的一员，因此说明课程会产生循环依赖，返回false
		if courseStatus[course] == 1 {
			return false
		}
		// 当节点状态为2，说明该节点已经被其他次dfs访问过，并且确认过没环，因此无需再次访问，返回true
		if courseStatus[course] == 2 {
			return true
		}
		// 2.本次递归中要做的事：将当前节点置为1，表示本次dfs中经过了该点
		courseStatus[course] = 1   // 判断是否成环
		// 3.递归调用：对当前节点的所有后序节点进行递归dfs判环，发现有环则返回false
		for _, afterCourse := range adjacency[course] {
			if !dfs(afterCourse) {
				return false
			}
		}
		// 如果当前节点的所有后序节点都不是环中的一员，则将当前节点置为2，表示已经确认过没环
		courseStatus[course] = 2
		return true
	}

	// 以图中每一个节点为起点，进行递归判环
	for i := 0; i < numCourses; i++ {
		if !dfs(i) {
			return false
		}
	}
	return 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// bfs
func canFinish(numCourses int, prerequisites [][]int) bool {
	// 初始化变量
	// 创建一个邻接表map，键为某课程编号，值为该课程的直接后序课程编号（即该课程节点在图中的出度对应的所有课程节点编号）
	adjacencyMap := make(map[int][]int)
	// 创建一个记录节点入度数量的map：键为某课程编号，值为该课程的入度数量
	inDegreeMap := make(map[int]int)
	// 创建一个队列，临时储存课程编号，辅助将图中入度为0的节点拿掉
	queue := make([]int, 0)
	// 结果集，储存可能的课程序列
	result := make([]int, 0)

	// 构建图：
	// 遍历prerequisites所有的课程依赖：
	for _, prerequisite := range prerequisites {
		// 将前序课程加入邻接表map的键中，将后序课程加入邻接表map的值中
		adjacencyMap[prerequisite[1]] = append(adjacencyMap[prerequisite[1]], prerequisite[0])
		// 将后序课程在入度map中的值数量加1
		inDegreeMap[prerequisite[0]]++
	}

	// 首先将图中初始化状态下，所有入度为0的课程节点入队
	for course := 0; course < numCourses; course++ {
		if inDegreeMap[course] == 0 {
			queue = append(queue, course)
		}
	}

	// 循环出队入队：
	for len(queue) > 0 {
		// 如果一个课程没有任何前序课程（入度为0），则可以开始学习；将队头课程节点出队，将该节点从图中拿掉，加入结果集中
		course := queue[0]
		queue = queue[1:]
		result = append(result, course)

		// 遍历邻接表map中，该课程的所有直接后序课程
		for _, nextCourse := range adjacencyMap[course] {
			// 将这些后序课程在入度map中的值减1
			inDegreeMap[nextCourse]--
			// 将新生成的入度为0的节点入队
			if inDegreeMap[nextCourse] == 0 {
				queue = append(queue, nextCourse)
			}
		}
	}

	// 将结果集中课程个数与原课程数比较：
	// 如果结果集中课程的数量比原课程数量少，图中还有剩余节点，说明图有环，即无法完成所有课程的学习
	// 如果结果集中课程的数量与原课程数量相等，图中没有剩余节点，说明图无环，即可以完成所有课程的学习
	return len(result) == numCourses
}
  1. 拓扑排序： 有向无环图 – 具体感受就是任务分配先后
  2. 整个问题就是 入度和出度的问题 ； 上游的节点入度为零，下游的节点出度为零
  3. 建议先理解bfs版本的代码：
    1. 用一个邻接矩阵来记录 上下游关系
    2. 用一个入度表来记录 那个是第一节课(入度==0)
    3. 当第一节课上完后，邻接矩阵中对应的所有下游课程的入度-1
    4. 将入度=0的课程放入队列
    5. len(result) == numCourses 这个是核心 （如果有环，那么意味着他的节点永远是入度不等于零，所以result永远不可能为0）
  4. 再理解dfs版本的代码；
    1. 邻接矩阵和入度表都一样的意思
    2. 他用 0 1 2 来表示在一次遍历中，某个节点是否被遍历过两遍（如果是，就是环，因为环是无线遍历的[前提是在某个遍历过程中]）
    3. 直接for循环启动

#

**Trie**（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
type Trie struct {
    children [26]*Trie
    isEnd    bool
}

func Constructor() Trie {
    return Trie{}
}

func (t *Trie) Insert(word string) {
    node := t
    for _, ch := range word {
        ch -= 'a'
        if node.children[ch] == nil {
            node.children[ch] = &Trie{}
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

func (t *Trie) SearchPrefix(prefix string) *Trie {
    node := t
    for _, ch := range prefix {
        ch -= 'a'
        if node.children[ch] == nil {
            return nil
        }
        node = node.children[ch]
    }
    return node
}

func (t *Trie) Search(word string) bool {
    node := t.SearchPrefix(word)
    return node != nil && node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
    return t.SearchPrefix(prefix) != nil
}
  1. 整体的结构就是树，只是这个树的每个节点是二十六位数组，每个数组存一个单词，很抽象我觉得，这样子浪费的内存也太多了吧
  2. 没什么好讲的