剑指Offer-整数篇

核心知识点

• 整数的取值范围：

• 一些边界值：
  • Integer.MAX_VALUE：0x7fffffff：2147483647
  • Integer.MIN_VALUE：0x80000000：-2147483648
• 二进制及十进制表示、转换

// 5的二进制、十进制、十六进制初始化
int i1 = Integer.valueOf("0101",2);
int i2 = 5;
int i3 = Integer.valueOf("5", 16);

// 十进制转二进制、转十六进制
System.out.println(Integer.toBinaryString(i2));
System.out.println(Integer.toHexString(i2));

• 位运算（Java）
  • &、｜、！、^、<<、>>、>>>

• - 'a'、- '0'、- 'A'的运用
  • 示例

// 将字母映射为数字
String s1 = "abcdefghijklmn";
int[] ints1 = new int[s1.length()];
for (int i = 0; i < s1.length(); i++) {
    int t = s1.charAt(i) - 'a';
    ints1[i] = t;
}

• i & (i-1)的作用及使用
  • 将 i 的二进制表示中的最低位1改为0，即：整数 i 的二进制形式中1的个数比i & (i-1)的二进制形式中1的个数多1。

• 奇数和偶数二进制形式差异
  • 偶数 i 和 i/2 的二进制形式中1的个数相同；
  • 奇数 i 比 i/2 的二进制形式中1的个数多1。

• 用 i >> 1 计算 i/2，用 i & 1 计算 1%2
• 异或的使用：任何一个数字异或它自己的结果都是0
  • 如果将数组中所有的数字进行异或运算，那么最终的结果就是只出现1次的数字。
    • 通用题目：输入一个整数数组，数组中只有1个数字出现m次，其他数字都出现n次。请找出那个唯一出现m次的数字。假设m不能被n整除。
  • 如果数组中所有数字的第1个数位相加之和能被n整除，那么出现m次的数字的第i个数位一定是0；否则出现m次的数字的第i个数位一定是1。
• (num >> (31-i)) & 1：整数num的二进制形式中从左数起第i个数位。
• 位运算是对二进制运算整数的运算，包括与运算、或运算、非运算、异或运算、左移运算、右移运算。
• i & (1<<j)：i的二进制的第j位是0还是1
  • 表示 i 和 1<<j（即2^j） 按位与后得到的数。
  • 1<<j 的二进制表示只有第j个位置（从右往左数，从0开始）上的数是1，其余位置上的数是0
  • i和1<<j 进行按位与操作时，i的第j个位置是1就返回1<<j（判断语句中即为true），i的第j个位置是0就返回0（判断语句中即为false）
  • 故i & (1<<j)可以计算i的二进制的第j位是0还是1
    • 假设i=40，即101000

• 1 & (i>>j)：i的二进制形式的第j位是0还是1，若为1则i>>j为奇数，若为0则i>>j为偶数。
  • 1 & (i>>1)：i的二进制形式的第j位是0还是1，若为1则i>>1为奇数，若为0则i>>1为偶数。
    • 1 & (i>>j)相当于i右移j位后，若为奇数则返回1，若为偶数则返回0。
    • i>>j 相当于 i/2^j;
    • 1 & (i>>j) 可以得出，对于数i，其二进制形式的第j位（从右到左，从0起），对应i>>j的奇偶性，其中为1时对应奇数，0时对应偶数。
    • 比如i=40，即101000，其40>>j的奇偶性，对应为j -> 0、1、2、3、4、5，40 的二进制 -> 0、0、0、1、0、1，对应40>>j的奇偶性 -> 偶、偶、偶、奇、偶、奇
      • 假设i=40，即101000

29. 两数相除

• 注意：0xc0000000 为 0x80000000 的一半，即-2^30
• 常规解法

class Solution {
    public int divide(int dividend, int divisor) {
        if(dividend == 0x80000000 && divisor == -1) {
            return Integer.MAX_VALUE;
        }

        int flag = 2;
        if(dividend > 0) {
            flag--;
            dividend = -dividend;
        }
        if(divisor > 0) {
            flag--;
            divisor = -divisor;
        }

        int result = divisionCore(dividend, divisor);
        return flag == 1 ? -result : result;
    }

    public int divisionCore(int dividend, int divisor) {
        int result = 0;
        while(dividend <= divisor) {
            int value = divisor;
            int quotient = 1;
            while(value >= 0xc0000000 && dividend <= value + value) {
                quotient += quotient;
                value += value;
            }
            result += quotient;
            dividend -= value;
        }
        return result;
    }
}

