剑指Offer-整数篇

发布于:2022-11-09 ⋅ 阅读:(8) ⋅ 点赞:(0) ⋅ 评论:(0)

核心知识点

  • 整数的取值范围:

  • 一些边界值:
    • Integer.MAX_VALUE0x7fffffff2147483647
    • Integer.MIN_VALUE0x80000000-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&(i-1)

1的个数

0

000

-

0

1

001

000

1

2

010

000

1

3

011

010

2

4

100

000

1

5

101

100

2

6

110

100

1

7

111

110

3

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

i

二进制表示

1的个数

奇偶性

0

0000

0

1

0001

1

2

0010

1

3

0011

2

4

0100

1

5

0101

2

6

0110

2

7

0111

3

8

1000

1

9

1001

2

10

1010

2

  • 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
    • i1<<j 进行按位与操作时,i的第j个位置是1就返回1<<j(判断语句中即为true),i的第j个位置是0就返回0(判断语句中即为false
    • i & (1<<j)可以计算i的二进制的第j位是0还是1
      • 假设i=40,即101000

j

二进制表示

1 << j

i& (1 << j)

对应十进制值

0

0000

000000001

0

1

1

0001

000000010

0

2

2

0010

000000100

0

4

3

0011

000001000

1000

8

4

0100

000010000

0

16

5

0101

000100000

100000

32

6

0110

001000000

0

64

7

0111

010000000

0

128

8

1000

100000000

0

256

  • 1 & (i>>j)i的二进制形式的第j位是0还是1若为1i>>j为奇数若为0i>>j为偶数
    • 1 & (i>>1)i的二进制形式的第j位是0还是1若为1i>>1为奇数若为0i>>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、540 的二进制 -> 0、0、0、1、0、1,对应40>>j奇偶性 -> 偶、偶、偶、奇、偶、奇
        • 假设i=40,即101000

i

j

i >> j

对应十进制值

1 & (i >> j)

奇偶性

101000

0

101000

40

0

101000

1

010100

20

0

101000

2

001010

10

0

101000

3

000101

5

1

101000

4

000010

2

0

101000

5

000001

1

1

101000

6

000000

0

0

101000

7

000000

0

0

101000

8

000000

0

0

29. 两数相除

  • 注意:0xc00000000x80000000 的一半,即-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;
    }
}