数组专题:
leetcode: 977
暴力解法也是最开始就可以想到的方法:
def sortedSquares(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
for i in range(len(nums)):
nums[i] *= nums[i]
nums.sort()
return nums
双指针法:根据题意,给定数组为非递减数组也可以理解为一个递增的数组。在这种情况下,最大值可能是原数组(nums)最左边的值(可能是一个较小的负数),也可能是最右边的值(一个原数组内最大的正数)。所以可以使用左右指针, left = 0, right = n-1, 通过对比左右两个值的平方的大小向新定义的数组中填值。
最开始定义 res 数组时,使用的 res = [],应改为对res 的一个初始化,因为后面需要用到 res 数组中的索引信息。
def sortedSquares(nums) :
size = len(nums)
left = 0
right = size-1
#res = []
res = [0]*len(nums)
i = size - 1
while left <= right :
if nums[left] **2 < nums[right] ** 2 :
res[i] = nums[right] ** 2
right -= 1
else :
res[i] = nums[left] **2
left+= 1
i -= 1
return res
leetcode 209
暴力解法:刚开始看的时候这个两个for 循环也思考了很久。
def minSubArrayLen(nums, target) :
l = len(nums)
#先定义一个无穷大的数
min_len = float('inf')
for i in range(l) :
cur_sum = 0
#j starts from i,从i开始慢慢更新j的值
#如果cur_sum > target, 跳出当前循环
#开始更新下一个i 的值,直到找到最短的子数组长度。
for j in range(i, l) :
cur_sum += nums[j]
if cur_sum >= target :
#j-i+1为当前子数组长度,加1是因为i,j均是从0开始
min_len = min(min_len, j-i+1)
break
#如果最后没有找到,就返回默认的0
return min_len if min_len != float('inf') else 0
第一层循环更新每个 i 的值的时候,第二层循环会更新 j 从当前 i 的值一直到 len(nums), 确保了最后会找到最短的子数组。
滑动窗口:不断的调节子序列的起始位置和终止位置,从而得出想要的结果。基本思想是维护一个窗口,通过移动窗口的两个边界来处理问题。使用两个指针,left and right 来扩大窗口,同时根据问题的要求调整做指针来缩小窗口。当右指针 right 扫描到字符串或数组的末尾事,算法执行完成。
本题中窗口就是满足 和大于等于 s的长度最小的连续子数组。窗口的起始位置如何移动:如果当前窗口值大于s, 窗口就要向前移动(缩小);
窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是for 循环的索引。
def minSubArrayLen(nums, target):
l = len(nums)
left = 0
right = 0
min_len = float('inf')
cur_sum = 0
while right < l :
cur_sum += nums[right]
while cur_sum >= target:
min_len = min (min_len, right-left+1)
#通过更新当前sum的值来改变left 的位置
cur_sum -= nums[left]
left += 1
right += 1
return min_len if min_len != float('inf') else 0
对于本题的理解,我认为关键点在于cur_sum 的更新
相关阅读:https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html#%E6%80%9D%E8%B7%AF
https://cloud.tencent.com/developer/article/2294180
leetcode 56
code:
def generateMatrix(n):
if n == 0: return []
res = [[0] * n for i in range(n)]
#four bound
left, right, up, down = 0, n-1, 0, n-1
#current position subscript
#dirs[cur_d] -> how to change x, y in next direction
x, y = 0, 0
#direction, right, down, left, up
dirs = [(0,1), (1, 0), (0, -1), (-1, 0)]
#current direction
cur_d = 0
count = 0
while count != n*n:
res[x][y] = count + 1
count += 1
#current dir is right and arrives at right bound
#change the move dir to the down and move the old
#up bound to the new up bound
if cur_d == 0 and y == right:
cur_d += 1
up += 1
elif cur_d == 1 and x == down:
cur_d += 1
right -= 1
elif cur_d == 2 and y == left:
cur_d += 1
down -= 1
elif cur_d == 3 and x == up :
cur_d += 1
left += 1
cur_d %= 4
x += dirs[cur_d][0]
y += dirs[cur_d][1]
return res
感想就是编程果然是很奇妙,别人的大脑都是怎么想出来的呢???
dirs[]用来维护方向,比如当 y == right, 需要改变到同一列下一行的时候。以 n = 5 为例,第一次 y == right 是 x=0, y=4, res[x][y] = 5的时候,这个时候需要转到下一行同一列进行更新数字6。此时 对应代码 cur_d = 0,dirs[1][1] = 0, 此时 y += dirs[cur_d][1] 的值保持不变,y=4,继续在同一列上进行更新。x += dirs[cur_d][0] 的值变成 0 + 1 = 1 也就是换到下一行。以此类推完成整个更新。
相关阅读:https://leetcode.cn/problems/spiral-matrix-ii/solutions/659234/ju-zhen-bian-li-wen-ti-de-si-bu-qu-by-fu-sr5c/
标签:right,cur,nums,min,Day2,len,left From: https://www.cnblogs.com/yuhao0451/p/17589057.html