LeetCode刷题小记 一、【数组】

LeetCode刷题小记 一、【数组】

写在前面

本系列笔记主要作为笔者刷题的题解，所用的语言为Python3，若于您有助，不胜荣幸。

1. 数组

1.1 理论基础

数组[array]是一种线性的数据结构，将相同的数据类型存储在连续的内存空间当中，我们将元素在数组中的位置称为该元素的索引[index]。由于数组是连续存储的特性，我们访问其中单个元素变得十分容易，我们只需要知道其索引就能访问其中的元素，索引本质上是内存地址的偏移量。

由于数组中元素的连续存在的，因此要在数组中插入、删除元素，需要移动后续的所有元素。所以数组的各项操作的时间复杂度如下

Operation	Time Complexity
插入、删除	$\mathcal{O}(n)$
查找	$\mathcal{O}(1)$

1.2 二分查找

704二分查找

二分查找的前提是有序数组（升序或者降序），且无重复元素。

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

二分查找的第一种写法是要定义在一个左闭右闭的区间里，[left, right]，所以终止条件就可以写为：while (left <= right)

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

• 时间复杂度：$\mathcal{O}(\log n)$
• 空间复杂度：$\mathcal{O}(1)$

第二种写法是将其定义在一个左闭右开的区间，[left, right)当中，所以终止条件必须写为：while (left < right)

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

35搜索插入位置

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

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

# 1、首先，在 nums 数组中二分查找 target；
# 2、如果二分查找失败，则 binarySearch 返回 -1，表明 nums 中没有 target。此时，searchRange 直接返回 {-1, -1}；
# 3、如果二分查找成功，则 binarySearch 返回 nums 中值为 target 的一个下标。然后，通过左右滑动指针，来找到符合题意的区间
class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:def binarySearch(nums: List[int], target: int) -> int:left: int = 0right: int = len(nums) - 1while left <= right:mid = left + (right - left) // 2if nums[mid] > target:right = mid - 1elif nums[mid] < target:left = mid + 1else:return midreturn -1index = binarySearch(nums, target)if index == -1: return [-1, -1]left = right = indexwhile left - 1 >= 0 and nums[left - 1] == target: left -= 1while right + 1 <= len(nums) - 1 and nums[right+1] == target: right += 1return [left, right]

69x的平方根

class Solution:def mySqrt(self, x: int) -> int:if x == 0 or x == 1:return xleft: int = 1right: int = xres: int = -1while left <= right:mid = left + (right - left) // 2if mid * mid <= x:  # 平方更要小于等于当前的x所以，这里用<=来限制区间res = midleft = mid + 1else:right = mid - 1return res

367有效的完全平方数

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

1.3 移除元素

27移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

可以使用双指针法：通过一个快指针和慢指针在一个for循环中完成两个for循环的工作。

定义快慢指针：

• 快指针：寻找新数组的元素，新数组就是不含有目标元素的数组，如果快指针指向的元素不等于val，那么它一定是输出数组中的元素，所以将其赋值给慢指针的位置
• 慢指针：指向更新，新数组的下标位置，如果快指针指向的元素等于val，说明它不是输出数组中的元素，我们直接移动快指针即可

双指针的方法，在处理数组和链表的操作当中都是非常常见的。

class Solution:def removeElement(self, nums: List[int], val: int) -> int:slowIndex: int = 0for fastIndex in range(len(nums)):if nums[fastIndex] != val:nums[slowIndex] = nums[fastIndex]slowIndex += 1return slowIndexclass Solution:def removeElement(self, nums: List[int], val: int) -> int:slowIndex: int = 0fastIndex: int = 0while fastIndex < len(nums):if nums[fastIndex] != val:nums[slowIndex] = nums[fastIndex]slowIndex += 1fastIndex += 1return slowIndex

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

class Solution:def removeDuplicates(self, nums: List[int]) -> int:fastIndex: int = 1slowIndex: int = 0while fastIndex <= len(nums) - 1:if nums[slowIndex] == nums[fastIndex]:fastIndex += 1elif nums[slowIndex] != nums[fastIndex]:slowIndex += 1nums[slowIndex] = nums[fastIndex]return slowIndex + 1

283移动零

class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""slowIndex: int = 0fastIndex: int = 0while fastIndex <= len(nums) - 1:if nums[fastIndex] != 0:nums[slowIndex] = nums[fastIndex]slowIndex += 1fastIndex += 1for i in range(slowIndex, fastIndex):nums[i] = 0

1.4 有序数组的平方

977有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

思路，该数组已经知道为有序数组，那么数组的中间值的平方一定是最小的，最大值一定是从两侧值的平方中进行选取，所以我们可以使用左右指针开始查找。

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:leftIndex: int = 0rightIndex: int = len(nums) - 1resIndex: int = len(nums) - 1res: List[any] = [float('inf')] * len(nums)while leftIndex <= rightIndex:elem1 = nums[leftIndex] ** 2elem2 = nums[rightIndex] ** 2if elem1 >= elem2:res[resIndex] = elem1leftIndex += 1else:res[resIndex] = elem2rightIndex -= 1resIndex -= 1return res

