一、数组经典题型

• * 前言
• 1、元素查找 (暴力解法、二分查找)
• • 35.搜索插入位置
  • 34.在排序数组中查找元素的第一个和最后一个位置
  • 69.x的平方根
  • 367.有效的完全平方数
  • 875.爱吃香蕉的珂珂
• 2、元素移除 (暴力解法、双指针法)
• • 26.删除有序数组中的重复项
  • 283.移动零
  • 844.比较含退格的字符串
  • 977.有序数组的平方
• 3、长度最小的子数组(暴力解法、滑动窗口)
• • 904.水果成篮
  • 76.最小覆盖子串
  • 239.滑动窗口最大值
• 4、过程模拟 (无算法，逻辑思维理解)
• • 54.螺旋矩阵
  • 剑指Offer29.顺时针打印矩阵
• 参考

* 前言

后续题目基于基础算法部分，请参考：算法刷题总结 (一) 数组

1、元素查找 (暴力解法、二分查找)

35.搜索插入位置

leetcode链接

(1). 暴力解法，遍历列表：

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:# 分别处理如下三种情况# 目标值在数组所有元素之前# 目标值等于数组中某一个元素# 目标值插入数组中的位置for i in range(len(nums)):# 一旦发现大于或者等于target的num[i]，那么i就是我们要的结果if nums[i]>=target:return i# 目标值在数组所有元素之后的情况# 如果target是最大的，或者 nums为空，则返回nums的长度return len(nums)

(2). 二分法，二分列表：

class Solution:def searchInsert(self, nums: List[int], target: int) -> int:# 分别处理如下四种情况# 目标值在数组所有元素之前 [0, -1]# 目标值等于数组中某一个元素 return middle;# 目标值插入数组中的位置 [left, right]，return right + 1# 目标值在数组所有元素之后的情况 [left, right]， 因为是右闭区间，所以 return right + 1# 1. 使用二分法快速查找(比遍历快)，如果能找到target，返回索引left, right = 0, len(nums)-1 # 定义target在左闭右闭的区间里，[left, right]while left<=right:mid = (left+right)//2if nums[mid]>target:# target 在左区间，所以[left, middle - 1]right = mid-1elif nums[mid]<target:# target 在右区间，所以[middle + 1, right]left = mid +1else:return mid# 2. 如果找不到# 返回right+1 或者 返回 leftreturn left

一个简单的中间过程

nums = [1,2,5,8,10] target = 9 searchInsert(nums, target) """ [left, right]: [0, 4] [left, right]: [3, 4] [left, right]: [4, 4] [left, right]: [4, 3] # 交叉退出 """

暴力与二分法的区别在于暴力是遍历列表，而二分法是二分查找，速度相对快。

34.在排序数组中查找元素的第一个和最后一个位置

leetcode链接

(1). 暴力法：

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:if target in nums:start = nums.index(target)end = len(nums)-(nums[::-1].index(target)+1)return [start, end]return [-1, -1]

(2). 二分法：

""" 寻找target在数组里的左右边界，有如下三种情况：情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1} 情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1} 情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1} """ class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:# 二分查找，寻找target的右边界（不包括target）# 如果rightBorder为没有被赋值（即target在数组范围的左边，例如数组[3,3]，target为2），为了处理情况一def getRightBorder(nums:List[int], target:int) -> int:# 定义target在左闭右闭的区间里，[left, right] left, right = 0, len(nums)-1# 记录一下rightBorder没有被赋值的情况rightBoder = -2 # 当left==right，区间[left, right]依然有效while left <= right:middle = left + (right-left) // 2if nums[middle] > target:right = middle - 1# 当nums[middle] == target的时候，更新left，这样才能得到target的右边界# 寻找右边界，nums[middle] == target的时候更新leftelse: left = middle + 1rightBoder = leftreturn rightBoderdef getLeftBorder(nums:List[int], target:int) -> int:left, right = 0, len(nums)-1 leftBoder = -2 # 记录一下leftBorder没有被赋值的情况while left <= right:middle = left + (right-left) // 2if nums[middle] >= target: # 寻找左边界，nums[middle] == target的时候更新rightright = middle - 1;leftBoder = right;else:left = middle + 1return leftBoderleftBoder = getLeftBorder(nums, target)rightBoder = getRightBorder(nums, target)# 情况一if leftBoder == -2 or rightBoder == -2: return [-1, -1]# 情况三if rightBoder -leftBoder >1: return [leftBoder + 1, rightBoder - 1]# 情况二return [-1, -1]

