第一周数组、链表、栈、队列

2021-11-25

10分钟阅读时长

题目数：19

本周作业

66.加一（Easy）半年内出题频次：

Facebook	字节跳动	微软	Amazon	快手	美团	Google	腾讯	华为	百度
0	0	3	3	0	0	4	0	0	0

// 写法一，面试推荐写法
func plusOne(digits []int) []int {
    n := len(digits)
    for i := n - 1; i >=0; i-- {
        digits[i] = (digits[i] + 1) % 10
        if digits[i] != 0 {
            return digits
        }
    }
    ans := make([]int, n + 1)
    ans[0] = 1
    return ans
}

// 写法二：
func plusOne(digits []int) []int {
    for i := len(digits) - 1; i >= 0; i-- {
        // 统计9的个数
        if digits[i] != 9 {
            digits[i]++
            for j := i + 1; j < len(digits); j++ {
                digits[j] = 0
            }
            return digits
        }
    }
    digits = make([]int, len(digits) + 1)
    digits[0] = 1
    return digits
}

21.合并两个有序链表（Easy）半年内出题频次：

Facebook	字节跳动	微软	Amazon	快手	美团	Google	腾讯	华为	百度
7	23	9	36	2	2	2	14	0	3

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{}
    cur := dummy
    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            cur.Next = list1
            list1, cur = list1.Next, cur.Next
        } else {
            cur.Next = list2
            list2, cur = list2.Next, cur.Next
        }
    }
    if list1 != nil {
        cur.Next = list1
    } else {
        cur.Next = list2
    }
    return dummy.Next
}

641.设计循环双端队列（Medium）半年内出题频次：

Facebook	字节跳动	微软	Amazon	快手	美团	Google	腾讯	华为	百度
2	0	0	0	0	0	0	0	0	0

85.最大矩形（Hard）半年内出题频次：

华为	字节跳动	Google	Amazon	Apple
3	8	5	4	4

实战例题

以下为课上实战例题

第 1 课数组、链表

数组

88.合并有序数组

（Easy）半年内出题频次：

Facebook	字节跳动	微软	Amazon	快手	美团	Google	腾讯	华为	百度
33	19	11	6	5	5	3	0	3	3

func merge(nums1 []int, m int, nums2 []int, n int) {
    last := m + n - 1
    for m, n = m - 1, n - 1; m >= 0 && n >= 0; last = last - 1 {
        if nums1[m] < nums2[n] {
            nums1[last], n = nums2[n], n - 1
        } else {
            nums1[last], m = nums2[m], m - 1
        }
    }
    for n >= 0 {
        nums1[last], last, n = nums2[n], last - 1, n - 1
    }
}

26.删除有序数组中的重复项

（Easy）半年内出题频次：

Facebook	字节跳动	微软	Amazon	滴滴	美团	Google	Apple
11	13	6	6	2	2	2	4

// 写法一
func removeDuplicates(nums []int) int {
    idx := 0
    for cur, n := 0, len(nums); cur < n; cur++ {
        if cur == 0 || nums[cur-1] != nums[cur] {
            nums[idx] = nums[cur]
            idx++
        }
    }
    return idx
}

// 写法二
func removeDuplicates(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }
    slow := 1
    for fast := 1; fast < n; fast++ {
        if nums[fast] != nums[fast-1] {
            nums[slow] = nums[fast]
            slow++
        }
    }
    return slow
}

283.移动零

（Easy）半年内出题频次：

Facebook	字节跳动	微软	Amazon	Bloomberg	Apple	Google	eBay	Cisco	SAP思爱普
19	9	8	7	7	5	5	3	3	2

// 写法一
func moveZeroes(nums []int)  {
    n := len(nums)
    for lastNonZero, i := 0, 0; i < n; i++ {
        if nums[i] != 0 {
            nums[lastNonZero], nums[i] = nums[i], nums[lastNonZero]
            lastNonZero++
        }
    }
}

// 写法二
func moveZeroes(nums []int)  {
    lastNonZero, n := 0, len(nums)
    for i := 0; i < n; i++ {
        if nums[i] != 0 {
            nums[lastNonZero] = nums[i]
            lastNonZero++
        }
    }
    for lastNonZero < n {
        nums[lastNonZero] = 0
        lastNonZero++
    }
}

链表

206.反转链表

（Easy）半年内出题频次：

Facebook	字节跳动	微软	Amazon	滴滴	美团	Google	腾讯	Apple	百度
4	42	9	13	7	7	6	14	7	4

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 迭代
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    for head != nil {
        // tmp := head.Next
        // head.Next = pre
        // pre = head
        // head = tmp
        pre, head, head.Next = head, head.Next, pre
    }
    return pre
}

