阅读量:10
2024/7/15 16:43 力扣 hot100 一刷 over
目录
🌼只出现一次的数字
AC 位运算
3 ^ 2 ^ 2 ^ 6 ^ 6 ==(交换律) 2 ^ 2 ^ 6 ^ 6 ^ 3(相同得 0) == 0 ^ 0 ^ 3 ==(0 异或任何数等于这个数本身) == 3
也就得到了出现一次的数
时间 O(n)，空间 O(1)
class Solution { public: int singleNumber(vector<int>& nums) { int ans = 0; // 0 ^ x == x, 所以初始化为 0 for (auto x : nums) ans ^= x; return ans; } };AC 计算和
通过额外 O(n) 空间的 unordered_set<int>，得到每个元素只出现一次的集合，换算得到结果
时间 O(n)，空间 O(n)
class Solution { public: int singleNumber(vector<int>& nums) { int sum1 = 0, sum2 = 0; // sum1原数组的和, sum2 去重后的和 unordered_set<int> nums2; for (auto x : nums) { nums2.insert(x); sum1 += x; } for (auto x : nums2) sum2 += x; // sum1 - sum2 == sum2 - 出现一次的元素 // 出现一次的元素 == 2*sum2 - sum1 return 2*sum2 - sum1; } };🎂多数元素
AC 摩尔投票
1）核心就是“对拼消耗”
2）采用摩尔投票的方法，候选人 cand_num 初始化为 nums[0]，票数 count 初始化为 1，当遇到相同的元素 count++，遇到不同的 count--
3）当 count == 0，更换候选人 cand_num，count = 1，继续遍历
4）遍历结束后，cand_num 就是多数元素（因为占半数以上）
时间 O(n)，空间 O(1)
class Solution { public: int majorityElement(vector<int>& nums) { int cand_num = nums[0], count = 0; for (auto x : nums) { if (count == 0) { count = 1; cand_num = x; } else count = cand_num == x ? count+1 : count-1; } return cand_num; } };🍫颜色分类
遍历一遍，统计 3 个数的出现次数...
class Solution { public: void sortColors(vector<int>& nums) { int n = nums.size(); int n0 = 0, n1 = 0, n2 = 0; for (auto x : nums) { n0 = (x == 0) ? n0+1 : n0; n1 = (x == 1) ? n1+1 : n1; n2 = (x == 2) ? n2+1 : n2; } for (int i = 0; i < n0; ++i) nums[i] = 0; for (int i = n0; i < n - n2; ++i) nums[i] = 1; for (int i = n0 + n1; i < n; ++i) nums[i] = 2; } }; // 0 1 1 2 2 2🍫下一个排列
坑1：<= 和 >=，因为都要找到比自己小，或者比自己大的，所以 = 的也要跳过
坑2：注意下标 < 0 的问题
时间 O(n)，空间 O(1)
/* 1 5 3 2 --> 2 5 3 1 --> 2 1 3 5 1）逆序遍历, 找到第一个变小的位置 nums[i] = 1 2）逆序遍历, 找到第一个 > nums[i] 的位置, 交换 3）[i+1, n-1] 降序-->升序 */ class Solution { public: void nextPermutation(vector<int>& nums) { int n = nums.size(), i = n - 2; while (i >= 0 && nums[i] >= nums[i + 1]) // >= i--; if (i >= 0) { // 3 2 1 这种降序, 直接跳过 2） int j = n - 1; while (j >= 0 && nums[j] <= nums[i]) // <= 很关键, 否则就不会跳过相同的元素 j--; swap(nums[i], nums[j]); } reverse(nums.begin() + i + 1, nums.end()); } };🥇寻找重复数
AC 快慢指针
Floyd判圈算法/龟兔赛跑算法，图解演示理解及证明。快慢双指针，前后双指针..._图的判环算法-CSDN博客
f 指针一次走 2 步，s 指针一次走 1 步，如果有环，那么 f 和 s 必然相遇。
相遇时，慢指针回到起点，快指针留在相遇点，然后等速一次走 1 步。
再次相遇点，就是环的起点
1）把每个 i 和 nums[i]，想象成一个图，i --> nums[i] 是一条连接 i 和 nums[i] 两个顶点的一条边
2）那么题目 “只有一个重复的整数”，这个整数就是环的入口，因为至少 2 条边指向这个整数
3）
slow每次移动一步，即slow = nums[slow]fast每次移动两步，即fast = nums[nums[fast]]
class Solution { public: int findDuplicate(vector<int>& nums) { int s = 0, f = 0; // 快慢指针 do { s = nums[s]; f = nums[nums[f]]; } while (s != f); // 第一次相遇 s = 0; // slow 回到起点 while (s != f) { s = nums[s]; f = nums[f]; } return f; } };