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;
}
};
