（本合集全部为Go语言实现）
Leetcode977
状态：按自定义排序策略的方式秒了。尝试使用双指针法，但是以为是需要原地进行操作，试了一下失败了
实现过程中的难点：需要明确的是对撞指针两者的平法比较时，大的一定是序列中最大的，但是小的不一定是序列中最小的（因为序列中有可能正负同时存在，此时最小的在序列中间）
为什么不能原地实现
如果对撞指针的平方比较时，大的一定是最大的，那么为什么不能按下边的方式？
if nums[0] * nums[0] > nums[r] * nums[r] {
nums[0], nums[r] = nums[r], nums[0] * nums[0]
}
r--
原因：对于一段负数序列，例如[-4, -3, -2, -1]，-1交换到首位后，就不会被交换了，这是不正确的
个人写法
自定义排序策略
import (
"math"
"sort"
)
type intList []int
func (ints intList) Len() int {
return len(ints)
}
func (ints intList) Swap(i, j int) {
ints[i], ints[j] = ints[j], ints[i]
}
func (ints intList) Less(i, j int) bool {
return math.Abs(float64(ints[i])) < math.Abs(float64(ints[j]))
}
func sortedSquares(nums []int) []int {
ints := intList(nums)
sort.Sort(ints)
for i := 0; i < len(nums); i++ {
nums[i] = nums[i] * num[i]
}
return nums
}
对撞双指针
func sortedSquares(nums []int) []int {
left, right := 0, len(nums) - 1
res := make([]int, len(nums))
for i := len(nums) - 1; i >= 0; i-- {
lNum := nums[left] * nums[left]
rNum := nums[right] * nums[right]
if lNum > rNum {
res[i] = lNum
left++
} else {
res[i] = rNum
right--
}
}
return res
}
Leetcode209
状态：可以写出来
实现过程中的难点：此题是典型的滑动窗口双指针类型，按滑动窗口类型的基本模版思路写就可以
对于滑动窗口模版的理解
基本模版如下
- 外层循环的终止条件为右指针越界判断
- 右指针右移直到达到题目条件
- 判断并赋值结果变量
- 左指针右移直到不符合题目条件
个人写法
import "math"
func minSubArrayLen(target int, nums []int) int {
minLen := math.MaxInt
left, right := 0, 0
curSum := 0
for right < len(nums) {
for right < len(nums) && curSum < target {
curSum += nums[right]
right++
}
for left < right && curSum >= target {
if minLen > right - left {
minLen = right - left
}
curSum -= nums[left]
left++
}
}
if minLen == math.MaxInt {
return 0
} else {
return minLen
}
}
Leetcode704
状态：秒了，这个题印象比较深刻
实现过程中的难点：多个方向的遍历赋值需要统一判断逻辑
个人写法
主要思路：为四个边分别维护一个变量标记当前需要赋值的下标位置
func generateMatrix(n int) [][]int {
res := make([][]int, n)
for i := 0; i < n; i++ {
res[i] = make([]int, n)
}
u, d, l, r := 0, n - 1, 0, n - 1
for i := 1; i <= n * n; {
for j := l; j <= r; j++ {
res[u][j] = i
i++
}
u++
for j := u; j <= d; j++ {
res[j][r] = i
i++
}
r--
for j := r; j >= l; j-- {
res[d][j] = i
i++
}
d--
for j := d; j >= u; j-- {
res[j][l] = i
i++
}
l++
}
return res
}
今日收获
- 第一道题写的时候稍微遇到了些困难
- 复习了滑动窗口法的基本模版思路
学习时长：整体2个小时左右