算法题要重复刷的

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

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

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

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即可
}

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

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

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