1.5 长度最小的子数组

209长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

本题采用的思想是，滑动窗口，滑动窗口可以分为最大滑动窗口和最小滑动窗口，具体的区别在于最大滑动窗口目的在于最大化满足条件的区间长度，而最小化滑动窗口目的在于最小化满足条件的区间长度。

最小滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最小长度。

while j < len(nums):判断[i, j]是否满足条件while 满足条件：不断更新结果(注意在while内更新！)i += 1 （最大程度的压缩i，使得滑窗尽可能的小）j += 1

最大滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最大长度。

while j < len(nums):判断[i, j]是否满足条件while 不满足条件：i += 1 （最保守的压缩i，一旦满足条件了就退出压缩i的过程，使得滑窗尽可能的大）不断更新结果（注意在while外更新！）j += 1

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:startIndex: int = 0result: any = float('inf')s: int = 0for endIndex in range(len(nums)):s += nums[endIndex]while s >= target:result = min(result, endIndex - startIndex + 1)s -= nums[startIndex]startIndex += 1return result if result != float('inf') else 0

defaultdict的用法

python中的defaultdict是collections库中的一种字典，与python中默认字典dict的区别在于，我们可以指定defaultdict当访问到不存在的key是的返回值，比如

from collections import defaultdict
d1 = defaultdict(int)		#设置d1访问不存在的key时返回0
d2 = defaultdict(list)		#设置d2访问不存在的key时返回空列表[]
d2 = defaultdict(bool)		#设置d3访问不存在的key时返回False
print(d1['a'])
print(d2['a'])
print(d3['a'])

返回的结果为

0
[]
False

904. 水果成篮

class Solution:def totalFruit(self, fruits: List[int]) -> int:left: int = 0right: int = 0result: int = 0classMap: dict = defaultdict(int)      #访问不存在的key返回0classCnt: int = 0while right <= len(fruits) - 1:# 判断是否满足情况if classMap[fruits[right]] == 0:classCnt += 1classMap[fruits[right]] += 1# 当不满情况的时候才对left进行移动，这样能够保证滑动窗口为最大while classCnt > 2:if classMap[fruits[left]] == 1:classCnt -= 1classMap[fruits[left]] -= 1 left += 1# 结果在外面进行更新result = max(result, right - left + 1)right += 1return result

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

class Solution:def minWindow(self, s: str, t: str) -> str:left: int = 0right: int = 0strMap: dict = collections.defaultdict(int)   #访问不存在的key时返回0strCnt: int = len(t)result: str = ''for char in t:strMap[char] += 1# 移动右边界while right <= len(s) - 1:# 判断当前字母是否被需要if s[right] in strMap:if strMap[s[right]] > 0:strCnt -= 1strMap[s[right]] -= 1# 压缩左边界while strCnt == 0:# 更新resultif not result or right - left + 1 < len(result):result = s[left: right + 1]# 判断当前字母是否可压缩if s[left] in strMap:if strMap[s[left]] == 0:strCnt += 1strMap[s[left]] += 1left += 1right += 1return result

1.6 螺旋矩阵II

59. 螺旋矩阵 II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

这道题的重点在于确定循环不变量，我们要保证每次循环的写法的区间都具有一致性，所以我们在这里采用左闭右开的方式来进行循环。

class Solution:def generateMatrix(self, n: int) -> List[List[int]]:nums: List[List[int]] = [[0] * n for _ in range(n)]startx: int = 0starty: int = 0loop: int = n // 2count: int = 1offset: int = 1for _ in range(loop):for j in range(starty, n - offset):nums[startx][j] = countcount += 1for i in range(startx, n - offset):nums[i][n - offset] = countcount += 1for j in range(n - offset, starty, -1):nums[n - offset][j] = countcount += 1for i in range(n - offset, startx, -1):nums[i][starty] = countcount += 1startx += 1starty += 1offset += 1if n % 2 == 1:nums[n // 2][n // 2] = countreturn nums

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

class Solution:def spiralOrder(self, matrix: List[List[int]]) -> List[int]:m: int = len(matrix)n: int = len(matrix[0])loop: int = min(m, n) // 2print(loop)startx: int = 0starty: int = 0offset: int = 1res: List[int] = []for _ in range(loop):for j in range(starty, n - offset):res.append(matrix[startx][j])for i in range(startx, m - offset):res.append(matrix[i][n - offset])for j in range(n - offset, starty, -1):res.append(matrix[m - offset][j])for i in range(m - offset, startx, -1):res.append(matrix[i][starty])startx += 1starty += 1offset += 1if min(m, n) % 2 == 1:if m <= n:for j in range(starty, n - (offset-1)):   #注意这里转完一圈之后offset实际上是被+1了，我们需要还原上一圈中的offsetres.append(matrix[startx][j])else:for i in range(startx, m - (offset-1)):res.append(matrix[i][starty])return res

Reference

[1] Hello 算法
[2] 代码随想录