⭐️前面的话⭐️

本篇文章介绍来自牛客试题广场的两道题题解，分别为【查找输入整数二进制中1的个数】和【手套】，展示语言java。

?博客主页：未见花闻的博客主页
?欢迎关注?点赞?收藏⭐️留言?
?本文由未见花闻原创，CSDN首发！
?首发时间：?2022年7月28日?
✉️坚持和努力一定能换来诗与远方！
?推荐书籍：?《算法》，?《算法导论》
?参考在线编程网站：?牛客网?力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
?作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

⭐️查找输入整数二进制中1的个数⭐️

?题目详情

输入一个正整数，计算它在二进制下的1的个数。

注意多组输入输出！！！！！！

数据范围： $1\le n\le 2^{31}-1$

输入描述：

输入一个整数

输出描述：

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

示例1

输入：

5

输出：

2

说明：

5的二进制表示是101，有2个1   

示例2

输入：

0

输出：

0

题目链接：查找输入整数二进制中1的个数

?解题思路

基本思路： 位运算

解题思路：
这道题需要我们根据一个整数的二进制序列，计算出二进制序列中有几个1，本质上就是考查位运算的使用。
方法1： 以大部分强类型语言为例，整型的储存形式是32位二进制序列，内存中储存的补码，对于正整数，二进制原码补码相同，对于负整数，补码是在原码除最高位取反得到反码的基础上加1。
最先想到的就是对输入的整数的二进制序列每一位进行判断是否是1。我们可以将这个二进制序列与1进行按位与运算，由于1的二进制序列只有末位是1，所以如果这个二进制序列的末位为1则返回1，否则返回0。然后我们再对这个二进制序列进行右移位操作，这样就能舍弃最右边的一个序列，经过32次操作，就能判断整个二进制序列有多少个1。

时间复杂度： 因为输入整数的二进制序列为32位，不论输入什么，都会循环32次，时间复杂度O(32)。

方法2： 假设输入的整数为n，我们不妨将n与n-1进行按位与运算，然后你会发现运算的结果与n相比，二进制序列中少了一个1，通俗来说，每进行一次这样的运算，二进制中的1就会减少一个，我们可以根据这种运算的特点来设计解法。我们可以将每次n&(n-1)的结果保存给n，直到n=0。计算进行运算的次数，即1的个数。

时间复杂度： 二进制序列中有几个1就循环几次，由于上一解法，最多循环判断32次，最坏时间复杂度O(32)。

?源代码

方法2：

public class Main {
    public static void main(String[] args) throws IOException {
    //使用缓存输入，也可以使用Scanner输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = "";
        while ((str = br.readLine()) != null) {
            int n = Integer.parseInt(str);
            int ans = 0;
            while (n != 0) {
                //每运算一次少一个1
                n &= n-1;
                ans++;
            }
            System.out.println(ans);
        }
    }
}

?总结

本题为二进制位运算运用题，关键是抓住n&(n-1)可以消除一位1的性质。
类似题：
剑指 Offer 15. 二进制中1的个数

⭐️手套⭐️

?题目详情

在地下室里放着n种颜色的手套，手套分左右手，但是每种颜色的左右手手套个数不一定相同。A先生现在要出门，所以他要去地下室选手套。但是昏暗的灯光让他无法分辨手套的颜色，只能分辨出左右手。所以他会多拿一些手套，然后选出一双颜色相同的左右手手套。现在的问题是，他至少要拿多少只手套(左手加右手)，才能保证一定能选出一双颜色相同的手套。

给定颜色种数n(1≤n≤13),同时给定两个长度为n的数组left,right,分别代表每种颜色左右手手套的数量。数据保证左右的手套总数均不超过26，且一定存在至少一种合法方案。

测试样例：

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

题目链接：手套

?解题思路

基本思路： 贪心或者理解为数学推理也行

解题思路：

题目已经告诉我们，手套的种类数不会大于13，手套总数不会大于26，所以说单种手型单种颜色手套数目的最大值不可能超过26。

