根据数据结构和算法的分类来进行刷题，有时候会有一种被剧透了的感觉，思考方向会不自觉靠着对应算法上去想。如果出现一道没有见过的题目，有时候很难想到对应的解法，通过一些关键词的常见套路，可以很快找到解题思路。
一、看数据范围大小
通过提供的数据范围大小可以大致判断出所需算法的时间复杂度
数据范围对应的时间复杂度
时间复杂度对应的算法
时间复杂度
二、数据结构
看处理对象的数据结构，比较常见的有：一维数组，二维数组，字符串，二叉树
1. 一维数组
根据我个人的做题经验，将数组问题大致划分为以下几个方向：数组有序，数组无序，子数组问题，子序列问题，多个数组问题。
数组有序
如果题目没有要求保留原来顺序的，都可以将数组进行排序。
a. 数组有序/有单调性
如果数组本身具有单调性，需要寻找的是数组中的某个值，可以考虑二分搜索。
33 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
虽然数组在某处进行了旋转，但依旧是部分有序的，仍然可以使用二分搜索。将数组分为左右两部分时可以发现，必定有一部分是有序，根据有序的部分可以判断上下界的迭代。
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
if nums[0] <= nums[mid]:
if nums[0] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
else:
if nums[mid] < target <= nums[len(nums) - 1]:
l = mid + 1
else:
r = mid - 1
return -1
4 寻找两个正序数组的中位数（归并+二分）
81 搜索旋转排序数组 II
153 寻找旋转排序数组中的最小值
378 有序矩阵中第 K 小的元素
如果数组本身已经排序，并且需要找出两个数字，那么可以使用双指针。
167 两数之和 II - 输入有序数组
b. 求解过程中存在单调性
在按照题目的描述一步步求解的过程中，如果发现搜索目标解的过程中，搜索过的值单调递增或者递减，可以通过维护单调栈来实现。要意识到这一点需要根据题目要求，将求解过程模拟出来。
42 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
首先思考什么样的柱子才能接到雨水，必然是一个“洼地”。假设对一片“洼地”从左向右遍历，在到达最低点前，柱子的高度一定是递减的，因此可以使用单调栈来记录数据。如果遍历到的数字不满足递减关系了，说明到了“洼地”的另一侧，此时可以计算出能接到的雨水的增量。更加详细的动画演示可以参考力扣的题解。
def trap(self, height: List[int]) -> int:
n = len(height)
stack = []
ans = 0
for i in range(n):
curr = height[i]
while stack and curr>height[stack[-1]]:
last = stack.pop()
while stack and height[stack[-1]]==height[last]:
stack.pop()
if stack:
h= min(height[stack[-1]], curr)-height[last]
ans += h*(i-stack[-1]-1)
stack.append(i)
return ans
c. 求解结果有序
对于前 k 大或前 k 小这类问题，有一个通用的解法：优先队列。优先队列可以在O(logn) 的时间内完成插入或删除元素的操作（其中 n 为优先队列的大小），并可以 O(1)地查询优先队列顶端元素。
215 数组中的第K个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
使用一个小根堆，如果小根堆的大小小于K就向里面加数字，否则就弹出堆顶（K+1个数中最小的），最后堆顶就是第K大的元素。
def findKthLargest(self, nums: List[int], k: int) -> int:
n = len(nums)
heap = []
for i in range(n):
heapq.heappush(heap, nums[i])
if len(heap)>k:
heapq.heappop(heap)
return heap[0]
数组无序
a. 存在对应关系
如果在数组中存在对应关系，可以通过哈希表存储关键字，减少计算，提高代码效率。这里的对应关系可以是一个数学关系，或者是某种映射关系，比如数组索引与对应数字的关系，与频数相关的题目也经常会用哈希表。
1两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
数组中的元素存在着对应关系：nums[i] = target - nums[j], nums[i] 与索引 i。
可以以nums[i]为key，以索引i为value，对于每一个值nums[i]，寻找target - nums[j]是否存在于哈希表内。
def twoSum(self, nums: List[int], target: int) -> List[int]:
table = {}
for i in range(len(nums)):
if target-nums[i] in table:
return [table[target-nums[i]],i]
table[nums[i]] = i
return []
454四数相加II
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
可以将这个四数相加的问题转化为两数相加的问题，将A,B,C,D分为两组，分别为A,B相加的所有可能结果和C,D相加的所有可能结果，要寻找的是满足 A[i] + B[j] = - C[k] - D[l]的元组的个数。
以A[i] + B[j]的值为key，以出现次数为value建立哈希表，在C,D中寻找满足A[i] + B[j] = - C[k] - D[l]的索引，并计算出现次数。
def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
n = len(A)
ans = 0
group1 = collections.defaultdict(int)
for i in range(n):
for j in range(n):
group1[A[i]+B[j]]+=1
for i in range(n):
for j in range(n):
tmp = C[i]+D[j]
if -tmp in group1:
ans += group1[-tmp]
return ans
其他用到了哈希表的题目：
30 串联所有单词的子串
138 复制带随机指针的链表
146 LRU缓存机制
b. 需要同时维护两个值
如果求解过程中需要同时维护两个变量，可以考虑双指针。如果暴力的解法需要用到多重循环枚举，并且在枚举时发现枚举元素间保持着某种关系，比如随着第一个元素增加，第二个元素是递减的（三数之和），就可以使用双指针的方法，将时间复杂度从减少到
。
11 盛最多水的容器
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
盛水需要左右两个边同时存在，并且左右两边中较小的那个决定了水位的高度，左右两边的间隔决定了容器的长度，可以使用左右两个指针来分别指向左右两边。
寻找盛水最多的容器需要遍历容器的长度和水位的高度，长度可以通过移动左右指针来实现。水位高度是由最短边决定的，因此无论长边如何移动，得到的水位高度都会等于或者小于短边的高度，因此每一次迭代，需要移动短的一边。
def maxArea(self, height: List[int]) -> int:
maxare = 0
left = 0
right = len(height) -1
while left <right:
distance = right-left
maxare = max(maxare, min(height[left],height[right])*(distance))
if height[left] <height[right]:
left += 1
else:
right -=1
return maxare
c. 左右各遍历一次
比较有技巧性的方法，从左向右遍历一次数组，再从右向左遍历一次数组，应用场景与双指针相似，但是不太容易想到。当要求解的是最大最小的问题，比如距离最近的最大是多少，有可能用到这种技巧。
581. 最短无序连续子数组
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组，并输出它的长度。
根据题意需要找到的是，数组中需要排序的最短子数组的边界。对于一个已经排好序的数组，从左到右遍历到的最大值应该等于当前值，从右到左遍历到的最小值，应该也是当前值；否则就说明当前遍历到的数字为乱序。从左到右遍历和从右到左遍历分别记录下需要排序的子数组的起始和终止位置。
def search(arr,n):
if n<2:
return 0
leftMax, leftId = float('-inf'), -1
rightMin, rightId = float('inf'),-1
for i in range(n):
if arr[i]>=leftMax:
leftMax = arr[i]
else:
leftId = i # index of num smaller than the leftMax
if leftId ==-1:
return 0
for i in range(n-1,-1,-1):
if arr[i]<=rightMin:
rightMin = arr[i]
else:
rightId = i
return leftId-rightId+1
网易校招笔试-电影院选座
疫情逐步缓和后，电影院终于开业了，但是由于当前仍处于疫情期间，应尽量保持人群不聚集的原则。所以当小易来电影院选定一排后，尽量需要选择一个远离人群的位置。已知由0和1组成的数组表示当前排的座位情况,其中1表示已被选座，0表示空座请问小易所选座位和最近人的距离座位数最大是多少？有如下假设：至少有一个人已选座，至少有一个空座位，且座位数限制为[2,1000]。
从左到右遍历一次，从右到左遍历一次，分别计算坐在位置i的适合，距离左边第一个1的距离和距离右边第一个的距离，取每个位置上左右距离中最小的那个，然后取其中的最大值。
参考：
Leetbook-2021 春招冲刺攻略
程序员代码面试指南
网友评论