第4周 DFS、BFS、贪心、二分查找
2021-12-20
15分钟阅读时长
题目数量：20
第9课 | 深度优先搜索和广度优先搜索
1. 深度优先搜索、广度优先搜索的实现和特性
参考链接
2. 实战题目解析：二叉树的层次遍历等问题
实战题目
/**
* 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 nil
}
queue := []*TreeNode{root}
for len(queue) > 0 {
level := []int{}
for size := len(queue); size > 0; size-- {
node := queue[0]
queue = queue[1:]
level = append(level, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
res = append(res, level)
}
return res
}
// dfs
func levelOrder(root *TreeNode) (res [][]int) {
if root == nil {
return nil
}
var dfs func(level int, root *TreeNode)
dfs = func(level int, root *TreeNode) {
if root == nil {
return
}
if len(res) < level {
res = append(res, []int{})
}
res[level - 1] = append(res[level - 1], root.Val)
dfs(level + 1, root.Left)
dfs(level + 1, root.Right)
}
dfs(1, root)
return res
}
// bfs
func minMutation(start string, end string, bank []string) (ans int) {
mp := map[string]bool{}
for _, b := range bank {
mp[b] = true
}
if !mp[end] || len(start) != len(end){
return -1
}
ws := []byte{'A', 'C', 'G', 'T'}
used := map[string]bool{}
queue := []string{start}
used[start] = true
n := len(start)
for len(queue) > 0 {
for size := len(queue); size > 0; size-- {
w := queue[0]
if w == end {
return ans
}
queue = queue[1:]
b := []byte(w)
for i := 0; i < n; i++ {
o := b[i]
for _, c := range ws {
b[i] = c
if used[string(b)] {
continue
}
if mp[string(b)] {
queue = append(queue, string(b))
used[string(b)] = true
}
}
b[i] = o
}
}
ans++
}
return -1
}
- 22. 括号生成 重点
// dfs，还有其他写法
func generateParenthesis(n int) (res []string) {
var generate func(int, int, string)
generate = func(left, right int, path string) {
if left == n && right == n {
res = append(res, path)
return
}
if left < n {
generate(left + 1, right, path + "(")
}
if right < left {
generate(left, right + 1, path + ")")
}
}
generate(0, 0, "")
return res
}
// bfs
// 其他写参考官方
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// bfs
func largestValues(root *TreeNode) (res []int) {
if root == nil {
return res
}
queue := []*TreeNode{root}
for len(queue) > 0 {
max := math.MinInt32
for size := len(queue); size > 0; size-- {
node := queue[0]
queue = queue[1:]
if max < node.Val {
max = node.Val
}
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
res = append(res, max)
}
return res
}
// dfs
课后作业
// 单bfs
func ladderLength(beginWord string, endWord string, wordList []string) int {
mp := map[string]struct{}{}
for _, word := range wordList {
mp[word] = struct{}{}
}
mp[beginWord] = struct{}{}
if _, ok := mp[endWord]; !ok {
return 0
}
cnt := 0
queue := []string{beginWord}
visited := map[string]struct{}{}
visited[beginWord] = struct{}{}
wordLen := len(beginWord)
for len(queue) > 0 {
cnt++
for size := len(queue); size > 0; size-- {
w := queue[0]
queue = queue[1:]
s := []byte(w)
// for i, b := range s {
for i := 0; i < wordLen; i++ {
b := s[i]
for j := byte('a'); j <= 'z'; j++ {
if j == b {
continue
}
s[i] = j
nextWord := string(s)
if _, ok := mp[nextWord]; !ok {
continue
}
if nextWord == endWord {
return cnt + 1
}
if _, ok := visited[nextWord]; !ok {
queue = append(queue, nextWord)
visited[nextWord] = struct{}{}
}
}
s[i] = b
}
}
}
return 0
}
// 双向 bfs
func ladderLength(beginWord string, endWord string, wordList []string) int {
mp := map[string]struct{}{}
for _, word := range wordList {
mp[word] = struct{}{}
}
mp[beginWord] = struct{}{}
if _, ok := mp[endWord]; !ok {
return 0
}
cnt := 0
beginMap := map[string]struct{}{}
beginMap[beginWord] = struct{}{}
endMap := map[string]struct{}{}
endMap[endWord] = struct{}{}
visited := map[string]struct{}{}
wordLen := len(beginWord)
for len(beginMap) > 0 && len(endMap) > 0 {
cnt++
if len(beginMap) > len(endMap) {
beginMap, endMap = endMap, beginMap
}
tmpMap := map[string]struct{}{}
for w, _ := range beginMap {
s := []byte(w)
for i := 0; i < wordLen; i++ {
b := s[i]
for j := byte('a'); j <= 'z'; j++ {
if j == b {
continue
}
s[i] = j
nextWord := string(s)
if _, ok := mp[nextWord]; !ok {
continue
}
if _, ok := endMap[nextWord]; ok {
return cnt + 1
}
if _, ok := visited[nextWord]; !ok {
tmpMap[nextWord] = struct{}{}
visited[nextWord] = struct{}{}
}
}
s[i] = b
}
}
beginMap = tmpMap
}
return 0
}
// bfs
func findLadders(beginWord string, endWord string, wordList []string) (res [][]string) {
mp := map[string]struct{}{}
for _, word := range wordList {
mp[word] = struct{}{}
}
if _, ok := mp[endWord]; !ok {
return res
}
from := map[string][]string{}
from[beginWord] = []string{}
steps := map[string]int{}
queue := []string{beginWord}
step := 0
var found bool
for len(queue) > 0 {
step++
for size := len(queue); size > 0; size-- {
curWord := queue[0]
queue = queue[1:]
s := []byte(curWord)
for i, b := range s {
for j := byte('a'); j <= 'z'; j++ {
s[i] = j
nextWord := string(s)
if steps[nextWord] == step {
from[nextWord] = append(from[nextWord], curWord)
}
if _, ok := mp[nextWord]; !ok {
continue
}
delete(mp, nextWord)
queue = append(queue, nextWord)
if _, ok := from[nextWord]; !ok {
from[nextWord] = []string{}
}
from[nextWord] = append(from[nextWord], curWord)
steps[nextWord] = step
if nextWord == endWord {
found = true
}
}
s[i] = b
}
}
if found {
step++
break
}
}
path := make([]string, step)
path[step - 1] = endWord
var dfs func(string, int)
dfs = func(preWord string, idx int) {
if preWord == beginWord {
res = append(res, append([]string(nil), path...))
return
}
for _, pre := range from[preWord] {
path[idx - 1] = pre
dfs(pre, idx - 1)
path[idx - 1] = ""
}
}
dfs(endWord, step - 1)
return res
}
// 双向 bfs
func findLadders(beginWord string, endWord string, wordList []string) (res [][]string) {
mp := map[string]struct{}{}
// 因为需要快速判断扩展出的单词是否在 wordList 里，因此需要将 wordList 存入哈希表，这里命名为「字典」
for _, word := range wordList {
mp[word] = struct{}{}
}
// 特殊用例判断
if _, ok := mp[endWord]; !ok {
return res
}
from := map[string][]string{}
// 第 1 步：广度优先遍历建图
// 记录扩展出的单词是在第几次扩展的时候得到的，key：单词，value：在广度优先遍历的第几层
steps1 := map[string]int{beginWord: 0}
steps2 := map[string]int{endWord: 0}
q1 := []string{beginWord}
q2 := []string{endWord}
step :=[2]int{}
found := false
update := func(q []string, steps1, steps2 map[string]int, flag int) []string {
step[flag]++
for size := len(q); size > 0; size-- {
currWord := q[0]
q = q[1:]
s := []byte(currWord)
for i, b := range s {
// 将每一位替换成 26 个小写英文字母
for j := byte('a'); j <= 'z'; j++ {
s[i] = j
nextWord := string(s)
if _, ok := mp[nextWord]; !ok {
continue
}
stepTmp, ok := steps1[nextWord]
if ok && step[flag] > stepTmp {
continue
}
if !ok || (ok && stepTmp == step[flag]) {
if flag == 0 {
from[nextWord] = append(from[nextWord], currWord)
} else {
from[currWord] = append(from[currWord], nextWord)
}
}
// 这一层扩展出的单词进入队列
q = append(q, nextWord)
// 记录 nextWord 的 step
steps1[nextWord] = step[flag]
// 当前层找到了
if _, ok := steps2[nextWord]; ok {
found = true
}
}
//改回原单词
s[i] = b
}
}
if found {
step[flag]++
}
return q
}
for len(q1) > 0 && len(q2) > 0 && !found {
if len(q1) < len(q2) {
q1 = update(q1, steps1, steps2, 0)
} else {
q2 = update(q2, steps2, steps1, 1)
}
}
// 第 2 步：深度优先遍历找到所有解，从 endWord 恢复到 beginWord ，所以每次尝试操作 path 列表的头部
if found {
l := step[0] + step[1]
path := make([]string, l)
var dfs func(string, int)
dfs = func(nextWord string, idx int) {
if nextWord == beginWord {
res = append(res, append([]string(nil), path...))
return
}
for _, word := range from[nextWord] {
path[idx - 1] = word
dfs(word, idx - 1)
path[idx - 1] = ""
}
}
path[l - 1] = endWord
dfs(endWord, l - 1)
}
return res
}
// 命名规范版本
func findLadders(beginWord string, endWord string, wordList []string) (res [][]string) {
mp := map[string]struct{}{}
for _, word := range wordList {
mp[word] = struct{}{}
}
if _, ok := mp[endWord]; !ok {
return res
}
from := map[string][]string{}
beginStep, endStep := map[string]int{beginWord: 0}, map[string]int{endWord: 0}
beginQueue, endQueue := []string{beginWord}, []string{endWord}
steps := [2]int{}
var found bool
update := func(q []string, step1, step2 map[string]int, flag int) []string {
steps[flag]++
for size := len(q); size > 0; size-- {
curWord := q[0]
q = q[1:]
s := []byte(curWord)
for i, b := range s {
for j := byte('a'); j <= 'z'; j++ {
s[i] = j
nextWord := string(s)
if _, ok := mp[nextWord]; !ok || j == b {
continue
}
oldStep, ok := step1[nextWord]
if ok && oldStep < steps[flag] {
continue
}
if !ok || oldStep == steps[flag] {
if flag == 0 {
from[nextWord] = append(from[nextWord], curWord)
} else {
from[curWord] = append(from[curWord], nextWord)
}
}
q = append(q, nextWord)
step1[nextWord] = steps[flag]
if _, ok := step2[nextWord]; ok {
found = true
}
}
s[i] = b
}
}
if found {
steps[flag]++
}
return q
}
for len(beginQueue) > 0 && len(endQueue) > 0 && !found {
if len(beginQueue) <= len(endQueue) {
beginQueue = update(beginQueue, beginStep, endStep, 0)
} else {
endQueue = update(endQueue, endStep, beginStep, 1)
}
}
if found {
step := steps[0] + steps[1]
path := make([]string, step)
path[step-1] = endWord
var dfs func(string, int)
dfs = func(s string, i int) {
if s == beginWord {
res = append(res, append([]string(nil), path...))
return
}
for _, word := range from[s] {
path[i-1] = word
dfs(word, i-1)
//path[i-1] = ""
}
}
dfs(endWord, step-1)
}
return res
}
// dfs
// bfs
var fx = [][2]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
func numIslands(grid [][]byte) (ans int) {
n, m := len(grid), len(grid[0])
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if grid[i][j] == '1' {
ans++
grid[i][j] = '0'
queue := [][2]int{{i, j}}
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
for _, f := range fx {
ni, nj := cur[0] + f[0], cur[1] + f[1]
if 0 <= ni && ni < n && 0 <= nj && nj < m && grid[ni][nj] == '1' {
grid[ni][nj] = '0'
queue = append(queue, [2]int{ni, nj})
}
}
}
}
}
}
return ans
}
// dfs
// bfs
func updateBoard(board [][]byte, click []int) [][]byte {
n, m := len(board), len(board[0])
queue := [][]int{click}
for len(queue) > 0 {
click = queue[0]
queue = queue[1:]
x, y := click[0], click[1]
if board[x][y] == 'M' || board[x][y] == 'X' {
board[x][y] = 'X'
} else {
//计算周围的地雷
count := 0
for i := -1; i <= 1; i++ {
for j := -1; j <= 1; j++ {
if i == 0 && j == 0 {
continue
}
nx, ny := x + i, y + j
if 0 <= nx && nx < n && 0 <= ny && ny < m && (board[nx][ny] == 'M' || board[nx][ny] == 'X'){
count++
}
}
}
//有地雷，标注地雷的个数
if count > 0 {
board[x][y] = byte(count + '0')
} else {
//没有地雷，标注为B
board[x][y] = 'B'
for i := -1; i <= 1; i++ {
for j := -1; j <= 1; j++ {
if i == 0 && j == 0 {
continue
}
nx, ny := x + i, y + j
if 0 <= nx && nx < n && 0 <= ny && ny < m && board[nx][ny] == 'E' {
queue = append(queue, []int{nx, ny})
board[nx][ny] = 'B'
}
}
}
}
}
}
return board
}
第10课 | 贪心算法
贪心的实现、特性及实战题目解析
参考链接
func coinChange(coins []int, amount int) int {
dp := make([]int, amount + 1)
for i := 1; i <= amount; i++ {
dp[i] = amount + 1 //初始化dp数组
//循环各个面值，找到dp[i]最优解
for _, coin := range coins {
if coin <= i && dp[i] > dp[i - coin] + 1 {
//递推公式
dp[i] = dp[i - coin] + 1
}
}
}
if dp[amount] > amount {
return -1
}
return dp[amount]
}
课后作业
// 写法一
func lemonadeChange(bills []int) bool {
five, ten := 0, 0
for _, bill := range bills {
if bill == 5 {
five++
} else if bill == 10 { // 10元是5元找零
five, ten = five - 1, ten + 1
} else if ten > 0 { // 有10元
five, ten = five - 1, ten - 1
} else { // 没有10元
five -= 3
}
if five < 0 { // 判断5元个数是否小于0
return false
}
}
return true
}
// 写法二
func lemonadeChange(bills []int) bool {
five, ten := 0, 0
for _, bill := range bills {
if bill == 5 {
five++
} else if bill == 10 {
if five < 0 {
return false
}
five--
ten++
} else { // 20
if five > 0 && ten > 0 {
five--
ten--
} else if five >= 3 {
five -= 3
} else {
return false
}
}
}
return true
}
// 贪心
func maxProfit(prices []int) (ans int) {
for i := 1; i < len(prices); i++ {
if prices[i] > prices[i-1] {
ans += prices[i] - prices[i-1]
}
}
return ans
}
// dp
func maxProfit(prices []int) int {
dp0, dp1 := 0, -prices[0]
for i := 0; i < len(prices); i++ {
dp0, dp1 = max(dp0, dp1 + prices[i]), max(dp0 - prices[i], dp1)
}
return dp0
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func findContentChildren(g []int, s []int) int {
sort.Ints(g)
sort.Ints(s)
child := 0
for j := 0; child < len(g) && j < len(s); j++ {
if g[child] <= s[j] {
child++
}
}
return child
}
- 874. 模拟行走机器人 重点在方向控制
// 效率最高写法
func robotSim(commands []int, obstacles [][]int) int {
obsMap := map[int]bool{}
for _, obstacle := range obstacles {
key := calculateHashKey(obstacle)
obsMap[key] = true
}
//方向数组
dx := []int{0, 1, 0, -1}
dy := []int{1, 0, -1, 0}
ans := 0
x, y := 0, 0
direction := 0 //0-N 1-E 2-S 3-W
for _, cmd := range commands {
if cmd == -2 { // 左转
direction = (direction + 3) % 4
} else if cmd == -1 { // 右转
direction = (direction + 1) % 4
} else {
for i := 0; i < cmd; i++ {
nx := x + dx[direction]
ny := y + dy[direction]
if obsMap[calculateHashKey([]int{nx, ny})] {
break
}
x, y = nx, ny
}
if tVal := x * x + y * y; tVal > ans {
ans = tVal
}
}
}
return ans
}
func calculateHashKey(obstacle []int) int {
return (30000 + obstacle[0]) * 60001 + (30000 + obstacle[1])
}
// 反向
func canJump1(nums []int) bool {
revCanJump := len(nums) - 1
for i := revCanJump; i >= 0; i-- {
if i + nums[i] >= revCanJump {
revCanJump = i
}
}
return revCanJump == 0
}
// 正向
func canJump(nums []int) bool {
can := nums[0]
for i := 1; i < len(nums); i++ {
if can < i {
return false
}
can = max(can, i + nums[i])
}
return true
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func jump(nums []int) (ans int) {
n := len(nums)
if n < 2 {
return ans
}
ans = 1
curMaxJump, preMaxJump := nums[0], nums[0]
for i := 1; i < n; i++ {
if i > preMaxJump {
preMaxJump = curMaxJump
ans++
}
if i + nums[i] > curMaxJump {
curMaxJump = i + nums[i]
}
}
return ans
}
第11课 | 二分查找
二分查找的实现、特性及实战题目解析
参考链接
实战题目
// 二分
// 牛顿迭代
// 二分
// 牛顿迭代
课后作业
// 标准二分
func search(nums []int, target int) int {
l, r := 0, len(nums) - 1
for l <= r {
mid := l + (r - l) >> 1
if nums[mid] == target {
return mid
} else if nums[l] <= nums[mid] { // nums[l] 可改为 nums[0]
if nums[l] <= target && target < nums[mid] {
r = mid - 1
} else {
l = mid + 1
}
} else {
if nums[mid] < target && target <= nums[r] {
l = mid + 1
} else {
r = mid - 1
}
}
}
return -1
}
// 位运算二分
// 二分查找
func searchMatrix(matrix [][]int, target int) bool {
m, n := len(matrix), len(matrix[0])
l, r := 0, m * n - 1
for l <= r {
mid := l + (r - l) >> 1
num := matrix[mid/n][mid%n]
if num < target {
l = mid + 1
} else if num > target {
r = mid - 1
} else {
return true
}
}
return false
}
// 官方使用系统库，一次、二次二分查找
// 写法一
func findMin(nums []int) int {
low, high := 0, len(nums) - 1
for low < high {
pivot := low + (high - low) >> 1
if nums[pivot] > nums[high] {
low = pivot + 1
} else {
high = pivot
}
}
return nums[low]
}
// 写法二： 复杂写法
func findMin(nums []int) int {
l, r := 0, len(nums) - 1
if nums[l] < nums[r] || l == r {
return nums[l]
}
for l < r {
m := l + (r - l) >> 1
if nums[m] > nums[m + 1] {
return nums[m + 1]
}
if nums[m - 1] > nums[m] {
return nums[m]
}
if nums[l] < nums[m] {
l = m + 1
} else {
r = m
}
}
return nums[l]
}
- 使用二分查找，寻找一个半有序数组 [4, 5, 6, 7, 0, 1, 2] 中间无序的地方 说明：同学们可以将自己的思路、代码写在第 4 周的学习总结中
本周作业及第6周预习
下周为期中考试周，无视频课程，会安排覃超老师进行答疑直播（具体时间以微信班级群通知为准）。请同学们自行复习~
本周作业
简单
使用二分查找，寻找一个半有序数组 [4, 5, 6, 7, 0, 1, 2] 中间无序的地方 说明：同学们可以将自己的思路、代码写在第 3 周的学习总结中