抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

LeetCode-Hot100-技巧

leetcode

发布于：2024年11月19日

字数：3.1k 字

时长：14 分钟

前言

题单LeetCode 热题 100的技巧部分，给出解析。

136. Single Number

原题链接

题目描述

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1: 

1
2
Input: nums = [2,2,1]
Output: 1

Example 2: 

1
2
Input: nums = [4,1,2,1,2]
Output: 4

Example 3: 

1
2
Input: nums = [1]
Output: 1

Constraints:

  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • Each element in the array appears twice except for one element which appears only once.

解题方法

给定一个非空整数数组 nums，其中除了一个元素之外，其他每个元素都出现了两次。要求找到那个只出现一次的元素。

这个问题要求我们实现一个线性时间复杂度的解决方案，并且只能使用常量级别的额外空间。

因为要求只能够使用常量级别的额外空间，所以我们就不能够使用哈希表来处理这个问题。

可以考虑使用异或操作：

  • 利用异或操作：

    • 异或（XOR）操作有两个非常重要的性质：
      • $a⊕a=0$（任何数与自己异或结果为0）
      • $a⊕0=a$（任何数与0异或结果还是这个数）

  • 应用异或找到单一数字：

    • 如果我们将数组中的所有数字都进行异或操作，相同的数字由于异或的性质会互相抵消为0，最终剩下的就是那个只出现一次的数字。
      • 这种方法的时间复杂度是 O(n)，并且只使用了 O(1) 的额外空间。

代码实现

1
2
3
4
5
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for n in nums:
            res ^= n
        return res

复杂度分析

时间复杂度：$O(n)$。

空间复杂度：$O(1)$。

169. Majority Element

原题链接

题目描述

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1: 

1
2
Input: nums = [3,2,3]
Output: 3

Example 2: 

1
2
Input: nums = [2,2,1,1,1,2,2]
Output: 2

Constraints:

  • n == nums.length
  • 1 <= n <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9

Follow-up: Could you solve the problem in linear time and in O(1) space?

解题方法

摩尔投票法

摩尔投票法可以很方便地解决这个问题。

哈希表

key：元素本身，value：出现次数。

遍历数组，统计出现次数之后计算谁出现次数最大，大于 $⌊n / 2⌋$ 则为众数。

排序

一定会出现众数，则从小到大排序之后取最中间的那个数就是结果。

代码实现

摩尔投票法

1
2
3
4
5
6
7
8
9
10
11
def majorityElement(self, nums: List[int]) -> int: 
	# 候选人与候选人票数
	res, count = 0 , 0 
	for n in nums: 
		# 票数为0，确定新的候选人
		if count == 0: 
			res = n 
		# 每有一个与候选人相同的元素，票数加1
		count += (1 if res == n else -1) 
	# 为什么不需要验证？因为题目保证了一定会出现众数
	return res

哈希表

1
2
3
4
5
6
7
8
9
10
11
def majorityElement(self, nums: List[int]) -> int:
	# 哈希表
	counts = {}
	# 遍历数组
	for num in nums:
		if num in counts:
			counts[num] += 1
		else:
			counts[num] = 1
		if counts[num] > len(nums) // 2:
			return num

排序

1
2
3
4
5
def majorityElement(self, nums: List[int]) -> int:

	nums.sort()

	return nums[len(nums)//2]

复杂度分析

方法 时间复杂度 空间复杂度
摩尔投票法 $O(n)$ $O(1)$
哈希表 $O(n)$ $O(n)$
排序 $O(nlogn)$ 根据排序算法决定

75. Sort Colors

原题链接

题目描述

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

Example 1: 

1
2
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Example 2: 

1
2
Input: nums = [2,0,1]
Output: [0,1,2]

Constraints:

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] is either 0, 1, or 2.

Follow up: Could you come up with a one-pass algorithm using only constant extra space?

解题方法

排序

要求原地变换，使用冒泡排序可解。

双指针

这是一个经典的荷兰国旗问题，可以用双指针法（Two Pointers）来实现一次遍历的解决方案，同时只需要常量的额外空间。我们将数组中的 0、1 和 2 分别视作红色、白色和蓝色，需要将它们按照顺序排序，即先把所有 0 放在前面，接着是 1，最后是 2。

解题思路： 我们使用三个指针：

  • low：指向最左边的未放好的红色（0）位置。
  • mid：当前处理的位置。
  • high：指向最右边的未放好的蓝色（2）位置。

我们遍历数组 nums，当 mid 小于等于 high 时：

  • 如果 nums[mid] == 0，将其与 nums[low] 交换，并将 low 和 mid 都向右移动。
  • 如果 nums[mid] == 1，不需要交换，只需将 mid 向右移动。
  • 如果 nums[mid] == 2，将其与 nums[high] 交换，并将 high 向左移动，但不移动 mid，因为从 high 交换过来的元素仍需要处理。

计数排序

除了使用双指针法（Two Pointers）的一次遍历解法外，还可以使用计数排序法（Counting Sort），这是一个两次遍历的解法。虽然这种方法的时间复杂度也是 O(n)，但它相对更简单，适合更容易理解和实现。

思路：

  1. 首先遍历数组，统计每种颜色（即 0、1、2）的出现次数。
  2. 然后根据统计结果，重新写回数组，使得数组中按顺序排列红色（0）、白色（1）、蓝色（2）。

步骤：

  1. 初始化三个计数器 count0、count1 和 count2，分别记录 0、1 和 2 的出现次数。
  2. 遍历整个数组，统计每个数字的出现次数。
  3. 根据计数结果，按照 0 的数量写入 0，再按照 1 的数量写入 1，最后按照 2 的数量写入 2。