69.x的平方根

leetcode链接

二分法：

class Solution:def mySqrt(self, x: int) -> int:left, right, ans = 0, x, -1# 遍历整数的平方，最大的小于x的值就是结果while left<=right:# 不断找中值分界点mid = (left+right)//2# 不断将结果存起来，最后更新保存的结果为最大值if mid*mid<=x:ans = midleft = mid + 1# 缩减大的值else:right = mid - 1return ans

此题还有牛顿迭代法解，只是套用一个公式。

367.有效的完全平方数

leetcode链接

二分法：

class Solution:def isPerfectSquare(self, num: int) -> bool:left, right, ans = 0, num, Falsewhile left<=right:mid = (left+right)//2if mid*mid<num:left = mid+1elif mid*mid>num:right = mid-1else:ans=Truereturn ansreturn ans

875.爱吃香蕉的珂珂

leetcode链接

暴力解法（超时）:

class Solution:def minEatingSpeed(self, piles: List[int], h: int) -> int:# 最慢一次吃一根，最快按最大值去吃每棵树，时间为树的个数# 遍历，寻找某个最小速度，使时间刚好为hfor i in range(1, max(piles)+1):nums = 0# 遍历树for j in piles:# 累加每棵树的次数nums = nums + math.ceil(j/i)# 第一次累计到h，就为吃的最慢，并且在警卫来之前走# 后面存在时间还为h，但是速度稍微快一些的情况，这个就不符合题意了if h==nums:return i

双指针法：
接着上一个代码进行修改，因为是遍历查找，所以可以使用快速查找的算法，二分法。

class Solution:def minEatingSpeed(self, piles: List[int], h: int) -> int:# 最慢一次吃一根，最快按最大值去吃每棵树，时间为树的个数# 遍历，寻找某个最小速度，使时间刚好为hleft, right = 1, max(piles)while left<=right:# 代替循环 for i in range(1, max(piles)+1):直接选取中点为速度mid = (left+right)//2# 累积时间nums = 0# 遍历树for j in piles:# 累加每棵树的次数nums = nums + math.ceil(j/mid)# 时间花的过多，增加速度,if nums>h:left = mid+1else:right = mid-1# 最后的mid与h可能不相等，不能为判断条件return left

注意这个例子：
piles,h = [312884470], 312884469
v只能取2，但是取2后，时间最多只能为156442235，不可能等于h，因为若等于1则又超时。
那么，二分法的条件判断，不能以nums==h为条件，最后倒数第二步为left=right=1，nums<h(156442235<312884469)，这时left = mid+1=2，此时left>right(2>1)，交错，输出2为正确结果。

2、元素移除 (暴力解法、双指针法)

26.删除有序数组中的重复项

leetcode链接
注意：当删除单个重复元素时，list可以无序，而删除多个重复元素时，保持相似的算法步骤则需要list有序，(这道题也指明了有序)，否则需要较多的更改逻辑结构，比如下面(2)中的第二个解法。

(1). 暴力遍历：

class Solution:def removeDuplicates(self, nums: List[int]) -> int:# 选取所有不重复，待遍历的元素for i in set(nums):# 设置计数器，方便后续大于1则删除count = 0# 遍历新创建的列表，防止删除原列表造成索引位移for j in nums[:]:# 重复则+1if i==j:count+=1# 多于一次重复则删除，否则不管if count>1:nums.remove(i)return len(nums)

(2). 快慢指针：

class Solution:def removeDuplicates(self, nums: List[int]) -> int:fast = 0slow = 0while fast<len(nums):if nums[fast] != nums[slow]:# 下一个索引赋值给新的不重复的值slow+=1nums[slow] = nums[fast]fast+=1# 这里要+1，表示下一位，即表示数组有效长度。# 因为原快慢指针算法，上面slow+1是在赋值之后，而这里是在赋值之前。return slow+1

第二个解法，可以删除无序list的重复元素，但较多的修改了原算法：

class Solution:def removeDuplicates(self, nums: List[int]) -> int:fast = 0# 从1开始，因为nums[:0]为空，慢指针这相当于取了域值，而不是前面的单个值slow = 1while fast<len(nums):# 这里取nums的slow索引之前的所有值进行重复元素的排查if nums[fast] not in nums[:slow]:# 相当于slow的阈值扩展nums[slow] = nums[fast]# 指向下一个待扩展进阈值的索引slow+=1fast+=1return slow

283.移动零

leetcode链接
(1). 暴力遍历：

