算法：（一）整数

1.1 整数基础知识

面试题1：整数除法

题目：输入两个int型整数，他们进行除法计算并返回商，要求不能使用乘号’*‘、除号’/‘以及求余符号’%'。当发生溢出时，返回最大的整数值。假设除数不为0。例如输入15和2，输出15/2的结果，即7。

思路：减法

注：负数除法取余详见：实数范围内的求模（求余）运算：负数求余究竟怎么求

public class IntegerDivision {
    public int divide(Integer dividend, Integer divisor){
        // 判断边界情况，即发生溢出的情况：只有-2^31 / -1时会发生溢出
        if(dividend == -0x80000000 && divisor == -1){
            return Integer.MAX_VALUE;
        }
        // 把被除数与除数都转化为负数进行计算，最后再判断商的符号
        // 为什么不转化为正数，因为若是被除数是-2^31，则转化为正数会溢出，int类型的取值范围是-2^31 ~ 2^31-1
        int negative = 2;
        if(dividend > 0){
            dividend = -dividend;
            negative--;
        }
        if(divisor > 0){
            divisor = -divisor;
            negative--;
        }
        int result = divideCore(dividend, divisor);
        return negative == 1 ? -result : result;
    }


    private int divideCore(Integer dividend, Integer divisor){
        /**
         * 两个负数相除
         * 时间复杂度为O(logn)
         */
        int result = 0;
        while(dividend <= divisor){
            // 小于被除数的最大数，同时是除数的倍数
            int value = divisor;
            // 商
            int quotient = 1;
            // 这里是判断被除数小于除数的2倍、4倍、8倍...，若小于，则减去这些，然后继续判断，直至被除数比除数大
            // 判断value >= 0xc0000000 是为了防止value + value溢出, 溢出之后value为正数，会发生死循环
            while(value >= 0xc0000000 && dividend <= value + value){
                value += value;
                quotient += quotient;
            }
            result += quotient;
            dividend -= value;
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

1.2 二进制

面试题2：二进制加法

题目：输入两个表示二进制的字符串，请计算他们的和，并以二进制字符串的形式输出。例如，输入的二进制字符串分别是“11”和“10”，则输出“101”。

思路：二进制位运算

public class BinaryAddition {
    // 此题将字符串做二进制位运算，而不是转化为整型进行计算，是因为二进制字符串可能很长，转化为整型会越界
    public String addBinary(String a, String b){
        // 用一个StringBuffer动态保存结果
        StringBuffer result = new StringBuffer();
        // cache表示进位
        int cache = 0;
        int i = a.length() - 1;
        int j = b.length() - 1;
        while(i >= 0 || j >= 0){
            // 多使用三元组表达式简化条件判断
            int bitA = i >= 0 ? a.charAt(i--) - '0' : 0;
            int bitB = j >= 0 ? b.charAt(j--) - '0' : 0;
            int sum = bitA + bitB + cache;
            cache = sum >= 2 ? 1 : 0;
            // result可能为0, 1, 2, 3，此种写法更简洁
            result.append(sum >= 2 ? sum - 2 : sum);
        }
        if (cache > 0){
            result.append(1);
        }
        // 结果反转
        return result.reverse().toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

面试题3：前n个数字二进制形式中1的个数

题目：输入一个非负数n，请计算0到n之间每个数字的二进制形式中1的个数，并输出一个数组。例如，输入的n为4，由于0、1、2、3、4的二进制形式中的个数分别为0、1、1、2、1，因此输出数组[0，1，1，2，1]。

思路：小技巧，i&(i-1)去除i的二进制数中最右边的1

public class NumberOfOne {
    public int[] countBits(Integer n){
        /**
         * 如何求一个数的二进制表示中1的个数？
         * 有一个小技巧，i & (i - 1)可以消除i的二进制表示中左右端的1
         * 例如i = 12，二进制表示为1100，12 - 1的二进制表示为1011，则1100 & 1011 = 1000
         * 时间复杂度为O(nk)，其中k为正整数的位数
         */
        int[] result = new int[n + 1];
        for (int i = 0; i <= n; i++){
            int num = i;
            // 判断一个数中有多少个1
            while(num != 0){
                result[i]++;
                num = num & (num - 1);
            }
        }
        return result;
    }
    
    public int[] countBitsPro(int n){
        /**
         * i & (i - 1)能消除i二进制表示中最右端的1
         * 则表明i二进制表示中1的个数比i & (i - 1)多1个
         * 而0的二进制表示中1的个数为0个，并且i > i & (i - 1)，即有边界且不会发生溢出
         * 故可以根据元素之间值的关系可以直接进行遍历计算
         * 时间复杂度为O(n)
         */
        int[] result = new int[n + 1];
        // 不用计算result[0]， 因为result[0]为0
        for (int i = 1; i <= n; i++){
            result[i] = result[i & (i - 1)] + 1;
        }
        return result;
    }
 
    public int[] countBitsProMax(Integer n){
        /**
         * 另一种直接根据数组元素间值的关系进行计算的方法
         * i与i/2的二进制表示中1的个数之间的关系是怎样的？
         * 若i是偶数，则i二进制表示中最后一位为0，i/2相当于右移一位，故i与i/2中1的个数相同
         * 若i是奇数，则i二进制表示中最后一位为1，i/2相当于右移一位，故i中1个个数比i/2多一个
         * 时间复杂度为O(n)
         */
        int[] result = new int[n + 1];
        for (int i = 1; i <= n; i++){
            // i >> 1表示 i/2，i & 1表示 i % 2；以后要多用位运算来提高语句执行效率
            result[i] = result[i >> 1] + (i & 1);
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

面试题4：只出现一次的数字

题目：输入一个整数数组，数组只有一个数字出现了一次，而其他数字都出现了三次。请找出那个只出现一次的数字。例如，如果输入的数组为[0, 1, 0, 1, 0, 1, 100]，则只出现一次的数字为100。

思路：已知两个相同的数经过异或运算结果为0；那么我们可以定义一种运算，使三个相同的数经过这个运算结果为0。

public class OnlyOnce {
    public int singleNumber(int[] nums){
        /**
         * 已知两个相同的数经过异或运算结果为0；那么我们可以定义一种运算，使三个相同的数经过这个运算结果为0。
         * int型都是32bit数组成的，故...
         */
        int[] bitSum = new int[32];
        for(int num : nums){
            for(int i = 0; i < 32; i++){
                // number & 1可以计算number的二进制数的最右端的数
                // (num >> (31 - i)) & 1 可以得到num二进制数的第i位数，i取值范围为0~31
                bitSum[i] += (num >> (31 - i)) & 1;
            }
        }
         int result = 0;
        for(int i = 0; i <32; i++){
            result = (result << 1) + (bitSum[i] % 3);
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

上面的代码中，其实包含了一个整数如何转化为其二进制数的数组，以及一个二进制数的数组如何转化为一个整数的方法。

public class OnlyOnce {
    
    ...

    public int[] intToBinaryArray(Integer num){
        /**
         * 将int型转化为其二进制数的数组
         */
        int[] bit = new int[32];
        for(int i = 0; i < 32; i++){
            bit[i] = (num >> (31 - i)) & 1;
        }
        return bit;
    }

    public String intToBinaryString(Integer num){
        /**
         * 将int型转化为其二进制数的字符串
         */
        String result = "";
        for(int i = 0; i < 32; i++){
            result += (num >> (31 - i)) & 1;
        }
        return result;
    }

    public int binaryArrayToInt(int[] binaryArray){
        /**
         * 将一个二进制数的数组转化为其int值
         */
        int result = 0;
        for(int i = 0; i <32; i++){
            result = (result << 1) + binaryArray[i];
        }
        return result;
    }

    public int binaryStringToInt(String binaryStr){
        /**
         * 将一个二进制数的字符串转化为其int值
         */
        int result = 0;
        for(int i = 0; i <32; i++){
            result = (result << 1) + (binaryStr.charAt(i) - '0');
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

面试题5：单词长度的最大乘积

题目：输入一个字符串数组words，请计算不包含相同字符的两个字符串*words[i]和words[j]*的长度乘积的最大值。如果所有字符串都包含至少一个相同字符，那么返回0。假设字符串中只包含英文小写字母。例如，输入的字符串数组words为[“abcw”, “foo”, “bar”, “fxyz”, “abcdef”]，数组中"bar"与"foo"没有相同字符，它们的长度乘积为9。"abcw"与"fxyz"也没有相同字符，它们的长度的乘积为16，则16是该数组不包含相同字符的一对字符串的长度乘积的最大值。

思路：通过hash比较（构造hash表：二维数组/二进制数）

public class HashComparison {
    public int maxProduct(String[] words){
        /**
         * 很容易想到的暴力解法：
         * 1.遍历数组中每一个单词，然后与数组中其右侧的单词进行比较（左侧不用比较，因为比较过了）
         * 2.两个单词比较又没有相同字符，最低级的解法是一个单词中的每一个字符和另一个单词中所有字符进行比较
         * 3.可以利用hash的思路来简化这种比较：
         *      1）用一种类hash方法将每个单词中出现的字符记录下来
         *      2）在比较的时候，通过比较hash的结果来判断两个单词是否有相同字符
         * 时间复杂度O(n^2)
         */
        // 使用一个二维数组当作hash表，每一行代表每个单词的hash值
        boolean[][] hash = new boolean[words.length][26];
        // 记录每个单词的hash值
        for(int i = 0; i < words.length; i++){
            for(char c : words[i].toCharArray()){
                hash[i][c-'a'] = true;
            }
        }
        int result = 0;
        // 根据hash表进行比较
        for (int i = 0; i < hash.length; i++){
            for(int j = i + 1; j < hash.length; j++){
                int k = 0;
                while(k < 26){
                    if(hash[i][k] == hash[j][k]){
                        break;
                    }
                    k++;
                }
                // 比较结束，没有相同字符
                if(k == 26){
                    int tempResult = words[i].length() * words[j].length();
                    result = Math.max(result, tempResult);
                }
            }
        }
        return result;
    }

    public int maxProductPro(String[] words){
        /**
         * 上面的解法是利用二维数组当作hash表记录hash结果，再比较二维数组的元素
         * 因为每一位的hash值只有两种可能
         * 所以更好的方法是利用二进制数当作hash表，再通过二进制与运算来进行比较
         * 虽然时间复杂度量级上与上面的方法一致，但通过与运算比较只需要1步，而比较二维数组则最多可能需要26步，故此方法明显优于上面的方法
         * 时间复杂度O(n^2)
         */
        int[] hash = new int[words.length];
        for(int i = 0; i < words.length; i++){
            for(char c : words[i].toCharArray()){
                // **精华操作**
                // |= : 与等于，和+=类似
                // int类型有32位，右边第1位为最低位，代表a；右边第2位代表b；以此类推高位26位代表z
                // 通过1的左移操作记录每一个字母是否出现
                hash[i] |= 1 << (c - 'a');
            }
        }
        int result = 0;
        // 比较hash表
        for(int i = 0; i < hash.length; i++){
            for(int j = i + 1; j < hash.length; j++){
                int flags = hash[i] & hash[j];
                if(flags == 0){
                    result = Math.max(result, words[i].length() * words[j].length());
                }
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71