力扣 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, 所以初始化为 0
        for (auto x : nums)
            ans ^= x;
        return ans;
    }
};

AC  计算和

通过额外 O(n) 空间的 unordered_set，得到每个元素只出现一次的集合，换算得到结果

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

🎂多数元素

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