力扣爆刷第102天之hot100五连刷96-100

力扣爆刷第102天之hot100五连刷96-100

一、136. 只出现一次的数字

题目链接：https://leetcode.cn/problems/single-number/description/?envType=study-plan-v2&envId=top-100-liked
思路：本题利用数学技巧，利用异或运算，一个数与0异或运算的结果还是它自身，此外，不同异或为1，相同为0，不同数异或会有一些大小变化，再进行相同数异或会减小掉变化。

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int n : nums) {
            res ^= n;
        }
        return res;
    }
}

二、169. 多数元素

题目链接：https://leetcode.cn/problems/majority-element/description/?envType=study-plan-v2&envId=top-100-liked
思路：投票算法，当前数如果重复出现则加1，出现别的数则减1，为0换下一个数。

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0, res = 0;
        for(int n : nums) {
            if(count == 0) {
                res = n;
            }
            count += n == res ? 1 : -1;
        }
        return res;
    }
}

三、75. 颜色分类

题目链接：https://leetcode.cn/problems/sort-colors/description/?envType=study-plan-v2&envId=top-100-liked
思路：3个数要排序，先0和1交换排序，然后再1和2交换排序。

class Solution {
    public void sortColors(int[] nums) {
        int zero = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == 0) {
                int temp = nums[zero];
                nums[zero] = nums[i];
                nums[i] = temp;
                zero++;
            }
        }
        int one = zero;
        for(int i = zero; i < nums.length; i++) {
            if(nums[i] == 1) {
                int temp = nums[one];
                nums[one] = nums[i];
                nums[i] = temp;
                one++;
            }
        }
    }
}

四、31. 下一个排列

题目链接：https://leetcode.cn/problems/next-permutation/description/?envType=study-plan-v2&envId=top-100-liked
思路：求下一个排列，是求下一个最小的大于它的值，基本原理从下图的5， 7， 6， 4处进行寻找，寻找最小的一个大于它的数，自然要从右边开始找，找第一个凹陷处，nums[i] < nums[i+1]，此时i= 5，然后再从右边找第一个大于5 的数，为6，也就是nums[j]>nums[i]，此刻这个6就是最小的一个大于它的数，然后交换，交换后[i, end]为单调递减，然后翻转即可。

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while(i >= 0 && nums[i] >= nums[i+1]) {
            i--;
        }
        if(i >= 0) {
            for(int j = nums.length-1; j >= 0; j--) {
                if(nums[j] > nums[i]) {
                    swap(nums, i, j);
                    break;
                }
            }
        }
        
        reverse(nums, i+1, nums.length-1);
    }

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

    void reverse(int[] nums, int i, int j) {
        while(i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }
}

五、287. 寻找重复数

题目链接：https://leetcode.cn/problems/find-the-duplicate-number/description/?envType=study-plan-v2&envId=top-100-liked
思路：寻找重复数，给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n）。这个是题目的描述，说明最大的数作为索引，也仅仅是数组结尾，所以可以把数组元素和索引建立联系，构建逻辑上的循环数组，和链表上的循环数组一样，使用快慢指针，慢的走一步，快的走两步，相遇就是环的入口，只不过此时拿到的是数组里的数，然后再有一个从起点出发，相遇即可拿到环的入口。

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0;
        slow = nums[slow];
        fast = nums[nums[fast]];
        while(slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        int one = 0;
        while(one != slow) {
            one = nums[one];
            slow = nums[slow];
        }
        return one;
    }
}