// 递归
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return newHead
}

// 头插法
func reverseList(head *ListNode) *ListNode {
    dummy := new(ListNode)
    for head != nil {
        head.Next, dummy.Next, head = dummy.Next, head, head.Next
    }
    return dummy.Next
}

25.K 个一组翻转链表

（Hard）半年内出题频次：

Facebook	字节跳动	微软	Amazon	快手	美团	Google	腾讯	Apple	eBay
5	40	13	15	2	2	3	6	3	3

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 方法一： 迭代 + 尾插法
func reverseKGroup(head *ListNode, k int) *ListNode {
    dummy := &ListNode{}
    dummy.Next = head
    pre, tail := dummy, dummy
    for pre.Next != nil {
        for i := 0; i < k && tail != nil; i++ {
            tail = tail.Next
        }
        if tail == nil {
            break
        }
        next := pre.Next
        for pre.Next != tail {
            cur := pre.Next
            pre.Next = cur.Next

            cur.Next = tail.Next
            tail.Next = cur
        }
        pre, tail = next, next
    }
    return dummy.Next
}

// 方法二：迭代 + 独立反转函数（递归、头插法、旧地反转）
func reverseKGroup(head *ListNode, k int) *ListNode {
    dummy := &ListNode{}
    dummy.Next = head
    pre, tail := dummy, dummy
    for pre.Next != nil {
        for i :=0; i < k &&tail != nil; i++ {
            tail = tail.Next
        }
        if tail == nil {
            break
        }
        next := tail.Next
        tail.Next = nil
        head =  pre.Next
        pre.Next = reverse(pre.Next)
        head.Next = next
        pre, tail = head, head
    }
    return dummy.Next
}

func reverse(head *ListNode) *ListNode {
    // 头插法
    dummy := &ListNode{}
    for head != nil {
        cur := head.Next
        head.Next = dummy.Next
        dummy.Next = head
        head = cur
    }
    return dummy.Next
}

// 方法三：递归 + 尾插法
func reverseKGroup(head *ListNode, k int) *ListNode {
    count, cur := 0, head
    for ; count < k && cur != nil; count++ {
        cur = cur.Next
    }
    if count == k {
        cur = reverseKGroup(cur, k)
        for ; count > 0; count-- {
            next := head.Next
            head.Next = cur
            cur = head
            head = next
        }
        head = cur
    }
    return head
}

136.邻值查找

（Medium）（ACWing）

141.环形链表

（Medium）半年内出题频次：

Facebook	字节跳动	微软	Amazon	Bloomberg	百度	腾讯	Apple	Shopee
4	11	7	7	3	3	3	2	2

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 方法一：快慢指针
func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow, fast = slow.Next, fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}

// 方法二：哈希表

142.环形链表 II

（Medium）半年内出题频次：

Facebook	字节跳动	微软	Amazon	快手	美团	Google	腾讯	华为	百度
2	14	2	2	0	2	0	0	0	0

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow, fast = slow.Next, fast.Next.Next
        if slow == fast {
            for slow != head {
                slow, head = slow.Next, head.Next
            }
            return slow
        }
    }
    return nil
}

第 2 课栈、队列

栈

20.有效的括号

（Medium）半年内出题频次：

Facebook	字节跳动	微软	Amazon	Apple	Google	Bloomberg	华为	LinkedIn	Shopee
12	24	15	25	10	7	9	8	13	7

// 写法一：
func isValid(s string) bool {
    n := len(s)
    if n % 2 == 1 {
        return false
    }
    pairs := map[byte]byte{
        ')': '(',
        ']': '[',
        '}': '{',
    }
    stack := []byte{}
    for _, c := range []byte(s) {
        if pairs[c] > 0 {
            if len(stack) == 0 || stack[len(stack)-1] != pairs[c] {
                return false
            }
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, c)
        }
    }
    return len(stack) == 0
}
// 写法二：
func isValid(s string) bool {
    n := len(s)
    if n % 2 == 1 {
        return false
    }
    pairs := map[byte]byte{
        ')': '(',
        ']': '[',
        '}': '{',
    }
    stack := []byte{}
    for i := 0; i < n; i++ { // 区别
        if pairs[s[i]] > 0 {
            if len(stack) == 0 || stack[len(stack)-1] != pairs[s[i]] {
                return false
            }
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, s[i])
        }
    }
    return len(stack) == 0
}

155.最小栈

（Medium）半年内出题频次：

Bloomberg	字节跳动	微软	Amazon	快手	美团	Google	Apple	高盛集团	Coupang
12	10	12	15	0	0	0	3	0	0

