我是靠谱客的博主 土豪板栗，最近开发中收集的这篇文章主要介绍leetcode-数组知识点（中等）11.盛最多水的容器15. 三数之和16. 最接近的三数之和18. 四数之和31. 下一个排列33. 搜索旋转排序数组34. 在排列数组中查找元素的第一个和最后一个位置36. 有效的数独39. 组合总和 40. 组合总和45. 跳跃游戏 46. 全排列47. 全排列（含重复元素）48. 旋转图像54. 螺旋矩阵55. 跳跃游戏 56. 合并区间57. 插入区间 59. 螺旋矩阵63. 不同路径64. 最小路径和73. 矩阵置零74. 搜索二维矩阵75. 颜色分，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
目录
11.盛最多水的容器
15. 三数之和
16. 最接近的三数之和
18. 四数之和
31. 下一个排列
33. 搜索旋转排序数组
34. 在排列数组中查找元素的第一个和最后一个位置
36. 有效的数独
39. 组合总和
40. 组合总和
45. 跳跃游戏
46. 全排列
47. 全排列（含重复元素）
48. 旋转图像
54. 螺旋矩阵
55. 跳跃游戏
56. 合并区间
57. 插入区间
59. 螺旋矩阵
63. 不同路径
64. 最小路径和
73. 矩阵置零
74. 搜索二维矩阵
75. 颜色分类
77. 组合
78. 子集
79. 单词搜索
80. 删除有序数组中的重复项
81. 搜索旋转排序数组
90. 子集
11.盛最多水的容器
# 超出时间限制
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
n = len(height)
li = []
for i in range(n-1):
area = 0
for j in range(i+1, n):
area = max(area, (j-i) * min(height[i], height[j]))
li.append(area)
return max(li)稍微动脑子想想就知道中等题不能再暴力解法了......利用双指针解法，每次移动较小的边界进行遍历（假设一定要移动边界的话，移动较小的那一边损失较小）
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
head = 0
tail = len(height)-1
area = 0
big = max(height) * tail # 标记该示例中可能出现的最大值
while head < tail:
area = max(area, (tail-head)*min(height[head], height[tail]))
if area >= big: # 出现最大值后终止循环
return area
if height[head] < height[tail]:
head += 1
else:
tail -= 1
return area15. 三数之和
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
li = []
n = len(nums)
if n < 3:
return []
for v1 in range(n-2):
v2 = v1 + 1
v3 = n - 1
while v2 < v3:
if nums[v2] + nums[v3] < -nums[v1]:
v2 += 1
elif nums[v2] + nums[v3] > -nums[v1]:
v3 -= 1
elif nums[v2] + nums[v3] == -nums[v1]:
if [nums[v1], nums[v2], nums[v3]] not in li:
li.append([nums[v1], nums[v2], nums[v3]])
v2 += 1
v3 -= 1
return li排序后设置三个指针v1，v2，v3，v2从前向后遍历，v3从后向前遍历，使得nums[v2] + nums[v3] == -nums[v1]，用时较长。
16. 最接近的三数之和
nums.sort()
n = len(nums)
count = nums[0] + nums[1] + nums[2]
for v1 in range(n-2):
if v1 > 0 and nums[v1] == nums[v1-1]:
continue # 如果移动v1后数值不变，继续执行下一次for循环
v2 = v1 + 1
v3 = n - 1
while v2 < v3:
tmp = nums[v1] + nums[v2] + nums[v3]
if tmp == target:
return target
if abs(tmp-target) < abs(count-target):
count = tmp
if tmp > target:
v3 -= 1
while v2 < v3 and nums[v3] == nums[v3+1]:
v3 -= 1
else:
v2 += 1
while v2 < v3 and nums[v2] == nums[v2 - 1]:
v2 += 1
return count18. 四数之和
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums.sort()
n = len(nums)
li = []
if n < 4:
return []
for v1 in range(n-3):
for v2 in range(v1+1, n-2):
v3 = v2+1
v4 = n-1
while v3 < v4:
tmp = nums[v1] + nums[v2] + nums[v3] + nums[v4]
if tmp == target:
if [nums[v1], nums[v2], nums[v3], nums[v4]] not in li:
li.append([nums[v1], nums[v2], nums[v3], nums[v4]])
v3 += 1
v4 -= 1
elif tmp < target:
v3 += 1
elif tmp > target:
v4 -= 1
return li类似前两题吧反正就是，讨论特殊情况太麻烦了直接用个not in语句判定一下，缺点是时间和内存都挺大。
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
li = [] # 定义一个返回值
if not nums or len(nums) < 4:
return li
nums.sort()
n = len(nums)
for v1 in range(n - 3):
# 当v1的值与前面的值相等时忽略
if v1 > 0 and nums[v1] == nums[v1 - 1]:
continue # continue,跳出本次for循环继续下一次for循环
# 获取当前最小值,如果最小值比目标值大,忽略
if nums[v1] + nums[v1 + 1] + nums[v1 + 2] + nums[v1 + 3] > target:
break # break,直接退出所有for循环
# 获取当前最大值,如果最大值比目标值小,忽略
if nums[v1] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target:
continue # continue,跳出本次for循环继续下一次for循环
for v2 in range(v1 + 1, n - 2):
if v2 > v1 + 1 and nums[v2] == nums[v2 - 1]:
continue
if nums[v1] + nums[v2] + nums[v2 + 1] + nums[v2 + 2] > target:
break
if nums[v1] + nums[v2] + nums[n - 2] + nums[n - 1] < target:
continue
left, right = v2 + 1, n - 1
while left < right:
tmp = nums[v1] + nums[v2] + nums[left] + nums[right]
if tmp == target:
li.append([nums[v1], nums[v2], nums[left], nums[right]])
left += 1
while left < right and nums[left] == nums[left - 1]:
left += 1
right -= 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
elif tmp < target:
left += 1
else:
right -= 1
return li一个重点是：break跳出所有循环，continue跳出本次循环，数值更新后继续下一次循环，两个语句都是针对while和for来说的。通过跳出不必要的循环以及判断特殊情况（而不是懒鬼方法直接not in）可以大大缩减时间和占用的内存。
31. 下一个排列
# 判决思路在笔记上，不知道为什么leetcode会报错，在电脑上跑是对的
class Solution(object):
# 将比a大的最小元素提取到前面，其他元素从大到小排列
def sort1(self, a, li): # 排序函数，a为非倒序元素，li为全倒序列表
tmp = li[0] # tmp初始化为li中最大值
head_v = 0 # head_v为指向tmp的指针
for i in range(len(li)-1， -1，-1): # 在li中寻找比a大的最小元素
if li[i] >= a:
tmp = li[i]
head_v = i
li.pop(head_v) # 从li中删除比a大的最小元素
li.append(a) # 将a添加到li
li.sort() # 从大到小排序
sortli = [tmp] # 存储排序结果
for val in li:
sortli.append(val)
return sortli
def nextPermutation(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
n = len(nums)
if n == 1: # 列表长度为1时直接返回
return nums
elif n == 2: # 列表长度为2时交换元素位置返回
nums[0], nums[1] = nums[1], nums[0]
return nums
else: # 列表长度大于2时
if nums[n-1] > nums[n-2]: # 末尾两个元素为正序，直接交换后返回
nums[n-1], nums[n-2] = nums[n-2], nums[n-1]
return nums
else: # 末尾两个元素为倒序
li = [nums[n-2], nums[n-1]] # 存储倒序列表
i = 3
flag = 1
while i<=n and flag: # 向前遍历直到找到非倒序的元素
if nums[n-i] > nums[n-i+1]:
li.insert(0, nums[n-i])
i += 1
else:
flag = 0
if flag: # 未找到非倒序元素（整个列表为倒序），直接从小到大排序后返回
nums.sort()
return nums
tmp_li = self.sort1(nums[n-i], li)
con = nums[0: n-i]
for val in tmp_li: # 连接前面不需要改变的列表切片，以及重新排序后的列表
con.append(val)
return con官方解法的思路类似，先找到一个“较右数”也就是“非倒序排列的最靠右的元素”，再在右面找到一个比“较右数”稍大的元素“较小数”（因为只需要比较右数稍大一点点，所以称为“较小数”），交换“较小数”和“较右数”，再重新排列“较小数”右侧的序列。（下面是另一个解法里的代码，感觉更加清晰）
class Solution:
def nextPermutation(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
n = len(nums)
if n == 0:
return []
elif n == 1:
return nums
else:
v1 = n - 2 # 倒数第二个数，获得“较右数”
v2 = n - 1 # 倒数第一个数，获得“较小数”
while v1 >= 0 and nums[v1] >= nums[v1 + 1]:
v1 -= 1
if v1 == -1: # while循环被v1>=0终止，整个序列倒序排列
return nums.sort()
else:
while nums[v1] >= nums[v2]:
# 不需要限制v2>v1是因为v1右侧的数一定比它大
v2 -= 1
nums[v1], nums[v2] = nums[v2], nums[v1]
# 交换较小数和较右数后，v1右侧依旧严格倒序排列，前后亮亮交换即可
left = v1 + 1
right = n - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return nums33. 搜索旋转排序数组
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if nums.count(target) == 0:
return -1
else:
return nums.index(target)偷懒解法↑（而且耗时更短哈哈哈）
class Solution:
def search(self, nums, target):
if not nums:
return -1
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[0] <= nums[mid]: # 假如左半边有序
if nums[0] <= target < nums[mid]: # target在左半边
right = mid - 1 # 在左半边二分查找
else: # target在右半边
left = mid + 1 # 在右半边二分查找
else: # 假如右半边有序
if nums[mid] < target <= nums[len(nums) - 1]:
left = mid + 1
else:
right = mid - 1
return -134. 在排列数组中查找元素的第一个和最后一个位置
class Solution(object):
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
count = nums.count(target)
if not count: # 不存在target
return [-1,-1]
if len(nums) == 1: # 存在target但nums中只有一个数
return [0,0]
# 二分法
left = 0
right = len(nums) - 1
flag = 1
while flag: # 前面已经判定过一定存在target，left一定小于right
mid = (left + right) // 2
if nums[mid] == target: # 找到target，停止循环
flag = 0
elif nums[mid] < target: # target在右半部分
left = mid + 1
else: # target在左半部分
right = mid - 1
while mid > 0: # 找到第一个出现的target
if nums[mid-1] == target:
mid -= 1
else:
break
return [mid, mid+count-1]官方思路，leftindex是寻找第一个等于target的下标减一，rightindex是寻找第一个大于target的下标减一。
class Solution(object):
# 二分查找
# leftindex寻找第一个大于等于target的位置(lower = true)
# rightindex寻找第一个大于targrt的位置减一(lower = false)
def binarySearch(self, nums, target, lower):
left = 0
right = len(nums) - 1
ans = len(nums)
while left <= right:
mid = (left + right) // 2
# leftindex：target在mid处或在左半边
# rightindex：target在左半边
if nums[mid] > target or (lower and nums[mid] >= target):
right = mid - 1
ans = mid
else:
left = mid + 1
return ans
def searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
leftindex = self.binarySearch(nums, target, True)
rightindex = self.binarySearch(nums, target, False) - 1
# 判断是否存在target
if leftindex <= rightindex and rightindex <= len(nums) - 1 and nums[leftindex] == nums[rightindex] == target:
return [leftindex, rightindex]
else:
return [-1,-1]36. 有效的数独
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
# 每行是否有重复
for i in range(9):
tmp = board[i][0:9]
while tmp.count("."):
tmp.remove(".")
tmp_set = set(tmp)
if len(tmp) != len(tmp_set):
return False
# 每列是否有重复
for i in range(9):
# tmp = board[0:8][i] 这种写法取的还是第一排，奇怪
tmp = []
for j in range(9):
tmp.append(board[j][i])
while tmp.count("."):
tmp.remove(".")
tmp_set = set(tmp)
if len(tmp) != len(tmp_set):
return False
# 每个方块是否有重复
for i in range(9):
tmp = []
if i % 3 == 0: # 第一竖列的三个方块
n = i // 3
for j in range(3):
tmp.append(board[3 * n][j])
tmp.append(board[3 * n + 1][j])
tmp.append(board[3 * n + 2][j])
elif i % 3 == 1: # 第二竖列的三个方块
n = i // 3
for j in range(3,6):
tmp.append(board[3 * n][j])
tmp.append(board[3 * n + 1][j])
tmp.append(board[3 * n + 2][j])
elif i % 3 == 2: # 第三竖列的三个方块
n = i // 3
for j in range(6,9):
tmp.append(board[3 * n][j])
tmp.append(board[3 * n + 1][j])
tmp.append(board[3 * n + 2][j])
while tmp.count("."):
tmp.remove(".")
tmp_set = set(tmp)
if len(tmp) != len(tmp_set):
return False
return True利用哈希表的解法，设置三个哈希表记录数字出现情况（内存消耗很大）：
class Solution(object):
def isValidSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: bool
"""
row = [[0 for _ in range(10)] for _ in range(9)] # 9*10列表，存储每一行的每个数是否出现过
col = [[0 for _ in range(10)] for _ in range(9)] # 9*10列表，存储每一列的每个数是否出现过
box = [[0 for _ in range(10)] for _ in range(9)] # 9*10列表，存储每方块的每个数是否出现过
for i in range(9):
for j in range(9):
if board[i][j] == ".":
continue
curnumber = int(board[i][j])
if row[i][curnumber]:
return False
if col[j][curnumber]:
return False
# n1 = i // 3 # 方块在第几行
# n2 = j // 3 # 方块在第几列
# n = 3 * n1 + n2
if box[3*(i//3) + j//3][curnumber]:
return False
row[i][curnumber] = 1
col[j][curnumber] = 1
box[3*(i//3) + j//3][curnumber] = 1
return True39. 组合总和
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
dict = {i:[] for i in range(target+1)}
for val in sorted(candidates, reverse=True):
for i in range(val, target+1):
if i == val:
dict[i] = [[val]]
else:
for x in dict[i-val]:
dict[i].extend([x + [val]])
return dict[target]或者使用标准的回溯结构：
class Solution:
def combinationSum(self, candidates, target):
def dfs(candidates, begin, size, path, res, target):
# begin存储遍历起点，避免重复遍历
if target < 0: # 当target比抽取元素和小的时候返回
return
if target == 0: # 当target等于抽取元素和的时候，在res中保存结果
res.append(path)
return
for index in range(begin, size):
# 继续搜索下一层
dfs(candidates, index, size, path + [candidates[index]], res, target - candidates[index])
size = len(candidates) # 决定树的宽度
if size == 0:
return []
path = [] # 存储单条路经
res = [] # 存储所有满足要求的路径
dfs(candidates, 0, size, path, res, target)
return rese.g. candiates = [2,3,6,7], target = 7
这组代码还有优化的余地，比如在path = [2,2]时的下一层for循环中[2,2,6]已经超出target，[2,2,7]一定会超过target因此不需要执行。
# 增加判决条件（剪枝操作）
class Solution:
def combinationSum(self, candidates, target):
def dfs(candidates, begin, size, path, res, target):
# begin存储遍历起点，避免重复遍历
# if target < 0: # 当target比抽取元素和小的时候返回
# return
if target == 0: # 当target等于抽取元素和的时候，在res中保存结果
res.append(path)
return
for index in range(begin, size):
residue = target - candidates[index]
if residue < 0:
break
# dfs(candidates, index, size, path + [candidates[index]], res, target - candidates[index])
dfs(candidates, index, size, path + [candidates[index]], res, residue)
size = len(candidates) # 决定树的宽度
if size == 0:
return []
candidates.sort()
path = [] # 存储单条路经
res = [] # 存储所有满足要求的路径
dfs(candidates, 0, size, path, res, target)
return res回溯方法效率并不高，相当于穷举法，关键是要结合剪枝算法降低复杂度。该方法中使用begin变量标记下一次遍历的开始元素，即剪枝的思想，避免重复遍历。题解中提到了另一种方法使用used数组记录使用过的数字，其区别在于：
40. 组合总和
和上一题的区别时每个数字在每个组合只能使用一次，更改begin位置并增加重复组合的判决语句即可。对于重复组合的判决思路如下：在同一层节点中只保留同样的数一次。
class Solution:
def combinationSum2(self, candidates, target):
def dfs(candidates, begin, size, path, res, target):
# begin存储遍历起点，避免重复遍历
if target == 0: # 当target等于抽取元素和的时候，在res中保存结果
res.append(path)
return
for index in range(begin, size):
residue = target - candidates[index]
if residue < 0:
break
if index > begin and candidates[index] == candidates[index-1]:
continue
dfs(candidates, index+1, size, path + [candidates[index]], res, residue)
size = len(candidates) # 决定树的宽度
if size == 0:
return []
candidates.sort()
path = [] # 存储单条路经
res = [] # 存储所有满足要求的路径
dfs(candidates, 0, size, path, res, target)
return res
45. 跳跃游戏
class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)-1
def dfs(nums, now, path, res):
if now > n:
return
if now == n: # 到达终点
res.append(path)
return
for step in range(1, nums[now]+1):
dfs(nums, now + step, path + [now + step], res)
path = [0] # 存储单条路经
res = [] # 存储所有满足要求的路径
dfs(nums, 0, path, res)
minjump = min(len(s) for s in res) - 1
return minjump利用穷举法，会超出时间限制。
采用贪心算法，假设每次走最远距离nums[i]，在最远距离中间节点(i+1, ...... , i+nums[i])检验第二步距离是否比最远距离nums[i]的第二步距离更远：
class Solution(object):
def jump(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)-1
i = 0
count = 0
while i <= n:
if i == n :
return count
if i + nums[i] < n:
maxrange = i + nums[i] + nums[i + nums[i]]
tmp = nums[i]
for step in range(1, nums[i]+1):
twostep = i + step + nums[i+step]
if twostep > maxrange:
maxrange = twostep
tmp = step
i += tmp
count += 1
else:
count += 1
return count46. 全排列
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
size = len(nums)
n = size
for i in range(1, size):
n *= i
def dfs(nums, used, path, res):
if len(res) == n:
return
if len(path) == size:
res.append(path)
return
for index in range(size):
if index not in used:
used.append(index)
dfs(nums, used, path + [nums[index]], res)
used.pop()
path = []
res = []
used = []
dfs(nums, used, path, res)
return res采用之前提到的用used存储已经在path里的元素的方法。
官方题解：
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
# first表示从左往右填完第first个位置
def dfs(first = 0):
if first == n: # 一组path填完
res.append(nums[:]) # 如果不加[:]，res里的结果会随着nums变化
# 将nums划分为左右两个部分，左边已填右边未填，回溯时动态维护nums
for i in range(first, n):
nums[first], nums[i] = nums[i], nums[first]
dfs(first + 1)
nums[first], nums[i] = nums[i], nums[first]
# 回溯结束后交换回来
n = len(nums)
res = []
dfs()
return res47. 全排列（含重复元素）
懒蛋判定法：
if nums[:] not in res:
res.append(nums[:])或者：
for i in range(first, n):
if i != first and nums[i] == nums[first]:
continue
nums[first], nums[i] = nums[i], nums[first]
dfs(first + 1)
nums[first], nums[i] = nums[i], nums[first]题解里看到的一种解法：
class Solution:
def permuteUnique(self, nums):
nums.sort()
self.res = []
used = [0 for _ in range(len(nums))]
self.backtrack([], nums, used)
return self.res
def backtrack(self, path, nums, used):
if len(path) == len(nums):
self.res.append(path)
return
for i in range(len(nums)):
if used[i] == 1:
continue
if i > 0 and nums[i] == nums[i - 1] and used[i - 1] == 0:
continue
used[i] = 1
self.backtrack(path + [nums[i]], nums, used)
used[i] = 0引入一个长度和nums一致的全0列表标记nums中的元素是否出现过，采用这种思路改进一下第一种方案，效果类似，看来使用列表标记是否出现可以降低耗时：
class Solution:
def permuteUnique(self, nums):
def dfs(nums, used, path, res):
if len(path) == size:
res.append(path)
return
for index in range(size):
if used[index] == 1:
continue
if index > 0 and nums[index] == nums[index-1] and used[index-1] == 0:
continue
used[index] = 1
dfs(nums, used, path + [nums[index]], res)
used[index] = 0
size = len(nums)
path = []
res = []
used = [0 for _ in range(size)]
nums.sort()
dfs(nums, used, path, res)
return res48. 旋转图像
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
for i in range(n // 2):
for j in range(n):
matrix[i][j], matrix[n-i-1][j] = matrix[n-i-1][j], matrix[i][j]
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
return matrix54. 螺旋矩阵
class Solution(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
n_row = len(matrix)
n_col = len(matrix[0])
tmp = [[0 for _ in range(n_col)] for _ in range(n_row)]
li = [matrix[0][0]]
now_row = 0
now_col = 0
tmp[now_row][now_col] = 1
while len(li) < n_row * n_col:
if now_col < n_col-1:
if tmp[now_row][now_col+1] == 0 and (now_row == 0 or tmp[now_row-1][now_col] != 0): # 向右遍历
now_col += 1
tmp[now_row][now_col] = 1
li.append(matrix[now_row][now_col])
continue
if now_row < n_row-1:
if tmp[now_row+1][now_col] == 0 and (now_col == n_col-1 or tmp[now_row][now_col+1] != 0): # 向下遍历
now_row += 1
tmp[now_row][now_col] = 1
li.append(matrix[now_row][now_col])
continue
if now_col > 0:
if tmp[now_row][now_col-1] == 0 and (now_row == n_row-1 or tmp[now_row+1][now_col] != 0): # 向左遍历
now_col -= 1
tmp[now_row][now_col] = 1
li.append(matrix[now_row][now_col])
continue
if now_row > 0:
if tmp[now_row-1][now_col] == 0 and (now_col == 0 or tmp[now_row][now_col-1] != 0): # 向上遍历
now_row -= 1
tmp[now_row][now_col] = 1
li.append(matrix[now_row][now_col])
continue
return li官方题解的写法更加简单，把上下左右存储在directions中不需要分开写：
class Solution(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if not matrix or not matrix[0]:
return list()
n_row, n_col = len(matrix), len(matrix[0])
tmp = [[False] * n_col for _ in range(n_row)]
total = n_row * n_col
li = [0] * total
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]] # 右，下，左，上
now_row, now_col = 0, 0
directionIndex = 0
for i in range(total):
li[i] = matrix[now_row][now_col]
tmp[now_row][now_col] = True
nextRow, nextColumn = now_row + directions[directionIndex][0], now_col + directions[directionIndex][1]
if not (0 <= nextRow < n_row and 0 <= nextColumn < n_col and not tmp[nextRow][nextColumn]):
# 如果[nextRow][nextColumn]不在界内，或者[nextRow][nextColumn]已经遍历过，转向
directionIndex = (directionIndex + 1) % 4
now_row += directions[directionIndex][0]
now_col += directions[directionIndex][1]
return li55. 跳跃游戏
维护一个“最远可以到达的位置”，对于一个可到达的位置x，在x+1，......，x+nums[i]范围内都是可到达的位置，当“最远可以到达的位置”大于等于数组最后一个位置，则返回True。
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
n = len(nums)
maxrange = 0
for i in range(n):
if i <= maxrange:
maxrange = max(maxrange, i+nums[i])
if maxrange >= n-1:
return True
return False56. 合并区间
class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: List[List[int]]
"""
def compare(a):
return a[0]
intervals.sort(key=compare)
n = len(intervals)
index = 1
while index < n:
if intervals[index-1][1] >= intervals[index][0]:
tmp = [intervals[index-1][0], max(intervals[index-1][1], intervals[index][1])]
intervals.pop(index)
intervals.pop(index-1)
intervals.insert(index-1, tmp)
n -= 1
else:
index += 1
return intervals使列表按照每个元素的第一位排列的方法：
或者：
intervals.sort(key=lambda x: x[0])
57. 插入区间
class Solution(object):
def insert(self, intervals, newInterval):
"""
:type intervals: List[List[int]]
:type newInterval: List[int]
:rtype: List[List[int]]
"""
left, right = newInterval
placed = False
ans = []
for li, ri in intervals:
if li > right:
# 在插入区间右侧且无交集
if not placed:
ans.append([left, right])
placed = True
ans.append([li, ri])
elif ri < left:
# 在插入区间左侧且无交集
ans.append([li, ri])
else:
# 与插入区间有交集
left = min(left, li)
right = max(right, ri)
if not placed:
ans.append([left, right])
return ans56. 57.的思路：
59. 螺旋矩阵
相当于螺旋排列的转化为顺序输出
class Solution(object):
def generateMatrix(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
li = [[0 for _ in range(n)] for _ in range(n)]
now_row = 0
now_col = 0
for i in range(1, n**2 + 1):
li[now_row][now_col] = i
if now_col < n-1 and (now_row == 0 or li[now_row-1][now_col] != 0): # 右
if li[now_row][now_col+1] == 0:
now_col += 1
continue
if now_row < n-1 and (now_col == n-1 or li[now_row][now_col+1] != 0): # 下
if li[now_row+1][now_col] == 0:
now_row += 1
continue
if now_col > 0 and (now_row == n-1 or li[now_row+1][now_col] != 0): # 左
if li[now_row][now_col-1] == 0:
now_col -= 1
continue
if now_row > 0 and (now_col == 0 or li[now_row][now_col-1] != 0): # 上
if li[now_row-1][now_col] == 0:
now_row -= 1
continue
return li或者使用dirs存储方向：
class Solution(object):
def generateMatrix(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 右，下，左，上
li = [[0] * n for _ in range(n)]
now_row, now_col, dirIdx = 0, 0, 0
for i in range(n * n):
li[now_row][now_col] = i + 1
dx, dy = dirs[dirIdx]
next_row, next_col = now_row + dx, now_col + dy
if next_row < 0 or next_row >= n or next_col < 0 or next_col >= n or li[next_row][next_col] > 0:
dirIdx = (dirIdx + 1) % 4 # 顺时针旋转至下一个方向
dx, dy = dirs[dirIdx]
now_row, now_col = now_row + dx, now_col + dy
return li63. 不同路径
动态规划的题目分为两大类：
1. 求最优解类，典型问题是背包问题；
2. 计数类，比如这里的统计方案数的问题。
它们都存在一定的递推性质，前者的递推性质还有一个名字，叫做 「最优子结构」 ——即当前问题的最优解取决于子问题的最优解，后者类似，当前问题的方案数取决于子问题的方案数。所以在遇到求方案数的问题时，我们可以往动态规划的方向考虑。
由于机器人只能向下或向右移动，所以（0，0）到（i，j）的路径总数取决于（0，0）到（i-1，j）的路径总数与（0，0）到（i，j-1）的路径总数，综上所述得到动态规划转移方程：
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
n_row, n_col = len(obstacleGrid), len(obstacleGrid[0])
def dfs(i, j, count):
if obstacleGrid[i][j] == 1:
return 0
if i == j == 0:
count = 1
return count
if i == 0 and j != 0:
return dfs(i, j-1, count)
elif j == 0 and i != 0:
return dfs(i-1, j, count)
elif i != 0 and j != 0:
return dfs(i-1, j, count) + dfs(i, j-1, count)
count = 0
num = dfs(n_row-1, n_col-1, count)
return num这种属于自底向上的递归方法（从终点推回起点），从结果倒推会产生大量的重复计算，因此会超出时间限制。
对自底向上递归方法的改进：增加字典d作为缓存避免重复计算：
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
n_row, n_col = len(obstacleGrid), len(obstacleGrid[0])
d = {} # 设置一个字典存储路径数
# dfs返回(i,j)到终点的路径数
def dfs(i, j):
if (i, j) in d: # (i,j)为键，这种方法只能判断键是否在字典中
return d[(i, j)] # 返回键(i,j)对应的值
if i >= n_row or j >= n_col or obstacleGrid[i][j] == 1:
return 0
if i == n_row-1 and j == n_col-1:
return 1
d[(i,j)] = dfs(i+1, j) + dfs(i, j+1)
return d[i,j]
return dfs(0,0)还可以与空间优化相结合，利用滚动数组可以把二维数组改为一维数组，一维数组的大小为列的长度（列数）。由于每次更新时只需要上面一排的数据不需要上上排的数据，因此可以进行空间优化。
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
n_row, n_col = len(obstacleGrid), len(obstacleGrid[0])
dp = [0 for _ in range(n_col)]
dp[0] = 1 if obstacleGrid[0][0] == 0 else 0
for i in range(n_row):
for j in range(n_col):
if obstacleGrid[i][j] == 1:
dp[j] = 0
elif obstacleGrid[i][j] == 0 and j-1 >= 0:
dp[j] += dp[j-1]
return dp[-1]在二维数组中改写为自顶向下的递归（即将dfs()的结果值存放到一个二维数组dp中，先填充左边一列和上边一排，根据左边和上边的路径数推导中间的路径数，也就是从起点向终点推）：
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
n_row, n_col = len(obstacleGrid), len(obstacleGrid[0])
dp = [[0 for _ in range(n_col)] for _ in range(n_row)]
if obstacleGrid[0][0] == 0:
dp[0][0] = 1
else:
return 0
for i in range(1, n_row): # 如果没有障碍物，到最左一列路径均为1
if obstacleGrid[i][0] == 0 and dp[i-1][0] != 0:
dp[i][0] = 1
else:
dp[i][0] = 0
for j in range(1, n_col): # 如果没有障碍物，到最上一排路径均为1
if obstacleGrid[0][j] == 0 and dp[0][j-1] != 0:
dp[0][j] = 1
else:
dp[0][j] = 0
if dp[n_row-1][n_col-1]:
return dp[n_row-1][n_col-1]
for i in range(1, n_row):
for j in range(1, n_col):
if obstacleGrid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[n_row-1][n_col-1]64. 最小路径和
自顶向下
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
n_row, n_col = len(grid), len(grid[0])
dp = [[0 for _ in range(n_col)] for _ in range(n_row)]
dp[0][0] = grid[0][0]
for i in range(1, n_row):
dp[i][0] = dp[i-1][0] + grid[i][0]
for j in range(1, n_col):
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, n_row):
for j in range(1, n_col):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[n_row-1][n_col-1]73. 矩阵置零
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
n_row , n_col = len(matrix), len(matrix[0])
row = []
col = []
for i in range(n_row):
for j in range(n_col):
if matrix[i][j] == 0:
row.append(i)
col.append(j)
for val in row:
for j in range(n_col):
matrix[val][j] = 0
for val in col:
for i in range(n_row):
matrix[i][val] = 0
return matrix官方题解：可以用一个列表标记原来的第一列是否有0，遍历剩下的数，如果遇到0把该行第一个数置零、该列第一个数置零，需要更少的额外空间。
74. 搜索二维矩阵
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
n_row, n_col = len(matrix), len(matrix[0])
if matrix[0][0] > target or matrix[n_row-1][n_col-1] < target:
return False
if n_row == 1:
i = 0
else:
for i in range(n_row): # 在第i行
if i == n_row-1 and matrix[i][0] <= target:
break
if matrix[i][0] <= target and matrix[i+1][0] > target:
break
for j in range(n_col):
if matrix[i][j] == target:
return True
return False或者采用二分查找降低时间复杂度，二维列表转换为一维列表：
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
n_row, n_col = len(matrix), len(matrix[0])
li = []
for val in matrix:
li.extend(val)
left = 0
right = n_row * n_col - 1
while left < right:
mid = (left + right) // 2
if left == mid or right == mid:
break
if li[mid] == target:
return True
elif li[mid] > target:
right = mid - 1
else:
left = mid + 1
if li[left] != target and li[right] != target:
return False
else:
return True75. 颜色分类
class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
n = len(nums)
mark0, mark1 = 0, 0
for i in range(n):
if nums[i] == 0:
nums[i], nums[mark0] = nums[mark0], nums[i]
if mark0 < mark1:
# 如果此时有排列好的1，即mark0 < mark1，把0交换到前面的过程中会把1放到后面，所以要放回来
nums[i], nums[mark1] = nums[mark1], nums[i]
mark0 += 1
mark1 += 1
elif nums[i] == 1:
nums[i], nums[mark1] = nums[mark1], nums[i]
mark1 += 1
return nums77. 组合
class Solution(object):
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
path = []
res = []
total = 1
for i in range(n-k+1, n+1):
total *= i
for i in range(1, k+1):
total /= i
def choose(n, k, begin, path, res):
if len(path) == k:
res.append(path)
return
if len(res) == total:
return
for index in range(begin, n+1):
choose(n, k, index+1, path+[index], res)
choose(n, k, 1, path, res)
return res78. 子集
区别于之前用回溯算法解的题，这题的终止条件是对于每个叶节点来说的。
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
n = len(nums)
# def countTotal(n, k):
# total = 1
# for i in range(n - k + 1, n + 1):
# total *= i
# for j in range(1, k + 1):
# total /= j
# return int(total)
#
# totalpath = 1 # 子集为空集时有一个
# for index in range(1, n + 1):
# totalpath += countTotal(n, index)
def choose(nums, begin, path, res):
res.append(path)
# if len(res) == totalpath:
# return
for element_i in range(begin, n):
choose(nums, element_i+1, path+[nums[element_i]], res)
path = []
res = []
choose(nums, 0, path, res)
return res之前为了写出一个终止条件计算子集数量，后来发现没有终止条件也可以正常运行，choose函数里的for循环运行完就自动跳出了。
题解中一种极简的迭代写法：
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = [[]]
for i in nums:
res = res + [[i] + num for num in res]
return res或者使用库函数：
import itertools
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
for i in range(len(nums) + 1):
for tmp in itertools.combinations(nums, i):
res.append(tmp)
return res79. 单词搜索
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 从board的(i,j)位置出发是否能搜索到单词，k代表word从第k个字符开始的后缀子串
def check(nowIndex_row, nowIndex_col, begin):
if board[nowIndex_row][nowIndex_col] != word[begin]: # 判断首字母是否匹配
return False
if begin == len(word) - 1: # 判断到最后一个返回True
return True
visited.add((nowIndex_row, nowIndex_col)) # 存储走过的路径
result = False
for dx, dy in directions:
nextIndex_row, nextIndex_col = nowIndex_row + dx, nowIndex_col + dy
if 0 <= nextIndex_row < len(board) and 0 <= nextIndex_col < len(board[0])
and (nextIndex_row, nextIndex_col) not in visited:
if check(nextIndex_row, nextIndex_col, begin + 1):
result = True
break
# 如果没有return True说明这条路径是不对的，返回上一层
visited.remove((nowIndex_row, nowIndex_col))
return result
n_row, n_col = len(board), len(board[0])
visited = set()
for i in range(n_row):
for j in range(n_col):
if check(i, j, 0):
return True
return False用check函数检验board每一个位置开始是否能够检索到word，检索到直接return true，如果遍历完所有位置没有return true说明检索不到，return false。
80. 删除有序数组中的重复项
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
i = 2
while i < n:
if nums[i] == nums[i-1] == nums[i-2]:
nums.pop(i)
i -= 1
n -= 1
i += 1
return len(nums)官方题解中定义i为慢指针，标记处理过的数组长度，n为快指针，标记数组总长度。
81. 搜索旋转排序数组
90. 子集
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = [[]]
nums.sort()
for i in range(len(nums)):
if i == 0 or (i > 0 and nums[i] != nums[i-1]):
li = [[nums[i]] + num for num in res]
res = res + [[nums[i]] + num for num in res]
else:
res = res + [[nums[i]] + num for num in li]
li = [[nums[i]] + num for num in li]
return res或者使用回溯的方法：
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = [] # 存放符合条件结果的集合
path = [] # 用来存放符合条件结果
def backtrack(nums,startIndex):
res.append(path[:])
for i in range(startIndex,len(nums)):
if i > startIndex and nums[i] == nums[i - 1]:
# 我们要对同一树层使用过的元素进行跳过
continue
path.append(nums[i])
backtrack(nums,i+1) # 递归
path.pop() # 回溯
nums.sort() # 去重需要排序
backtrack(nums,0)
return res最后
以上就是土豪板栗为你收集整理的leetcode-数组知识点（中等）11.盛最多水的容器15. 三数之和16. 最接近的三数之和18. 四数之和31. 下一个排列33. 搜索旋转排序数组34. 在排列数组中查找元素的第一个和最后一个位置36. 有效的数独39. 组合总和 40. 组合总和45. 跳跃游戏 46. 全排列47. 全排列（含重复元素）48. 旋转图像54. 螺旋矩阵55. 跳跃游戏 56. 合并区间57. 插入区间 59. 螺旋矩阵63. 不同路径64. 最小路径和73. 矩阵置零74. 搜索二维矩阵75. 颜色分的全部内容，希望文章能够帮你解决leetcode-数组知识点（中等）11.盛最多水的容器15. 三数之和16. 最接近的三数之和18. 四数之和31. 下一个排列33. 搜索旋转排序数组34. 在排列数组中查找元素的第一个和最后一个位置36. 有效的数独39. 组合总和 40. 组合总和45. 跳跃游戏 46. 全排列47. 全排列（含重复元素）48. 旋转图像54. 螺旋矩阵55. 跳跃游戏 56. 合并区间57. 插入区间 59. 螺旋矩阵63. 不同路径64. 最小路径和73. 矩阵置零74. 搜索二维矩阵75. 颜色分所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复