第7周 字典树和并查集、高级搜索、红黑树和AVL树

题目数量：17

第13课 | 字典树和并查集

1. Trie树的基本实现和特性

参考链接

• 二叉树的层次遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// bfs
func levelOrder(root *TreeNode) (res [][]int) {
    if root == nil {
        return res
    }
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        curLevel := []int{}
        for cnt := len(queue); cnt > 0; cnt-- {
            node := queue[0]
            queue = queue[1:]
            curLevel = append(curLevel, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        res = append(res, curLevel)
    }
    return res
}
// dfs

• 208. 实现 Trie (前缀树)

type Trie struct {
   child [26]*Trie
   isEnd     bool
}


func Constructor() Trie {
    return Trie{}
}


func (this *Trie) Insert(word string)  {
    root := this
    for _, w := range word {
        if root.child[w - 'a'] == nil{
            root.child[w - 'a'] = &Trie{}
        }
        root = root.child[w - 'a'] 
    }
    root.isEnd = true
}

func (this *Trie) SearchPrefix(prefix string) *Trie {
    root := this
    for _, w := range prefix {
        if root.child[w - 'a'] == nil {
            return nil
        }
        root = root.child[w - 'a']
    }
    return root
}

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


func (this *Trie) StartsWith(prefix string) bool {
    return this.SearchPrefix(prefix) != nil
}


/**
 * Your Trie object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */

• Tire 树代码模板 失效，看PHP

2. Trie树实战题目解析：单词搜索2

实战题目

• 208. 实现 Trie (前缀树)

// 上面重复

• 212. 单词搜索 II 重点练习

var fx = [][]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
func findWords(board [][]byte, words []string) (res []string) {
    trie := &Trie{}
    for _, word := range words {
        trie.Insert(word)
    }
    m, n := len(board), len(board[0])
    var backtracking func (i, j int, root *Trie)
    backtracking = func(i, j int, root *Trie) {
        letter := board[i][j]
        board[i][j] = '#'
        node := root.child[letter - 'a']
        if node.word != "" {
            res = append(res, node.word)
            node.word = ""
        }
        for _, f := range fx {
            ni, nj := i + f[0], j + f[1]
            if ni < 0 || ni >= m || nj < 0 || nj >= n || board[ni][nj] == '#'{
                continue
            }
            if node.child[board[ni][nj] - 'a'] != nil {
                backtracking(ni, nj, node)
            }
        }
        board[i][j] = letter
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if trie.StartsWith(string(board[i][j])) {
                backtracking(i, j, trie)
            }
        }
    }
    return res
}

type Trie struct {
   child [26]*Trie
   word     string
}


func Constructor() Trie {
    return Trie{}
}


func (this *Trie) Insert(word string)  {
    root := this
    for _, w := range word {
        if root.child[w - 'a'] == nil{
            root.child[w - 'a'] = &Trie{}
        }
        root = root.child[w - 'a'] 
    }
    root.word = word
}

func (this *Trie) SearchPrefix(prefix string) *Trie {
    root := this
    for _, w := range prefix {
        if root.child[w - 'a'] == nil {
            return nil
        }
        root = root.child[w - 'a']
    }
    return root
}

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


func (this *Trie) StartsWith(prefix string) bool {
    return this.SearchPrefix(prefix) != nil
}

• 分析单词搜索 II 用 Tire 树方式实现的时间复杂度，请同学们提交在第 7 周的学习总结中。

3. 并查集的基本实现、特性和实战题目解析

参考链接

• 200.岛屿数量

// dfs、bfs、并查集 见下面实战部分题解

• 并查集代码模板 失效，看PHP

