【随想录day2】LeetCode209长度最小的子数组 | LeetCode59螺旋矩阵

三法师 / 2024-09-17 / 原文

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