剑指offer解析

一、整数篇

1. 整数的除法

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231−1]。本题中，如果除法结果溢出，则返回 231 − 1

class Solution {
    public int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == -1) 
            return Integer.MAX_VALUE;
        int sign = (a > 0) ^ (b > 0) ? -1 : 1;
        if (a > 0) a = -a;
        if (b > 0) b = -b;
        int result = 0;
        while (a <= b) {
            a -= b;
            result += 1;
        }
        return sign > 0 ? result : -result;
    }
}

2. 二进制加法

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。
输入为 非空 字符串且只包含数字 1 和 0。

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder res = new StringBuilder();
        int pointA = a.length() - 1;
        int pointB = b.length() - 1;

        int carry = 0;
        while (pointA >= 0 || pointB >= 0) {
            int x = pointA >= 0 ? (a.charAt(pointA) - '0') : 0;
            int y = pointB >= 0 ? (b.charAt(pointB) - '0') : 0;
            int sum = x + y + carry;
            
            res.append(sum % 2);
            carry = sum / 2;

            pointA -= 1;
            pointB -= 1;
        }
        if (carry != 0) res.append(carry);
        return res.reverse().toString();
    }
}

3. 前 n 个数字二进制中 1 的个数

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组

示例：

输入: n = 2
输出: [0,1,1]
解释: 
0 --> 0
1 --> 1
2 --> 10

===============================

输入: n = 5
输出: [0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

class Solution {
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        
        // 动态规划
        // i 偶数;  dp[i] = dp[i-1]   偶数相对于前一位的奇数bits数不变
        // i 奇数; dp[i] = dp[i / 2] 偶数最后一位是0
        // 综上: dp[i] = dp[i >> 1] + i & 1
        // i 为偶数 i & 1 = 0
        // i 为奇数 i & 1 = 1
        for (int i = 0; i <= n; i++) {
            res[i] = res[i >> 1] + (i & 1);
        }
        return res;
    }
}