那年我双手离桌，被《剑指offer》打的还不了手（第八天）

跟着博主一起刷题
这里使用的是题库：
https://leetcode.cn/problem-list/xb9nqhhg/?page=1

目录

• • 剑指 Offer 55 – II. 平衡二叉树
  • 剑指 Offer 56 – I. 数组中数字出现的次数
  • 剑指 Offer 56 – II. 数组中数字出现的次数 II

剑指 Offer 55 – II. 平衡二叉树

剑指 Offer 55 – II. 平衡二叉树
这道题和上一篇文章中二叉树的深度如出一辙，这里求出左右子树的最大深度后判断即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        return maxDepth(root)!=-1;
    }

    private int maxDepth(TreeNode root) {
        if(root==null)return 0;
        int left=maxDepth(root.left);
        if(left==-1)return -1;
        int right=maxDepth(root.right);
        if(right==-1)return -1;
        if(Math.abs(left-right)>1){
            return -1;
        }
        return Math.max(left,right)+1;
    }
}

剑指 Offer 56 – I. 数组中数字出现的次数

剑指 Offer 56 – I. 数组中数字出现的次数
我们知道，如果只有一个数字唯一出现，其余数字均出现两次，我们可以直接异或求解，但这里有两个还能用这种方法吗？
我的回答是：可以，我们全部异或后，设唯一出现的两个数字为a，b，那最终的结果就是：
a^b
既然a和b不相同，那么他们的二进制至少有一位是不相同的，那么我们就根据某一位的不相同来把我们的数字分为两组，两组再分别异或，得到结果。
难点：这个某一位是哪一位？
解答：根据异或的性质，相同为0，相异为1，可根据结果那位为1，得到该位不相同。

class Solution {
    public int[] singleNumbers(int[] nums) {
        int ab=0;
        for(int i:nums){
            ab^=i;
        }
        int bit=0;
        while(bit<32){
            if((ab&(1<<bit))!=0){
                break;
            }
            bit++;
        }
        int a=0;
        int b=0;
        for(int i:nums){
            if((i&(1<<bit))!=0){
                a^=i;
            }else{
                b^=i;
            }
        }
        int[] ret=new int[2];
        ret[0]=a;
        ret[1]=b;
        return ret;
    }
}

剑指 Offer 56 – II. 数组中数字出现的次数 II

剑指 Offer 56 – II. 数组中数字出现的次数 II
和上题不同的时，这道题不能再异或了，得另寻他法。
我一开始的想法是，利用哈希表记录出现次数即可

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int i:nums){
            map.put(i,map.getOrDefault(i,0)+1);
        }
        for(int i:nums){
            if(map.get(i)==1)return i;
        }
        return -1;
    }
}

但是又想像上一题一样空间复杂度维持在O(1)，必须使用其他方法。
上一题我们利用了a和b某位二进制位不同来分组异或，核心就是二进制位。那么这道题也是如此，注意看，一个数字出现三次，那么对于某一个二进制位来说，要么出现1三次，要么为0。那么我们将所有数字在不同二进制位1的个数算出来再取模3，得到的结果就是唯一出现的那个数字在该比特位的值。
比如
【1，1，1，3】
1二进制表示的最后四位：0001
3二进制表示的最后四位：0011
那么最后一位出现了4个1，%3得到1，即是唯一出现数字在最后一位的值，剩下的位以此类推即可。

public int singleNumber(int[] nums) {
        int xor=0;
        int[] bits=new int[32];
        for(int i=0;i<nums.length;i++){
            for(int j=0;j<32;j++){
                bits[j]+=(nums[i]&(1<<j))==0?0:1;
            }
        }
        int ret=0;
        for(int i=0;i<32;i++){
            ret<<=1;
            ret|=bits[31-i]%3;
        }
        return ret;
    }