欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 房产 > 家装 > 力扣 hot100 -- 技巧

力扣 hot100 -- 技巧

2024/11/30 11:32:18 来源:https://blog.csdn.net/csdner250/article/details/140419926  浏览:    关键词:力扣 hot100 -- 技巧

2024/7/15 16:43        力扣 hot100 一刷 over

目录

🌼只出现一次的数字

AC  位运算

AC  计算和

🎂多数元素

AC  摩尔投票

🍫颜色分类

🍫下一个排列

🥇寻找重复数

AC  快慢指针


🌼只出现一次的数字

136. 只出现一次的数字 - 力扣(LeetCode)

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, 所以初始化为 0for (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 - sum1return 2*sum2 - sum1;}
};

🎂多数元素

169. 多数元素 - 力扣(LeetCode)

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

🍫颜色分类

75. 颜色分类 - 力扣(LeetCode)

遍历一遍,统计 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

🍫下一个排列

31. 下一个排列 - 力扣(LeetCode)

坑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());}
};

🥇寻找重复数

287. 寻找重复数 - 力扣(LeetCode)

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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com