算法题要重复刷的

算法

发布日期: 2023-12-09

前言

算法题有一些困难题，需要反复刷

还有一些技巧性题目，比如位运算

还有什么基础数学的那种，

LCR 138. 有效数字 - 力扣（LeetCode）

LCR 170. 交易逆序对的总数 - 力扣（LeetCode）

思路：一看要求onlogn肯定是归并排序

ps：冒泡排序也能做，但是会超时

我的问题在于：你如何知道合并的两个子数组是排序了的

答：其实就是一个归并排序的过程，只不过在处理期间去计算逆序对，因为你最早是从单个数字开始归并，所以肯定是排序了的

但是这一题和链表归并排序还不一样，有点小区别，你得用temp数组覆盖原来的

class Solution {
    int count=0;
    public int reversePairs(int[] nums) {
            this.count=0;
            mergeSort(nums, 0, nums.length-1);
            return count;
    }

    public void mergeSort(int[]nums,int left,int right)
    {
        if(left>=right)
        {
            return;
        }
        int mid=(left+right)/2;

        mergeSort(nums, left, mid);
        mergeSort(nums, mid+1, right);
        merge(nums, left, mid, right);
    }



    public void merge(int []nums,int left,int mid ,int right)//因为这题给的是数组，不是链表
    {
        int[]temp=new int[right-left+1];//所以需要temp数组，然后来覆盖掉排序前的数组
        int i=left;
        int j=mid+1;
        int t =0;
        while (i<=mid&&j<=right) {
            if(nums[i]<=nums[j])
            {
                temp[t++]=nums[i++];
            }else
            {
                count+=mid-i+1;
                temp[t++]=nums[j++];
            }
        }

        while(i<=mid)
        {
            temp[t++]=nums[i++];
        }

        while (j<=right) {
            temp[t++]=nums[j++];
        }

        for(int k=0;k<temp.length;k++)//把原来的数组覆盖掉
        {
            nums[left+k]=temp[k];
        }
        
    }
}

二进制中1的个数_牛客题霸_牛客网 (nowcoder.com)

public int NumberOf1 (int n) {
    // write code here
     int res=0;
     while(n!=0)
     {
        res++;
        n&=(n-1);
     }
     return res;
}

记住：n&(n-1)可以消除用二进制表示的n里面最后一位的1

不用加减乘除做加法_牛客题霸_牛客网 (nowcoder.com)

使用位运算：

异或可以提供两位的非进位信息

与运算可以提供进位信息

这里的操作是把所有的sum位和进位一起处理了

public int encryptionCalculate(int dataA, int dataB) {
    while (dataB!=0) {
        int c=(dataA&dataB)<<1;//进位
        dataA=dataA^dataB;//本位
        dataB=c;
    }
    return dataA;
}

有一说一看不懂

50. Pow(x, n) - 力扣（LeetCode）

思路：分治，快速幂

还要求空间复杂度o1，我操你妈了

快速幂：当n为偶数，那么xn次方等于x n/2次方的平方

n为奇数，还得再乘个x

public double myPow(double x, int n) {
    if(x==0.0f)return 0.0d;
    long b=n;
    double res=1.0;
    if(b<0)//负次方的情况
    {
        x=1/x;
        b=-b;
    }
    while(b>0)
    {
        if((b&1)==1)res*=x;//最后一位是1说明让他是奇数，那么res乘一个x
        x*=x;//x执行平方
        b>>=1;//相当于b/2
    }
    return res;//因为你不停除2最后总会留下一个1，所以直接返回res即可
}

数组中只出现一次的两个数字_牛客题霸_牛客网 (nowcoder.com)

有一说一这个也挺难的，就是把他分类

我们知道如果有只出现一次的一个数字，那么对所有的数字异或，会留下这个只出现一次的数字

现在这里有两个只出现一次的a和b，那么我们全部异或，得到的结果就是a和b的异或

因为a和b不同，那么a和b肯定有一位，不同，就是说a的一位为1，b的一位为0

我们找到这一位，然后按这一位是不是为1进行分类，

然后对有相同性质的分别异或，留下来的就是a和b

知识点：x&-x可以取出二进制x中最低位的那个1，这个要牢记啊！！！

public int[] FindNumsAppearOnce (int[] nums) {
    // write code here
    int xorsum=0;
    for(int num:nums)
    {
        xorsum^=num;
    }
    int lsb=(xorsum==Integer.MIN_VALUE?xorsum:xorsum&(-xorsum));//xorsum是-2147483648的时候变为正数会溢出，因为32位的int正数范围是0~2147483647,而为什么是min.value时，直接返回xorsum呢，因为-2147483638二进制是1000000000，最低位的1其实就是她自己
    int t1=0,t2=0;
    for(int num:nums)
    {
        if((lsb&num)!=0)
        {
            t1^=num;
        }else
        {
            t2^=num;
        }
    }
    if(t1>t2)
    {
        return new int[]{t2,t1};
    }
    return new int[]{t1,t2};
}

LCR 138. 有效数字 - 力扣（LeetCode）

这题目太他妈恶心了，老子按照宫水三叶的题解来写

class Solution {
    //思路：就是宫水三叶的
    public boolean validNumber(String s) {
        int n=s.length(),l=0,r=n-1;
        while(l<n&&s.charAt(l)==' ')l++;
        while(r>=0&&s.charAt(r)==' ')r--;
        if(l>r)return false;
        s=s.substring(l, r+1).replace('e', 'E');
        n=s.length();

        int idx=0;
        while(idx<n&&s.charAt(idx)!='E')idx++;//走到有E的地方
        if(idx==n){
            return check(s,true);//说明没E，那么就整个串判断
        }else
        {
            return check(s.substring(0,idx),true)&&check(s.substring(idx+1),false);
        }
    }

    boolean check(String s,boolean isDecimal)
    {
        if(s.equals(".")||s.equals(""))return false;
        int n=s.length();
        for(int i=0,cnt=0;i<n;i++)
        {
            char c=s.charAt(i);
            if(c=='+'||c=='-')
            {
                if(i!=0||i==n-1)return false;//符号没出现在对的地方,返回false
            }else if(c=='.')
            {
                if(!isDecimal)return false;//右半部分只能是整数，如果右半部分有了.说明错了
                if(cnt!=0)return false;//cnt是小数点的个数，如果已经出现过小数点了，那么就错了！
                boolean a=i-1>=0&&Character.isDigit(s.charAt(i-1));
                boolean b=i+1<n&&Character.isDigit(s.charAt(i+1));
                if(!(a||b))return false;//小数点左右至少得有一位是数字
                cnt++;
            }else if(!Character.isDigit(c))return false;//又不是符号又不是数字又不是小数点，直接返回false
        }
        return true;
    }
}

路径总和3

233. 数字 1 的个数 - 力扣（LeetCode）

困难题，恶心的要死啊

反正记住了，那就拿23x4举例子，自己推吧

public int countDigitOne(int n) {
        //cur=0,那么等于高*digit
        //cur=1那么等于高位的加上自己的1在加上地位的数字
        //cur=2,3,....9那么等于高位+1乘digit，因为你这一位本身也可以取1了
        int digit=1;
        int low=0;
        int cur=n%10;//一开始是个位，所以对10取余
        int high=n/10;
        int res=0;
        while(high!=0||cur!=0)
        {
            if(cur==0)res+=high*digit;
            else if(cur==1)res+=high*digit+low+1;
            else res+=(high+1)*digit;
            low+=cur*digit;//将cur加入low
            cur=high%10;//下一轮的cur是本轮high的最低位
            high/=10;
            digit*=10;
        }
        return res;
}