题目的意思就是，我们无法分辨颜色，只能分辨手套的手型，给你n种颜色的手套，并告诉你每种颜色手套的左右手手套分别有多少只，我们需要求至少拿出多少只手套才能保证有一双完整相同颜色的手套。

面对这种问题，我们考虑运气最差的情况，求出运气最差情况下至少需要多少手套就行了。

假设每种颜色的左右手手套数量都不为0，这种情况下，我们把左手手套全部拿出来，右手手套就拿一个，或者把右手手套全部拿出来，左手手套就拿一个，这样时一定能够满足题意的，由于我们要求最小值，我们选上述两种方案中手套数量较少的一种即可，但是不对，因为我们还可以少一定，就是找出左手手套中最小数目颜色的的手套（右手手套也是同理），对于这种手套我们就拿一个，剩余的全部放回，也能够保证题目要求，因为不管怎么取，每种颜色的手套都至少能够取到1个，下面我们使用符合来表示上述分析：不妨设左手手套数量为leftSum，右手手套数量为rightSum，左手手套中按照颜色分类，最少数量的手套数为leftMin，同理右手的为rightMin，初始情况下，根据题意，leftMin<26, rightMin<26。

此时根据上述分析，至少需要的手套数目为：
$$min(leftSum-leftMin+1,rightSum-leftMin+1)+1$$

上面的分析都是建立在某种颜色某种手型的手套数量均不为0的基础上推理得到的，但是题目可不保证手套数量一定不为0，所以我们需要进行优化。

我们可以分为两组进行计算，第一组就是左右手手套数量均不为0种类的手套，我们归为一组，按照上述方案计算，得到所需要的最小手套数量，另一组就是左右手手套中左手或右手数量为0的手套种类为一组，由于左手或右手手套一定存在数量为0，所以对于同颜色的手套来说，所对应其他数量不为0的手套必须拿上，否则无法保证另外一组拿到的手套是那一组里面的手套，所以说这一组拿到的是多余但必须那的手套数目，我们记为zeroRelativeSum。

所以进行相同思路的计算，那么最终至少需要拿到的手套数量为，第一组最少手套数量，加上第二组多拿的手套数量，即
$$min(leftSum-leftMin+1,rightSum-leftMin+1)+1+zeroRelativeSum$$

其中，leftSum为第一组左手手套总数，leftMin第一组左手手套中以颜色分类最少手套的数量，rightSum为第一组右手手套总数，rightMin第一组右手手套中以颜色分类最少手套的数量，zeroRelativeSum为第二组多拿的手套数量。

?源代码

import java.util.*;

public class Gloves {
    public int findMinimum(int n, int[] left, int[] right) {
        // write code here
        int leftSum = 0;
        int rightSum = 0;
        //int leftMin = Integer.MAX_VALUE;
        //int rightMin = Integer.MAX_VALUE;
        int leftMin = 26;
        int rightMin = 26;
        int zeroRelativeSum = 0;
        for (int i = 0; i < n; i++) {
            //如果某颜色某手型手套数量为0，加上相同颜色相对手型手套数量
            if (left[i] * right[i] == 0) {
                //因为出现此情况一定至少有一种手套数量为0，我们直接都记起来即可
                zeroRelativeSum += left[i] + right[i];
            } else {
                leftSum += left[i];
                if (leftMin > left[i]) {
                    leftMin = left[i];
                }
                rightSum += right[i];
                if (rightMin > right[i]) {
                    rightMin = right[i];
                }
            }
        }
        leftSum += zeroRelativeSum - leftMin + 1 + 1;
        rightSum += zeroRelativeSum -rightMin + 1 + 1;
        return leftSum < rightSum ? leftSum : rightSum;
    }
}

?总结

本题为贪心分析题，如果不能理解就当成数学逻辑题，解决此题的关键就是分析出什么条件才能使手套数量最少，但又能拿到至少一双同颜色的手套。