做网站兴趣爱好百度营销推广官网

977 有序数组的平方

链接：https://leetcode.cn/problems/squares-of-a-sorted-array/description/

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

思路：分三种情况
-1. 全正，直接返回原数组平方
-2. 全负，返回原数组平方的逆序
-3. 有正有负
（1）寻找中间点位（绝对值从小变大的起点或者相邻乘积<=0的位置）
（2）左指针为mid-1 ，右指针为mid + 1
(3) 转换为两个有序数组合并问题
（4） 注意点：等其中一个结束后要把未结束的那个剩余的数字全部追加到最后

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:snums = [num * num for num in nums]if nums[0] >= 0:return snumselif nums[-1] <=0:return list(reversed(snums))mid = 0for i in range(len(nums)-1):if (nums[i] * nums[i+1])<=0:if abs(nums[i]) < nums[i+1]:mid = ielse:mid = i + 1left = mid - 1right = mid + 1ans = [snums[mid]]# print("========")# print(ans)# print("========")while left >=0 and right <= len(nums)-1:if snums[left] < snums[right]:ans.append(snums[left])left -= 1else:ans.append(snums[right])right += 1# print(ans, left ,right)if left == -1:ans.extend(snums[right:])elif right == len(nums):ans.extend(list(reversed(snums[:left+1])))return ans

209. 长度最小的子数组

链接：https://leetcode.cn/problems/minimum-size-subarray-sum/description/

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

思路：双指针，右指针探路，选择区间内满足条件的，满足后，左指针移动，找到最小满足的，以此类推
难点：边界条件处理

代码实现

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:left = 0right = 0 length = len(nums)ans = 1e5 +1temp = nums[0]while right < len(nums):if temp < target:right += 1if right != len(nums):temp += nums[right]# print("==", left, right, nums[left:right+1], ans)else: ans = min(ans, right + 1 -left)temp -= nums[left]left += 1      # print("****", left, right, nums[left:right+1], ans)while left <=right and temp >= target:ans = min(ans, right + 1 -left)temp -= nums[left]left += 1          # print("@@@", left, right, nums[left:right+1], ans)if ans == 1e5+1:return 0return ans

59. 螺旋矩阵 II

链接：https://leetcode.cn/problems/spiral-matrix-ii/description/

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

思路：模拟，设置上下左右四个方向，注意方向的设置必须按照顺时针，即右-》下-》左-》上循环往复，碰壁则调转方向。
Python代码实现

class Solution:def generateMatrix(self, n: int) -> List[List[int]]:if n == 1:return [[1]]# temp = list(range(1, n*n +1))# print(temp)# ans = [[0]*n] *n   谁这样写谁是笨蛋# print(ans)ans = [[0] * n for _ in range(n)]# print(ans)# 右下左上 顺时针方向direc = [[0,1], [1,0],[0, -1], [-1,0]]row, col, idx = 0, 0, 0for i in range(n * n):ans[row][col] = i + 1dx, dy = direc[idx]r, c = row + dx, col + dyif r< 0 or r>= n or c<0 or c >=n or ans[r][c]>0:# 碰壁了，顺时针旋转方向idx = (idx+1)% 4dx, dy = direc[idx]row, col = row + dx, col +dy# print(ans)return ans