DAY 1
本篇内容包含数组的两类经典题目:
- 二分查找
- 双指针
相关链接
边界条件注意
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 { mid := (left + right) / 2 if nums[mid] > target { right = mid - 1 } else if nums[mid] < target { left = mid + 1 } 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 { mid := (left + right) / 2 if nums[mid] > target { right = mid } else if nums[mid] < target { left = mid + 1 } else { return mid } } return -1 }
|
相关链接
经典双指针
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 }
|
解法很多,我选择分别查找第一个和最后一个位置
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 }
|
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 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 }
|
相关链接
经典滑动窗口
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 }
|
相关链接
自己写的,感觉纯脑筋急转弯
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 }
|