代码实现

排序

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        for i in range(n - 1, -1, -1):
            for j in range(i):
                if nums[j] > nums[j + 1]:
                    temp = nums[j]
                    nums[j] = nums[j + 1]
                    nums[j + 1] = temp

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        low, mid, high = 0, 0, len(nums) - 1
        
        while mid <= high:
            if nums[mid] == 0:
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1

计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 计数
        count0, count1, count2 = 0, 0, 0
        for num in nums:
            if num == 0:
                count0 += 1
            elif num == 1:
                count1 += 1
            else:
                count2 += 1

        # 根据计数结果修改原数组
        for i in range(count0):
            nums[i] = 0
        for i in range(count0, count0 + count1):
            nums[i] = 1
        for i in range(count0 + count1, count0 + count1 + count2):
            nums[i] = 2

复杂度分析

方法 时间复杂度 空间复杂度
排序 $O(n^2)$ $O(1)$
双指针 $O(n)$ $O(1)$
计数排序 $O(n)$ $O(1)$

31. Next Permutation

原题链接

题目描述

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

  • For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

  • For example, the next permutation of arr = [1,2,3] is [1,3,2].
  • Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
  • While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

Example 1: 

1
2
Input: nums = [1,2,3]
Output: [1,3,2]

Example 2: 

1
2
Input: nums = [3,2,1]
Output: [1,2,3]

Example 3: 

1
2
Input: nums = [1,1,5]
Output: [1,5,1]

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

解题方法

题目要求找到一个数组的下一个排列，即字典序中的下一个较大排列。如果当前排列已经是字典序的最大排列，那么需要返回字典序最小的排列（升序排列）。要求就地替换，且只使用常数级额外空间。

解题思路：

  1. 从右往左找到第一个不符合递增趋势的元素：

    • 从数组末尾开始，找到第一个前一位小于后一位的元素，记作 nums[i]。此时，[i+1, n-1] 部分是一个递减序列。

  2. 从右往左找到比 nums[i] 大的最小元素：

    • 在递减序列中，从右往左找到第一个比 nums[i] 大的元素，记作 nums[j]。

  3. 交换nums[i]和nums[j]：

    • 交换这两个元素后，[i+1, n-1] 部分仍然是递减序列。

  4. 反转 [i+1, n-1] 部分：

    • 将 [i+1, n-1] 部分反转，使其变为升序（最小字典序）。

如果找不到 nums[i]，说明整个数组是递减的，直接将其反转为升序即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        # Step 1: 从右往左找到第一个下降点
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        if i >= 0:  # 存在下降点
            # Step 2: 找到比 nums[i] 大的最小值
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            # 交换 nums[i] 和 nums[j]
            nums[i], nums[j] = nums[j], nums[i]

        # Step 3: 反转 nums[i+1:] 使其变为升序
        nums[i + 1:] = nums[i + 1:][::-1]

复杂度分析

时间复杂度： $O(n)$，最多遍历数组两次：一次寻找i和j，一次反转后半部分。

空间复杂度： $O(1)$，使用了常数级别的额外空间。

287. Find the Duplicate Number

原题链接

题目描述

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Example 1: 

1
2
Input: nums = [1,3,4,2,2]
Output: 2

Example 2: 

1
2
Input: nums = [3,1,3,4,2]
Output: 3

Example 3: 

1
2
Input: nums = [3,3,3,3,3]
Output: 3

Constraints:

  • 1 <= n <= 10^5
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up:

  • How can we prove that at least one duplicate number must exist in nums?
  • Can you solve the problem in linear runtime complexity?

解题方法

本题同样可以使用「龟兔赛跑」的思想，但我们需要将输入的数组看成链表。

根据题目给出的前提，n + 1 长度的数组存储的数据大小区间在 [1, n] 里，且只有 1 个重复数字。

那么, 我们考虑将数组索引和数组的数值做一个映射关系：
$$
n→f(n)=n→nums[n]
$$
以数组 [1,3,4,2] 为例子，这个映射关系 $n→f(n)$ 为：

  • 0→1 (索引 0 的值为 1)
  • 1→3 (索引 1 的值为 3)
  • 2→4 (索引 2 的值为 4)
  • 3→2 (索引 3 的值为 2)

从数组的索引 0 出发，根据 $f(n)$ 计算出一个数值，将这个值作为新的下标，同样地再用这个函数计算，依次类推，直到下标出界，这样得出一个序列：

$0→1→3→2→4→null$

数组中没有重复数字时，可以发现序列不出现循环，那么数组中如果有重复的数字呢？

以数组 [1,3,4,2,2] 为例，分析序列：
$0→1→3→2→4→2→4→…$

其中 $2→4$ 是一个循环，所以，当数组中出现重复的数时，会产生多对一的映射，就会形成一个“环”。

因此，我们就可以使用龟兔赛跑算法，来解决环形链表问题：

  • 数组中有一个重复整数等价于链表中存在一个环
  • 数组中的重复整数等价于链表的环入口

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # Initialize the slow and fast pointers
        slow = nums[0]
        fast = nums[0]
        
        # Move slow by 1 step and fast by 2 steps
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        
        # Find the start of the cycle
        slow = nums[0]
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        
        return slow

复杂度分析

时间复杂度: $O(n)$

空间复杂度: $O(1)$

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://blog.skyheart.moe/posts/1485f71c/

更新于：2024年11月19日

技巧

评论