目录
- 977. 有序数组的平方 算法的正确性采用反证法证明
- 209. 长度最小的子数组 思维打开, 抓住滑动窗口定义本质与意义, 笑对Corner Cases
- 59. 螺旋矩阵 II 抓住循环不变量, 模拟螺旋矩阵
977. 有序数组的平方 算法的正确性采用反证法证明
Problem: 977. 有序数组的平方
思路
讲述看到这一题的思路
结论: 对于非递减数列, 绝对值最大的元素一定是第0个或最后一个
反证法证明:
若是第i个绝对值最大(0<i<n-1), 则
因为|nums[i]| > |nums[0]|, 所以nums[i] > 0
因为|nums[i]| > |nums[n-1]|, 所以nums[i] < 0
矛盾!
解题方法
描述你的解题方法
双指针即可
Code
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
l = []
i = 0
j = len(nums)-1
n = len(nums)-1
while j>=i:
if nums[j]*nums[j] > nums[i]*nums[i]:
l.append(nums[j]*nums[j])
j -= 1
else:
l.append(nums[i]*nums[i])
i += 1
n -= 1
l.reverse()
return l
209. 长度最小的子数组 思维打开, 抓住滑动窗口定义本质与意义, 笑对Corner Cases
Problem: 209. 长度最小的子数组
看这段代码, 你会觉得极其的简洁, 我来解释一下为什么
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
Sum = 0
start = 0
size = float("inf")
for end in range(len(nums)):
Sum += nums[end]
while Sum >= target:
size = min(size, end - start + 1)
Sum -= nums[start]
start += 1
return 0 if size == float("inf") else size
如何定义滑动窗口?
- start: 窗口起始
- end: 窗口结束
- 窗口: [start,end]构成的闭区间
那么, 我们考虑一下start和end取值的意义:
- start < end: 不必说
- start == end: 窗口只含有1个元素
start > end
: 窗口为空
也就是说出现start > end(其实只有start = end+1), 是无需害怕的
这也是闭区间
的意义
如果换一个定义方法?
- start: 窗口起始
- end: 窗口结束下一个
- 窗口: [start,end)构成的闭区间
那么, 我们考虑一下start和end取值的意义:
- start < end: 不必说
start == end
: 窗口为空
代码
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
start = 0
end = 1
Sum = 0
size = float("inf")
while end <= len(nums):
Sum += nums[end-1]
while Sum >= target:
size = min(size, end - start)
Sum -= nums[start]
start += 1
end += 1
return 0 if size == float("inf") else size
59. 螺旋矩阵 II 抓住循环不变量, 模拟螺旋矩阵
解题思路
可以把方阵的每一圈4个顶点:
- (i, i)
- (i, n-i-1)
- (n-i-1, n-i-1)
- (n-i-1, i)
以某个顶点为起始点, 下一个为结束点, 且为左开右闭即可
代码
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
x = y = 0
val = 1
loop = int(n/2)
i = 0
matrix = [[0] * n for _ in range(n)]
while i < loop:
while x == i and y < n-i-1:
matrix[x][y] = val
val += 1
y += 1
while y == n-i-1 and x < n-i-1:
matrix[x][y] = val
val += 1
x += 1
while x == n-i-1 and y > i:
matrix[x][y] = val
val += 1
y -= 1
while y == i and x > i:
matrix[x][y] = val
val += 1
x -= 1
i += 1
x += 1
y += 1
print(matrix)
if n%2 != 0:
matrix[int(n/2)][int(n/2)] = n*n
return matrix
标签:end,val,nums,int,随想录,start,抓住,数组,size
From: https://www.cnblogs.com/ywh-pku/p/16833611.html