LeetCode209长度最小的子数组
1、题目:
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0
示例:
输入:s = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
提示:
1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
2、代码
2.1 Python版
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
sum = 0
i = 0
j = 0
subl = 0
result = float('inf')
while j < len(nums):
sum += nums[j]
while sum >= target:
subl = j - i + 1
result = min(result, subl)
sum -= nums[i]
i += 1
j += 1
return result if result != float('inf') else 0
2.2 C++版
3、总结
1、在使用双指针法的时候,j作为双指针的右下标来遍历整个列表
2、在j老实前进的过程中,i作为左下标的收紧区间来找到最小长度的子串。中间时时更新,找到一个小了一点的长度值就喜新厌旧地丢弃原来的长度。而它的初始化长度是老实巴交的float('inf'),一个注定被抛弃的存在。因为如果他不被抛弃,那就意味着我们遍历整个数组的努力是徒劳。而即便他幸运地,或者不幸地没有被抛弃,他也终究不会被返回。我们毫无发现时,函数将返回0,略带失望。
3、双指针法就是这样的,有时候我觉得他不如暴力法。在暴力法中,作为子集两端的下标i和j相伴走到最后,哪怕是徒劳。返回0的失望与他们无关。我喜欢后一个故事,但是效率让我们选择前者。
LeetCode
1、题目:
给定一个正整数 n,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
2、代码
2.1 Python版
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
startx, starty = 0, 0
loop, mid = n // 2, n//2
num = 1
matrix = [[0] * n for _ in range(n)]
#range取的是左闭右开区间
for offset in range(1, loop + 1):
for i in range(starty, n - offset):
matrix[startx][i] = num
num += 1
for i in range(startx, n - offset):
matrix[i][n - offset] = num
num += 1
for i in range(n - offset, starty, -1):
matrix[n - offset][i] = num
num +=1
for i in range(n - offset, startx, -1):
matrix[i][starty] = num
num += 1
startx += 1
starty += 1
if n % 2 != 0:
matrix[mid][mid] = num
return matrix
2.2 C++版
3、总结
1、循环不变量,重复的相遇发生在每一个转角,我希望邂逅你,而这也是事实。
2、晕了,待补
参考资料
https://programmercarl.com/0209.长度最小的子数组.html#算法公开课
https://programmercarl.com/0059.螺旋矩阵II.html#其他语言版本