有序数组三个方法,长度最小的子数组两个方法,螺旋矩阵纯写(模拟行为)
题目链接
给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
示例 :
输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]
直接理解,先一个一个平方,再排序
#暴力破解
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
for i in range(len(nums)):
nums[i]*=nums[i]
j=sorted(nums) # nums.sort()不要变量接收-永久排序,sorted()需要-临时排序
return j
列表(list)推导:将循环和条件语句的功能结合到一行代码中
基础语法:
[expression for item in iterable]
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
return sorted(i**2 for i in nums)
数组有序,平方之后的最大值在必定在数组两头。
比较两头大小,放入新列表。
#双指针法
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
l=0
r=i=len(nums)-1
result=len(nums)*[float('inf')] #长度*空间大小
while l<=r:
if nums[l]**2<nums[r]**2:
result[i]=nums[r]**2
r-=1
else:
result[i]=nums[l]**2
l+=1
i-=1
return result
使用三种方法解题,复习了双指针法
题目链接
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
示例 :
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
目的:找到>=target的最小长度
本方法在leetcode超时
#暴力破解
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
lenth=len(nums)
minlen=float('inf')
for i in range(lenth):
sum=0
for j in range(i,lenth):
sum+=nums[j]
if sum>=target:
minlen=min(minlen,j-i+1)
break
if minlen!=float('inf'):
return minlen
else:
return 0
#滑动窗口(双指针)
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left=right=0
minlen=float('inf')
sum=0
for right in range(len(nums)):#找第一个>=target
sum+=nums[right]
while sum>=target:
minlen=min(minlen,right-left+1)
sum-=nums[left] #减掉窗口最左侧
left+=1
if minlen!=float('inf'):
return minlen
else:
return 0
滑动先画图,多了缩小,小了扩大,一直更新minlen
题目链接
给你一个正整数
n
n
n ,生成一个包含 1 到
n
2
n^2
n2 所有元素,且元素按顺时针顺序螺旋排列的
n
?
n
n*n
n?n正方形矩阵 matrix 。
示例:
输入:n = 3
输出:[[1,2,3],[8,9,4],[7,6,5]]
#左闭右开
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
nums=[[0]*n for _ in range(n)] #生成n*n的0列表
x=y=0
count=1
loop=mid=n//2
for bias in range(1,loop+1): #循环圈数
for j in range(y,n-bias): #i控制行,j控制列;左到右
nums[x][j]=count
count+=1
for i in range(x,n-bias):#上到下
nums[i][n-bias]=count
count+=1
for j in range(n-bias,y,-1):#右到左
nums[n-bias][j]=count
count+=1
for i in range(n-bias,x,-1):#下到上
nums[i][y]=count
count+=1
x+=1
y+=1
if n%2!=0: #n为奇数进行中心填充
nums[mid][mid]=count
return nums
没具体算法,靠观察,画个图,不然太容易乱了
借个图