class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""for i in nums[:]:# 查询到0就删除原表的0，结尾添加0if i==0:nums.remove(0)nums.append(0)

(2). 快慢指针：
先快慢指针把非零的选出来，再根据slow的长度将list后续非有效部分变成0

class Solution:def moveZeroes(self, nums: List[int]) -> None:fast = 0slow = 0while fast<len(nums):if nums[fast] != 0:nums[slow] = nums[fast]slow += 1fast+=1nums[slow:]=[0]*(len(nums)-slow)

每次遇到0就交换，把0换到fast的索引位置，把非0的值换到slow的位置，最后0都在结尾。有点类似冒泡。

class Solution:def moveZeroes(self, nums: List[int]) -> None:fast = 0slow = 0while fast<len(nums):if nums[fast] != 0:nums[slow], nums[fast] = nums[fast], nums[slow]slow += 1fast+=1

844.比较含退格的字符串

leetcode链接
(1). 重构字符串：

class Solution:def backspaceCompare(self, s: str, t: str) -> bool:def change(x):tmp = []for p in x:if p != '#':tmp.append(p)elif tmp:tmp.pop()return ''.join(tmp)return change(s) == change(t)

(2). 双指针：

class Solution:def backspaceCompare(self, S: str, T: str) -> bool:i, j = len(S) - 1, len(T) - 1skipS = skipT = 0while i >= 0 or j >= 0:while i >= 0:if S[i] == "#":skipS += 1i -= 1elif skipS > 0:skipS -= 1i -= 1else:breakwhile j >= 0:if T[j] == "#":skipT += 1j -= 1elif skipT > 0:skipT -= 1j -= 1else:breakif i >= 0 and j >= 0:if S[i] != T[j]:return Falseelif i >= 0 or j >= 0:return Falsei -= 1j -= 1return True

参考答案

977.有序数组的平方

leetcode链接
(1). 重构后排序：

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:nums = list(map(lambda x:x**2, nums))nums.sort()return nums

(2). 双指针法：
参考答案

3、长度最小的子数组(暴力解法、滑动窗口)

904.水果成篮

leetcode链接

(1). 暴力遍历：
算法同上，但会超时。

(2). 滑动窗口：
因为普通算法会超时，这里用Counter进行存储每次遍历的值。

def totalFruit(fruits):# ind表示起始点# s用来存储最大长度ind,s = 0,0# 使用Counter，累次计数，不然会超时d = Counter()# 开始遍历for i in range(len(fruits)):print('-------------------------------')# 计数d[fruits[i]]+= 1print(d)# 种类大于2则删除起始元素# 该被删除的元素有多少个数，起始点就后移多少位while len(d)>2:print('***1***')print('d1',d)print('dd',fruits[ind])# 起始点前移，减去起始点一次# 如果减到0则删除，避免占用一个种类d[fruits[ind]]-=1if d[fruits[ind]] == 0:del d[fruits[ind]]print('d2',d)# 起始点前移ind += 1print('***2***')# 选取原长度与处理后(删除或增加后)的长度的最大长度保留下来s = max(s, i-ind+1)print(s)return stest = [3,3,3,1,2,1,1,2,3,3,4] totalFruit(test)

结果打印：

------------------------------- Counter({3: 1}) 1 ------------------------------- Counter({3: 2}) 2 ------------------------------- Counter({3: 3}) 3 ------------------------------- Counter({3: 3, 1: 1}) 4 ------------------------------- Counter({3: 3, 1: 1, 2: 1}) ***1*** d1 Counter({3: 3, 1: 1, 2: 1}) dd 3 d2 Counter({3: 2, 1: 1, 2: 1}) ***2*** ***1*** d1 Counter({3: 2, 1: 1, 2: 1}) dd 3 d2 Counter({3: 1, 1: 1, 2: 1}) ***2*** ***1*** d1 Counter({3: 1, 1: 1, 2: 1}) dd 3 d2 Counter({1: 1, 2: 1}) ***2*** 4 ------------------------------- Counter({1: 2, 2: 1}) 4 ------------------------------- Counter({1: 3, 2: 1}) 4 ------------------------------- Counter({1: 3, 2: 2}) 5 ------------------------------- Counter({1: 3, 2: 2, 3: 1}) ***1*** d1 Counter({1: 3, 2: 2, 3: 1}) dd 1 d2 Counter({1: 2, 2: 2, 3: 1}) ***2*** ***1*** d1 Counter({1: 2, 2: 2, 3: 1}) dd 2 d2 Counter({1: 2, 2: 1, 3: 1}) ***2*** ***1*** d1 Counter({1: 2, 2: 1, 3: 1}) dd 1 d2 Counter({1: 1, 2: 1, 3: 1}) ***2*** ***1*** d1 Counter({1: 1, 2: 1, 3: 1}) dd 1 d2 Counter({2: 1, 3: 1}) ***2*** 5 ------------------------------- Counter({3: 2, 2: 1}) 5 ------------------------------- Counter({3: 2, 2: 1, 4: 1}) ***1*** d1 Counter({3: 2, 2: 1, 4: 1}) dd 2 d2 Counter({3: 2, 4: 1}) ***2*** 5 5