type MinStack struct {
    stack, minStack []int
}


func Constructor() MinStack {
    return MinStack{}
}


func (this *MinStack) Push(val int)  {
    this.stack = append(this.stack, val)
    minVal := val
    if len(this.minStack) > 0 && this.minStack[len(this.minStack)-1] < val {
        minVal = this.minStack[len(this.minStack)-1]
    }
    this.minStack = append(this.minStack, minVal)
}


func (this *MinStack) Pop()  {
    l := len(this.stack)
    this.stack = this.stack[:l-1]
    this.minStack = this.minStack[:l-1]
}


func (this *MinStack) Top() int {
    return this.stack[len(this.stack)-1]
}


func (this *MinStack) GetMin() int {
    return this.minStack[len(this.minStack)-1]
}


/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(val);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.GetMin();
 */

150.逆波兰表达式求值

（Medium）半年内出题频次：

Facebook	字节跳动	微软	Amazon	LinkedIn	Google
3	3	3	8	6	6

224.基本计算器 (选做)

（Hard）半年内出题频次：

Facebook	字节跳动	微软	Amazon	Roblox	Shopee	Google	Apple	Wish
8	15	12	7	6	3	4	2	2

单调栈、单调队列

84.柱状图中最大的矩形 重点重点重点

（Hard）半年内出题频次：

字节跳动	微软	Amazon	eBay	Google	华为
7	5	9	2	3	2

// 写法一：
func largestRectangleArea(heights []int) (ans int) {
    // 比栈顶元素小大才出栈，最后一个元素后需要补一个0，让最后一个元素有机会出栈。
    heights = append(heights, 0)
    // 单调升序栈
    stack := []int{}
    for i, height := range heights {
        for len(stack) > 0 && height < heights[stack[len(stack)-1]] {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            width := i
            if len(stack) > 0 {
                width = i - stack[len(stack)-1] - 1
            }
            ans = max(ans,  heights[top] * w)
        }
        stack = append(stack, i)
    }
    return ans
}
// 写法二：
func largestRectangleArea(heights []int) (maxArea int) {
    stack := []int{}
    stack = append(stack, -1)
    for i, height := range heights {
        // 从小 -> 大 栈
        for stack[len(stack) - 1] != -1 && height < heights[stack[len(stack) - 1]]{
            top := stack[len(stack) - 1]
            stack = stack[:len(stack) - 1]
            h := heights[top]
            maxArea = max(maxArea, h * (i - stack[len(stack) - 1] - 1))
        }
        stack = append(stack, i)
    }
    last := len(heights)
    // 处理剩余数据
    for stack[len(stack) - 1] != -1 {
        top := stack[len(stack) - 1]
        stack = stack[:len(stack) - 1]
        h := heights[top]
        maxArea = max(maxArea, h * (last - stack[len(stack) - 1] - 1))
    }
    return maxArea
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

239.滑动窗口最大值

（Hard）半年内出题频次：

Facebook	字节跳动	微软	Amazon	高盛集团	Google	阿里巴巴	Bloomberg	Twitter
6	6	5	27	2	8	2	2	2

// 方法一：双端队列

// 方法二：大顶堆

42.接雨水 重点重点重点

（Hard）半年内出题频次：

Facebook	字节跳动	微软	Amazon	高盛集团	美团	Google	Bloomberg	网易	Apple
35	34	9	46	34	5	10	11	7	5

// 方法一：单调栈（大->小）
func trap(heights []int) (ans int) {
    stack := []int{}
    for i, height := range heights {
        for len(stack) > 0 && height > heights[stack[len(stack)-1]]{
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if len(stack) == 0 {
                break
            }
            ans += ((min(height, heights[stack[len(stack)-1]]) - heights[top]) * (i - stack[len(stack)-1] - 1))
        }
        stack = append(stack, i)
    }
    return ans
}
// 方法二：双指针
func trap(height []int) (ans int) {
    left, right := 0, len(height) - 1
    leftMax, rightMax := 0, 0
    for left < right {
        leftMax = max(leftMax, height[left])
        rightMax = max(rightMax, height[right])
        if height[left] < height[right] {
            ans += leftMax - height[left]
            left++
        } else {
            ans += rightMax - height[right]
            right--
        }
    }
    return ans
}

// 公共函数
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
}

第一周 数组、链表、栈、队列

本周作业

实战例题

第 1 课 数组、链表

数组

链表

第 2 课 栈、队列

栈

单调栈、单调队列

本页内容

第一周数组、链表、栈、队列

第 1 课数组、链表

第 2 课栈、队列