当前位置：首页 > news >正文

leetcode hot100：解题思路大全

news 来源：原创 2025/7/20 18:21:21

因为某大厂的算法没有撕出来，怒而整理该贴。只有少数题目有AC代码，大部分只会有思路或者伪代码。

技巧

只出现一次的数字

题目

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

1 <= nums.length <= 3 * 10^4
-3 * 10^4 <= nums[i] <= 3 * 10^4
除了某个元素只出现一次以外，其余每个元素均出现两次。

思路

我们可以利用异或运算（XOR）的特性：

异或的性质：
a ^ a = 0（相同数字异或结果为 0）
a ^ 0 = a（任何数字与 0 异或仍是它本身）
异或满足交换律和结合律，即 a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b。

因此，对整个数组进行异或运算，最终结果就是只出现一次的数字。

代码

class Solution:def singleNumber(self, nums: List[int]) -> int:res = 0for num in nums:res ^= numreturn res

多数元素

题目

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

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

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

思路1：排序

假设整个数组元素个数为n，因为多数元素的个数一定大于n//2。
所以排序后，下标为n//2的元素一定是多数元素。
因为假设排序后的数组构成如下：

前x个比多数元素小的元素+k个多数元素+后y个比多数元素大的元素
其中x一定小于n//2，y一定小于n//2，不然就和多数元素的定义违背了
所以构成就是
x+k+y=n
其中x<n//2，y<n//2，k>n//2
画线段长度，找到中间的点，那么一定是在k那部分出现的。

代码复杂度为O(nlogn)，因为python底层的nums.sort()时间复杂度是这个。
空间复杂度为O(1)（原地排序）或O(n)（非原地排序）。

代码1：排序

