字节跳动2022冬季高频面试题

206. 反转链表

迭代法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func reverseList(head *ListNode) *ListNode {
    // 特殊情况判断
    if head == nil {
        return head
    }
    // 记录两个相邻节点
    pre, next := head, head.Next
    // 前节点next设空，防止成环
    pre.Next = nil
    for next != nil {
        // 翻转方向，并后移指针
        pre, next, next.Next = next, next.Next, pre
    }

    return pre
}
递归法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func reverseList(head *ListNode) *ListNode {
    // 终止条件：找到尾节点
    if head == nil || head.Next == nil {
        return head
    }
    // 保存下一个节点
    next := head.Next
    // 返回尾节点作为新的头节点
    newHead := reverseList(head.Next)
    // 将当前节点next设nil，以防止成环
    head.Next = nil
    // 链表反向
    next.Next = head

    return newHead
}

23. 合并K个升序链表

归并法-递归实现
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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func mergeList(list1, list2 *ListNode) *ListNode {
    // 使用虚拟头节点简化代码
    vhead := &ListNode{}
    current := vhead
    // 合并有序链表
    for list1 != nil || list2 != nil {
        // list2已遍历完，则直接取list1剩余部分
        if list2 == nil {
            current.Next, current = list1, list1
            break
        }
        // list1已遍历完，则直接取list2剩余部分
        if list1 == nil {
            current.Next, current = list2, list2
            break
        }
        // 取两者中较小值添加到合并链表尾部
        if list1.Val < list2.Val {
            current.Next, current = list1, list1
            list1 = list1.Next
        } else {
            current.Next, current = list2, list2
            list2 = list2.Next
        }
    }
    return vhead.Next
}

func mergeKLists(lists []*ListNode) *ListNode {
    // 边界情况
    if len(lists) == 0 {
        return nil
    }
    if len(lists) == 1 {
        return lists[0]
    }
    // 归并完左右两部分以后合并
    mid := len(lists) >> 1
    return mergeList(mergeKLists(lists[:mid]), mergeKLists(lists[mid:]))
}
归并法-迭代实现
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
52
53
54
55
56
57
58
59
60
61
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func mergeList(list1, list2 *ListNode) *ListNode {
    // 使用虚拟头节点简化代码
    vhead := &ListNode{}
    current := vhead
    // 合并有序链表
    for list1 != nil || list2 != nil {
        // list2已遍历完，则直接取list1剩余部分
        if list2 == nil {
            current.Next, current = list1, list1
            break
        }
        // list1已遍历完，则直接取list2剩余部分
        if list1 == nil {
            current.Next, current = list2, list2
            break
        }
        // 取两者中较小值添加到合并链表尾部
        if list1.Val < list2.Val {
            current.Next, current = list1, list1
            list1 = list1.Next
        } else {
            current.Next, current = list2, list2
            list2 = list2.Next
        }
    }
    return vhead.Next
}

func mergeKLists(lists []*ListNode) *ListNode {
    // 特殊情况
    if len(lists) == 0 {
        return nil
    }

    // 迭代归并
    for len(lists) > 1 {
        length := len(lists)
        newLen := length / 2
        // 每次合并两个相邻位置
        for i := 0; i < length / 2; i++ {
            lists[i] = mergeList(lists[2*i], lists[2*i+1])
        }
        // 奇数长度最后一个无需合并
        if length % 2 > 0 {
            lists[length/2] = lists[length-1]
            newLen++
        }
        // 缩短lists长度
        lists = lists[:newLen]
    }

    return lists[0]
}
小顶堆
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

type KListHeap struct {
    // 链表数组的索引作为堆元素
    idxHeap []int
    // 链表数组
    lists []*ListNode
    // 链表数组的长度
    len int
}

func makeKListHeap(lists []*ListNode) *KListHeap {
    idxHeap := make([]int, len(lists)+1)
    len := len(lists)
    for k := range idxHeap {
        idxHeap[k] = k-1
    }
    klh := &KListHeap{idxHeap, lists, len}
    // O(n) 建堆
    for k := klh.len / 2; k >= 1; k-- {
        klh.down(k)
    }
    return klh
}

