Java题目训练——查找输入整数二进制中1的个数和手套

谁借莪１个温暖的怀抱￠ 2023-09-30 21:08 22阅读 0赞

**目录**

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

二、手套

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

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

题目描述:

> 输入一个正整数，计算它在二进制下的1的个数。  
> 注意多组输入输出!!!!!!
> 
> 数据范围: 1<=n<=![2^\{31\}][2_31]\-1

输入描述:

> 输入一个整数

输出描述:

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

示例

> 示例1
> 
> 输入: 5
> 
> 输出: 2
> 
> 说明:5的二进制表示是101，有2个1

> 示例2
> 
> 输入: 0
> 
> 输出: 0
> 
> 说明:

**题目解析：**

> 直接利用java中将整型转成二进制字符串的方法，得到输入数字的二进制表示字符串，再利用一个for循环，统计字符串中1的个数即可。

import java.util.Scanner;
    public class Main {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            while (in.hasNextInt()) {
                int x = in.nextInt();
                System.out.println(fun(x));
            }
        }
    
        public static int fun(int x){
            String b = Integer.toBinaryString(x);
            int count = 0;
            for(int i = 0; i < b.length(); i++){
                if(b.charAt(i) == '1'){
                    count++;
                }
            }
            return count;
        }
    }

### 二、手套 ###

题目描述:

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

测试样例:

> 4,\[0,7,1,6\],\[1,5,0,6\]
> 
> 返回:10(解释:可以左手手套取2只，右手手套取8只)

**题目解析：**

> 思考该题目的时候我们应该在最坏情况中找到最优解，最坏的情况就是我们拿到了其中一只手的全部手套，那么这时我们只需要再拿一只，就能保证拿出来的一定会有一对手套。
> 
> 由于可以分出左右手，我们设左手的手套总数量为leftSum，右手手套总数量为rightSum，所以我们最坏情况可以拿左右手中数量较小的一只手的全部（即min = Math.min(leftSum, rightSum)），再拿另一只手的一只（即min + 1），就能保证有一对。
> 
> 但是这时我们考虑一种情况，如果其中总数量较少一只手（min）的其中一个颜色数量是0，那我们这时再去另一个手套堆里拿是不是很有可能拿到的就是这个颜色的手套，这时是无法配对的，所以拿一只是不够的，需要我们把这个颜色全部拿走，再拿才有可能拿到一对，即只要有0，这个颜色的左右手就都分出来加入总数（其中有一只手这个颜色为0）。
> 
> 于是我们可以一开始就把左右手中只要其中一只手的某个颜色的数量为0的左右手数量都全部加上（算在最坏情况中），才能保证配对。
> 
> 此时我们已经把最坏情况都考虑到了，那现在考虑如何才能使拿到的手套数量最优呢，就要从其中总数量较少一只手（min）切入。如何求保证拿到该手所有颜色的手套的数量呢？
> 
> 转换思路，又要考虑最坏的情况了，最坏情况就是一直拿到数量最多的颜色，然后次之，最后才拿到数量最少的颜色，那数量最少的颜色是不是拿一个就够了，即（min = sum - minColor + 1）。
> 
> 思路大致如此，代码通过循环更新实现。

import java.util.*;
    
    public class Main {
        public int findMinimum(int n, int[] left, int[] right) {
            int num = 0;//其中有0的总数
            int leftMin = 26;//左手数量最小的颜色（除了0）
            int rightMin = 26;//右手数量最小的颜色（除了0）
            int leftSum = 0;//左手总数量（除了0）
            int rightSum = 0;//右手总数量（除了0）
    
            for(int i = 0; i < n; i++){
                if(left[i] == 0||right[i] == 0){//其中有0的情况，单独考虑
                    num += left[i];
                    num += right[i];
                }else{//其中两个手的所有颜色都不为0
                    leftMin = Math.min(leftMin, left[i]);//左手数量最小的颜色
                    rightMin = Math.min(rightMin, right[i]);//右手数量最小的颜色
                    leftSum += left[i];//左手总数量
                    rightSum += right[i];//右手总数量
                }
            }
    
            int min = Math.min(leftSum - leftMin + 1,rightSum - rightMin + 1) + num + 1;//左右手总数量较小的再加1
    
            return min;
        }
    }

如有建议或想法，欢迎一起讨论学习~

[2_31]: https://latex.csdn.net/eq?2%5E%7B31%7D