76.最小覆盖子串

leetcode链接

(1). 暴力遍历：
方法同上，但会超时

(2). 滑动窗口：
大致思路同上，但是这里需要加上flag进行判断，进入while循环，也就是起始点后移的的条件，因为字母会出现重复增删，flag只计算一次，d仍然需要计算每次改变。

def minWindow(s, t):ind,l = 0,'*'*len(s)+'*'# 动态改变d = Counter(t)# while判断flag = Counter(t)print('d:',d)# 遍历sfor i in range(len(s)):print('-------------------------')print('1l',l)# s出现在t中if s[i] in d:d[s[i]] -= 1# 为0则t中都出现过，小于0则出现的次数多于t# flag变为0，表示出现过if d[s[i]] <= 0:flag[s[i]]=0print('1d:',d)# 缩小窗口，前移起始索引print('******************')while sum(flag.values()) == 0:# 缩小前，保留值print('cmp:', l, s[ind:i+1])l = min(l, s[ind:i+1], key=len)# 如果删的是t中的字符，d中减去if s[ind] in d:d[s[ind]] +=1# 待出现的数量大于等于标准# flag变为1表示没出现if d[s[ind]]>0:flag[s[ind]]=1# 索引前移ind += 1print('******************')print('2l',l)print('2d:',d)print('ind, end', ind, i)return '' if l == '*'*len(s)+'*' else la="ADOBECODEBANC" b="ABC" # "BANC" minWindow(a,b)

结果过程展示：

d: Counter({'A': 1, 'B': 1, 'C': 1}) ------------------------- 1l ************** 1d: Counter({'B': 1, 'C': 1, 'A': 0}) ****************** ****************** 2l ************** 2d: Counter({'B': 1, 'C': 1, 'A': 0}) ind, end 0 0 ------------------------- 1l ************** 1d: Counter({'B': 1, 'C': 1, 'A': 0}) ****************** ****************** 2l ************** 2d: Counter({'B': 1, 'C': 1, 'A': 0}) ind, end 0 1 ------------------------- 1l ************** 1d: Counter({'B': 1, 'C': 1, 'A': 0}) ****************** ****************** 2l ************** 2d: Counter({'B': 1, 'C': 1, 'A': 0}) ind, end 0 2 ------------------------- 1l ************** 1d: Counter({'C': 1, 'A': 0, 'B': 0}) ****************** ****************** 2l ************** 2d: Counter({'C': 1, 'A': 0, 'B': 0}) ind, end 0 3 ------------------------- 1l ************** 1d: Counter({'C': 1, 'A': 0, 'B': 0}) ****************** ****************** 2l ************** 2d: Counter({'C': 1, 'A': 0, 'B': 0}) ind, end 0 4 ------------------------- 1l ************** 1d: Counter({'A': 0, 'B': 0, 'C': 0}) ****************** cmp: ************** ADOBEC ****************** 2l ADOBEC 2d: Counter({'A': 1, 'B': 0, 'C': 0}) ind, end 1 5 ------------------------- 1l ADOBEC 1d: Counter({'A': 1, 'B': 0, 'C': 0}) ****************** ****************** 2l ADOBEC 2d: Counter({'A': 1, 'B': 0, 'C': 0}) ind, end 1 6 ------------------------- 1l ADOBEC 1d: Counter({'A': 1, 'B': 0, 'C': 0}) ****************** ****************** 2l ADOBEC 2d: Counter({'A': 1, 'B': 0, 'C': 0}) ind, end 1 7 ------------------------- 1l ADOBEC 1d: Counter({'A': 1, 'B': 0, 'C': 0}) ****************** ****************** 2l ADOBEC 2d: Counter({'A': 1, 'B': 0, 'C': 0}) ind, end 1 8 ------------------------- 1l ADOBEC 1d: Counter({'A': 1, 'C': 0, 'B': -1}) ****************** ****************** 2l ADOBEC 2d: Counter({'A': 1, 'C': 0, 'B': -1}) ind, end 1 9 ------------------------- 1l ADOBEC 1d: Counter({'A': 0, 'C': 0, 'B': -1}) ****************** cmp: ADOBEC DOBECODEBA cmp: ADOBEC OBECODEBA cmp: ADOBEC BECODEBA cmp: ADOBEC ECODEBA cmp: ADOBEC CODEBA ****************** 2l ADOBEC 2d: Counter({'C': 1, 'A': 0, 'B': 0}) ind, end 6 10 ------------------------- 1l ADOBEC 1d: Counter({'C': 1, 'A': 0, 'B': 0}) ****************** ****************** 2l ADOBEC 2d: Counter({'C': 1, 'A': 0, 'B': 0}) ind, end 6 11 ------------------------- 1l ADOBEC 1d: Counter({'A': 0, 'B': 0, 'C': 0}) ****************** cmp: ADOBEC ODEBANC cmp: ADOBEC DEBANC cmp: ADOBEC EBANC cmp: EBANC BANC ****************** 2l BANC 2d: Counter({'B': 1, 'A': 0, 'C': 0}) ind, end 10 12 'BANC'