func (klh *KListHeap) down(k int) {
    x := k
    // 和左孩子比较
    if 2 * k <= klh.len {
        node := klh.lists[klh.idxHeap[x]]
        left := klh.lists[klh.idxHeap[2*k]]
        if left != nil && (node == nil || left.Val < node.Val) {
            x = 2 * k
        }
    }
    // 和右孩子比较
    if 2 * k + 1 <= klh.len {
        node := klh.lists[klh.idxHeap[x]]
        right := klh.lists[klh.idxHeap[2*k+1]]
        if right != nil && (node == nil || right.Val < node.Val) {
            x = 2 * k + 1
        }
    }
    // 需要交换则继续下沉
    if x != k {
        klh.idxHeap[k], klh.idxHeap[x] = klh.idxHeap[x], klh.idxHeap[k]
        klh.down(x)
    }
}

func (klh *KListHeap) pop() *ListNode {
    // 排除特殊情况
    if klh.len == 0 {
        return nil
    }
    // 堆顶
    ridx := klh.idxHeap[1]
    // 堆顶对应链表头
    node := klh.lists[ridx]
    // 如果当前链表头不为空, 则后移并重排堆
    if node != nil {
        klh.lists[ridx] = node.Next
        klh.down(1)
    }
    return node
}

func mergeKLists(lists []*ListNode) *ListNode {
    heap := makeKListHeap(lists)
    vhead := &ListNode{}
    current := vhead
    // 每次将堆顶弹出，添加到新链表尾
    for node := heap.pop(); node != nil; node = heap.pop() {
        current.Next, current = node, node
    }
    return vhead.Next
}

25. K 个一组翻转链表

模拟法
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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func reverse(head *ListNode) *ListNode {
    // 特殊情况
    if head == nil {
        return head
    }
    pre, next := head, head.Next
    // 避免成环
    pre.Next = nil
    // 两两翻转
    for next != nil {
        pre, next, next.Next = next, next.Next, pre
    }
    return pre
}

func reverseKGroup(head *ListNode, k int) *ListNode {
    vhead := &ListNode{}
    // 已处理完成的链表尾与正要处理的链表头
    preTail, curHead := vhead, head
    for {
        // 获取需处理的链表尾
        curTail := curHead
        for i := 1; curTail != nil && i < k; i++ {
            curTail = curTail.Next
        }
        // 剩余链表长度不足, 无需处理
        if curTail == nil {
            preTail.Next = curHead
            break
        }
        // 将已处理完成链表尾与当前链表段连接
        curTail.Next, curHead, preTail.Next, preTail = nil, curTail.Next, curTail, curHead
        // 翻转当前链表段
        reverse(preTail)
    }

    return vhead.Next
}

143. 重排链表

链表寻中 & 链表翻转 & 链表合并
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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func reverse(head *ListNode) *ListNode {
    if head == nil {
        return head
    }
    pre, next := head, head.Next
    pre.Next = nil
    for next != nil {
        pre, next, next.Next = next, next.Next, pre
    }
    return pre
}

func reorderList(head *ListNode)  {
    // 链表寻中: 
    // 2n或2n+1个节点寻找到的是第n+1个
    mid, fast := head, head
    for fast != nil && fast.Next != nil {
        mid, fast = mid.Next, fast.Next.Next
    }

    list1 := head
    // 翻转后半链表
    list2 := reverse(mid)

    vhead := &ListNode{}
    current := vhead
    // 合并链表
    for list1 != mid && list2 != nil {
        current, current.Next, list1 = list1, list1, list1.Next
        current, current.Next, list2 = list2, list2, list2.Next
    }
}

199. 二叉树的右视图

