DAY 1

本篇内容包含数组的两类经典题目：

  1. 二分查找
  2. 双指针

704.二分查找

相关链接

边界条件注意

Carl 哥的视频讲的很清楚，墙裂建议观看

主流的就是两种写法，左闭右闭和左闭右开，如果你选择了一种写法，就应该全程保持这一种写法

  • 左闭右闭

    起始区间为 [0,n - 1] ，继续循环的条件是区间合法，也就是 left <= right

    更新左右边界值时，由于 mid 已经被排除，所以更新为 mid + 1 与 mid - 1

  • 左闭右开

    起始区间为 [0,n] ，因为 [1,1) 不是一个合法的区间（左右不能相等），所以 left < right

    更新左右边界值时，因为左闭所以 mid + 1 ，而右开所以 mid （已经排除了但是右边界是开的）

整数溢出问题

计算 mid 通常使用 (left + right) / 2

但是如果 left 和 right 很大，就可能溢出，可以使用 left + (right - left) / 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func search(nums []int, target int) int {
    n := len(nums)
    left, right := 0, n-1 // 左闭右闭

    for left <= right { // [1,1] 可以是一个合理区间，所以要有等号
        mid := (left + right) / 2
        if nums[mid] > target {
            right = mid - 1 // 这里要减一，区间是左闭右闭，不应该再包括 mid
        } else if nums[mid] < target {
            left = mid + 1 // 这里要加一，区间是左闭右闭，不应该再包括 mid
        } else {
            return mid
        }
    }
    return -1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func search(nums []int, target int) int {
    n := len(nums)
    left, right := 0, n // 左闭右开

    for left < right { // [1,1) 不是一个合理区间，所以不能有等号
        mid := (left + right) / 2
        if nums[mid] > target {
            right = mid // 右开
        } else if nums[mid] < target {
            left = mid + 1 // 左闭
        } else {
            return mid
        }
    }
    return -1
}

27.移除元素

相关链接

经典双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
func removeElement(nums []int, val int) int {
    n := len(nums)
    left, right := 0, 0

    for right < n {
        if nums[right] != val {
            nums[left] = nums[right]
            left++
        }
        right++
    }
    return left
}

34.在排序数组中查找元素的第一个和最后一个位置

解法很多，我选择分别查找第一个和最后一个位置

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
func searchRange(nums []int, target int) []int {
    n := len(nums)
    if n == 0 {
        return []int{-1, -1}
    }

    return []int{findFirst(nums, target), findLast(nums, target)}
}

func findFirst(nums []int, target int) int {
    n := len(nums)
    left, right := 0, n-1
    if nums[left] == target {
        return left
    }

    for left <= right {
        mid := (left + right) / 2

        if nums[mid] < target && mid+1 < n && nums[mid+1] == target {
            return mid + 1
        }

        if nums[mid] >= target {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }

    return -1
}

func findLast(nums []int, target int) int {
    n := len(nums)
    left, right := 0, n-1
    if nums[right] == target {
        return right
    }

    for left <= right {
        mid := (left + right) / 2

        if nums[mid] > target && mid-1 >= 0 && nums[mid-1] == target {
            return mid - 1
        }

        if nums[mid] <= target {
            left = mid + 1
        } else {
            right = mid - 1
        }

    }

    return -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
45
46
47
48
49
50
51
52
func searchRange(nums []int, target int) []int {
    n := len(nums)
    if n == 0 {
        return []int{-1, -1}
    }

    return []int{findFirst(nums, target), findLast(nums, target)}
}

func findFirst(nums []int, target int) int {
    n := len(nums)
    left, right := 0, n-1
    ans := -1

    for left <= right {
        mid := (left + right) / 2

        if nums[mid] > target {
            right = mid - 1
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
            ans = mid
        }
    }

    return ans
}

func findLast(nums []int, target int) int {
    n := len(nums)
    left, right := 0, n-1
    ans := -1

    for left <= right {
        mid := (left + right) / 2

        if nums[mid] < target {
            left = mid + 1
        } else if nums[mid] > target {
            right = mid - 1
        } else {
            left = mid + 1
            ans = mid
        }

    }

    return ans
}

35.搜索插入位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func searchInsert(nums []int, target int) int {
    n := len(nums)
    left, right := 0, n-1

    for left <= right {
        mid := (left + right) / 2

        if nums[mid] > target {
            right = mid - 1
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            return mid
        }
    }

    return left
}

DAY 2

本篇内容包含数组的另外两类经典题目：

  1. 滑动窗口
  2. 模拟

同时复习一下双指针

977.有序数组的平方

相关链接

想多了，居然想从中间入手往两边扫

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 sortedSquares(nums []int) []int {
    n := len(nums)

    for i := 0; i < n; i++ {
        if nums[i] < 0 {
            nums[i] = -nums[i]
        }
    }

    idx := 0
    for idx+1 < n && nums[idx+1] <= nums[idx] {
        idx++
    }

    left, right := idx-1, idx+1

    ans := []int{nums[idx] * nums[idx]}

    for left >= 0 || right < n {
        for left >= 0 && (right >= n || nums[left] <= nums[right]) {
            ans = append(ans, nums[left]*nums[left])
            left--
        }

        for right < n && (left < 0 || nums[right] <= nums[left]) {
            ans = append(ans, nums[right]*nums[right])
            right++
        }
    }

    return ans
}

看了题解之后发现直接从两边向中间就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func sortedSquares(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)
    idx := n - 1

    left, right := 0, n-1
    for left != right {
        if nums[left]*nums[left] >= nums[right]*nums[right] {
            ans[idx] = nums[left] * nums[left]
            idx--
            left++
        } else {
            ans[idx] = nums[right] * nums[right]
            idx--
            right--
        }
    }

    ans[idx] = nums[left] * nums[left]
    return ans
}

209.长度最小的子数组

相关链接

经典滑动窗口

for 外层是窗口的右边界，如果满足条件则记录并尝试移动左边界

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 minSubArrayLen(target int, nums []int) int {
    n := len(nums)

    ans := math.MaxInt
    sum := 0

    for left, right := 0, 0; right < n; right++ {
        sum += nums[right]
        for sum >= target {
            ans = min(ans, right-left+1)
            sum -= nums[left]
            left++
        }
    }

    if ans == math.MaxInt {
        return 0
    } else {
        return ans
    }

}

func min(i, j int) int {
    if i < j {
        return i
    }
    return j
}

59.螺旋矩阵 II

相关链接

自己写的，感觉纯脑筋急转弯

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
func generateMatrix(n int) [][]int {
    ans := make([][]int, n)
    for i := 0; i < n; i++ {
        ans[i] = make([]int, n)
    }

    x, y := 0, 0
    curr := 1
    len := n

    for len > 0 {
        for i := 0; i < len; i++ {
            ans[x][y] = curr
            y++
            curr++
        }
        len--
        y--
        x++
        for i := 0; i < len; i++ {
            ans[x][y] = curr
            x++
            curr++
        }
        y--
        x--
        for i := 0; i < len; i++ {
            ans[x][y] = curr
            y--
            curr++
        }
        y++
        x--
        len--
        for i := 0; i < len; i++ {
            ans[x][y] = curr
            x--
            curr++
        }
        y++
        x++
    }
    return ans
}