重新刷题求职2-DAY2

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] <= 104
• nums 已按 非递减顺序 排序

核心思路：双指针（左右指针）

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, numsl+1, ..., 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 <= 109
• 1 <= nums.length <= 105
• 1 <= 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 matirx

better 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