整数——算法专项刷题（一）

一、整数

整数题目中常用算法及思想：位运算

注意点：溢出

1.1整数除法

原题链接

给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

注意：

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

示例 1：

• 输入：a = 15, b = 2
• 输出：7
• 解释：15/2 = truncate(7.5) = 7

提示:

• -2^31 <= a, b <= 2^31 - 1
• b != 0

思路： 使用倍增思想，除数 和 商 一直倍增，直到除数 * 2倍 小于 被除数 ，然后 被除数 - 除数 继续这个过程 并将商累加

注意点： 将 a b 变成负数 因为 Integer.MIN_VALUE 的绝对值 大于 Integer.MAX_VALUE 如果同时对 a b进行 取正操作可能会导致溢出，所以全变成 负数 进行处理

class Solution{
public int divide(int a, int b) {

int min = Integer.MIN_VALUE, max = Integer.MAX_VALUE, min_limit = min >>1;

// 特判
  if(a == min && b == -1) return max; 

  boolean isPos = (a < 0 && b > 0) || (a > 0 && b < 0) ? false :true;

 
//将 a b 都变成负数，方便后续处理
 if(a > 0) a = -a;
 if(b > 0 ) b = -b;

 int ans = 0;

 while(a <= b){

   int d = b ,c = 1;
      //d >= min_limit 防止倍增的时候溢出
   while(d >= min_limit && d + d >= a){

       // 倍增 因为是负数 倍增 一直在变小 
     d <<= 1;

     c <<= 1;

   }

    //更新 被除数
   a -= d;
//累加商
   ans += c;


 }

    //根据原 a b 正负判断结果 符号
 return isPos ? ans : -ans;


  }

}
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

1.2 二进制加法

原题链接

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:

• 输入: a = “11”, b = “10”

• 输出: “101”

提示：

• 每个字符串仅由字符 '0' 或 '1' 组成。
• 1 <= a.length, b.length <= 10^4
• 字符串如果不是 "0" ，就都不含前导零。

思路： 使用StringBuffer 进行字符拼接， 二进制进位思想 逆序从低位到高位相加 本位 %2 进位 / 2

注意点： 判断最高位是否进位

class Solution {
    public String addBinary(String a, String b) {

    int len1 = a.length()-1;
    int len2 = b.length()-1;

    StringBuffer sb = new StringBuffer();


    
    //进位
    int num = 0;

    while(len1 >= 0 || len2 >= 0){
        int num1 = len1 >= 0 ? a.charAt(len1) - '0' : 0;
        int num2 = len2 >= 0 ? b.charAt(len2) - '0' : 0;

        int temp = num + num1 + num2;

        //本位
        sb.append(temp % 2);

        //进位
        num = temp / 2;

   len1--;
   len2--;

    }

        //判断最高位是否进位
if(num == 1) sb.append('1');

return sb.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
26
27
28
29
30
31
32
33
34
35
36
37

1.3 前n个数字二进制中1的个数

原题链接

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

示例 1:

• 输入: n = 5

• 输出: [0,1,1,2,1,2]

• 解释:

• 0 --> 0

• 1 --> 1

• 2 --> 10

• 3 --> 11

• 4 --> 100

• 5 --> 101

• 0 <= n <= 105

思路: 找规律 奇数二进制1的个数 = 上一个数 +1 偶数二进制最后一位为0 这个数/2 左移一位就是 原来的数

比如： 6 -> 110 6 / 2 = 3 ->11 二进制1的个数是相等的

class Solution {
    public int[] countBits(int n) {

     int[] res = new int[n+1];
     

     for(int i = 1; i <= n ;i++){

//奇数等于上一个数加1
  if( i % 2 != 0){
      res[i] = res[i-1] + 1;
  }
  //偶数判断情况 相当于商左移了一位
else {
    res[i] = res[i / 2];
}
      
     }

     return res;

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1.4 只出现一次的数字

原题链接

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。

示例 1：

• 输入：nums = [0,1,0,1,0,1,100]
• 输出：100

提示：

• 1 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

解法1： map集合统计出现次数

class Solution {
    public int singleNumber(int[] nums) {
      int n = nums.length;

      Map<Integer,Integer> map = new HashMap();

      for(int i = 0; i < n; i++){
          map.put(nums[i],map.getOrDefault(nums[i] ,0) + 1);
      }

      for(int num : map.keySet()){
          if(map.get(num) == 1) return num;
      }


return 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

解法2：位运算

使用一个长度为32的数组cnt 记录下所有数值的每一位出现1的次数，再对cnt数组 每一位 mod 3 重新拼凑出只出现一次的数

例如 1，1，1，3 1 -> 00001 3->00011 存入数组后 [0,0,0,…,0,1,4] 进行 mod 3 操作后 得到 [0,0,0,…,0,1,1] 转为十进制就是3

class Solution {
    public int singleNumber(int[] nums) {
        


   int[] cnt = new int[32];

for(int num : nums){
    //对每一个数进位 位运算
    for(int i = 0; i < 32;i++){
        if( ((num >> i) & 1)  == 1  ){
            cnt[i]++;
        }
    }
}

int ans = 0;
for(int i = 0 ;i < 32; i++){
    if( cnt[i] % 3 == 1 ){
ans += (1 << i);
    }
}
   return ans;

    }
}
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

1.5排序数组中两个数字之和

原题链接

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足0 <= answer[0] < answer[1] < numbers.length。

假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。

示例 1：

• 输入：numbers = [1,2,4,6,10], target = 8
• 输出：[1,3]
• 解释：2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 。

提示：

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers 按 递增顺序 排列
• -1000 <= target <= 1000
• 仅存在一个有效答案

思路： 双指针，从前后向中间对数组扫描，遇到 大于 target的 右指针就 -1 ，小于 target的 左指针就 + 1 直到相等

class Solution {
    public int[] twoSum(int[] numbers, int target) {

      int l = 0 , r = numbers.length - 1;
   

    while( l < r){
        int num = numbers[l] + numbers[r];

if(num > target){
    r--;
}else if(num < target){
     l++;
}else{
    return new int[]{l,r};
}

    }

    return new int[]{};
     


    }
}
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

1.6单词长度的最大乘积

原题链接

给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。

示例 1:

• 输入: words = [“abcw”,“baz”,“foo”,“bar”,“fxyz”,“abcdef”]
• 输出: 16
• 解释: 这两个单词为 “abcw”, “fxyz”。它们不包含相同字符，且长度的乘积最大。

提示：

• 2 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] 仅包含小写字母

思路： 将字符串转化为二进制数， a -> 0 b->1 这样两个二进制数相与等于0 说明 两个字符串没有相等字符

注意点： 优先级 算术运算符 > 逻辑运算符

class Solution {
    public int maxProduct(String[] words) {
           
           
    int len = words.length;
    int[] nums = new int[len];

    for(int i = 0; i < len; i++){
        for(int j = 0; j < words[i].length(); j++){

            //将字符串转为 26位 二进制数 从a开始  1表示出现过 0表示没有 出现
            nums[i] |= (1 << (words[i].charAt(j) - 'a'));
        }
    }

    int res = 0;
    for(int i = 0 ;i < len -1 ; i++){
        for(int j = i+1; j < len; j++){

            //两个二进制数 相与等于0 说明两个字符串字符不一样
            if( (nums[i] & nums[j]) == 0){
                res = Math.max(res, words[i].length() * words[j].length());
            }
        }
    }

    return res;
   


    }
}
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

会持续更新的~