# 二刷力扣--数组

## 数组

### 数组理论基础

Python中的list不要求相同类型。 Python中的array.array中的元素是相同类型的。

### 二分查找(704)

class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left <= right:
mid =  left  + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid+1
elif nums[mid] >target:
right = mid-1
return -1


### 移除元素(27)

#双指针

class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
fast = 0
slow = 0
while fast < len(nums):
if nums[fast] == val:
fast += 1
else:
nums[slow] = nums[fast]
fast += 1
slow += 1
return slow


class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
for i in range(len(nums)-1, -1, -1):# 注意顺序
if nums[i] == val:
nums.pop(i)

return len(nums)


### 有序数组的平方(977)

#双指针

class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
res = [0]*len(nums)
i = 0
j = len(nums) - 1
end = len(nums)-1
while j >= i:
if abs(nums[i]) > abs(nums[j]):
res[end] = nums[i]**2
i += 1
else:
res[end] = nums[j]**2
j -= 1
end -= 1
return res


### 长度最小的子数组(209)

#滑动窗口

class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
res = 10**6
s = 0
i = 0 # 窗口左边界

for j in range(len(nums)): # j是窗口的右边界
s += nums[j]
# 每次更新i(起始位置)
while s >= target:
subLength = j-i+1
res = res if  res < subLength else subLength
s -= nums[i]
i += 1

return res if res != 10**6 else 0


python 缩进好容易看错，尤其是在leetcode的编辑器中。

### 螺旋矩阵(59)

#模拟

class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
def next_(i,j,direction):
if direction == 'right':
if j < n-1 and mat[i][j+1] == 0 :
j += 1
else:
direction = 'down'
i += 1
elif direction == 'down':
if i < n-1 and mat[i+1][j] == 0:
i += 1
else:
direction = 'left'
j -= 1
elif direction == 'left':
if j > 0 and mat[i][j-1] == 0:
j -= 1
else:
direction = 'up'
i -= 1
elif direction == 'up':
if i > 0 and mat[i-1][j] == 0:
i -= 1
else:
direction = 'right'
j += 1
return i, j, direction

mat = [[0 for j in range(n)] for i in range(n)]
i,j = 0,0
direction = 'right'
for x in range(1, 1+n**2):
mat[i][j] = x
i,j,direction = next_(i,j,direction)
print(i,j,direction)

return mat



LeetCode官网给出的题解更简洁。参考官网的解后优化了一下自己的代码：

class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
directions = [(0,1), (1,0), (0,-1), (-1,0)] # 右 下 左 上
def next_(i,j,directionIndex):
direction = directions[directionIndex]
t_i, t_j =  i + direction[0], j + direction[1]
if not (0<= t_i <= n-1) or not (0<= t_j <= n-1) or mat[t_i][t_j] != 0:
directionIndex = (directionIndex +1) % 4
direction = directions[directionIndex]
t_i, t_j =  i + direction[0], j + direction[1]
return t_i, t_j, directionIndex

mat = [[0 for j in range(n)] for i in range(n)]
i,j = 0,0
directionIndex = 0  # 右
for x in range(1, 1+n**2):
mat[i][j] = x
i,j,directionIndex = next_(i,j,directionIndex)

return mat


## 数组小结

LeetCode中的题目需要注意给出的数组是否有序。通常会用到双指针滑动窗口等技巧。

|
14天前
|

11 0
|
14天前
|

8 0
|
14天前

9 1
|
14天前
|

11 1
|
14天前
|

13 1
|
2天前
|

6 0
|
27天前
|

18 3
|
27天前
|

10 1
|
27天前

12 1
|
27天前

12 1