leetcode题目按类型
二分查找
✅ 二分查找框架
✅ 找中间
1
2
3
4
5
6
7
8
9
10
11
def binary_search(nums:List[int], target:int):
l, r = 0, len(nums)-1
while l <= r:
mid = (l+r)//2
if nums[mid] < target:
l = mid + 1
elif nums[mid] > target:
r = mid -1
elif nums[mid] == target:
return -1
return -1
✅ 左边界
1
2
3
4
5
6
7
8
9
10
11
12
13
def left_bound(nums:List[int], target:int):
l, r = 0, len(nums)-1
while l <= r:
mid = (l+r)//2
if nums[mid] < target:
l = mid + 1
elif nums[mid] > target:
r = mid - 1
elif nums[mid] == target:
r = mid - 1
if l > len(nums)-1 or nums[l] != target:
return -1
return l
✅ 右边界
1
2
3
4
5
6
7
8
9
10
11
12
13
def right_bound(nums:List[int], target:int):
l, r = 0, len(nums)-1
while l <= r:
mid = (l+r)//2
if nums[mid] < target:
l = mid + 1
elif nums[mid] > target:
r = mid - 1
elif nums[mid] == target:
l = mid + 1
if r < 0 or nums[r] != target:
return -1
return r
总结
还有同学指出这么一个规律：
- 当
while (left < right)时，对应的更新式是left = middle + 1，right = middle - 当
while (left <= right)时，对应的更新式是left = middle + 1，right = middle - 1
本题由于【当区间长度为1时，即可停止二分查找】，所以是 while (left < right) ，所以是 left = middle + 1，right = middle
要求
- 数据结构排好序
- 线性表具有随机访问的特点(如数组)
- 线性表可以根据中间元素特点推测两侧元素性质
二分法步骤
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
n = len(numbers)
for i in range(n):
if 2 * numbers[i] > target:
break
a = i+1
b = n-1
while a <= b:
c = (a+b)//2
if numbers[c] == target - numbers[i]:
return [i+1, c+1]
elif numbers[c] < target - numbers[i]: # 注意必须是elif
a = c + 1 # 注意有+1 -1，保证不在边界，确保不会死循环
else:
b = c - 1
关键字：重复— 想哈希表（O(n),O(n))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 二分查找，小于等于i的个数 icnt[i]≤i
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
n = len(nums)
l, r, ans = 1, n-1, -1
while l<=r:
mid = (l+r)//2
cnt = 0
for i in range(n):
cnt += nums[i] <= mid
if cnt <= mid:
l = mid + 1
else:
r = mid -1
ans = mid
return ans
✅(20m) 167. 两数之和 II - 输入有序数组
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2)不是从零开始的。 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
1
示例:输入: numbers = [2, 7, 11, 15], target = 9输出: [1,2]解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
2️⃣ 双指针+二分
缩减搜索空间的思想：
实际上还有几道题也是用到了这样的缩减搜索空间的思想：
普通双指针：
1
class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: i, j = 0, len(numbers)-1 while i < j: m = (i + j) >> 1 if numbers[i] + numbers[j] == target: return [i+1,j+1] elif numbers[i] + numbers[j] < target: i += 1 else: j -= 1 return []
双指针+二分：
✅(30m) 349. 两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。
1
示例 1：输入：nums1 = [1,2,2,1], nums2 = [2,2]输出：[2]示例 2：输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出：[9,4] 说明：输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。
1
class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: nums1 = sorted(list(set(nums1))) nums2 = sorted(list(set(nums2))) n1 = len(nums1) n2 = len(nums2) i, j = 0, 0 ans = [] while i<n1 and j<n2: if nums1[i] == nums2[j]: ans.append(nums1[i]) i += 1 j += 1 elif nums1[i] < nums2[j]: i += 1 elif nums1[i] > nums2[j]: j += 1 return ans
1
from typing import Listnums1 = [1,2,2,1]nums2 = [2,2]solution = Solution()result = solution.intersection(nums1, nums2)result
🚩287. 寻找重复数
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间(包括 1 和 n)，可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
1
示例 1:输入: [1,3,4,2,2]输出: 2示例 2:输入: [3,1,3,4,2]输出: 3说明：不能更改原数组(假设数组是只读的)。只能使用额外的 O(1) 的空间。时间复杂度小于 O(n2) 。数组中只有一个重复的数字，但它可能不止重复出现一次。
2️⃣关键字：重复— 想哈希表（O(n),O(n))
1
# 二分查找，小于等于i的个数 icnt[i]≤iclass Solution: def findDuplicate(self, nums: List[int]) -> int: n = len(nums) l, r, ans = 1, n-1, -1 while l<=r: mid = (l+r)//2 cnt = 0 for i in range(n): cnt += nums[i] <= mid if cnt <= mid: l = mid + 1 else: r = mid -1 ans = mid return ans
1
from typing import Listnums = [1,3,4,2,2]solution = Solution()result = solution.findDuplicate(nums)result
🚩300. 最长上升子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。
1
示例:输入: [10,9,2,5,3,7,101,18]输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。说明:可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n2) 。进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
2️⃣ 注意用贪心+二分做可优化到O(nlogn)复杂度
🚩378. 有序矩阵中第K小的元素
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
1
示例：matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15]],k = 8,返回 13。 提示：你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。
1
# 官解class Solution: def kthSmallest(self, matrix: List[List[int]], k: int) -> int: n = len(matrix) def check(mid): i, j = n-1, 0 num = 0 while i >= 0 and j<n: if matrix[i][j] <= mid: num += i +1 j += 1 else: i -= 1 return num>=k left, right = matrix[0][0], matrix[-1][-1] # 注意是从-1，-1 while left < right: mid = (left + right)//2 if check(mid): right = mid else: left = mid + 1 return left
2️⃣
走法步骤：
1
初始位置在 matrix[n - 1][0]matrix[n−1][0]（即左下角）；设当前位置为 matrix[i][j]matrix[i][j]。若 matrix[i][j] \leq midmatrix[i][j]≤mid，则将当前所在列的不大于 midmid 的数的数量（即 i + 1i+1）累加到答案中，并向右移动，否则向上移动；不断移动直到走出格子为止。
时间复杂度：O(n\log(r-l))O(nlog(r−l))，二分查找进行次数为 O(\log(r-l))O(log(r−l))，每次操作时间复杂度为 O(n)O(n)。
✅(30m)35. 搜索插入位置
🚩(30m)153. 寻找旋转排序数组中的最小值
难度中等352
假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。
请找出其中最小的元素。
示例 1：
1
输入：nums = [3,4,5,1,2]输出：1
示例 2：
1
输入：nums = [4,5,6,7,0,1,2]输出：0
示例 3：
1
输入：nums = [1]输出：1
注意：
-
比较时比较nums[0]即可
-
注意停止条件是：
1
if nums[mid] > nums[mid + 1]: return nums[mid + 1] if nums[mid - 1] > nums[mid]: return nums[mid]
2️⃣
1
// 疑问：为什么 high = mid;而不是 high = mid-1;// 解答：{4,5,1,2,3}，如果high=mid-1，则丢失了最小值1
✅(30m) 14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
1
2
3
4
5
6
7
8
9
10
11
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
所有输入只包含小写字母 a-z 。
🚩4. 寻找两个有序数组的中位数
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
1
2
3
4
5
6
7
8
9
10
11
12
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
2️⃣
1
2
3
nums1 = [1, 2]
nums2 = [3, 4]
1
2
3
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
1
2
3
solution = Solution()
result = solution.findMedianSortedArrays(nums1,nums2)
result
✅(1.5h) 88. 合并两个有序数组
给你两个有序整数数组 nums1 _和 _nums2，请你将 nums2 _合并到 _nums1 _中，_使 _nums1 _成为一个有序数组。
说明：
- 初始化 nums1 和 nums2 的元素数量分别为 m 和 _n _。
- 你可以假设 nums1 _有足够的空间(空间大小大于或等于 _m + n)来保存 nums2 中的元素。
示例：
1
2
3
4
5
输入：
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]·
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
i = m-1
j = n-1
while i>=0 and j>=0:
if nums1[i] < nums2[j]:
nums1[i+j+1] = nums2[j]
j -= 1
else:
nums1[i+j+1] = nums1[i]
i -= 1
if j>=0:
nums1[:j+1] = nums2[:j+1]
1
2
3
4
# 法2
# 注意用深拷贝
nums1[:] = nums1[:m] + nums2
nums1.sort()
🚩33. 搜索旋转排序数组
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
1
2
3
4
5
6
7
8
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
2️⃣
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# logn → 二分法
class Solution:
def search(self, nums, 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[mid] > nums[0]: # 边界条件是最左最右
if nums[0] <= target < nums[mid]: # 注意有等于
r = mid - 1
else:
l = mid + 1
else:
if nums[len(nums)-1] >= target > nums[mid] :
l = mid + 1
else:
r = mid - 1
return -1
1
2
3
4
5
6
from typing import List
nums = [4,5,6,7,0,1,2]
solution = Solution()
result = solution.search(nums, 0)
result
