[数据结构与算法]剑指offer 2021/8/5

41. 数据流中的中位数

代码：

创建一个大顶堆一个小顶堆，大顶堆中保存较大的元素，小顶堆中保存较小的元素。

class MedianFinder {

    /** initialize your data structure here. */
    Queue<Integer> A,B;
    public MedianFinder() {
        //小顶堆（默认），且堆中保存较大的元素
        A=new PriorityQueue<>();
        //大顶堆（用lambda表达式实现接口），且堆中保存较小的元素
        B=new PriorityQueue<>((a,b)->b-a);
    }
    
    public void addNum(int num) {
        //A、B中元素数量不同，则向B中添加元素（即先向A中添加元素，然后将A的堆顶元素加入到B中）
        //这样可以保证B中始终存放较小的元素
        if(A.size()!=B.size()){
            A.add(num);
            B.add(A.poll());
        }
        //A、B中数量相同，则向A中添加元素（即现象B中添加元素，然后将B的堆顶元素加入到A中）
        //这样可以保证A中始终存放较大的元素
        else{
            B.add(num);
            A.add(B.poll());
        }
    }
    
    public double findMedian() {
        //A、B中元素数量不等，则返回A的堆顶元素，否则，返回A、B堆顶元素之和除以2
        //注意除数一定要写成2.0，否则计算会出错！
        return A.size()!=B.size() ? A.peek() : (A.peek()+B.peek())/2.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

注意：

PriorityQueue()默认是一个小顶堆

28. 对称的二叉树

代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        //当root为null时返回true，否则，递归遍历左右子树
        return root==null ? true : recur(root.left, root.right);
    }
    boolean recur(TreeNode L, TreeNode R){
        //如果左右子树为空，返回true
        if(L==null && R==null)  return true;
        //如果只有左子树/右子树为空，或者左右子树值不相等，返回false
        if(L==null || R==null || L.val!=R.val)
            return false;
        //判断L的左子树和R的右子树，以及L的右子树和R的左子树是否对称
        return recur(L.left, R.right) && recur(L.right, R.left);
    }
}

56 - II. 数组中数字出现的次数 II

代码：

class Solution {
    public int singleNumber(int[] nums) {
        int[] count = new int[32];
        int res=0;
        //计算所有数字各个位之和
        //对每一个数字进行计数
        for(int i = 0; i < nums.length; ++i){
            //对每一位进行计数
            for(int j = 0; j < 32; ++j){
                count[j] += nums[i] & 1;
                nums[i] >>>= 1;
            }
        }
        //将每一位count的值模三
        for(int i = 0; i < 32; ++i){
            count[i] %= 3;
        }
        //将count的值赋给res的各个位
        for(int i = 0; i < 32; ++i){
            res <<= 1;
            res |= count[31-i];
        }
        return res;
    }
}

注意

1.>>：带符号右移
>>>：无符号右移

43. 1～n 整数中 1 出现的次数

代码：

算法思想

class Solution {
    public int countDigitOne(int n) {
        int digit=1, res=0, high = n/10, cur = n%10, low = 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=high%10;
            high/=10;
            digit*=10;
        }
        return res;
    }
}

65. 不用加减乘除做加法

代码：

算法思想

class Solution {
    public int add(int a, int b) {
        //从第二轮开始，b存放的值是进位，若进位为0，则a为最终答案
        while(b!=0){
            //c计算进位
            int c=(a&b)<<1;
            //a用来存放非进位和
            a=a^b;
            b=c;
        }
        return a;
    }
}