type UF struct {
    Parent []int
    Count int
}
func NewUF(count int) *UF {
    parent := make([]int, count)
    for i := range parent {
        parent[i] = i
    }
    return &UF{
        Parent: parent,
        Count: count,
    }
}
func (u *UF) Find(p int) int {
    parent := u.Parent
    for p != parent[p] {
        // a <- b <- p 改 为 a <- b , a <- p // 路径压缩
        parent[p] = parent[parent[p]]
        p = parent[p]
    }
    return p
}
func (u *UF) Union(p, q int) {
    rootP := u.Find(p)
    rootQ := u.Find(q)
    if rootP != rootQ {
        u.Parent[rootP] = rootQ
        u.Count--
    }
}

实战题目

• 547. 省份数量 原 朋友圈 题

// 并查集
type UF struct {
    parent []int
    count int
}
func NewUF(count int) *UF {
    parent := make([]int, count)
    for i := range parent {
        parent[i] = i
    }
    return &UF{
        parent: parent,
        count: count,
    }
}

func (u *UF) find(p int) int {
    parent := u.parent
    for p != parent[p] {
        parent[p] = parent[parent[p]]
        p = parent[p]
    }
    return p
}

func (u *UF) union(p, q int) {
    rootP := u.find(p)
    rootQ := u.find(q)
    if rootP != rootQ {
        u.parent[rootP] = rootQ
        u.count--
    }
}

func findCircleNum(M [][]int) int {
    m := len(M)
    u := NewUF(m)
    for i := 0; i < m; i++ {
        for j := 0; j < m; j++ {
            if M[i][j] == 1 && i != j {
                u.union(i, j)
            }
        }
    }
    return u.count
}

• 200. 岛屿数量

// dfs
// bfs
// 并查集
func numIslands(grid [][]byte) int {
    m, n := len(grid), len(grid[0])
    u := NewUF(grid)
    dx := []int{1, 0, -1, 0}
    dy := []int{0, 1, 0, -1}
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == '1' {
                grid[i][j] = '0'
                for k := 0; k < 4; k++ {
                    x, y := i + dx[k], j + dy[k]
                    if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' {
                        u.Union(i * n + j, x * n + y)
                    }
                }
            }
        }
    }
    return u.Count()
}

type UF struct {
    parent []int
    rank []int
    count int
}

func NewUF(grid [][]byte) *UF {
    m, n := len(grid), len(grid[0])
    parent := make([]int, m * n)
    count := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            idx := i * n + j
            if grid[i][j] == '1' {
                count++
                parent[idx] = idx
            } else {
                parent[idx] = -1
            }
        }
    }
    return &UF{
        parent: parent,
        rank: make([]int, len(parent)),
        count: count,
    }
}

func (u *UF) Find(p int) int {
    parent := u.parent
    for p != parent[p] {
        parent[p] = parent[parent[p]]
        p = parent[p]
    }
    return p
}

func (u *UF) Union(x, y int) {
    rootX, rootY := u.Find(x), u.Find(y)
    if rootX != rootY {
        if u.rank[rootX] < u.rank[rootY] {
            u.parent[rootX] = rootY
        } else if u.rank[rootX] > u.rank[rootY]  {
            u.parent[rootY] = rootX
        } else {
            u.parent[rootY] = rootX
            u.rank[rootX] += 1
        }
        u.count--
    }
}

func (u *UF) Count() int {
    return u.count
}

• 130. 被围绕的区域

type Uf struct {
	parent []int
}

func NewUf(n int) *Uf {
	parent := make([]int, n)
	for i := range parent {
		parent[i] = i
	}
	return &Uf{parent: parent}
}

func (u *Uf) find(p int) int {
	parent := u.parent
	for p != parent[p] {
		parent[p] = parent[parent[p]]
		p = parent[p]
	}
	return p
}

func (u *Uf) Union(p, q int) {
	rootP, rootQ := u.find(p), u.find(q)
	if rootP != rootQ {
		u.parent[rootP] = rootQ
	}
}

func (u *Uf) IsConnect(p, q int) bool {
	return u.find(p) == u.find(q)
}

