这是算法记录的第二天，包含左右指针、滑动窗口和遍历
leetcode:977.209.151.48.54.59
左右指针
977.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
思路
- 先观察这个数组，注意到特点是单调不减的，所以即使是平方后最大值也只会出现在左右两端，所以引出了左右指针，两个指针相向而行直至相遇
- 每次比较左右两边指针指向的元素平方的大小，大的就放在最后的数组中，相应指针左移/右移这样就得到最后的排序结果
代码
// 左右指针相向而行
func sortedSquares(nums []int) []int {
n := len(nums)
//分别指向原数组的左端、右端和新数组的尾部
l, r, k := 0, n-1, n-1
sortedNums := make([]int, n)
//取等号时处理最后一个元素
for l <= r {
left2 := nums[l] * nums[l]
right2 := nums[r] * nums[r]
if left2 > right2 {
sortedNums[k] = left2
l++
} else {
sortedNums[k] = right2
r--
}
//新数组位置前移一位
k--
}
return sortedNums
}
滑动窗口
209.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
思路
滑动窗口是使用一个for循环完成了暴力解法的2层for循环 而滑动窗口的终止位置则是循环的索引 滑动窗口和快慢指针有些类似，但更像一个窗口不断移动
确定：
- 窗口内是什么
- 如何移动窗口的起始位置
- 如何移动窗口的结束位置
对于这道题而言，窗口内就是满足条件的子数组，当子数组的和sum大于等于target了就得移动，表示此时子数组不满足条件，窗口结束位置就是循环的i
关键：
满足条件后起始位置的移动
sum -= nums[k]
k++
代码
func minSubArrayLen(target int, nums []int) int {
l := len(nums)
sum, k, result := 0, 0, l+10086 // 分别代表子数组求和大小、滑动窗口开始点、最终的子数组长度
for i := 0; i < l; i++ {
sum += nums[i]
for sum >= target {
sub := i - k + 1 //计算子数组的长度并比较
if sub < result {
result = sub
}
sum -= nums[k] //窗口移动
k++
}
}
// 不存在情况，可以设置为任意比原数组长度大的值（数组本身也是自己的子数组，包含自己的情况）
if result == l+10086 {
return 0
}
return result
}
数组遍历
48.旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
思路
通过一维的力扣第 151 题「 颠倒字符串中的单词」的反转再反转解法可以引出二维矩阵的思考
通过旋转90°可以知道行列进行了转化，而矩阵的对称也正将行列进行了变化，所以考虑根据主对角线进行对称，但对称后还不一样，再观察就是将每一行的都再反转就会得到目标矩阵了
同理，如果是逆时针旋转90°的话可以根据副对角线对称再反转每一行，最后结果就是旋转后的了
代码
func rotate(matrix [][]int) {
l := len(matrix)
//矩阵对称
for i := 0; i < l; i++ {
for j := i + 1; j < l; j++ {
tmp := matrix[i][j]
matrix[i][j] = matrix[j][i]
matrix[j][i] = tmp
}
}
//对每一行反转
for i := 0; i < l; i++ {
//将前一半和后一半反转，所以除二，奇数中间的正好不用转了
for j := 0; j < l/2; j++ {
tmp := matrix[i][j]
matrix[i][j] = matrix[i][l-1-j]
matrix[i][l-1-j] = tmp
}
}
}
54.螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
思路
没什么过多的精妙，就是圈定好上下左右四个边界，再按照右、下、左、上的顺序进行遍历就行，每遍历一行/列就把对应边界缩小一个单位，还要注意边界是否取等问题
代码
func spiralOrder(matrix [][]int) []int {
//获得矩阵的行列
m, n := len(matrix), len(matrix[0])
//定义边界
right, down, left, up := n-1, m-1, 0, 0
//长度要为0
result := make([]int, 0, m*n)
//结束条件是result中达到原矩阵元素个数
for len(result) < m*n {
//模拟从左到右的一行遍历
if up <= down {
for i := left; i <= right; i++ {
result = append(result, matrix[up][i])
}
//上边界降低
up++
}
//模拟从上往下的一列遍历
if left <= right {
for i := up; i <= down; i++ {
result = append(result, matrix[i][right])
}
//右边界向中间缩减
right--
}
//模拟从右往左的一行遍历
if up <= down {
for i := right; i >= left; i-- {
result = append(result, matrix[down][i])
}
//下边界上升
down--
}
//模拟从下往上的一列遍历
if left <= right {
for i := down; i >= up; i-- {
result = append(result, matrix[i][left])
}
//左边界向中间缩减
left++
}
}
return result
}
59.螺旋矩阵II
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1
输出：[[1]]
思路
和螺旋矩阵I基本一样，只不过是不断往里面填充递增的数，依旧是四个边界和四个方向，注意一些边界取等问题，golang的话二维切片的初始化也得更熟悉
代码
func generateMatrix(n int) [][]int {
//初始化二维切片
matrix := make([][]int, n)
for i := range matrix {
matrix[i] = make([]int, n)
}
//递增的填充数
num := 1
up, down, left, right := 0, n-1, 0, n-1
for num <= n*n {
if up <= down {
for i := left; i <= right; i++ {
matrix[up][i] = num
num++
}
up++
}
if right >= left {
for i := up; i <= down; i++ {
matrix[i][right] = num
num++
}
right--
}
if up <= down {
for i := right; i >= left; i-- {
matrix[down][i] = num
num++
}
down--
}
if right >= left {
for i := down; i >= up; i-- {
matrix[i][left] = num
num++
}
left++
}
}
return matrix
}