【Java版oj】day15查找输入整数二进制中1的个数、手套

港控/mmm° 2024-03-25 22:08 63阅读 0赞

**目录**

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

（1）原题再现

（2）问题分析

（3）完整代码

二、手套

（1）原题再现

（2）问题分析

（3）完整代码

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

> ## 一、查找输入整数二进制中1的个数 ##
> 
> ### （1）原题再现 ###
> 
> [查找输入整数二进制中1的个数\_\_牛客网][1]
> 
> 输入一个正整数，计算它在二进制下的1的个数。
> 
> **注意多组输入输出！！！！！！**
> 
> **输入描述:**
> 
> 输入一个整数
> 
> **输出描述:**
> 
> 计算整数二进制中1的个数
> 
> **示例1**
> 
> 输入
> 
> 5
> 
> 输出
> 
> 2
> 
> **说明**
> 
> 5的二进制表示是101，有2个1
> 
> ### （2）问题分析 ###
> 
> 这道题很简单。常规的方法无非是把十进制不断除以2转成二进制，并计数1的个数。但是，我只需要一行核心代码就搞定了！！！记住**Integer.bitCount()方法！！！**直接就是计算十进制转二进制数中1的个数
> 
> ### （3）完整代码 ###
> 
>     import java.util.Scanner;
>     
>     public class Main {
>         public static void main(String[] args) {
>             Scanner sc = new Scanner(System.in);
>             while (sc.hasNextInt()) {
>                 int num = sc.nextInt();
>                 System.out.println(Integer.bitCount(num));
>             }
>         }
>     }
> 
> ![6cae8ab4e67f4670b4ef77cac77386c4.png][]

> ## 二、手套 ##
> 
> ### （1）原题再现 ###
> 
> [手套\_牛客题霸\_牛客网][Link 1]
> 
> **描述**
> 
> 在地下室里放着n种颜色的手套，手套分左右手，但是每种颜色的左右手手套个数不一定相同。A先生现在要出门，所以他要去地下室选手套。但是昏暗的灯光让他无法分辨手套的颜色，只能分辨出左右手。所以他会多拿一些手套，然后选出一双颜色相同的左右手手套。现在的问题是，他至少要拿多少只手套(左手加右手)，才能保证一定能选出一双颜色相同的手套。
> 
> 给定颜色种数n(1≤n≤13),同时给定两个长度为n的数组left,right,分别代表每种颜色左右手手套的数量。数据保证左右的手套总数均不超过26，且一定存在至少一种合法方案。
> 
> 测试样例：
> 
> 4,\[0,7,1,6\],\[1,5,0,6\]
> 
> 返回：10
> 
> (解释：可以左手手套取2只，右手手套取8只)
> 
> ### （2）问题分析 ###
> 
> 这题是个中等题，看似复杂，很多解析都说利用贪心算法。在我看来这就一道数学题。
> 
> 因为A先生可以分清左右手，所以大情况分为两种：
> 
> 情况一：把左手手套全拿出来，右手手套随意选择一个。
> 
> 首先为了使选择的左手手套最少，我们可以找出左手某种颜色手套数最少的那个，只要留下一个即可，就是+1。这是在除去某种颜色手套数为0的情况下，如果最小手套数是0，再+1就会出问题。简而言之，就是找手套序列中不为0的最小数。
> 
> 其次如果左手某种颜色手套数为0，而右手对应的手套数不为0，我们就不能在右手手套中随意选择一个，因为可能选到左手没有的颜色。这时，我们需要选择右手对应左手为0的某种颜色的手套数+1。
> 
> 情况二：把右手手套全拿出来，左手手套随意选择一个。注意情况点同理。
> 
> 故而我们分**两大种、三小种情况讨论**：
> 
> **（1）一只手套数为0，另一只手套数不为0：**
> 
> 将不为0的手套数加入要取出的手套总数中。
> 
> **1.该颜色左手手套数为0，右手不为0：**left\[i\] == 0 && right\[i\] != 0
> 
> 将不为0的手套数加入要取出的手套总数中  
> **2.该颜色左手手套数不为0，右手为0：**left\[i\] != 0 && right\[i\] == 0
> 
> 将不为0的手套数加入要取出的手套总数中  
> **（2）该颜色左手手套数和右手都不为0：**left\[i\] != 0 && right\[i\] != 0
> 
> 将不为0的手套数加入要取出的手套总数中
> 
> 最后就是将总数-手套最小的数+2，+2的原因是在左手中选择要+1，在右手中选择也要+1
> 
> 对比先选左手或先选右手，哪种情况更小。
> 
> ### （3）完整代码 ###
> 
>     import java.util.*;
>     
>     public class Gloves {
>         public int findMinimum(int n, int[] left, int[] right) {
>             int leftNum = 0, rightNum = 0;
>             int leftMin = Integer.MAX_VALUE;
>             int rightMin = Integer.MAX_VALUE;
>             for (int i = 0; i < n; i++) {
>                 if (left[i] == 0 && right[i] != 0) {
>                     leftNum += right[i];
>                     rightNum += right[i];
>                 }
>                 if (left[i] != 0 && right[i] == 0) {
>                     rightNum += left[i];
>                     leftNum += left[i];
>                 }
>                 if (left[i] != 0 && right[i] != 0) {
>                     leftNum += left[i];
>                     rightNum += right[i];
>                     leftMin=Math.min(leftMin,left[i]);
>                     rightMin=Math.min(rightMin,right[i]);  
>                 }
>             }
>             leftNum=leftNum-leftMin+1+1;
>             rightNum=rightNum-rightMin+1+1;
>             return Math.min(leftNum,rightNum);
>         }
>     }
> 
> ![07589a4c22d041c29bdbfc8264e8103b.png][]

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

![0988a959fc134c01bec93ec797512266.png][]

[1]: https://www.nowcoder.com/questionTerminal/1b46eb4cf3fa49b9965ac3c2c1caf5ad
[6cae8ab4e67f4670b4ef77cac77386c4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c393a412606b4378ae0ff32f46df80b1.png
[Link 1]: https://www.nowcoder.com/practice/365d5722fff640a0b6684391153e58d8?tpId=49&&tqId=29337&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
[07589a4c22d041c29bdbfc8264e8103b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/607f56b88a5a43d0842c17fe7c78b6ab.png
[0988a959fc134c01bec93ec797512266.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/9fac4e90551444c09f3fd272c8f83f5e.png