代码随想录算法训练营第二天| 977. 有序数组的平方、209. 长度最小的子数组、59. 螺旋矩阵ii-爱代码爱编程
Leetcode 977. 有序数组的平方
题目描述:给你一个按 非递减顺序 排序的整数数组
nums
,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
题目链接:https://leetcode.cn/problems/squares-of-a-sorted-array/
解题思路:首先,最直观的解法就是平方后排序(这里可以复习一下排序算法)。 其次,双指针可以降低时间复杂度,使用双指针要明确指针代表的意思,该题是非递减顺序排序的整数数组,所以两个指针应分别指向数组起始位置和末尾,进而判断对应位置的数字平方大小。
1. 暴力解法
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
return sorted(num * num for num in nums)
2. 双指针
- 双指针定义:
- left指针:指向数组起始位置。
- right指针:指向数组结尾位置。
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
left, right = 0, n - 1
temp = n - 1
ans = [-1] * n
while left <= right:
if nums[left] ** 2 > nums[right] ** 2:
ans[temp] = nums[left] ** 2
left += 1
else:
ans[temp] = nums[right] ** 2
right -= 1
temp -= 1
return ans
- 注意:双指针可降低时间复杂度,使用双指针要明确指针的含义。
Leetcode 209. 长度最小的子数组
题目描述:给定一个含有
n
个正整数的数组和一个正整数target
。找出该数组中满足其和≥ target
的长度最小的连续子数组[nums_l, nums_l+1, ..., nums_r-1, nums_r]
,并返回其长度。如果不存在符合条件的子数组,返回0
。
题目链接:https://leetcode.cn/problems/minimum-size-subarray-sum/
解题思路:使用两个for循环的暴力解法在本题会超时,所以考虑双指针,题目中说要找出满足条件的连续数组,进而想到不断的调节子序列的起始位置和终止位置,从而得出要想结果的滑动窗口。使用滑动窗口要注意明确窗口内是什么、如何移动窗口起始位置和结束位置。
1. 滑动窗口
- 窗口定义:满足其和
≥ s
的长度最小的连续子数组 - 窗口的起始位置如何移动:如果当前窗口的值大于
s
了,窗口就要向前移动了(也就是该缩小了)。 - 窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是
for
循环里的索引。
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
s = 0
left = 0
length = float("inf")
for right in range(n):
s += nums[right]
while s >= target:
length = min(length, right - left + 1)
s -= nums[left]
left += 1
return 0 if length == float("inf") else length
- 注意:滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。
Leetcode 59. 螺旋矩阵II
题目描述:给你一个正整数
n
,生成一个包含1
到n^2
所有元素,且元素按顺时针顺序螺旋排列的n x n
正方形矩阵matrix
。
题目链接:https://leetcode.cn/problems/spiral-matrix-ii/
- 解题思路:本题是模拟题,按题目要求模拟即可。模拟过程中需要注意边界问题。
- 定义当前左右上下边界
l, r, t, b
,初始值num = 1
,迭代终止值tar = n * n
; - 当
num <= tar
时,始终按照从左到右
从上到下
从右到左
从下到上
填入顺序循环,每次填入后:执行num += 1
,得到下一个需要填入的数字; - 更新边界:例如从左到右填完后,上边界
t += 1
,相当于上边界向内缩 1。 - 使用
num <= tar
而不是l < r || t < b
作为迭代条件,是为了解决当n
为奇数时,矩阵中心数字无法在迭代过程中被填充的问题。
- 定义当前左右上下边界
1. 模拟-设定边界(Leetcode Krahets大神解法)
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
matrix = [[0] * n for _ in range(n)]
left, right, top, bottom = 0, n - 1, 0, n - 1
num, target = 1, n * n
while num <= target:
# left to right:
for i in range(left, right + 1):
matrix[top][i] = num
num += 1
top += 1
# top to bottom:
for i in range(top, bottom + 1):
matrix[i][right] = num
num += 1
right -= 1
# right to left:
for i in range(right, left - 1, -1):
matrix[bottom][i] = num
num += 1
bottom -= 1
# bottom to top:
for i in range(bottom, top - 1, -1):
matrix[i][left] = num
num += 1
left += 1
return matrix
总结
- 双指针是很好的降低时间复杂度的方法,使用双指针要明确指针定义。
- 滑动窗口也是双指针的一种类型,所以也能够降低时间复杂度。使用滑动窗口要明确窗口内是什么,如何移动窗口起始位置和结束位置。
- 模拟题需要注意边界问题。
参考链接:
代码随想录-有序数组的平方
代码随想录-长度最小的子数组
代码随想录-螺旋矩阵II
Leetcode题解-Krahets大神模拟设定边界法