学习资料:https://programmercarl.com/数组总结篇.html#数组的经典题目
移动窗格,首尾指针根据条件变化
模拟行为,循环不变量(左闭右闭或左闭右开)整个过程保持一致
学习记录:
209.长度最小的子数组(用while使得尾指针遍历全部;用while实现,当[首:尾]之和>目标值,才移动首指针;为了求最小长度,先设置最小长度为正无穷float('inf'))
点击查看代码
class Solution(object):
def minSubArrayLen(self, target, nums):
"""
:type target: int
:type nums: List[int]
:rtype: int
"""
begin=0
end=0
sum=0
min_len=float('inf') #设置为无穷大,方便找到最小值
while end < len(nums):
sum += nums[end]
while sum >= target:
sum -= nums[begin]
sub_l=end-begin+1
min_len = min(sub_l, min_len)
begin += 1
end += 1
if min_len != float('inf'):
return min_len
else:
return 0
59.螺旋矩阵(边界值很多,有初始横纵指针、左闭右开需要从n剪掉的offset、从1开始计数的count;当奇数阶矩阵,中间多出来的1项单独设置;螺旋转的圈数为n//2)
点击查看代码
class Solution(object):
def generateMatrix(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
start_x = 0
start_y = 0
nums = [[0]*n for _ in range(n)]
cycle, mid = n//2, n//2
offset=1
count=1
for c in range(cycle):
for j in range(start_y, n-offset):
nums[start_x][j]=count
count += 1
for i in range(start_x, n-offset):
nums[i][n-offset]=count
count += 1
for j in range(n-offset, start_y, -1):
nums[n-offset][j]=count
count += 1
for i in range(n-offset, start_x, -1):
nums[i][start_y] = count
count += 1
start_x += 1
start_y += 1
offset += 1
if n%2 != 0:
nums[mid][mid]=count
return nums
PS:
螺旋矩阵好绕啊,被9个数字给绕麻了
今天阴天,好冷,终于要放假了