LeetCode 算法学习笔记-面试篇(上)- 第 013 ~ 025 题(第 05 ~ 08 天)
06.02.01 练习题目(第 05 天)
1. 0033. 搜索旋转排序数组
1.1 题目大意
描述:给定一个整数数组 nums,数组中值互不相同。给定的 nums 是经过升序排列后的又进行了「旋转」操作的。再给定一个整数 target。
要求:从 nums 中找到 target 所在位置,如果找到,则返回对应下标,找不到则返回 -1。
说明:
- 旋转操作:升序排列的数组 nums 在预先未知的第 k 个位置进行了右移操作,变成了 [nums[k]], nums[k+1], … , nums[n-1], … , nums[0], nums[1], … , nums[k-1]。
示例:
输入:nums = [4,5,6,7,0,1,2], target = 0 输出:4 输入:nums = [4,5,6,7,0,1,2], target = 3 输出:-1
1.2 题解: 修改后的二分法 (ChatGPT解释代码)
关键:二分后的左右两侧必有一侧是升序的[left, mid] 或者[mid, right]。
搜索旋转排序数组的问题可以使用修改后的二分查找算法来解决。以下是解题思路和代码:
-
初始化左右指针,分别指向数组的起始和结束位置:left = 0,right = len(nums) – 1。
-
在循环中,计算中间位置 mid:mid = (left + right) // 2。
-
判断中间元素是否等于目标值,若是则直接返回中间位置。
-
判断左半部分是否是有序的,即 nums[left] <= nums[mid],如果是的话,检查目标值是否在左半部分,即 nums[left] <= target <= nums[mid],如果是,则将右指针移到 mid – 1 处,否则将左指针移到 mid + 1 处。
-
如果左半部分不是有序的,那么右半部分必然是有序的。检查目标值是否在右半部分,即 nums[mid] <= target <= nums[right],如果是,则将左指针移到 mid + 1 处,否则将右指针移到 mid – 1 处。
-
不断缩小搜索范围,直到找到目标值或者左指针大于右指针为止。
以下是代码实现:
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
# 判断中间元素是否等于目标值
if nums[mid] == target:
return mid
# 判断左半部分是否是有序的
if nums[left] <= nums[mid]:
# 检查目标值是否在左半部分
if nums[left] <= target <= nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
# 右半部分必然是有序的
# 检查目标值是否在右半部分
if nums[mid] <= target <= nums[right]:
left = mid + 1
else:
right = mid - 1
# 循环结束,未找到目标值,返回 -1
return -1
这个算法的时间复杂度为 O(log n),其中 n 是数组的长度。
2. 0162. 寻找峰值
2.1 题目大意
描述:给定一个整数数组 nums。
要求:找到峰值元素并返回其索引。必须实现时间复杂度为
O
(
log
n
)
O(\log n)
O(logn) 的算法来解决此问题。
说明:
- 峰值元素:指其值严格大于左右相邻值的元素。
- 数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。
- 可以假设
n
u
m
s
[
−
1
]
=
n
u
m
s
[
n
]
=
−
∞
nums[-1] = nums[n] = -∞
nums[−1]=nums[n]=−∞。
1
≤
n
u
m
s
.
l
e
n
g
t
h
≤
1000
1 \le nums.length \le 1000
1≤nums.length≤1000。
−
2
31
≤
n
u
m
s
[
i
]
≤
2
31
−
1
-2^{31} \le nums[i] \le 2^{31} – 1
−231≤nums[i]≤231−1。
- 对于所有有效的
i
i
i 都有
n
u
m
s
[
i
]
!
=
n
u
m
s
[
i
+
1
]
nums[i] != nums[i + 1]
nums[i]!=nums[i+1]。
示例:
输入:nums = [1,2,3,1] 输出:2 解释:3 是峰值元素,你的函数应该返回其索引 2。 输入:nums = [1,2,1,3,5,6,4] 输出:1 或 5 解释:你的函数可以返回索引 1,其峰值元素为 2;或者返回索引 5, 其峰值元素为 6。
2.2 题解: 使用二分查找
参考:https://leetcode.cn/problems/find-peak-element/solutions/2570331/python3javacgotypescript-yi-ti-yi-jie-er-9xk5

