我要评论2024/7/15 16:43 力扣 hot100 一刷 over
目录
🌼只出现一次的数字
ac 位运算
时间 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)，空间 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 摩尔投票
时间 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;
}
};🍫颜色分类
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🍫下一个排列
时间 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 快慢指针
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;
}
};
发表评论