力扣刷题Hot100

今天有点忙...选了个HOT题目较少的章节刷/

1. 136. 只出现一次的数字 - 力扣（LeetCode）
2. 169. 多数元素 - 力扣（LeetCode）
3. 75. 颜色分类 - 力扣（LeetCode）
4. 31. 下一个排列 - 力扣（LeetCode）
5. 287. 寻找重复数 - 力扣（LeetCode）

只出现一次的数字

经典异或题

当且仅当两个输入值不同时，异或运算输出为真（1），否则输出为假（0），即“同为 0，异为 1”。

▼
java
复制代码
class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int x : nums){
            ans ^= x;
        }
        return ans;
    }
}

多数元素

推荐题解：169. 多数元素 - 力扣（LeetCode）

个人理解：使用投票法，假设我们已知某个数是众数了，那么我们指定一个投票规则，遍历数组，但钱元素是众数票数+1

否则票数-1，那么理论上票数最终会是大于0的。那么现在问题是如何确定众数？

同样利用票数的规则，如果我们遍历到某个数，发现当前票数==0，意味着已经出现众数了，并且，众数后续还会出现，答案也肯定能在后面能找到。那么我们可以将当前的元素假设为众数，并用一个变量记录，后续在投票，后面遍历的元素等于假设的众数，票数+ 1.否则 - 1；

如果当前票数<0，意味着，前面非众数数量大于众数的数量；

0 则意味着，已经出现众数了，择当前记录的假设的众数变量就是众数

▼
java
复制代码
class Solution {
    public int majorityElement(int[] nums) {
        int x = 0;
        int votes = 0;
        for (int c : nums){
            if (votes == 0){
                x = c;
            }
            votes += x == c ? 1 : -1;
        }
        return x;
    }
}

颜色分类

经典三色问题

▼
java
复制代码
class Solution {
    public void sortColors(int[] nums) {
        int n0 = 0;
        int n1 = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++){
            int temp = nums[i];
            nums[i] = 2;
            if (temp < 2){
                nums[n1 ++] = 1;
            }
            if (temp < 1){
                nums[n0 ++] = 0;
            }
        }
        return;
    }
}

下一个排列

推荐题解：31. 下一个排列 - 力扣（LeetCode）

▼
java
复制代码
class Solution {
    private int[] nums;
    public void nextPermutation(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        if (n == 0 || n == 1){
            return;
        }
        for (int i = n - 2; i >= 0; i --){
            if (nums[i] < nums[i + 1]){
                for (int j = n - 1; j > i; j--){
                    if (nums[j] > nums[i]){
                        swap(i,j);
                        rserve(i + 1, n -1);
                        return;
                    }
                }
            }
        }
        rserve(0,n-1);
        return;
    }


    private void swap(int i ,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        return;
    } 

    private void rserve(int i , int j){
        while (i < j){
            swap(i , j);
            i ++;
            j --;
        }
        return;
    }
}

寻找重复数字

暴力map能做，但是有个更有意思的做法，这个思路跟缺失的第一个正数那道题很像。

核心思路：环形链表

▼
java
复制代码
class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[0];

        while (true){
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast){
                fast = nums[0];
                while (slow != fast){
                    fast = nums[fast];
                    slow = nums[slow];
                }
                return fast;
            }
        }
    }
}