2.3 ChatGPT解释代码
这段代码实现了在数组中查找峰值元素的算法。以下是代码的中文解释:
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
# 初始化左右指针,分别指向数组的起始和结束位置
left, right = 0, len(nums) - 1
# 在循环中进行二分查找
while left > 1
# 判断中间元素与其右侧元素的大小关系
if nums[mid] > nums[mid + 1]:
# 如果中间元素大于右侧元素,说明峰值在左侧,将右指针移到中间位置
right = mid
else:
# 如果中间元素小于等于右侧元素,说明峰值在右侧,将左指针移到中间位置的右侧
left = mid + 1
# 循环结束时,左指针指向的位置即为峰值元素的索引
return left
这个算法利用了二分查找的思想,不断缩小搜索范围,直到找到峰值元素。在每一步中,判断中间元素与其右侧元素的大小关系,根据关系调整左右指针,最终得到峰值元素的索引。
补充:
mid = (left + right) >> 1 是使用位运算右移一位来计算中间位置的一种写法。在二分查找中,计算中间位置是通过取左右指针的平均值,而右移一位相当于除以2。这是一种常见的位运算技巧,用于提高代码的执行效率。
与 mid = (left + right) // 2 相比,这两种写法在结果上是等价的,都能正确计算中间位置。使用位运算右移一位可能在某些情况下更高效,因为计算机底层对于位运算的支持更好。
总的来说,两者在功能上是相同的,选择哪一种写法通常取决于个人或团队的编码风格和习惯。
3. 0004. 寻找两个正序数组的中位数
3.1 题目大意
描述:给定两个正序(从小到大排序)数组 nums1、nums2。
要求:找出并返回这两个正序数组的中位数。
说明:
- 算法的时间复杂度应该为
O
(
log
(
m
+
n
)
)
O(\log (m + n))
O(log(m+n)) 。
n
u
m
s
1.
l
e
n
g
t
h
=
=
m
nums1.length == m
nums1.length==m。
n
u
m
s
2.
l
e
n
g
t
h
=
=
n
nums2.length == n
nums2.length==n。
0
≤
m
≤
1000
0 \le m \le 1000
0≤m≤1000。
0
≤
n
≤
1000
0 \le n \le 1000
0≤n≤1000。
1
≤
m
+
n
≤
2000
1 \le m + n \le 2000
1≤m+n≤2000。
−
1
0
6
≤
n
u
m
s
1
[
i
]
,
n
u
m
s
2
[
i
]
≤
1
0
6
-10^6 \le nums1[i], nums2[i] \le 10^6
−106≤nums1[i],nums2[i]≤106。
示例:
输入:nums1 = [1,2], nums2 = [3,4] 输出:2.50000 解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5
3.2 题解:使用二分查找
参考视频:【LeetCode004-两个有序数组的中位数-最优算法代码讲解】
找了多个视频看,这个讲的比较清晰,容易理解。第k小的方法也有很多视频,但个人感觉k/2的形式不太容易理解(第k小的方法时间复杂度是O(log (m+n)),刚好符合题目要求)。

