当前位置:   article > 正文

Python刷力扣--长度最小的子数组、螺旋矩阵 II_python 力扣 创建矩阵

python 力扣 创建矩阵

来源:力扣(LeetCode)

长度最小的子数组

链接:

https://leetcode.cn/problems/minimum-size-subarray-sum/

 

  1. class Solution:
  2. def minSubArrayLen(self, target: int, nums: List[int]) -> int:
  3. n=len(nums)
  4. ans=n+1
  5. sum=0
  6. start,end=0,0
  7. while end<n:
  8. sum+=nums[end]
  9. while sum>=target:
  10. ans=min(ans,end-start+1)
  11. sum-=nums[start]
  12. start+=1
  13. end+=1
  14. return 0 if ans==n+1 else ans

思路:

题我采用最简单和不会超时长的滑动窗口。理解题意:本题要求找连续的子数组,满足两个条件:1、这个子数组的元素和>=target ,2、长度最小。首先,我们考虑两种极端情况:1、数组为空;2、数组全部元素和小于target。所以定义一个变量“ans=n+1”,在最后判断一下ans,如果还是n+1,说明遍历完没有找到一个子数组的和>=target,同时解决两种极端情况。注意“ans”主要是为了记录子数组长度而存在的。其次,我们再定义“start、end”双指针用来索引子数组第一位和最后一位和“sum”记录子数组的元素和。最后,当“end<n”开始遍历,我们使用sum记录和,判断一下sum是否>=target,当不满足条件时,将“end+=1”;直到满足sum>=target这个条件时,开启循环寻找最小的子数组长度。我们取“ans”和“end-start+1”的最小值,由于我们此时已经记录了子数组的长度,所以我们需要将“start+=1”,此时子数组不包含nums[start]的值,所以要在start+1前将sum-nums[start]的值;

螺旋矩阵 II

链接:

https://leetcode.cn/problems/spiral-matrix-ii/

 

  1. class Solution:
  2. def generateMatrix(self, n: int) -> List[List[int]]:
  3. dirs=[(0,1),(1,0),(0,-1),(-1,0)]
  4. matrix=[[0]*n for _ in range(n)]
  5. dirIdx,row,col=0,0,0
  6. for i in range(n*n):
  7. matrix[row][col]=i+1
  8. dx,dy=dirs[dirIdx]
  9. r,c=row+dx,col+dy
  10. if r<0 or r==n or c==n or matrix[r][c]>0:
  11. dirIdx=(dirIdx+1)%4
  12. dx,dy=dirs[dirIdx]
  13. row,col=row+dx,col+dy
  14. return matrix

思路:

题目理解:本题需要构建一个n x n 正方形矩阵,将元素按顺时针顺序螺旋排列。主要解决两个方面:1、怎么按照顺时针螺旋行走;2、怎么防止超越边界。解题:首先,我们需要构建一个n x n 元都为0的矩阵,向里面填元素。其次,我们填元素是一个一个填所以遍历次数是n x n ,定义初始点坐标“row,col=0,0”。我们一初始点向右为x轴正向,向下为y轴正向。定义一个列表存储四个行走方向按照→、↓、←、↑排列,定义“dirIdx=0”初始向右走。最后,我们在循环里将矩阵对应位置进行赋值,然后我们判断一下,当走到最后一行或列的时候我们要转弯,走到以前填过元素的地方要转弯。注意:“r<0”是因为第一列的行数为0,所以这边不能直接为“r=0”。

本文为学习算法的小白发布,不喜勿喷

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Li_阴宅/article/detail/993191
推荐阅读
相关标签
  

闽ICP备14008679号