• 其他解法参考：力扣

67. 二进制求和

• 代码片段
  • 片段01

a.charAt(i--);

// 上述代码相当于
a.charAt(i);
i= i- 1;

• • 片段02

// 从右往左依次取值，如"10"，先取0，再取1
int digitA = i >= 0 ? a.charAt(i--) - '0' : 0;

• • 片段03

// 逢二进一的处理
StringBuilder result = new StringBuilder();
int carry = 0;

int sum = digitA + digitB + carry;
// 需要计算下一步的carry以及sum值为2时，按0处理
carry = sum >= 2 ? 1 : 0;
sum = sum >= 2 ? sum - 2 : sum;
result.append(sum);

• 代码示例

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder result = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        while (i >= 0 || j >= 0) {
            int digitA = i >= 0 ? a.charAt(i--) - '0' : 0;
            int digitB = j >= 0 ? b.charAt(j--) - '0' : 0;
            int sum = digitA + digitB + carry;
            carry = sum >= 2 ? 1 : 0;
            sum = sum >= 2 ? sum - 2 : sum;
            result.append(sum);
        }
        if (carry == 1) {
            result.append(1);
        }
        return result.reverse().toString();
    }
}

• 参考示例：力扣

剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

• 核心原理：整数 i 的二进制形式中1的个数比i & (i-1)的二进制形式中1的个数多1。
• 代码示例

class Solution {
    public int[] countBits(int n) {
        int[] result = new int[n+1];
        for(int i=0; i <= n; ++i) {
            int j = i;
            while(j != 0) {
                result[i]++;
                j = j & (j - 1);
            }
        }
        return result;
    }
}

剑指 Offer II 004. 只出现一次的数字

• 核心原理： 如果数组中所有数字的第 i 个数位相加之和能被3整除，那么只出现1次的数字的第 i 个数位一定是0；如果数组中所有数字的第 i 个数位相加之和被除3余1，那么只出现1次的数字的第 i 个数位一定是1；
• (num >> (31 - i)) & 1 用来得到整数n的二进制形式中从左数起第 i 个数位。
• (result << 1) 结果为当前的值*2，如10 << 1，得到100，其中'10'十进制值为2，'100'的十进制值为4
• 代码示例

class Solution {
    public int singleNumber(int[] nums) {
        int[] bitSums = new int[32];
        for (int num : nums) {
            for (int i=0; i< 32; i++) {
                bitSums[i] += (num >> (31 - i)) & 1;
            }
        }

        int result = 0;
        for (int i=0; i<32; i++) {
            result = (result << 1) + bitSums[i] % 3;
        }
        return result;
    }
}

剑指 Offer II 005. 单词长度的最大乘积

• 核心原理：用哈希表记录字符中出现的字符。
• 示例代码

class Solution {
    public int maxProduct(String[] words) {
        boolean[][] flags = new boolean[words.length][26];
        for (int i = 0; i < words.length; i++) {
            for (char c: words[i].toCharArray()) {
                flags[i][c-'a'] = true;
            }
        }

        int result = 0;
        for (int i = 0; i < words.length; i++) {
            for (int j = i+1; j < words.length; j++) {
                int k = 0;
                for (; k < 26; k++) {
                    if (flags[i][k] && flags[j][k]) {
                        break;
                    }
                }
                if (k == 26) {
                    int prod = words[i].length() * words[j].length();
                    result = Math.max(result, prod);
                }
            }
        }
        return result;
    }
}

• 核心原理：用整数的二进制数位记录字符串中出现的字符。

• • 如果两个字符串中包含相同的字符，那么它们对应的整数相同的某个数位都为1，两个整数的与运算将不会等于0。如果两个字符串没有相同的字符，那么它们对应的整数的与运算的结果等于0。
  • 1<<j（即2^j），由此使用1 << (ch-'a')

• 代码示例

class Solution2 {
    public int maxProduct(String[] words) {
        int[] flags = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            for (char ch: words[i].toCharArray()) {
                flags[i] = flags[i] | (1 << (ch-'a')); 
            }
            System.out.println(Integer.toBinaryString(flags[i]));
        }

        int result = 0;
        for (int i = 0; i < words.length; i++) {
            for (int j = i+1; j < words.length; j++) {
                if ((flags[i] & flags[j]) == 0) {
                    int prod = words[i].length() * words[j].length();
                    result = Math.max(result, prod);
                }
            }
        }
        return result;
    }
}