Python实现:
这种解法的特点是将两个数组分别看做左右两部分后,两个左边看成一个整体,会有一个最大值;两个数组右边看成一个整体,会有一个最小值。也就是提前算了max(x_left, y_left) 和min(x_right, y_right)。
from typing import List
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# 1. 保证 nums1 是较短的数组
if len(nums1) > len(nums2):
return self.findMedianSortedArrays(nums2, nums1)
m, n = len(nums1), len(nums2)
left, right = 0, m
# 2. 二分查找
while left nums2[y]:
right = x - 1
elif y != 0 and x != m and nums2[y - 1] > nums1[x]:
left = x + 1
else:
# 4. 计算左侧和右侧的最大和最小值
if x == 0:
max_left = nums2[y - 1]
elif y == 0:
max_left = nums1[x - 1]
else:
max_left = max(nums1[x - 1], nums2[y - 1])
# 5. 根据数组长度之和的奇偶性返回中位数
if (m + n) % 2 == 1:
return max_left
if x == m:
min_right = nums2[y]
elif y == n:
min_right = nums1[x]
else:
min_right = min(nums1[x], nums2[y])
# 6. 返回最终的中位数
return (max_left + min_right) / 2
3.3 ChatGPT提供 (另一种解法)
这种方法提前判断了四个边界的情况,并赋值最大最小值的形式,具体解释见代码注释。时间复杂度是O(log min(m, n))
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# 保证 nums1 是较短的数组
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
# 中位数在合并后的正序数组中是第z个值,奇数偶数都是这个公式,向下取整。
z = (m + n + 1) // 2
# 根据较短的数组做二分查找
left, right = 0, m
while left <= right:
# 在 nums1 中找到一个分割点x
x = (left + right) // 2
# 通过分割点x计算在 nums2 中的分割点y
y = z - x
# 分别计算两个数组分割点左右两侧的值
# 考虑nums1的左边界,即x == 0 时,将x_left设为负无穷,这样就一定小于y_right
x_left = float('-inf') if x == 0 else nums1[x - 1]
# 考虑nums1的右边界,即x == m 时,将x_right设为正无穷,这样就一定大于y_left
x_right = float('inf') if x == m else nums1[x]
# 考虑nums2的左边界,即y == 0 时,将y_left设为负无穷,这样就一定小于x_right
y_left = float('-inf') if y == 0 else nums2[y - 1]
# 考虑nums2的右边界,即y == n 时,将y_right设为负无穷,这样就一定大于x_left
y_right = float('inf') if y == n else nums2[y]
# 判断是否找到了合适的分割点
if x_left <= y_right and y_left y_right:
# 如果 x_left 大于 y_right,说明当前分割点过大,需要减小
right = x - 1
else:
# 如果 x_left 小于等于 y_right,说明当前分割点过小,需要增加
left = x + 1
# 如果循环结束仍未找到合适的分割点,说明输入数组未按顺序排列
raise ValueError("Input arrays are not sorted.")
这个算法使用二分查找,通过在较短的数组中找到一个分割点,然后在另一个数组中找到相应的位置,来判断是否找到了中位数的位置。根据分割点左右两侧的值,计算得到中位数。
06.02.02 练习题目(第 06 天)
1. 0240. 搜索二维矩阵 II
1.1 题目大意
描述:给定一个
m
×
n
m \times n
m×n 大小的有序整数矩阵 matrix。matrix 中的每行元素从左到右升序排列,每列元素从上到下升序排列。再给定一个目标值 target。
要求:判断矩阵中是否可以找到 target,如果可以找到 target,返回 True,否则返回 False。
说明:
-
m
=
=
m
a
t
r
i
x
.
l
e
n
g
t
h
m == matrix.length
m==matrix.length。
n
=
=
m
a
t
r
i
x
[
i
]
.
l
e
n
g
t
h
n == matrix[i].length
n==matrix[i].length。
1
≤
n
,
m
≤
300
1 \le n, m \le 300
1≤n,m≤300。
−
1
0
9
≤
m
a
t
r
i
x
[
i
]
[
j
]
≤
1
0
9
-10^9 \le matrix[i][j] \le 10^9
−109≤matrix[i][j]≤109。
- 每行的所有元素从左到右升序排列。
- 每列的所有元素从上到下升序排列。
−
1
0
9
≤
t
a
r
g
e
t
≤
1
0
9
-10^9 \le target \le 10^9
−109≤target≤109。
示例:

输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 输出:True

输入:matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20 输出:False
1.2 题解:转化为图形式(易于理解)
参考:240. 搜索二维矩阵 II(贪心,清晰图解)

