代码随想录算法训练营第十五天 | 数组 |长度最小的子数组和螺旋矩阵II

长度最小的子数组

【题目简介】

【自写数组解法】

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        minLength = float('inf')
        slow = 0
        fast = 0
        cur_sum = nums[slow]

        # 终止条件：fast不能超过最大索引值
        while slow <= fast and fast <= len(nums)-1:
            # 需要重新计算时间
            if cur_sum >= target:
                minLength = min(minLength, fast-slow + 1)
                #print(slow, fast, cur_sum, minLength)
                cur_sum -= nums[slow]
                slow += 1


            if cur_sum < target:
                fast += 1
                if fast <= len(nums)-1:
                    cur_sum += nums[fast]
                # print("2: ",slow, fast, cur_sum, minLength)


            if fast == len(nums) and minLength == float('inf'):
                return 0

        return minLength
                

1. 自己写的一种形式，AC了，不过有些地方想的不是很明白；
2. 很有意思的一个想法是如果加和大于目标值，则起始位置+1；如果加和小于目标值，则终止位置-1；
3. 循环条件：slow小于等于fast，同时fast应该小于等于最大索引值；
4. 终止条件：如果fast达到最大索引的时候，并且最小长度依旧是inf时；
5. 优化加和计算：一定要避免每次更新slow或者fast需要重复计算所有元素的总和！

螺旋矩阵II （有难度的！）

【题目简介】

1. 循环次数：7–>3; 3–> 1; 所以for循环的次数是n//2; 具体的代码是：range(1, 1 + n//2);
2. 上边界循环的边界：（1） range( offset-1, n-offset); matrix[offset-1][i];
3. 右边界循环的边界：（2）range( offset-1, n-offset); matrix[j][n-offset];
4. 下边界循环的边界：（3）range(n-offset, offset-1, -1); matrix[n-offset][i];
5. 左边界循环的边界：（4）range(n-offset, offset-1, -1); matrix[j][offset-1];

【随想录解法】

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        nums = [[0] * n for _ in range(n)]
        startx, starty = 0, 0               # 起始点
        loop, mid = n // 2, n // 2          # 迭代次数、n为奇数时，矩阵的中心点
        count = 1                           # 计数

        for offset in range(1, loop + 1) :      # 每循环一层偏移量加1，偏移量从1开始
            for i in range(starty, n - offset) :    # 从左至右，左闭右开
                nums[startx][i] = count
                count += 1
            for i in range(startx, n - offset) :    # 从上至下
                nums[i][n - offset] = count
                count += 1
            for i in range(n - offset, starty, -1) : # 从右至左
                nums[n - offset][i] = count
                count += 1
            for i in range(n - offset, startx, -1) : # 从下至上
                nums[i][starty] = count
                count += 1                
            startx += 1         # 更新起始点
            starty += 1

        if n % 2 != 0 :			# n为奇数时，填充中心点
            nums[mid][mid] = count 
        return nums

【自优化解法】

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        # 构建矩阵
        matrix = [[0] * n for _ in range(n)]

        # 构建循环
        loop, mid = n//2, n//2
        count = 1 # 

        # 螺旋矩阵需要注意规律: 全部围绕offset进行
        for offset in range(1, loop + 1):           # 注意的边界
            for i in range(offset-1, n - offset):   # 
                matrix[offset-1][i] = count
                count += 1
            for j in range(offset-1, n- offset):
                matrix[j][n-offset] = count
                count += 1
            for i in range(n-offset, offset-1, -1):
                matrix[n-offset][i] = count
                count += 1
            for j in range(n-offset, offset-1, -1):
                matrix[j][offset-1] = count
                count += 1

        # 中心区域的特殊处理
        if n%2 != 0:
            matrix[mid][mid] = count

        return matrix

1. for循环中全部围绕offset进行即可；