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

蔚落 2024-04-01 14:14 39阅读 0赞

### 一、整数 ###

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

注意点：**溢出**

#### 1.1整数除法 ####

[原题链接][Link 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 二进制加法 ####

[原题链接][Link 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.3 前n个数字二进制中1的个数 ####

[原题链接][Link 3]

> 给定一个非负整数 `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.4 只出现一次的数字 ####

[原题链接][Link 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;
        }
    }

**解法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.5排序数组中两个数字之和** ####

[原题链接][Link 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.6单词长度的最大乘积** ####

[原题链接][Link 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;
       
    
    
        }
    }

***会持续更新的~***

[Link 1]: https://leetcode.cn/problems/xoh6Oh/?envType=study-plan&id=lcof-ii&plan=lcof&plan_progress=4kehfu1
[Link 2]: https://leetcode.cn/problems/JFETK5/?envType=study-plan&id=lcof-ii&plan=lcof&plan_progress=4kehfu1
[Link 3]: https://leetcode.cn/problems/w3tCBm/?envType=study-plan&id=lcof-ii&plan=lcof&plan_progress=4kehfu1
[Link 4]: https://leetcode.cn/problems/WGki4K/?envType=study-plan&id=lcof-ii&plan=lcof&plan_progress=4kehfu1
[Link 5]: https://leetcode.cn/problems/kLl5u1/
[Link 6]: https://leetcode.cn/problems/aseY1I/?envType=study-plan&id=lcof-ii&plan=lcof&plan_progress=4kehfu1