func solve(board [][]byte) {
	m, n := len(board), len(board[0])
	u := NewUf(m*n + 2)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if (i == 0 || i == m-1 || j == 0 || j == n-1) && board[i][j] == 'O' {
				u.Union(i*n+j, m*n)
			} else if board[i][j] == 'O' {
				dx := []int{1, 0, -1, 0}
				dy := []int{0, 1, 0, -1}
				for k := 0; k < 4; k++ {
					x, y := i+dx[k], j+dy[k]
					if board[x][y] == 'O' {
						u.Union(i*n+j, x*n+y)
					}
				}
			}
		}
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if !u.IsConnect(i*n+j, m*n) && board[i][j] == 'O' {
				board[i][j] = 'X'
			}
		}
	}
}

第14课｜高级搜索

1. 剪枝的实现和特性

参考链接

• DFS 代码模板
• BFS 代码模板
• AlphaZero Explained
• 棋类复杂度

2. 剪枝实战题目解析：数独

实战题目

• 70. 爬楼梯

// 动态规划
func climbStairs(n int) int {
	i, j, k := 0, 1, 1
	for m := 1; m <=n; m++ {
		k = i + j
        i, j = j, k
	}
	return k
}
// dfs 记录中间值进行剪枝
func climbStairs(n int) int {
	mp := map[int]int{}
	var climb func(i int) int
	climb = func(i int) int {
		if i <= 2 {
			return i
		}
		if _, ok := mp[i]; !ok {
			mp[i] = climb(i-1) + climb(i-2)
		}
		return mp[i]
	}
	return climb(n)
}

• 22. 括号生成

// dfs
func generateParenthesis(n int) (res []string) {
	var generate func(l, r int, path string)
	generate = func(l, r int, path string) {
		if l == n && r == n {
			res = append(res, path)
			return
		}
		if l < n {
			generate(l+1, r, path+"(")
		}
		if r < l {
			generate(l, r+1, path+")")
		}
	}
	generate(0, 0, "")
	return res
}
// bfs, 需要结构体记录，左右括号数量和当前括号字符串

• 51. N皇后

func solveNQueens(n int) (res [][]string) {
    size := 1 << n - 1
    var dfs func(int, int, int, int, []int)
    dfs = func (row, cols, pie, na int, queens []int) {
        if row == n {
            ans := make([]string, n)
            for i := 0; i < n; i++ {
                s := make([]byte, n)
                for j := 0; j < n; j++ {
                    if queens[i] == j {
                        s[j] = 'Q' 
                    } else {
                        s[j] = '.'
                    }
                }
                ans[i] = string(s)
            }
            res = append(res, ans)
            return
        }
        bit := size & (^(cols | pie | na))
        for bit > 0 {
            p := bit & -bit // 获取最后一个位1
            bit &= bit - 1 // 移除最后一个1
            queens = append(queens, bits.OnesCount(uint(p-1)))
            dfs(row + 1, cols | p, (pie | p ) << 1, (na | p) >> 1, queens)
            queens = queens[:row]
        }
    }
    dfs(0, 0, 0, 0, []int{})
    return res
}

• 36. 有效的数独

// 自己写法
func isValidSudoku(board [][]byte) bool {
    if len(board) != 9 || len(board[0]) != 9 {
        return false
    }
    blocks, rows, cols := [9]map[byte]bool{},  [9]map[byte]bool{},  [9]map[byte]bool{}
    for i := 0; i < 9; i++ {
        blocks[i] = map[byte]bool{}
        rows[i] =  map[byte]bool{}
        cols[i] =  map[byte]bool{}
    }
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if board[i][j] != '.' {
                n := board[i][j]
                b := i / 3 * 3 + j / 3
                if rows[i][n] || cols[j][n] || blocks[b][n] {
                    return false
                }
                rows[i][n] = true
                cols[j][n] = true
                blocks[b][n] = true
            }
        }
    }
    return true
}
// 优化写法
func isValidSudoku(board [][]byte) bool {
    if len(board) != 9 || len(board[0]) != 9 {
        return false
    }
    blocks, rows, cols := [9][9]int{},  [9][9]int{},  [9][9]int{}
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if board[i][j] != '.' {
                n := board[i][j] - '1'
                b := i / 3 * 3 + j / 3
                if rows[i][n] > 0 || cols[j][n] > 0|| blocks[b][n] > 0 {
                    return false
                }
                rows[i][n]++
                cols[j][n]++
                blocks[b][n]++
            }
        }
    }
    return true
}