深度优先遍历
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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var MAX_NODE_COUNT int = 100
func rightSideView(root *TreeNode) []int {
    ans := make([]int, 0, MAX_NODE_COUNT)
    var dfs func(rt *TreeNode, depth int) 
    dfs = func(rt *TreeNode, depth int) {
        if rt == nil {
            return
        }
        // 每层首个访问的节点即为最右
        if len(ans) <= depth {
            ans = append(ans, rt.Val)
        }
        // 先访问右节点，保证最右边先访问到
        dfs(rt.Right, depth+1)
        dfs(rt.Left, depth+1)
    }

    dfs(root, 0)
    return ans
}
广度优先遍历
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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var MAX_NODE_COUNT int = 100
func rightSideView(root *TreeNode) []int {
    // 特殊情况
    if root == nil {
        return []int{}
    }

    ans := make([]int, 0, MAX_NODE_COUNT)
    queue := make([]*TreeNode, 0, MAX_NODE_COUNT)
    queue = append(queue, root)

    // 层序遍历
    for len(queue) > 0 {
        length := len(queue)
        // 保存每层最右节点值
        ans = append(ans, queue[length-1].Val)
        for i := 0; i < length; i++ {
            node := queue[i]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        // 更新queue
        queue = queue[length:]
    }

    return ans
}

236. 二叉树的最近公共祖先

回溯法
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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    var ans *TreeNode
    var backtrace func(rt *TreeNode) bool
    backtrace = func(rt *TreeNode) bool {
        // 边界情况
        if rt == nil {
            return false
        }

        // 左右子树是否存在目标节点
        ok1 := backtrace(rt.Left)
        ok2 := backtrace(rt.Right)
        // 自身是否为目标节点
        ok3 := (rt == p || rt == q)

        // 最近公共祖先需满足3种ok的两种
        if (ok1 && ok2) || (ok1 || ok2) && ok3 {
            ans = rt
        }

        // 返回当前子树是否存在目标节点
        return ok1 || ok2 || ok3
    }

    backtrace(root)
    return ans
}

103. 二叉树的锯齿形层序遍历

广度优先遍历
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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

var MAX_NODE_COUNT = 2000

func zigzagLevelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    ans := make([][]int, 0, MAX_NODE_COUNT)
    queue := make([]*TreeNode, 0, MAX_NODE_COUNT)
    queue = append(queue, root)
    for len(queue) > 0 {
        length := len(queue)
        layer := make([]int, 0, len(queue))
        // 根据所在层数判断遍历方向
        if len(ans) % 2 == 0 {
            for _, node := range queue {
                layer = append(layer, node.Val)
            }
        } else {
            for i := len(queue)-1; i >= 0; i-- {
                node := queue[i]
                layer = append(layer, node.Val)
            }
        }
        ans = append(ans, layer)

        // 继续遍历下一层
        for i := 0; i < length; i++ {
            node := queue[i]
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        // 更新队列
        queue = queue[length:]
    }

    return ans
}

5. 最长回文子串