239.滑动窗口最大值

leetcode链接

滑动窗口

class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:n = len(nums)# 注意 Python 默认的优先队列是小根堆q = [(-nums[i], i) for i in range(k)]# 将列表转化为堆heapq.heapify(q)# 最大值为堆顶ans = [-q[0][0]]for i in range(k, n):# 插入一个值以及索引heapq.heappush(q, (-nums[i], i))# 不用每次删除窗口外的值，而是当最大值在窗口外再进行删除# 判断堆顶是否在窗口外while q[0][1] <= i - k:# 在窗口外则弹出heapq.heappop(q)# 每次存储堆顶为最大值ans.append(-q[0][0])return ans

4、过程模拟 (无算法，逻辑思维理解)

54.螺旋矩阵

leetcode链接

过程模拟：
套用螺旋矩阵二的模板：

class Solution:def spiralOrder(self, matrix: List[List[int]]) -> List[int]:# 存储遍历的值res = []# 长和宽length, width = len(matrix), len(matrix[0])# 上下左右走一圈的次数，最小边长整除2loop = min(length, width)//2# 起始点，用来定位遍历点startx, starty = 0, 0# 开始循环for offset in range(1,loop+1):# 从左到右，左闭右开for i in range(starty, width-offset):res.append(matrix[startx][i])# 从上到下，上闭下开for i in range(startx, length-offset):res.append(matrix[i][width-offset])# 从右到左，右闭左开for i in range(width-offset, starty, -1):res.append(matrix[length-offset][i])# 从下到上，下闭上开for i in range(length-offset, startx, -1):res.append(matrix[i][starty])# 起始点下移startx += 1starty += 1# 为正方形时，当为奇数，中间有一个点没被遍历到，手动添加，为中点if length == width and length%2!=0:res.append(matrix[length//2][length//2])# 为非长方形时else:# 短的边为奇数时，添加没被遍历到的点if width>length and length%2!=0:for i in range(width-length+1):res.append(matrix[length//2][i+loop])elif width<length and width%2!=0:for i in range(length-width+1):res.append(matrix[i+loop][width//2])return res

剑指Offer29.顺时针打印矩阵

leetcode链接

思路同上：

class Solution:def spiralOrder(self, matrix: List[List[int]]) -> List[int]:res = []if matrix:length, width = len(matrix),len(matrix[0])loop = min(length, width)//2startx, starty = 0, 0for offset in range(1, loop+1):for i in range(starty, width-offset):res.append(matrix[startx][i])for i in range(startx, length-offset):res.append(matrix[i][width-offset])for i in range(width-offset, starty, -1):res.append(matrix[length-offset][i])for i in range(length-offset, startx, -1):res.append(matrix[i][starty])startx+=1starty+=1if length==width and length%2!=0:res.append(matrix[length//2][length//2])else:if length>width and width%2!=0:for i in range(length-width+1):res.append(matrix[i+loop][width//2])elif length<width and length%2!=0:for i in range(width-length+1):res.append(matrix[length//2][i+loop])return reselse:return res

参考

算法刷题总结 (一) 数组
代码随想录

总结

以上是生活随笔为你收集整理的一、数组经典题型的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。