• 37. 解数独

// 自己写法
func solveSudoku(board [][]byte) {
    blocks, rows, cols := [9]map[byte]bool{},  [9]map[byte]bool{},  [9]map[byte]bool{}
    for i := 0; i < 9; i++ {
        blocks[i] =  map[byte]bool{}
        rows[i] = map[byte]bool{}
        cols[i] =  map[byte]bool{}
    }
    emptys := [][2]int{} // 需要填写的位置
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            n := board[i][j]
            if n == '.' {
                emptys = append(emptys, [2]int{i, j})
            } else {
                b := i / 3 * 3 + j / 3
                rows[i][n] = true
                cols[j][n] = true
                blocks[b][n] = true
            }
        }
    }
    var backtrack func(int) bool
    backtrack = func(idx int) bool {
        if idx == len(emptys) {
            return true
        }
        i, j := emptys[idx][0], emptys[idx][1]
        b := i / 3 * 3 + j / 3
        for num := byte('1'); num <= '9'; num++ {
            if rows[i][num] || cols[j][num] || blocks[b][num] {
                continue
            }
            rows[i][num], cols[j][num], blocks[b][num] = true, true, true
            board[i][j] = num
            if backtrack(idx + 1) {
                return true
            }
            rows[i][num], cols[j][num], blocks[b][num] = false, false, false
        }
        return false
    }
    backtrack(0)
}
// 高效写法
func solveSudoku(board [][]byte) {
    blocks, rows, cols := [9][9]int{},  [9][9]int{},  [9][9]int{}
    emptys := [][2]int{} // 需要填写的位置
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if board[i][j] == '.' {
                emptys = append(emptys, [2]int{i, j})
            } else {
                b := i / 3 * 3 + j / 3
                n := board[i][j] - '1'
                rows[i][n]++
                cols[j][n]++
                blocks[b][n]++
            }
        }
    }
    var backtrack func(int) bool
    backtrack = func(idx int) bool {
        if idx == len(emptys) {
            return true
        }
        i, j := emptys[idx][0], emptys[idx][1]
        b := i / 3 * 3 + j / 3
        for num := 0; num < 9; num++ {
            if rows[i][num] == 1 || cols[j][num] == 1 || blocks[b][num] == 1 {
                continue
            }
            rows[i][num], cols[j][num], blocks[b][num] = 1, 1, 1
            board[i][j] = byte(num + '1')
            if backtrack(idx + 1) {
                return true
            }
            rows[i][num], cols[j][num], blocks[b][num] = 0, 0, 0
        }
        return false
    }
    backtrack(0)
}

3. 双向BFS的实现、特性和题解

实战题目

• 127. 单词接龙

func ladderLength(beginWord string, endWord string, wordList []string) int {

}

• 433. 最小基因变化

// 一条基因序列由一个带有8个字符的字符串表示，其中每个字符都属于 "A", "C", "G", "T"中的任意一个
func minMutation(start string, end string, bank []string) int {

}

课后作业

• 总结双向 BFS 代码模版，请同学们提交在第 7 周学习总结中。

4. 启发式搜索的实现、特性和题解

参考链接

• A* 代码模板
• 相似度测量方法
• 二进制矩阵中的最短路径的 A* 解法
• 8 puzzles 解法比较

实战题目

• 1091. 二进制矩阵中的最短路径

