刷题_15：查找输入整数二进制中1的个数 and 手套

超、凢脫俗 2023-09-29 23:51 12阅读 0赞

### 一.查找输入整数二进制中1的个数 ###

**题目链接：**

> [查找输入整数二进制中1的个数][1]

**题目描述：**

> **输入一个正整数，计算它在二进制下的1的个数。  
> 注意多组输入输出！！！！！！数据均为int类型。**

**输入描述：**

> **输入一个整数**

**输出描述：**

> **计算整数二进制中1的个数**

**示例1：**

> **输入：  
> 5  
> 输出：  
> 2**

**示例2：**

> **输入：  
> 0  
> 输出：  
> 0**

**个人总结：**

> **我们把每个输入的数字与(&)上该数字减去一个1，直到这个数字为0为止，能与多少次，就有多少个1。  
> 证明：  
> 以数字22为例进行解释，我们可以看出，每一次与num - 1相与，都会使num的最低位1消失，所以总共与了几次，就有几个1。**  
> ![在这里插入图片描述][f6759e2d06ab43b391138feb2651432f.jpeg]

**代码实现：**

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()) {
        
                int num = sc.nextInt();
                int cnt = 0;
                while (num != 0) {
        
                    cnt++;
                    num = num & (num - 1);
                }
                System.out.println(cnt);
            }
        }
    }

--------------------

### 二.手套 ###

**题目链接：**

> [手套][Link 1]

**题目描述：**

> **在地下室里放着n种颜色的手套，手套分左右手，但是每种颜色的左右手手套个数不一定相同。A先生现在要出门，所以他要去地下室选手套。但是昏暗的灯光让他无法分辨手套的颜色，只能分辨出左右手。所以他会多拿一些手套，然后选出一双颜色相同的左右手手套。现在的问题是，他至少要拿多少只手套(左手加右手)，才能保证一定能选出一双颜色相同的手套。  
> 给定颜色种数n(1≤n≤13),同时给定两个长度为n的数组left,right,分别代表每种颜色左右手手套的数量。数据保证左右的手套总数均不超过26，且一定存在至少一种合法方案。**

**示例1：**

> **输入：  
> 4,\[0,7,1,6\],\[1,5,0,6\]  
> 输出：  
> 10(解释：可以左手手套取2只，右手手套取8只)**

**个人总结：**

> **要想能够让左右手套至少有一副配对  
> 我们可以先把左手手套每种都至少拿一只，然后再随便拿一只右手手套就可以成功配对  
> 那么如何保证每种手套都能拿一种呢？  
> 我们以\[3 7 2 3 5\]为例  
> 拿5种？肯定不行的，有可能都是同一个颜色  
> 拿7种？不行，有可能都是同一个颜色  
> 8？也不行  
> …  
> 全部拿走？不合适了，题目问我们最少拿几种  
> 全部拿走再减去最少的，这样有可能就缺了最少的一种颜色，因此再+1。大家可能会有疑惑了，既然是问最少拿多少手套，为什么不减去最多的呢？以上述例子为例，如果我们减去7，但其实我们是不知道我们减去的手套是什么颜色的，你希望它全部都是7对应的颜色，其实他可能是其他颜色的手套，这会导致有一种颜色可能一个都没有，这样就不能保证一定可以配对上了。  
> 如果某个颜色没有手套，就必须得把该颜色对应的另一边手套累加起来。  
> 先计算出左手和右手手套的总数，然后减去各自的最少的数再加一  
> 这样就可以保证取出的手套至少每种都有一只  
> 计算总数的时候，比较左手每个手套都取到和右手每个手套都取到两者谁较小，决定取左手还是取右手(左右手是可以分辨的)  
> 最后再加上另一种手套的一只就行**

**代码实现：**

import java.util.*;
    
    public class Gloves {
        
        public int findMinimum(int n, int[] left, int[] right) {
        
            // write code here
            int leftSum = 0, leftMin = Integer.MAX_VALUE;
            int rightSum = 0, rightMin = Integer.MAX_VALUE;
            int sum = 0;
            for (int i = 0; i < n; i++) {
        
                if (left[i] == 0 || right[i] == 0) {
        
                    sum += (left[i] + right[i]);
                } else {
        
                    leftSum += left[i];
                    rightSum += right[i];
                    leftMin = Math.min(leftMin, left[i]);
                    rightMin = Math.min(rightMin, right[i]);
                }
            }
            return sum + Math.min(leftSum - leftMin + 1, rightSum - rightMin + 1) + 1;
        }
    }

[1]: https://www.nowcoder.com/questionTerminal/1b46eb4cf3fa49b9965ac3c2c1caf5ad
[f6759e2d06ab43b391138feb2651432f.jpeg]: https://img-blog.csdnimg.cn/f6759e2d06ab43b391138feb2651432f.jpeg
[Link 1]: https://www.nowcoder.com/questionTerminal/365d5722fff640a0b6684391153e58d8