动态规划
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
func longestPalindrome(s string) string {
    // dp[i][j]: 长度为i, 以j开始的字符串s[j:i+j]是否为回文串
    // dp[i][j] = dp[i-2][j+1] && s[j] == s[i+j-1]
    // 初始条件: dp[0][...] = true; dp[1][...] = true
    // 由于递推只与上两次结果有关，这里只保存上两次结果
    dp0 := make([]bool, len(s))
    dp1 := make([]bool, len(s))
    for k := range dp0 {
        dp0[k], dp1[k] = true, true
    }
    dp := make([]bool, len(s))

    ans := s[0:1]
    // 遍历所有长度
    for i := 2; i <= len(s); i++ {
        // 遍历所有开始位置
        for j := 0; i + j <= len(s); j++ {
            dp[j] = (s[j] == s[i+j-1] && dp0[j+1])
            // 由于i不减，只要满足即可替换答案
            if dp[j] {
                ans = s[j:i+j]
            }
        }
        // 更新dp
        copy(dp0, dp1)
        copy(dp1, dp)
    }

    return ans
}
中心扩展
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func longestPalindrome(s string) string {
    ans := ""
    for k := range s {
        // k 为中心
        l := 0
        for ; k - l >= 0 && k + l < len(s) && s[k-l] == s[k+l]; l++ {
        }
        if 2 * l - 1 > len(ans) {
            ans = s[k-l+1:k+l]
        }
        // k 与 k+1 为中心
        l = 0
        for ; k - l >= 0 && k + l + 1 < len(s) && s[k-l] == s[k+l+1]; l++ {
        }
        if 2 * l > len(ans) {
            ans = s[k-l+1:k+l+1]
        }
    }

    return ans
}
马拉车
1
2
3
4
// 核心思想是 
// 以一个臂长足够长的位置作为对称中心，
// 找到其后面位置在前面的对称位置，
// 从而用已计算好的前面位置的臂长得到当前节点最短臂长

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
26
27
28
29
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func lengthOfLongestSubstring(s string) int {
    // 窗口不变性: 窗口内不存在重复字符
    ans := 0
    visited := map[byte]bool{}
    i, j := 0, 0
    for ; j < len(s); j++ {
        // 发生重复, 违背窗口不变性
        // 移动i指针, 缩减窗口, 保证窗口不变性
        if visited[s[j]] {
            for ; s[i] != s[j]; i++ {
                visited[s[i]] = false
            }
            i++
        }
        // 更新当前字符为已遍历
        visited[s[j]] = true
        // 更新最大长度
        ans = max(ans, j-i+1)
    }

    return ans
}

300. 最长递增子序列