// A* Search 启发式搜索
type Node struct {
    x, y, f int
}
func shortestPathBinaryMatrix(grid [][]int) (cnt int) {
    
}
// bfs
func shortestPathBinaryMatrix(grid [][]int) (cnt int) {
    m, n := len(grid), len(grid[0])
    if grid[0][0] == 1 || grid[m - 1][n - 1] == 1{
        return -1
    }
    if m == 1 && n == 1 {
        return 1
    }
    dx := []int{0, 1, 0, -1, -1, 1, -1, 1}
    dy := []int{1, 0, -1, 0, -1, 1 , 1, -1}
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    queue := [][2]int{{0, 0}}
    visited[0][0] = true
    for len(queue) > 0 {
        cnt++
        for size := len(queue); size > 0; size-- {
            i, j := queue[0][0], queue[0][1]
            queue = queue[1:]
            for k := 0; k < 8; k++ {
                x, y := i + dx[k], j + dy[k]
                if x >= 0 && x < m && y >= 0 && y < n && !visited[x][y] && grid[x][y] != 1 {
                    if x == m - 1 && y == n - 1 {
                        return cnt + 1
                    }
                    queue = append(queue, [2]int{x, y})
                    visited[x][y] = true   
                }
            }
        }
    }
    return -1
}

• 773. 滑动谜题

func slidingPuzzle(board [][]int) int {

}

• 37. 解数独

// 方法二：位预算优化
// 方法三：枚举优化
// 方法一：高效写法
func solveSudoku(board [][]byte) {
    blocks, rows, cols := [9][9]int{},  [9][9]int{},  [9][9]int{}
    emptys := [][2]int{} // 需要填写的位置
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if board[i][j] == '.' {
                emptys = append(emptys, [2]int{i, j})
            } else {
                b := i / 3 * 3 + j / 3
                n := board[i][j] - '1'
                rows[i][n]++
                cols[j][n]++
                blocks[b][n]++
            }
        }
    }
    var backtrack func(int) bool
    backtrack = func(idx int) bool {
        if idx == len(emptys) {
            return true
        }
        i, j := emptys[idx][0], emptys[idx][1]
        b := i / 3 * 3 + j / 3
        for num := 0; num < 9; num++ {
            if rows[i][num] == 1 || cols[j][num] == 1 || blocks[b][num] == 1 {
                continue
            }
            rows[i][num], cols[j][num], blocks[b][num] = 1, 1, 1
            board[i][j] = byte(num + '1')
            if backtrack(idx + 1) {
                return true
            }
            rows[i][num], cols[j][num], blocks[b][num] = 0, 0, 0
        }
        return false
    }
    backtrack(0)
}

第15课 | 红黑树和AVL树

AVL树和红黑树的实现和特性

参考链接

• 平衡树

本周作业及下周预习

请同学们优先完成中等难度题目，每周的作业要求是提交 2 道作业题目，其他题目可根据自身情况选择练习。

本周作业

简单

• 70. 爬楼梯

中等

• 208. 实现 Trie (前缀树)
• 547. 朋友圈
• 200. 岛屿数量
• 130. 被围绕的区域
• 36. 有效的数独
• 22. 括号生成
• 127. 单词接龙
• 433. 最小基因变化

困难

• 212. 单词搜索 II
• 51. N皇后
• 37. 解数独

下周预习

预习知识点：

• 位图：如何实现网页爬虫中的 URL 去重功能？
• 概率统计：如何利用朴素贝叶斯算法过滤垃圾短信？
• 排序（上）：为什么插入排序比冒泡排序更受欢迎？
• 排序（下）：如何用快排思想在 O(n) 内查找第 K 大元素？
• 线性排序：如何根据年龄给 100 万用户数据排序？
• 排序优化：如何实现一个通用的、高性能的排序函数？
• 堆和堆排序：为什么说堆排序没有快速排序快？
• 拓扑排序：如何确定代码源文件的编译依赖关系？

预习题目：

• N 皇后
• LRU 缓存机制
• 有效的字母异位词