LeetCode977. 有序数组的平方
解法
这道题有两道解法，首先就是最容易想到的解法，暴力解法
其次，这道题也可以使用双指针来解决。双指针我是真的没有想到，卡哥nb!
解法一、暴力
没啥好说的，平方后排序，或者abs之后排序再平方都行。
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
for i in range(len(nums)):
nums[i] = (nums[i])**2
nums.sort()
return nums
解法二、双指针
双指针的这个解法在题目有个小提示，就是非递减序列
这五个字说明了两个问题：
第一、如果序列出现了负数，那么负数一定是出现在左边的。
那么平方后呢？大数一定是出现在两边的，从两边逐渐向中间递减的。
第二、这个序列在一定程度是有序的(如果无序的序列我觉得就只能用上面的暴力了)
那么双指针的思路就是设置两个指针，一个指向头，一个指向尾，进行比对后插入新数组。
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
left = 0
right = len(nums)-1
i = len(nums) - 1
new_nums = [0 for i in nums]
while left <= right:
if abs(nums[left]) > abs(nums[right]):
new_nums[i] = nums[left]*nums[left]
i -=1
left+=1
elif abs(nums[left]) < abs(nums[right]):
new_nums[i] = nums[right] * nums[right]
i -= 1
right -= 1
elif abs(nums[left]) == abs(nums[right]) and left != right:
new_nums[i] = nums[left] * nums[left]
i -= 1
new_nums[i] = nums[left] * nums[left]
i -= 1
left += 1
right -= 1
else:
new_nums[i] = nums[left] * nums[left]
i -= 1
left += 1
right -= 1
return new_nums
代码随想录的代码
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
l, r, i = 0, len(nums)-1, len(nums)-1
res = [float('inf')] * len(nums) # 需要提前定义列表，存放结果
while l <= r:
if nums[l] ** 2 < nums[r] ** 2: # 左右边界进行对比，找出最大值
res[i] = nums[r] ** 2
r -= 1 # 右指针往左移动
else:
res[i] = nums[l] ** 2
l += 1 # 左指针往右移动
i -= 1 # 存放结果的指针需要往前平移一位
return res
(一如既往的简洁)
209.长度最小的子数组
暴力解法
暴力解法就是使用双重循环，把每一种情况都遍历一遍(但是现在加了新的案例，已经过不了了)
#暴力解法，加了新的案例过不了
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
size = 10 ** 5
for i in range(len(nums)):
count = 0
num = 0
for j in range(i, len(nums)):
count += nums[j]
num += 1
if count >= target and size > num:
size = num
break
if size == 10 ** 5:
return 0
return size
滑动窗口
emmm，不是太理解其中的原理，就是，为什么可以这样做。
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left = 0
right = 0
lens = len(nums)
size = float("inf")
sum_nums = 0
while right < lens:
sum_nums += nums[right]
while sum_nums >= target:
size = min(size,right-left+1)
sum_nums -= nums[left]
left += 1
right +=1
return size if size != float("inf") else 0
59.螺旋矩阵II
难点分析
这道题的难度在于需要你去分析边界值，并且他在不停的绕，所以很容易就把自己给绕进去。我第一次写这道题，完全没有分析出来，写的代码就是一坨。完全是靠卡哥的视频和录友讲解
模拟法解题
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
matrex = [[0 for i in range(n)] for i in range(n)]
choice = "t"
nums = n ** 2
t = 0 # 上边界
b = n - 1 # 下边界
l = 0 # 左边界
r = n - 1 # 右边界
num = 1
i, j = 0, 0
while num <= nums:
matrex[i][j] = num
if choice == "t":
j += 1
# 碰到墙就右拐，把上边往里缩一格，下面同理
if j == r:
choice = "r"
t += 1
# 靠着右边走
elif choice == "r":
i += 1
if i == b:
choice = "b"
r -= 1
elif choice == "b":
j -= 1
if j == l:
choice = "l"
b -= 1
elif choice == "l":
i -= 1
if i == t:
choice = "t"
l += 1
num += 1
return matrex
