136.只出现一次的数字
🎭 题目小剧场
想象你在一个派对上，每个人都成双成对地出现，只有一个人是孤单的。你的任务是在嘈杂的人群中，快速找出那个落单的人。这就像在一堆重复的数字中，找到唯一一个只出现一次的数字！
💡 解题思路
位运算解法（异或操作）：
1.利用异或运算的性质：
2.将所有数字进行异或运算，最终结果就是只出现一次的数字
3.成对出现的数字会相互抵消为0，最后剩下的就是目标数字
🐍 Python代码实现
class Solution: def singleNumber(self, nums: List[int]) -> int: """ 位运算解法 - 时间复杂度O(n)，空间复杂度O(1) """ result = 0 for num in nums: result ^= num return result
📊 复杂度分析
时间复杂度：O(n) - 只需要遍历一次数组
空间复杂度：O(1) - 只使用常数额外空间
🌟 算法精髓
这个算法的巧妙之处在于"异或性质"。利用异或运算的独特性质，让成对的数字自动抵消，最终"剩下"的就是我们寻找的数字。
🎯 小白友好贴士
result = 0 初始化结果为0
for num in nums 遍历所有数字
result ^= num 进行异或运算
return result 返回最终结果
🔍 算法执行过程示例
示例：nums = [4, 1, 2, 1, 2]初始：result = 0第1步：num = 4 result = 0 ^ 4 = 4第2步：num = 1 result = 4 ^ 1 = 5第3步：num = 2 result = 5 ^ 2 = 7第4步：num = 1 result = 7 ^ 1 = 6第5步：num = 2 result = 6 ^ 2 = 4结束：return result = 4 ✅验证：只有4出现一次，其他数字都出现两次
🎯 核心思想总结
异或性质：利用异或运算的独特性质
自动抵消：成对数字会相互抵消为0
交换结合：异或运算满足交换律和结合律
一次遍历：只需遍历数组一次即可得到结果
169.多数元素
🎭 题目小剧场
想象你在班级投票选班长，每个同学都投一票。你的任务是快速找出得票最多的候选人，而且你知道这个人的得票数超过了半数。这就像在一堆数字中，找到那个出现次数超过一半的数字！
💡 解题思路
摩尔投票法（Boyer-Moore Voting Algorithm）：
1.核心思想：利用"对拼消耗"的原理
2.设置一个候选者和计数器
3.遍历数组：
如果计数器为0，设置当前元素为新的候选者
如果当前元素等于候选者，计数器加1
如果当前元素不等于候选者，计数器减1
4.最后剩下的候选者就是多数元素
🐍 Python代码实现
class Solution: def majorityElement(self, nums: List[int]) -> int: """ 摩尔投票法 - 时间复杂度O(n)，空间复杂度O(1) """ candidate = None count = 0 for num in nums: if count == 0: candidate = num count = 1 elif num == candidate: count += 1 else: count -= 1 return candidate
📊 复杂度分析
时间复杂度：O(n) - 只需要遍历一次数组
空间复杂度：O(1) - 只使用常数额外空间
🌟 算法精髓
这个算法的巧妙之处在于"对拼消耗"。不同元素相互抵消，由于多数元素出现次数超过一半，它最终会"胜出"成为候选者。
🎯 小白友好贴士
🔍 算法执行过程示例
示例：nums = [2, 2, 1, 1, 1, 2, 2]初始：candidate = None, count = 0第1步：num = 2 count == 0，设置候选者 candidate = 2, count = 1第2步：num = 2 num == candidate，计数加1 candidate = 2, count = 2第3步：num = 1 num != candidate，计数减1 candidate = 2, count = 1第4步：num = 1 num != candidate，计数减1 candidate = 2, count = 0第5步：num = 1 count == 0，设置候选者 candidate = 1, count = 1第6步：num = 2 num != candidate，计数减1 candidate = 1, count = 0第7步：num = 2 count == 0，设置候选者 candidate = 2, count = 1结束：return candidate = 2 ✅验证：2出现4次，超过总数7的一半
🎯 核心思想总结
对拼消耗：不同元素相互抵消
多数优势：多数元素数量超过一半，最终胜出
一次遍历：只需遍历数组一次
常数空间：不需要额外存储空间
75.颜色分类
🎭 题目小剧场
想象你有一堆红、白、蓝三种颜色的小球，需要把它们按红、白、蓝的顺序排列。这就像荷兰国旗的三种颜色，所以这个问题也叫"荷兰国旗问题"。你的任务是在一次遍历中完成这个排序！
💡 解题思路
三指针法（荷兰国旗算法）：
1.设置三个指针：
low：指向下一个0应该放置的位置
mid：当前遍历的位置
high：指向下一个2应该放置的位置
2.遍历规则：
如果nums[mid] == 0：交换nums[low]和nums[mid]，然后low++，mid++
如果nums[mid] == 1：只需要mid++
如果nums[mid] == 2：交换nums[mid]和nums[high]，然后high--（注意：mid不移动）
3.当mid > high时，排序完成
🐍 Python代码实现
class Solution: def sortColors(self, nums: List[int]) -> None: """ 三指针法 - 时间复杂度O(n)，空间复杂度O(1) """ low = 0 mid = 0 high = 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] == 2 nums[mid], nums[high] = nums[high], nums[mid] high -= 1
📊 复杂度分析
时间复杂度：O(n) - 只需要遍历一次数组
空间复杂度：O(1) - 只使用常数额外空间
🌟 算法精髓
这个算法的巧妙之处在于"分区思想"。通过三个指针将数组分为四个区域，确保每次操作都维持分区的不变性，最终实现一次遍历完成排序。
🎯 小白友好贴士
🔍 算法执行过程示例
示例：nums = [2, 0, 2, 1, 1, 0]初始：low = 0, mid = 0, high = 5 nums = [2, 0, 2, 1, 1, 0]第1步：mid = 0, nums[0] = 2 nums[mid] == 2，交换nums[0]和nums[5] nums = [0, 0, 2, 1, 1, 2] high = 4, mid = 0第2步：mid = 0, nums[0] = 0 nums[mid] == 0，交换nums[0]和nums[0] nums = [0, 0, 2, 1, 1, 2] low = 1, mid = 1第3步：mid = 1, nums[1] = 0 nums[mid] == 0，交换nums[1]和nums[1] nums = [0, 0, 2, 1, 1, 2] low = 2, mid = 2第4步：mid = 2, nums[2] = 2 nums[mid] == 2，交换nums[2]和nums[4] nums = [0, 0, 1, 1, 2, 2] high = 3, mid = 2第5步：mid = 2, nums[2] = 1 nums[mid] == 1，mid++ low = 2, mid = 3第6步：mid = 3, nums[3] = 1 nums[mid] == 1，mid++ low = 2, mid = 4结束：mid = 4 > high = 3，排序完成 nums = [0, 0, 1, 1, 2, 2] ✅
🎯 核心思想总结
分区思想：将数组分为四个区域
三指针协作：low、mid、high各司其职
不变性维护：每次操作都保持分区性质
一次遍历：高效的O(n)时间复杂度
31.下一个排列
🎭 题目小剧场
想象你在破解一个数字密码锁，你需要找到比当前密码大的"下一个"密码，但要是所有可能组合中"最小"的那个。这就像在字典中查找一个单词的下一个词条，要找比它大但最接近的那个！
💡 解题思路
标准算法（两步变换）：
1.第一步：找到下降点
2.第二步：找到交换点并交换
3.第三步：反转后缀
🐍 Python代码实现
class Solution: def nextPermutation(self, nums: List[int]) -> None: """ 标准算法 - 时间复杂度O(n)，空间复杂度O(1) """ n = len(nums) if n <= 1: return # 第一步：找到下降点 i = n - 2 while i >= 0 and nums[i] >= nums[i + 1]: i -= 1 # 第二步：找到交换点并交换 if i >= 0: j = n - 1 while nums[j] <= nums[i]: j -= 1 nums[i], nums[j] = nums[j], nums[i] # 第三步：反转后缀 left, right = i + 1, n - 1 while left < right: nums[left], nums[right] = nums[right], nums[left] left += 1 right -= 1
📊 复杂度分析
🌟 算法精髓
这个算法的巧妙之处在于"局部调整"。通过找到第一个需要改变的位置，进行最小化的调整，然后重置后面的部分，确保得到的是"下一个"排列。
🎯 小白友好贴士
i = n - 2 从倒数第二个元素开始
while i >= 0 and nums[i] >= nums[i + 1] 找到下降点
if i >= 0 如果找到下降点才需要交换
while nums[j] <= nums[i] 找到第一个大于nums[i]的元素
nums[i], nums[j] = nums[j], nums[i] 交换元素
while left < right 反转后缀部分
🔍 算法执行过程示例
示例：nums = [1, 2, 3, 6, 5, 4]初始：nums = [1, 2, 3, 6, 5, 4]第一步：找到下降点 i = 4: nums[4] = 5 >= nums[5] = 4，继续 i = 3: nums[3] = 6 >= nums[4] = 5，继续 i = 2: nums[2] = 3 < nums[3] = 6，找到下降点 i = 2第二步：找到交换点并交换 j = 5: nums[5] = 4 > nums[2] = 3，找到交换点 j = 5 交换 nums[2] 和 nums[5] nums = [1, 2, 4, 6, 5, 3]第三步：反转后缀 反转 nums[3:] = [6, 5, 3] 反转后：[3, 5, 6]最终结果：[1, 2, 4, 3, 5, 6] ✅
🎯 核心思想总结
寻找突破点：从后向前找到第一个可以增加的位置
最小化增加：找到刚好大于突破点的数字进行交换
重置后缀：将后面的部分重置为最小排列
原地操作：所有操作都在原数组上进行
287.寻找重复数
🎭 题目小剧场
想象你在一个环形跑道上跑步，由于跑道设计有问题，你最终会回到起点。这个问题就像在一条数字链中寻找那个让你"循环"的重复数字。题目要求不能修改数组，而且只能用O(1)的额外空间，这让问题变得很有挑战性！
💡 解题思路
快慢指针法（Floyd's Tortoise and Hare）：
1.第一阶段：找到相遇点
慢指针每次走一步，快指针每次走两步
由于存在重复数字，它们一定会在环中相遇
2.第二阶段：找到入口点
将一个指针重置到起点
两个指针都每次走一步
它们再次相遇的位置就是重复数字
🐍 Python代码实现
class Solution: def findDuplicate(self, nums: List[int]) -> int: """ 快慢指针法 - 时间复杂度O(n)，空间复杂度O(1) """ # 第一阶段：找到相遇点 slow = nums[0] fast = nums[0] while True: slow = nums[slow] # 慢指针走一步 fast = nums[nums[fast]] # 快指针走两步 if slow == fast: break # 第二阶段：找到入口点 slow = nums[0] # 重置慢指针到起点 while slow != fast: slow = nums[slow] # 每次走一步 fast = nums[fast] # 每次走一步 return slow
📊 复杂度分析
时间复杂度：O(n) - 两个阶段都是线性时间
空间复杂度：O(1) - 只使用常数额外空间
🌟 算法精髓
这个算法的巧妙之处在于将数组转换为"链表"，利用快慢指针在环中相遇的原理，找到循环的入口点，这个入口点就是重复的数字。
🎯 小白友好贴士
🔍 算法执行过程示例
示例：nums = [1, 3, 4, 2, 2]将数组视为链表：0 → 1 → 3 → 2 → 4 → 2 → 4 → 2 → ...第一阶段：找到相遇点 初始：slow = 0, fast = 0 第1轮： slow = nums[0] = 1 fast = nums[nums[0]] = nums[1] = 3 slow = 1, fast = 3 第2轮： slow = nums[1] = 3 fast = nums[nums[3]] = nums[2] = 4 slow = 3, fast = 4 第3轮： slow = nums[3] = 2 fast = nums[nums[4]] = nums[2] = 4 slow = 2, fast = 4 第4轮： slow = nums[2] = 4 fast = nums[nums[4]] = nums[2] = 4 slow = 4, fast = 4找到相遇点：4第二阶段：找到入口点重置：slow = 0, fast = 4 第1轮： slow = nums[0] = 1 fast = nums[4] = 2 slow = 1, fast = 2 第2轮： slow = nums[1] = 3 fast = nums[2] = 4 slow = 3, fast = 4 第3轮： slow = nums[3] = 2 fast = nums[4] = 2 slow = 2, fast = 2找到入口点：2结束：return 2 ✅
🎯 核心思想总结
链表转换：将数组索引和值视为链表结构
循环检测：使用快慢指针检测循环
入口定位：通过数学原理找到循环入口
空间优化：不使用额外空间，满足题目要求
10个月宝宝每天需要喝多少奶粉？