apache新建网站,wordpress 熊掌号代码,wordpress高端企业主题,html5网站是用什么软件做的吗977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums#xff0c;返回 每个数字的平方 组成的新数组#xff0c;要求也按 非递减顺序 排序。
示例 1#xff1a;
输入#xff1a;nums [-4,-1,0,3,10]
输出#xff1a;[0,1,9,16,100]
解释#xff1a;平方后…977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。
示例 1
输入nums [-4,-1,0,3,10]
输出[0,1,9,16,100]
解释平方后数组变为 [16,1,0,9,100]
排序后数组变为 [0,1,9,16,100]示例 2
输入nums [-7,-3,2,3,11]
输出[4,9,9,49,121]提示
1 nums.length 104-104 nums[i] 104nums 已按 非递减顺序 排序
核心思路双指针左右指针
from collections import deque
class Solution:def sortedSquares(self, nums: List[int]) - List[int]:#左右指针加双端队列左右指针是关键左右端点取绝对值大的加入其中退出循环的条件l r可以取等res deque()l, r 0, len(nums) - 1while l r:if abs(nums[l]) abs(nums[r]):res.appendleft(nums[l] ** 2)l 1else:res.appendleft(nums[r] ** 2)r - 1return list(res)209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的
子数组
[numsl, numsl1, ..., numsr-1, numsr] 并返回其长度**。**如果不存在符合条件的子数组返回 0 。
示例 1
输入target 7, nums [2,3,1,2,4,3]
输出2
解释子数组 [4,3] 是该条件下的长度最小的子数组。示例 2
输入target 4, nums [1,4,4]
输出1示例 3
输入target 11, nums [1,1,1,1,1,1,1,1]
输出0提示
1 target 1091 nums.length 1051 nums[i] 104
核心思想
滑动窗口快慢指针
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) - int:# 滑动窗口快慢指针始终维持窗口内部的子数组的和大于等于target小了则right ,大了则left # 跳出循环条件, right len(nums) - 1if sum(nums) target:return 0left, right 0, 0sum_v 0res len(nums) 1while right len(nums):while sum_v target and right len(nums):sum_v nums[right]right 1while sum_v target and left right:sum_v - nums[left]left 1res min(res, right - left 1)return res
更好的写法
class Solution:def minSubArrayLen(self, target: int, nums: List[int]) - int:# 双指针 快慢指针n len(nums)min_length n 1slow, fast 0, 0sum_value 0 while fast n:sum_value nums[fast]while sum_value target:length fast - slow 1min_length min(min_length, length)sum_value - nums[slow]slow 1fast 1return min_length if min_length n else 0
59. 螺旋矩阵 II
给你一个正整数 n 生成一个包含 1 到 n2 所有元素且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1 输入n 3
输出[[1,2,3],[8,9,4],[7,6,5]]示例 2
输入n 1
输出[[1]]提示
1 n 20
class Solution:def generateMatrix(self, n: int) - List[List[int]]:#这道题就没有什么算法硬写#但是有一些帮助写的小trick设置好左、右、上、下四个边界可以帮助写代码#注意点2设置好四个边界后边界需要进行相应的收缩l_border, r_border, u_border, d_border 0, n, 0, n#初始化i, j 0, 0value 1matirx [[0 for i in range(n)] for j in range(n)]while True:for j in range(l_border, r_border):matirx[i][j] valuevalue 1u_border 1j r_border - 1for i in range(u_border, d_border):matirx[i][j] valuevalue 1r_border - 1for j in range(r_border - 1, l_border - 1, -1):matirx[i][j] valuevalue 1d_border - 1for i in range(d_border - 1, u_border - 1, -1):matirx[i][j] valuevalue 1l_border 1if value n**2:return matirxbetter code
class Solution:def generateMatrix(self, n: int) - List[List[int]]:matrix [[0] * n for _ in range(n)]left, right, top, bottom 0, n - 1, 0, n - 1num 1while left right and top bottom:# 向右填充for j in range(left, right 1):matrix[top][j] numnum 1top 1if top bottom:break# 向下填充for i in range(top, bottom 1):matrix[i][right] numnum 1right - 1if right left:break# 向左填充for j in range(right, left - 1, -1):matrix[bottom][j] numnum 1bottom - 1if bottom top:break# 向上填充for i in range(bottom, top - 1, -1):matrix[i][left] numnum 1left 1return matrix
