LEETCODE 1318. Minimum Flips to Make a OR b Equal to c 解题思路分析

题目大意:

或运算的最小翻转次数

给你三个正整数 a、b 和 c。

你可以对 a 和 b 的二进制表示进行位翻转操作,返回能够使按位或运算   a OR b == c  成立的最小翻转次数。

「位翻转操作」是指将一个数的二进制表示任何单个位上的 1 变成 0 或者 0 变成 1 。

示例 1:

输入:a = 2, b = 6, c = 5
输出:3
解释:翻转后 a = 1 , b = 4 , c = 5 使得 a OR b == c

示例 2:

输入:a = 4, b = 2, c = 7
输出:1

示例 3:

输入:a = 1, b = 2, c = 3
输出:0

提示:

  • 1 <= a <= 10^9
  • 1 <= b <= 10^9
  • 1 <= c <= 10^9

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1318

解题思路分析:

这是一道二进制位运算的题目,或运算大家应该不陌生,对于2个二进制数字,逐位进行比较,1或0是1,1或1是1,0或0是0。回到本题,要想a或b等于c的话,那么我们要逐位比较a和b,查看其或运算结果是否等于c相对位置上的值,如果等于的话,不需要翻转。当不相等时,需要分两种情况查看c当前位置上的值,如果c当前位上的值是0,说明,a和b当前位上的值必须都是0,此时,a和b不为0的个数即是要翻转的次数。反之,如果c当前位是1,说明a和b至少一个需要是1,换句话说,如果a和b当前位都是0时,需要翻转1次。循环完所有位数之后即可统计出总的翻转次数。

另外补充一点,之前的文章也多次讲到过,十进制数如何转化为二进制,并且得到二进制上每一位的数字,原理很简单,当前十进制数与2的余数即是相对应二进制数的最低位。取得最低位后,将当前十进制数除以2,继续求与2的余数,得到次低位,以此类推,直到当前十进制数为0为止。

实现代码:

public int minFlips(int a, int b, int c) {
    int res=0; // 返回结果
    // 当a,b,c三个数都为0时,结束循环
    while(c>0 || a>0 || b>0){
        // 取得二进制数c的最低位
        int cc = c % 2;
        // 取得二进制数a的最低位
        int aa = a % 2;
        // 取得二进制数b的最低位
        int bb = b % 2;
        // 当cc为0时,需要aa和bb均为0才可以,
        // 因此不为0的需要做出翻转
        if(cc==0) res+=(aa+bb);
        // 当cc为1时,aa和bb至少1个是1即可,
        // 因此当aa和bb都为0时,需要做出1次翻转
        else if(aa==0&&bb==0) res++;
        // 将a,b,c分别除以2,以便计算次低位
        c /=2;
        a /=2;
        b /=2;
    }
    return res;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Minimum Flips to Make a OR b Equal to c.

Memory Usage: 33.8 MB, less than 100.00% of Java online submissions for Minimum Flips to Make a OR b Equal to c.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1318-minimum-flips-to-make-a-or-b-equal-to-c-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。