动态规划
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
var MAX_NUM int = 10001
var MIN_NUM int = -10001

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func lengthOfLIS(nums []int) int {
    // dp[i][j]: 前i个元素, 刚好满足最长子序列长度为j的最小序列结尾元素
    // dp[i][j] = min(nums[i], dp[i-1][j]) if nums[i] > dp[i-1][j-1]
    // dp[i][j] = dp[i-1][j]
    // 由于只与上一轮结果相关, 因此可以压缩空间
    dp := make([]int, len(nums)+1)
    for k := range dp {
        dp[k] = MAX_NUM
    }
    dp[0] = MIN_NUM

    for i := 1; i <= len(nums); i++ {
        for j := i; j >= 1; j-- {
            if nums[i-1] > dp[j-1] {
                dp[j] = min(nums[i-1], dp[j])
            }
        }
    }

    for k := len(nums); k >= 1; k-- {
        if dp[k] != MAX_NUM {
            return k
        }
    }

    return 0
}
动态规划 & 二分优化
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
52
53
var MAX_NUM int = 10001
var MIN_NUM int = -10001

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func bSearch(arr []int, target int) int {
    // 查找第一个大于或等于target的值
    left, right := 0, len(arr)
    for left < right {
        mid := (left + right) >> 1
        if arr[mid] >= target {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left
}

func lengthOfLIS(nums []int) int {
    // dp[i][j]: 前i个元素, 刚好满足最长子序列长度为j的最小序列结尾元素
    // dp[i][j] = min(nums[i], dp[i-1][j]) if nums[i] > dp[i-1][j-1]
    // dp[i][j] = dp[i-1][j]
    // 由于只与上一轮结果相关, 因此可以压缩空间
    dp := make([]int, len(nums)+1)
    for k := range dp {
        dp[k] = MAX_NUM
    }
    dp[0] = MIN_NUM

    for i := 0; i < len(nums); i++ {
        // 由于dp具有单增的性质
        // 并且每个nums[i-1]最多只会更新一个与之最接近的元素
        // 因此可以使用二分优化
        j := bSearch(dp, nums[i])
        dp[j] = min(nums[i], dp[j])
    }

    // 找到最大长度
    for k := len(nums); k >= 1; k-- {
        if dp[k] != MAX_NUM {
            return k
        }
    }

    return 0
}

215. 数组中的第K个最大元素

堆
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
func findKthLargest(nums []int, k int) int {
    // 边界情况
    if len(nums) == 1 {
        return nums[0]
    }
    // 进行partition
    i, j := -1, len(nums)
    mid := nums[(i + j) >> 1]
    for i < j {
        i++
        for ; nums[i] > mid; i++ {
        }
        j--
        for ; nums[j] < mid; j-- {
        }
        if i < j {
            nums[i], nums[j] = nums[j], nums[i]
        }
    }

    // 判断第k大元素在左半还是右半
    if j + 1 >= k {
        return findKthLargest(nums[:j+1], k)
    }
    return findKthLargest(nums[j+1:], k-j-1)
}

33. 搜索旋转排序数组

二分查找
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
func search(nums []int, target int) int {
    left, right := 0, len(nums) - 1
    for left < right {
        mid := (left + right) >> 1
        // mid和target在相同升序子数组中
        if (nums[mid] <= nums[right]) == (target <= nums[right]) {
            if nums[mid] >= target {
                right = mid
            } else {
                left = mid + 1
            }
        } else {
        // mid和target在不同升序子数组中
            // mid在左数组, target在右数组
            if nums[mid] > target {
                left = mid + 1
            } else {
            // mid在右数组, target在左数组
                right = mid - 1
            }
        }
    }

    if nums[left] == target {
        return left
    }
    return -1
}

15. 三数之和

排序 & 双指针
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
func threeSum(nums []int) [][]int {
    // 排序
    sort.Ints(nums)
    ans := make([][]int, 0, len(nums))
    for i := 0; i < len(nums)-2; i++ {
        // 排除重复解
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        j, k := i+1, len(nums)-1
        // 双指针寻找目标值
        for j < k {
            // 比目标大则需要减小，故左移k
            if nums[j] + nums[k] > -nums[i] {
                k--
            } else if nums[j] + nums[k] < -nums[i] {
            // 比目标小则需要增大，故右移j
                j++
            } else {
            // 找到可行解
                ans = append(ans, []int{nums[i], nums[j], nums[k]})
                tmp := nums[j]
                // 排除重复解
                for j < k && nums[j] == tmp {
                    j++
                }
            }
        }
    }

    return ans
}

121. 买卖股票的最佳时机

动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func maxProfit(prices []int) int {
    // dp0: 未持有状态
    // dp1: 持有状态
    // 状态转移: dp0只能由dp1转换得到, dp1为当前最便宜的股票
    dp0, dp1 := 0, -prices[0]
    for _, v := range prices {
        dp0, dp1 = max(dp0, dp1+v), max(dp1, -v)
    }

    return dp0
}

42. 接雨水

两次遍历
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
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func trap(height []int) int {
    // ans_i = max( min( max(height[:i]), max(height[i+1:]) ) - height[i], 0 )
    // 方法0:
    // 对于i，分别求出lmax_i = max(height[0:i]) 和 rmax_i = max(height[i+1:]), 然后计算min(lmax_i, rmax_i)

    // 方法1：
    // 从左往右扫描：
    // ans_left_i = max( max(height[0:i]) - height[i], 0 )
    // 从右往左扫描:
    // ans_right_i = max( max(height[i+1:]) - height[i], 0 )
    // 合并结果
    // ans_i = min(ans_left_i, ans_right_i) 等价于初始公式
    n := len(height)
    ans := 0
    lmax := 0
    ansLeft := make([]int, n)
    for i, h := range height {
        ansLeft[i] = max(lmax - h, 0)
        lmax = max(lmax, h)
    }

    rmax := 0
    ansRight := make([]int, n)
    for j := n-1; j >= 0; j-- {
        h := height[j]
        ansRight[j] = max(rmax - h, 0)
        rmax = max(rmax, h)
    }

    for k := 0; k < n; k++ {
        ans += min(ansLeft[k], ansRight[k])
    }

    return ans
}
前缀最大值 & 后缀最大值 & 双指针
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
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func trap(height []int) int {
    // 方法2：
    // 记录左边的最大值lmax=max(height[:l])与右边的最大值rmax=max(height[r:])
    // 也是分两种情况:
    // 当lmax < rmax, 
    //     max(height[:i]) = lmax => min( lmax, max(height[i+1:]) ) = lmax
    //     => ans_i = max(lmax - height[i], 0)
    //     lmax = max(lmax, height[i])
    // 当lmax > rmax, 得到ans_j, 更新rmax
    // 当lmax == rmax, 任得一个即可
    n := len(height)
    i, j, lmax, rmax := 0, n-1, height[0], height[n-1]
    ans := 0
    for i <= j {
        if lmax < rmax {
            lmax = max(lmax, height[i])
            ans += max(lmax - height[i], 0)
            i++
        } else {
            rmax = max(rmax, height[j])
            ans += max(rmax - height[j], 0)
            j--
        }
    }

    return ans
}
单调栈 & 横向划分
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
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func trap(height []int) int {
    // 方法3：单调栈，横向划分
    // ans_i_j = (j - i - 1) * min() if i > height[k] && j > height[k], i < k < j
    n := len(height)
    ans := 0
    stack := make([]int, 0, n)
    for j, h := range height {
        for len(stack) > 0 && height[stack[len(stack)-1]] <= h {
            if len(stack) > 1 {
                i := stack[len(stack)-2]
                ans += (j - i - 1) * (min(height[i], height[j]) - height[stack[len(stack)-1]])
            }
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, j)
    }

    return ans
}

46. 全排列

回溯法
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
func permute(nums []int) [][]int {
    ans := make([][]int, 0, 1<<len(nums))
    // 记录已使用的元素
    visited := make([]bool, len(nums))
    // 记录当前排列
    current := make([]int, len(nums))
    var dfs func(depth int) 
    dfs = func(depth int) {
        if depth == len(nums) {
            // 复制当前合法排列并添加到结果中
            tmp := make([]int, len(current))
            copy(tmp, current)
            ans = append(ans, tmp)
            return
        }
        for k := range nums {
            // 回溯下一层
            if !visited[k] {
                current[depth] = nums[k]
                visited[k] = true
                dfs(depth+1)
                visited[k] = false
            }
        }
    }
    dfs(0)

    return ans
}

200. 岛屿数量

深度优先遍历
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
func numIslands(grid [][]byte) int {
    ans := 0
    for i, row := range grid {
        for j, v := range row {
            if v == '1' {
                ans++ 
                grid[i][j] = '0'
                queue := [][]int{[]int{i, j}}
                for len(queue) > 0 {
                    x := queue[0]
                    if x[0] - 1 >= 0 && grid[x[0]-1][x[1]] == '1' {
                        queue = append(queue, []int{x[0]-1, x[1]})
                        grid[x[0]-1][x[1]] = '0'
                    }
                    if x[0] + 1 < len(grid) && grid[x[0]+1][x[1]] == '1' {
                        queue = append(queue, []int{x[0]+1, x[1]})
                        grid[x[0]+1][x[1]] = '0'
                    }
                    if x[1] - 1 >= 0 && grid[x[0]][x[1]-1] == '1' {
                        queue = append(queue, []int{x[0], x[1]-1})
                        grid[x[0]][x[1]-1] = '0'
                    }
                    if x[1] + 1 < len(grid[0]) && grid[x[0]][x[1]+1] == '1' {
                        queue = append(queue, []int{x[0], x[1]+1})
                        grid[x[0]][x[1]+1] = '0'
                    }
                    queue = queue[1:]
                }
            }
        }
    }

    return ans
}

41. 缺失的第一个正数

标记法
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
func firstMissingPositive(nums []int) int {
    // n个数, 未出现的数肯定在1-n+1之间
    // 先将nums的所有非正数变为n+1
    // 利用nums的n个位置标记为负数，
    // 没有被标记为负数的即为答案
    n := len(nums)
    for k, v := range nums {
        if v <= 0 {
            nums[k] = n+1
        }
    }

    for _, v := range nums {
        if v <= -1 && v >= -n && nums[-v-1] > 0 {
            nums[-v-1] = -nums[-v-1]
        } else if v >= 1 && v <= n && nums[v-1] > 0 {
            nums[v-1] = -nums[v-1]
        }
    }

    for k, v := range nums {
        if v > 0 {
            return k + 1
        }
    }
    
    return n+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
func firstMissingPositive(nums []int) int {
    // n个数, 未出现的数肯定在1-n+1之间
    // 利用nums的n个位置填1-n的数
    
    n := len(nums)
    for i := 0; i < len(nums); i++ {
        // current位置的内容要和移动到next位置交换,
        // 直至current位置的值不在1-n范围内
        current := i
        next := nums[current] - 1
        for next >= 0 && next < len(nums) && nums[next] != nums[current] {
            nums[next], nums[current] = nums[current], nums[next]
            next = nums[current] - 1
        }
    }

    for i, v := range nums {
        if v != i + 1 {
            return i+1
        }
    }

    return n+1
}

54. 螺旋矩阵

模拟法
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
func spiralOrder(matrix [][]int) []int {
    // 右->下->左->上 方向
    directions := [4][2]int{[2]int{0, 1}, [2]int{1, 0}, [2]int{0, -1}, [2]int{-1, 0}}
    // 当前方向
    direct := 0
    // 记录已到达位置
    m, n := len(matrix), len(matrix[0])
    visited := make([][]bool, m)
    for k := range visited {
        visited[k] = make([]bool, n)
    }
    // 当前位置
    x, y := 0, 0
    ans := make([]int, 0, m*n)
    for i := 0; i < m*n; i++ {
        visited[x][y] = true
        ans = append(ans, matrix[x][y])
        dx, dy := directions[direct][0], directions[direct][1]
        if x + dx >= m || x + dx < 0 || y + dy >= n || y + dy < 0 || visited[x+dx][y+dy] {
            direct = (direct + 1) % len(directions)
            dx, dy = directions[direct][0], directions[direct][1]
        }
        x, y = x + dx, y + dy
    }

    return ans
}
分层模拟
1

146. LRU 缓存

双端队列 & map
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
type LRUListNode struct {
    prev *LRUListNode
    next *LRUListNode
    key int
    val int
}

type LRUList struct {
    head *LRUListNode
    tail *LRUListNode
    len int
}

func makeLRUList() LRUList {
    head, tail := &LRUListNode{}, &LRUListNode{}
    head.next, tail.prev = tail, head
    return LRUList{head, tail, 0}
}

func (lst *LRUList) moveToHead(node *LRUListNode) {
    prevNode, nextNode := node.prev, node.next
    prevNode.next, nextNode.prev = nextNode, prevNode

    prevNode, nextNode = lst.head, lst.head.next
    node.prev, node.next = prevNode, nextNode
    prevNode.next, nextNode.prev = node, node
}

func (lst *LRUList) pop() *LRUListNode {
    if lst.len == 0 {
        return nil
    }
    node := lst.tail.prev
    prevNode, nextNode := node.prev, node.next
    prevNode.next, nextNode.prev = nextNode, prevNode
    node.prev, node.next = nil, nil
    lst.len--

    return node
}

func (lst *LRUList) push(node *LRUListNode) {
    prevNode, nextNode := lst.head, lst.head.next
    node.prev, node.next = prevNode, nextNode
    prevNode.next, nextNode.prev = node, node
    lst.len++
}

type LRUCache struct {
    key2node map[int]*LRUListNode
    LRUList
    cap int
}


func Constructor(capacity int) LRUCache {
    lst := makeLRUList()
    key2node := map[int]*LRUListNode{}
    return LRUCache{key2node, lst, capacity}
}


func (this *LRUCache) Get(key int) int {
    if node, ok := this.key2node[key]; ok {
        this.moveToHead(node)
        return node.val
    }

    return -1
}


func (this *LRUCache) Put(key int, value int)  {
    if node, ok := this.key2node[key]; ok {
        this.moveToHead(node)
        node.val = value
        return
    }

    for this.len >= this.cap {
        node := this.pop()
        delete(this.key2node, node.key)
    }
    node := &LRUListNode{key: key, val: value}
    this.push(node)
    this.key2node[key] = node
}


/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */