行业知识
算法第二天数组2
2026-11-19 22:11:09
来源:互联网转载
977 有序数组的平方
index.php/tags-41973.html" >���你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
我的思路
- 遍历数组,每个元素取平方后代替原本元素
- 对新的数组进行从小到大排序(快排,冒泡)
暴力求解
def sortedSquares(nums: List[int]) -> List[int]:for i in range(len(nums)):nums[i]=nums[i]*nums[i]nums.sort()return nums
def sortedSquares(nums: List[int]) -> List[int]:return sorted(x*x for x in nums)
- list.sort()在原list上进行修改,return nums.sort() 没有返回的对象,结果就是null;并且排序的对象只能是列表
- sorted(iterable, reverse=False),排序对象是一个可迭代的对象,reverse=True降序
双指针法
左右两个指针,那边平方大那边指针向前或后进一,之后将大的写到列表最后面并且指针向前进一,直到左右俩指针重合
def sortedSquares(nums: List[int]) -> List[int]:i,j,k=0,len(nums)-1,len(nums)-1 #左右指针,以及一个写入指针res=[1 for i in range(len(nums))] #建立一个新表存放新数组while i=target:min_len=min(min_len,j-i+1)break #只中断内循环(该起始的子数组最小已找到,其他起始的子数组最小也需要找到进行比较)return min_len if min_len!=float('inf) else 0- for循环套判断不能写多个return 这样只能循环一次相当于只有一次循环
- float(‘inf’)表示无穷大
滑动窗口
每次滑动时要固定一边再滑动另一边
def minSubArrayLen(target: int, nums: List[int]) -> int:l=len(nums)left,right=0,0 #滑动窗口的起始与截止指针min_len=float('inf') sub_sum=0 #子序列各个元素累加存储while right=target:min_len=min(min_len,right-left+1)sub_sum-=nums[left] # 起始要往后移一位,因此要减去这一位的值left+=1 # 起始往后移一位right+=1 # 截止位往后移一位return min_len if min_len!=float('inf) else 059 螺旋矩阵II
给你一个正整数 n ,生成一个包含 1 到 n 2 n^2 n2所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
自己的思路
没有思路
答案思路
当n为偶数时,有n/2或n//2层
当n为奇数时,有**(n-1)/2**或 n//2层和一个中心点,中心点坐标(n//2,n//2)
每层都有4个方向,每个方向有(n-2*第几层数+1)个元素(最外层是第1层,次外层第2层…)
不需要知道有多少个元素,只需要知道每层起始坐标,每个方向的终止坐标都能求得。n-layer
def generateMatrix(n: int) -> List[List[int]]:array=[[0]*n for _ in range(n)] #创建n*n数组startx,starty=0,0 # 起始点坐标loop,mid=n//2,n//2 #迭代次数(有几层);n为奇数时,矩阵的中心点count=1 # 计数for layer in range(1,loop+1): # 循环每一层for i in range(starty,n-layer): #每一层中从左到右方向nums[startx][i]=countcount+=1for i in range(startx,n-layer): #每一层中从上到下方向nums[i][n-layer]=count count+=1for i in range(n-layer,starty,-1)# 每一层中从右到左方向nums[n-layer][i]=countcount+=1for i in range(n-layer,startx,-1) # 每一层中从下到上方向nums[i][starty]=countcount+=1startx+=1starty+=1if n%2!=0:nums[mid][mid]=countreturn nums
- 数组乘法 [2]*5=[2,2,2,2,2]=[2 for _ in range(5)]