每日算法--2023.2.28

1.剑指offer 56 数组中数字出现的次数2

class Solution {
    public int singleNumber(int[] nums) {
        int[] cnt = new int[32];
        int n = nums.length;
        for(int i = 0;i<n;i++){
            int cur = nums[i], t = 0;
            while(cur!=0){
                if((cur&1)== 1){
                    cnt[t]++;
                }
                cur = cur>>1;
                t++;
            }
        }
        int res = 0;
        for(int i = 0;i<32;i++){
            if(cnt[i]%3 == 1){
                res += (1<<i);
            }
        }
        return res;

    }
}

2.剑指offer56 --数组中出现的次数1

class Solution {
    public int[] singleNumbers(int[] nums) {
        int n = nums.length, sum = 0;
        for(int i = 0;i<n;i++){
            sum ^=nums[i];
        }
        int cnt = 0;
        while(sum!=0){
            if((sum &1) == 1){
                break;
            }
            sum = sum>>1;
            cnt++;
        }
         int res1 = 0, res2 = 0;
         for(int i = 0;i<n;i++){
             if((nums[i] & (1<<cnt)) == 0){
                 res1 ^= nums[i]; 
             }else{
                 res2 ^= nums[i];
             }
         }  
         return new int[]{res1,res2}; 
    }
}

3.剑指offer59 -- 滑动窗口的最大值

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> queue = new LinkedList<>();
        int[] res = new int[n-k+1];
        int t = 0;
        for(int i = 0, j = 0;j<n;j++){
            int cur = nums[j];
            while(!queue.isEmpty()&&cur>queue.getLast()){
                queue.removeLast();
            }
            queue.addLast(cur);
            if(j-i+1>k){
                int temp = queue.getFirst();
                if(temp == nums[i]){
                    queue.removeFirst();
                }
                i++;
            }
            if(j-i+1 == k){
                res[t++] = queue.getFirst();
            }
        }
        return res;
    }
}

4.剑指offer64

class Solution {
    public int sumNums(int n) {
        return n == 0?0:sumNums(n-1) + n;
    }
}

5.剑指offer 66 -- 构建乘积数组

class Solution {
    //前缀积与后缀积
    public int[] constructArr(int[] a) {
        int n = a.length;
        int[] preorderNum = new int[n+2];
        int[] postorderNum = new int[n+2];
        preorderNum[0] = 1;postorderNum[n+1] = 1;
        for(int i = 1;i<=n;i++){
            preorderNum[i] = preorderNum[i-1]*a[i-1];
        }
        for(int i = n;i>=1;i--){
            postorderNum[i] = postorderNum[i+1] * a[i-1];
        }
        int[] res = new int[n];
        for(int i = 0;i<n;i++){
            res[i] = preorderNum[i] * postorderNum[i+2]; 
        } 
        return res;
    }
}