class Solution:def majorityElement(self, nums: List[int]) -> int:nums.sort()return nums[len(nums)//2]

0ms，击败100.00%

思路2：候选人算法

维护一个候选人数字和候选人数字对应的选票，然后遍历数组。
如果遍历的当前数字和候选人数字不同的话，候选人数字对应的选票-1.
如果遍历的当前数字和候选人数字相同的话，候选人数字对应的选票+1.
如果选票为0，候选人数字被替代成当前数字。

这个算法正确是因为多数元素的选票最后一定>=0，所以最后候选人数字一定是多数数字。时间复杂度为O(n)，空间复杂度为O(2)

代码2：候选人算法

class Solution:def majorityElement(self, nums: List[int]) -> int:candidate = nums[0]vote = 1for i in range(1, len(nums)):if candidate != nums[i]:vote -= 1else:vote += 1if vote == 0:candidate = nums[i]vote = 1return candidate

6ms，击败54.58%。
明明时间复杂度更低，但是实际运行时间更长hhh

颜色分类

思路：荷兰国旗解法/三指针法/三分类问题

荷兰国旗问题就是该题目的问题。
三指针法适用于该类的所有变种，就是需要划分为三个部分
＜x和＝x和＞x的三个部分的问题。

我们维护三个指针：

left：0的右边界（指向最终数组最后一个0的下标+1）
right：2的左边界（指向最终数组第一个2的下标-1）
cur：当前遍历的数字。

初始时left为0，cur为0，right为len(nums)-1，然后随着cur的向右遍历，
left逐步向右扩大，right逐步向左扩大，直到我们cur超过right指针，表示所有的0和2都已经排序好，那么相应地，1也会排序好。

注意：当nums[right]==2时，我们不应该有cur+=1。
即right和cur位置进行交换，因为right位置的数字可能是0，1，2。
所以cur不能向右移动，因为需要二次检查。
而如果nums[cur]==0，那么就是left和cur位置进行交换。
又因为left永远指向第一个非0位置，并且left永远在cur的左边。
所以left位置都是排列好的数字，所以left位置只会是1.所以不需要二次检查。
可以通过[1,2,0]例子来查看。

代码

class Solution:def sortColors(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""left, cur = 0, 0right = len(nums)-1while cur <= right:if nums[cur] == 0 :nums[left], nums[cur] = nums[cur], nums[left]left += 1cur += 1elif nums[cur] == 2:nums[right], nums[cur] = nums[cur], nums[right]right -= 1"""注意这里不能有cur += 1。right和cur位置进行交换，因为right位置的数字可能是0，1，2所以cur不能向右移动，因为需要二次检查。而如果nums[cur]==0，那么就是left和cur位置进行交换又因为left永远指向第一个非0位置+left永远在cur的左边，所以left位置都是排列好的数字所以left位置只会是1.所以不需要二次检查。可以通过[1,2,0]例子来查看。           """else:cur += 1return

0ms，击败100.00%

下一个排列

题目

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。

必须原地修改，只允许使用额外常数空间。

提示：
1 <= nums.length <= 100
0 <= nums[i] <= 100

思路

错误思路

最开始我想的思路是：

从左到右遍历数组，对每个数找到其右边第一个大于它的数。- 找得到，冒泡到当前数的前面，并进行输出- 找不到，继续向右遍历下一个数如果直到遍历完所有数，都找不到，则直接输出升序排列的数组。为此我们可以预处理整个数组，得到rightMax，如果rightMax都是-1，
则意味着直到遍历完所有的数，都会找不到右边更大的数，那么直接输出升序排列的数组。

但实际上这样的思路是错的，归根结底错在从左到右遍历这上面。
因为越左的数权重越大，越右的数权重越小，我们要找的下一个更大的字典序排列应该是尽可能修改越右的数的。

其次，错误的点在于，不应该找右边第一个大于它的数。而应该找右边第一个大于它且最接近它的数。

譬如对于例子1,3,2，按照我的思路一开始修改的是
3,1,2，但实际上对于这个例子的正确答案应该是2,1,3。

正确思路

正确的思路应该是，我们将整个数组根据上升/下降趋势划分为不同的区间。
如果排除掉题目的特殊规定，即如果找不到下一个区间，那么将字典序最小的区间（完全上升）认为是其下一个区间，那么我们发现：
如果一个区间是上升的（从左往右看），那么它存在字典序更大的下一个区间。
如果一个区间是下降的（从左往右看），那么它不会存在字典序更大的下一个区间。

所以我们如果要找到题目的下一个区间，首先我们得找到从左往右看的最后一个上升区间，修改它，修改的权重小，如果是从左往右看的第一个上升区间的话，修改的权重大。
所以反过来，就是我们要找到从右往左看的第一个下降区间，我们要修改它。
那么具体修改这个区间的哪个数呢？同样的，根据我们应该修改权重最小的那个数，那么就是这个区间的右边界这个数（从左往右看）。
所以准确来说，我们要修改的是，从右往左看的第一个下降点。
具体应该怎么修改呢？刚刚也有提到，从左往右看的话，对于要修改的数，不应该找右边第一个大于它的数，而应该找右边第一个大于它且最接近它的数。
那么在这里，从右往左看的话，我们需要找到下降点右边第一个大于它且最接近它的数，又因为这个数肯定处在上升区间（从右往左看），所以从右往左遍历到的第一个大于下降点的数就是了。
我们交换这两个数，之后从左往右看，反转下降点右边的下降区间，将其都变为上升区间，从而保证了字典序最小。

看不懂的话看一下这一版deepseek的解释：

排列的“递增”和“递减”趋势：
- 如果我们从后向前看，排列的末尾部分通常是降序的（比如 […, 3, 2, 1]），这时候已经是这部分的最大排列，无法再增大。
- 如果末尾部分是升序的（比如 […, 1, 2, 3]），我们可以通过交换来生成更大的排列。
关键点：第一个下降的位置：
- 从后向前遍历，找到第一个满足 nums[i] < nums[i+1] 的位置 i。这意味着 nums[i] 是可以增大的，而 nums[i+1…n-1] 是降序的（即这部分已经最大，无法再增大）。
- 例如，[1, 3, 2] 中 i=0（nums[0]=1 < nums[1]=3），而 nums[1…2]=[3,2] 是降序的。
交换和反转：
为了生成最小的更大排列，我们需要：
- 在 nums[i+1…n-1] 中找到最小的比 nums[i] 大的数 nums[j]（因为这部分是降序的，所以从后向前找第一个比 nums[i] 大的数即可）。
- 交换 nums[i] 和 nums[j]，这样 nums[i] 变大了，但 nums[i+1…n-1] 仍然是降序的。
- 反转 nums[i+1…n-1]，使其变成升序（即最小的排列），从而保证新排列是严格的下一个排列。

寻找重复数

题目

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有一个重复的整数，返回这个重复的数。

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

提示：

1 <= n <= 10^5
nums.length == n + 1
1 <= nums[i] <= n
nums 中只有一个整数出现两次或多次，其余整数均只出现一次

进阶：

如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

思路

最关键点在于1 <= nums[i] <= n，所以将数组视为一个链表，其中 nums[i] 表示节点 i 指向的下一个节点是 nums[i]。由于存在重复数字，链表一定存在环，且环的入口就是重复的数字。
确定这个链表不会存在独立节点的关键点就是因为数字范围是 [1, n]，而数组长度是 n + 1，因此可以将 nums[i] 看作指针。
那么就转换为了快慢指针问题。

第一阶段：检测环：
用快慢指针，慢指针每次走一步（slow = nums[slow]），快指针每次走两步（fast = nums[nums[fast]]）。直到快慢指针相遇。
第二阶段：找到环的入口（重复数字）：
将快指针重置到起点（0），然后快慢指针每次都走一步。
再次相遇的点就是环的入口（重复数字）。

技巧