这段代码是在一个行列有序的二维矩阵中搜索目标值 target 的位置。具体步骤如下:
- 初始化 i 为 0,j 为矩阵的最右边(n-1),即从矩阵的右上角开始。
- 进入循环,判断当前位置 matrix[i][j] 与目标值 target 的关系:
- 如果当前值等于目标值,返回 True,表示找到了目标值。
- 如果当前值大于目标值,说明目标值可能在当前值的左边,将 j 减一(向左移动)。
- 如果当前值小于目标值,说明目标值可能在当前值的下边,将 i 加一(向下移动)。
- 循环直到找到目标值或者越过矩阵边界。
- 如果循环结束,仍未找到目标值,返回 False。
这个算法采用了从矩阵的右上角(或左下角)开始的策略,通过对当前元素的比较,逐步缩小搜索范围。这样的时间复杂度是 O(m + n),其中 m 是矩阵的行数,n 是矩阵的列数。
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m = len(matrix)
n = len(matrix[0])
# i, j = m - 1, 0 # 从矩阵的左下角开始
# while j = 0:
# if matrix[i][j] == target:
# return True
# elif matrix[i][j] > target:
# i -= 1 # 向上移动
# else:
# j += 1 # 向右移动
# return False
i, j = 0, n - 1 # 从矩阵右上角开始
while i = 0:
if matrix[i][j] == target:
return True
elif matrix[i][j] < target:
i += 1 # 向下移动
else:
j -= 1 # 向左移动
return False
2. 0069. x 的平方根
2.1 题目大意
要求:实现 int sqrt(int x) 函数。计算并返回 x 的平方根(只保留整数部分),其中 x 是非负整数。
说明:
-
0
≤
x
≤
2
31
−
1
0 \le x \le 2^{31} – 1
0≤x≤231−1。
示例:
输入:x = 4 输出:2 输入:x = 8 输出:2 解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
2.2 题解:使用二分查找
class Solution:
def mySqrt(self, x: int) -> int:
# 初始化搜索范围的左右边界
left, right = 0, x
# 开始二分查找
while left <= right:
# 计算中间值
mid = (left + right) // 2
# 判断中间值的平方与目标值的关系
if mid * mid <= x:
# 如果中间值的平方小于等于目标值,可能是满足条件的整数平方根
# 将当前中间值存储在result中,并将搜索范围缩小到mid的右侧
result = mid # 关键一步,单独存储结果
left = mid + 1
else:
# 如果中间值的平方大于目标值,将搜索范围缩小到mid的左侧
right = mid - 1
# 循环结束时,result中存储的是满足条件的整数平方根
return result
这段代码是一个求解非负整数平方根的二分查找算法,通过注释提供了对每个关键步骤的中文解释。
时间复杂度:
二分查找的时间复杂度是 O(log x),其中 x 是输入的非负整数。因为每一轮都将搜索范围减半,所以时间复杂度是对数级别的。
空间复杂度:
这个算法的空间复杂度是 O(1),因为只使用了有限个变量(left、right、mid、result)来存储中间结果,而不随输入 x 的增加而线性增长。
3. 0283. 移动零
3.1 题目大意
描述:给定一个数组 nums。
要求:将所有 0 移动到末尾,并保持原有的非 0 数字的相对顺序。
说明:
- 只能在原数组上进行操作。
-
1
≤
n
u
m
s
.
l
e
n
g
t
h
≤
1
0
4
1 \le nums.length \le 10^4
1≤nums.length≤104。
−
2
31
≤
n
u
m
s
[
i
]
≤
2
31
−
1
-2^{31} \le nums[i] \le 2^{31} – 1
−231≤nums[i]≤231−1。
示例:
输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0] 输入: nums = [0] 输出: [0]
3.2 题解:使用双指针
参考图解:
https://leetcode.cn/problems/move-zeroes/solutions/494449/shuang-zhi-zhen-xiang-xi-tu-jie-by-xueliangwang
这是一个将数组中的零移动到末尾的函数。下面是中文解释:
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
不返回任何值,直接在原数组上进行修改。
参数:
nums -- 整数数组
"""
j = 0 # j指针用来指示第一个0所在的位置
for i in range(len(nums)): # i指针用来遍历数组
if nums[i] != 0:
# 当发现非零元素时,将其交换到数组的开头(通过与nums[j]交换位置)
nums[j], nums[i] = nums[i], nums[j]
j += 1
该函数通过使用两个指针 i 和 j,其中 i 用于遍历数组,j 用于指示当前数组中第一个零的位置。当发现非零元素时,通过与 nums[j] 交换位置,将非零元素置于数组的开头。这样,遍历完成后,所有的零都会被移动到数组的末尾。
06.02.05 练习题目(第 07 天)
1. 0415. 字符串相加
1.1 题目大意
描述:给定两个字符串形式的非负整数 num1 和num2。
要求:计算它们的和,并同样以字符串形式返回。
说明:
-
1
≤
n
u
m
1.
l
e
n
g
t
h
,
n
u
m
2.
l
e
n
g
t
h
≤
1
0
4
1 \le num1.length, num2.length \le 10^4
1≤num1.length,num2.length≤104。
n
u
m
1
num1
num1 和
n
u
m
2
num2
num2 都只包含数字
0
∼
9
0 \sim 9
0∼9。
n
u
m
1
num1
num1 和
n
u
m
2
num2
num2 都不包含任何前导零。
- 你不能使用任何內建 BigInteger 库, 也不能直接将输入的字符串转换为整数形式。
示例:
输入:num1 = "11", num2 = "123" 输出:"134" 输入:num1 = "456", num2 = "77" 输出:"533"
1.2 题解:双指针,清晰图解
参考:https://leetcode.cn/problems/add-strings/solutions/1/add-strings-shuang-zhi-zhen-fa-by-jyd
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
"""
返回两个字符串形式的数字的和。
参数:
num1 -- 第一个字符串形式的数字
num2 -- 第二个字符串形式的数字
返回:
str -- 两个字符串形式数字的和
"""
i, j = len(num1) - 1, len(num2) - 1
res = '' # 存储结果的字符串
carry = 0 # 进位标志
while i >= 0 or j >= 0:
# 取当前位置上的数字,如果超过字符串长度则为0
m = int(num1[i]) if i >= 0 else 0
n = int(num2[j]) if j >= 0 else 0
# 将当前位置的数字与进位相加
tmp = m + n + carry
carry = tmp // 10 # 计算进位
res = str(tmp % 10) + res # 将当前位置的结果添加到res字符串的开头
i, j = i - 1, j - 1
# 处理最高位的进位
return '1' + res if carry else res
2. 0239. 滑动窗口最大值
2.1 题目大意
描述:给定一个整数数组 nums,再给定一个整数 k,表示为大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。我们只能看到滑动窗口内的 k 个数字,滑动窗口每次只能向右移动一位。
要求:返回滑动窗口中的最大值。
说明:
-
1
≤
n
u
m
s
.
l
e
n
g
t
h
≤
1
0
5
1 \le nums.length \le 10^5
1≤nums.length≤105。
−
1
0
4
≤
n
u
m
s
[
i
]
≤
1
0
4
-10^4 \le nums[i] \le 10^4
−104≤nums[i]≤104。
1
≤
k
≤
n
u
m
s
.
l
e
n
g
t
h
1 \le k \le nums.length
1≤k≤nums.length。
示例:
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3 输出:[3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 输入:nums = [1], k = 1 输出:[1]
3. 0003. 无重复字符的最长子串
3.1 题目大意
描述:给定一个字符串 s。
要求:找出其中不含有重复字符的最长子串的长度。
说明:
-
0
≤
s
.
l
e
n
g
t
h
≤
5
∗
1
0
4
0 \le s.length \le 5 * 10^4
0≤s.length≤5∗104。
- s 由英文字母、数字、符号和空格组成。
示例:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
06.02.04 练习题目(第 08 天)
1. 0076. 最小覆盖子串
1.1 题目大意
描述:给定一个字符串 s、一个字符串 t。
要求:返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “”。
说明:
-
1
≤
s
.
l
e
n
g
t
h
,
t
.
l
e
n
g
t
h
≤
1
0
5
1 \le s.length, t.length \le 10^5
1≤s.length,t.length≤105。
- s 和 t 由英文字母组成。
示例:
- 示例 1:
输入:s = "ADOBECODEBANC", t = "ABC" 输出:"BANC"
- 示例 2:
输入:s = "a", t = "a" 输出:"a"
2. 0718. 最长重复子数组
2.1 题目大意
描述:给定两个整数数组 nums1、nums2。
要求:计算两个数组中公共的、长度最长的子数组长度。
说明:
-
1
≤
n
u
m
s
1.
l
e
n
g
t
h
,
n
u
m
s
2.
l
e
n
g
t
h
≤
1000
1 \le nums1.length, nums2.length \le 1000
1≤nums1.length,nums2.length≤1000。
0
≤
n
u
m
s
1
[
i
]
,
n
u
m
s
2
[
i
]
≤
100
0 \le nums1[i], nums2[i] \le 100
0≤nums1[i],nums2[i]≤100。
示例:
- 示例 1:
输入:nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] 输出:3 解释:长度最长的公共子数组是 [3,2,1] 。
- 示例 2:
输入:nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] 输出:5
3. 0083. 删除排序链表中的重复元素
3.1 题目大意
描述:给定一个已排序的链表的头 head。
要求:删除所有重复的元素,使每个元素只出现一次。返回已排序的链表。
说明:
- 链表中节点数目在范围
[
0
,
300
]
[0, 300]
[0,300] 内。
−
100
≤
N
o
d
e
.
v
a
l
≤
100
-100 \le Node.val \le 100
−100≤Node.val≤100。
- 题目数据保证链表已经按升序排列。
示例:
- 示例 1:
输入:head = [1,1,2,3,3] 输出:[1,2,3]
4. 0082. 删除排序链表中的重复元素 II
4.1 题目大意
描述:给定一个已排序的链表的头 head。
要求:删除原始链表中所有重复数字的节点,只留下不同的数字。返回已排序的链表。
说明:
- 链表中节点数目在范围
[
0
,
300
]
[0, 300]
[0,300] 内。
−
100
≤
N
o
d
e
.
v
a
l
≤
100
-100 \le Node.val \le 100
−100≤Node.val≤100。
- 题目数据保证链表已经按升序排列。
示例:
- 示例 1:
输入:head = [1,2,3,3,4,4,5] 输出:[1,2,5]
本文来自网络,不代表协通编程立场,如若转载,请注明出处:https://net2asp.com/b44ca9451d.html
