力扣-Hot100-技巧【算法学习day.31】

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.只出现一次的数字

题目链接:136. 只出现一次的数字 - 力扣（LeetCode）

题面:

基本分析：用异或，当两数相同时，异或结果是0，而0和A异或答案是A，由此线性遍历数组，记录异或结果，最终结果则为出现一次的元素

代码:

class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        int l = 1;
        int ans = 0;
        int n = nums.length;
        if(n==0)return 0;
        if(n==1)return nums[0];
        while(l<n){
            if(nums[l]!=nums[l-1]){
                ans = nums[l-1];
                break;
            }
            l+=2;
        }
        if(nums[n-1]!=nums[n-2])ans = nums[n-1];
        return ans;
    }
}

2.多数元素

题目链接:169. 多数元素 - 力扣（LeetCode）

题面:

基本分析:可以采用哈希表，也可以排序后取索引为n/2的元素，还可以采用摩尔投票，详细可以看力扣的大佬题解

代码:

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        int n = nums.length;
        int flag = n/2;
        int ans = 0;
        for(int a:nums){
            map.put(a,map.getOrDefault(a,0)+1);
            if(map.get(a)>flag){
                ans = a;
                break;
            }
        }
        return ans;
    }
}

3.颜色分类

题目链接:75. 颜色分类 - 力扣（LeetCode）

题面:

基本分析:可以采用双指针前后遍历进行排序，我采取的是一个稍微复杂点的双指针

代码:

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans,1);
        int l = 0;
        int r = n-1;
        for(int i = 0;i<n;i++){
            if(nums[i]==1)continue;
            if(nums[i]==0)ans[l++] = 0;
            else if(nums[i]==2)ans[r--]=2;
        }
        for(int i =0;i<n;i++)nums[i]=ans[i];
    }
}

4.下一个排列

题目链接:31. 下一个排列 - 力扣（LeetCode）

题面:

基本分析:想找到下一个排列，可以从后往前遍历，找到第一个小于最后一个元素的数，记其索引为k，然后交换，由于最后一个数更大，他被调到高位后整个排列就更大了，为了让这个排序尽可能小，就把k之后的数从小到大排序

代码:

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length, k = n - 1;
        while (k - 1 >= 0 && nums[k - 1] >= nums[k]) k--;
        if (k == 0) {
            reverse(nums, 0, n - 1);
        } else {
            int u = k;
            while (u + 1 < n && nums[u + 1] > nums[k - 1]) u++;
            swap(nums, k - 1, u);
            reverse(nums, k, n - 1);
        }
    }
    void reverse(int[] nums, int a, int b) {
        int l = a, r = b;
        while (l < r) swap(nums, l++, r--);
    }
    void swap(int[] nums, int a, int b) {
        int c = nums[a];
        nums[a] = nums[b];
        nums[b] = c;
    }
}

5.寻找重复数

题目链接:287. 寻找重复数 - 力扣（LeetCode）

题面:

基本分析:采用循环链表，详细看大佬题解，非常巧妙

代码:

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