刷题日记-Day2- Leedcode-977. 有序数组的平方，209. 长度最小的子数组，59. 螺旋矩阵 II-Python实现
刷题日记-Day2- Leedcode-977. 有序数组的平方，209. 长度最小的子数组，59. 螺旋矩阵 II-Python实现
刷题日记Day2- 977 有序数组的平方
- 209. 长度最小的子数组
- 59. 螺旋矩阵 II
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 snums
elif nums[-1] <=0:
return list(reversed(snums))
mid = 0
for i in range(len(nums)-1):
if (nums[i] * nums[i+1])<=0:
if abs(nums[i]) < nums[i+1]:
mid = i
else:
mid = i + 1
left = mid - 1
right = mid + 1
ans = [snums[mid]]
# print("========")
# print(ans)
# print("========")
while left >=0 and right <= len(nums)-1:
if snums[left] < snums[right]:
ans.append(snums[left])
left -= 1
else:
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 ans209. 长度最小的子数组
链接：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 = 0
right = 0
length = len(nums)
ans = 1e5 +1
temp = nums[0]
while right < len(nums):
if temp < target:
right += 1
if 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 0
return ans59. 螺旋矩阵 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, 0
for i in range(n * n):
ans[row][col] = i + 1
dx, dy = direc[idx]
r, c = row + dx, col + dy
if r< 0 or r>= n or c<0 or c >=n or ans[r][c]>0:
# 碰壁了，顺时针旋转方向
idx = (idx+1)% 4
dx, dy = direc[idx]
row, col = row + dx, col +dy
# print(ans)
return ans腾讯云开发者
