Day2 |977.有序數(shù)組的平方 | 209.長度最小的子數(shù)組| 59.螺旋矩陣II
977.有序數(shù)組的平方
題目鏈接：
977. 有序數(shù)組的平方 - 力扣（Leetcode）
給一個按 非遞減順序 排序的整數(shù)數(shù)組 nums，返回 每個數(shù)字的平方 組成的新數(shù)組，要求也按 非遞減順序 排序。
拿到題的第一感覺:
對每個數(shù)平方，然后排序（典型的暴力解法，在排序的時候想到除了調(diào)用sort方法，要自己寫一個排序的代碼好像不會）
看了題解以后，才感覺雙指針的操作好巧妙。
收獲的點：
因為數(shù)組nums中可能含有負(fù)數(shù)，平方后比較大的數(shù)在兩邊，分別定義left和right指針，定義一個新列表res, 用site從后往前收集元素
site = len(nums)-1
if nums[left] **2 > nums[right]**2:
res[site] = nums[left]**2
site -=1
left +=1
else:
res[site] = nums[right]**2
site -=1
right -=1
完整代碼：
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
left,right = 0,len(nums)-1
res = [-1]*len(nums) #這里有犯一個錯誤，以為定義一個空列表也行，因為后面調(diào)用了res[site]應(yīng)該是要有長度才對
site = len(nums)-1
if len(nums) == 1:
return [nums[0]*nums[0]]
while left <= right:
if nums[left]*nums[left] < nums[right]*nums[right]:
res[site] = nums[right]*nums[right]
right -=1
else:
res[site]=nums[left]*nums[left]
left +=1
site-=1
return res
209.長度最小的子數(shù)組
題目鏈接：
209. 長度最小的子數(shù)組 - 力扣（Leetcode）
給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) target 。
找出該數(shù)組中滿足其和 ≥ target 的長度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其長度。如果不存在符合條件的子數(shù)組，返回 0。
拿到題的第一感覺：
子集可能有很多，還要比較子集的長度，有點懵。看了題解，理清了頭緒：因為數(shù)組中都是正整數(shù)，所以當(dāng)前x個元素加和大于target的話，x+1個肯定也是大于的，所以就把x的左邊界的元素去掉，看能否繼續(xù)滿足，滿足則減去，建立while循環(huán)，直到減到最少。從左到右依次遍歷，更新每次的最小長度。
收獲的點：
1）這種滑動窗口思想的實現(xiàn)：
while s >= target:
ans = min(ans,right-left+1)
s -= s[left] #不斷把左邊多余的減去，減少長度
left +=1
2）enumerate函數(shù)的使用:同時獲取了列表的索引和對應(yīng)的元素
s =0
for right,x in enumerate(nums):
s+= x
#right在后面（循環(huán)體內(nèi)部有調(diào)用）
完整代碼：
#方法一：
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
ans = n + 1 # 也可以寫 inf
s = left = 0
for right, x in enumerate(nums):
s += x
while s - nums[left] >= target:
s -= nums[left]
left += 1
if s >= target:
ans = min(ans, right-left+1)
return ans if ans <= n else 0
#方法二：
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left = 0
ans = len(nums)+1
s = 0
for right,x in enumerate(nums):
s += x
while s - nums[left] >= target:
s -= nums[left]
left +=1
if s >= target:
ans = min(ans,right-left+1)
return ans if ans <= len(nums) else 0
59.螺旋矩陣II
題目鏈接：
給一個正整數(shù) n ，生成一個包含 1 到 n2 所有元素，且元素按順時針順序螺旋排列的 n x n 正方形矩陣 matrix。
拿到題目的感覺：
感覺有點復(fù)雜，不知道怎么下手。第一遍看題解也沒太明白，后來把代碼中的循環(huán)代入具體的數(shù)值，豁然開朗。
收獲的點：
1）這類模擬題很重要的一點是想清楚步驟減的規(guī)律，比如這個螺旋遵循的就是：從左到右->從上到下->從右到左->從下到上。
2）邊界的處理要堅持設(shè)定的原則，比如左閉右閉，只要保持都是這個區(qū)間就行，如果要包含right那個元素，區(qū)間右側(cè)定義為right+1即可：range(left,right+1),實際上執(zhí)行的是[left,right]。
3）while 循環(huán)的真的很好用，以前大部分時候都會選擇for 循環(huán)，對while循環(huán)掌握的不熟練。經(jīng)過這幾個題發(fā)現(xiàn)，當(dāng)需要循環(huán)到滿足一定條件時，可以考慮設(shè)定while循環(huán)。
- 生成矩陣的方式
matrix= [[0]*n for _ in range(n)]
#生成n*n的矩陣，因為[0]*n是生成n個0的列表
當(dāng)然也可以這樣：
matrix = [ [0 for _ in range(n)] for _ in range(n)]
完整代碼：
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
t,b,l,r = 0,n-1,0,n-1
mat = [[0]*n for _ in range(n)]
num,tar = 1,n*n
while num <= tar:
for i in range(l,r+1):
mat[t][i] = num
num +=1
t +=1
for i in range(t,b+1):
mat[i][r] = num
num +=1
r -= 1
for i in range(r,l-1,-1):
mat[b][i] = num
num +=1
b -= 1
for i in range(b,t-1,-1):
mat[i][l] = num
num +=1
l +=1
return mat
理清楚循環(huán)遍歷的方式后，解決54. 螺旋矩陣 - 力扣（Leetcode） 也就很容易了，是一樣的套路：明確上下左右邊和遍歷的遍歷，while循環(huán)的終止條件，邊更新的位置，邊界的設(shè)定。
54螺旋矩陣的代碼如下：
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix or not matrix[0]:
return []
l,r,t,b = 0,len(matrix[0])-1,0,len(matrix)-1
res = []
s = len(matrix[0]) * len(matrix)
while s > 0:
for i in range(l,r+1):
res.append(matrix[t][i])
s -=1
t +=1
for i in range(t,b+1):
res.append(matrix[i][r])
s -=1
r -=1
for i in range(r,l-1,-1):
res.append(matrix[b][i])
s -=1
b -=1
for i in range(b,t-1,-1):
res.append(matrix[i][l])
s -=1
l +=1
return res[0:len(matrix)*len(matrix[0])]
