【Leetcode Medium】1318. Minimum Flips to Make a OR b Equal to c

原题链接

题目描述

Given 3 positives numbers a, b and c. Return the minimum flips required in some bits of a and b to make ( a OR b == c ). (bitwise OR operation).
Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation.

修改a或者b的二进制表示,使得a or b = c

解题思路

尝试做了一场leetcode的周赛题目,这是第二题(直接倒在了第三题),题目不难,我的思路也非常常规,就是把三个数的二进制值都get到然后进行比较,一个小坑是三个数的二进制表示长度可能不一,要提前处理(由于题目约束里说了三个数都是正数,所以在前面加0就可以)
code:

class Solution {
    public int minFlips(int a, int b, int c) {
        String C = Integer.toBinaryString(c);
        String A = Integer.toBinaryString(a);
        String B = Integer.toBinaryString(b);
        int flip = 0;
        
        String[] addtmp = addZero(A, B, C);
        
        char[] binaryA = addtmp[0].toCharArray();
        char[] binaryB = addtmp[1].toCharArray();
        char[] binaryC = addtmp[2].toCharArray();   
        
        for (int i = binaryC.length - 1; i >= 0; i--) {
            char tmp = binaryC[i];
            char tmpA = binaryA[i];
            char tmpB = binaryB[i];
            //if tmp == 1, requires one or two '1' in A and B
            //if tmp == 0, requires both 0 in A and B
            if (tmp == '1') {
                if (tmpA == '0' && tmpB == '0') {
                    flip++;
                }
            }
            else {
                if ((tmpA == '1' && tmpB == '0') || (tmpA == '0' && tmpB == '1')) {
                    flip++;
                }
                else if (tmpA == '1' && tmpB == '1')
                    flip += 2;
            }
        }
        return flip;
        
    }
    
    private String[] addZero(String a, String b, String c) {
        int maxLen = a.length();
        if (b.length() > maxLen)
            maxLen = b.length();
        if (c.length()> maxLen)
            maxLen = c.length();
        
        
        int tmp = maxLen - a.length();
        String zerotmp = "";
        
        for (int i = 0; i < tmp; i++) {
            zerotmp += "0";
        }
        a = zerotmp + a;
                
        tmp = maxLen - b.length();
        zerotmp = "";
        
        for (int i = 0; i < tmp; i++) {
            zerotmp += "0";
        }
        b = zerotmp + b;
        
        tmp = maxLen - c.length();
        zerotmp = "";
        
        for (int i = 0; i < tmp; i++) {
            zerotmp += "0";
        }
        c = zerotmp + c;
        
        String[] res = new String[3];
        res[0] = a;
        res[1] = b;
        res[2] = c;
        
        
        return res;
    }
}

TIP:

对于我的解法来说,由于使用了一个private方法,由此引出了一个重要的知识点:
Java中函数传参是call by value
Java中所有的参数传递,传递的都是副本
如果原变量代表的是value(如基本类型),那么在函数中修改该值,对原变量不会造成影响;如果原变量代表的是地址(如String,或自定义对象类型),给副本重新赋值(即修改指向)不会改变原变量,若对副本指向的内容做出改变,则会影响到原变量
具体可以参考这一篇,写的比较详细
https://www.cnblogs.com/woshimrf/p/5263018.html

其他解法

本质思路是一样的,只不过利用二进制数的操作(如左移,做与操作判断是1还是0)可以避免长度不一致问题,就不需要我的那个private方法,也不需要转换成二进制再转成charArray这样了

class Solution {
    public int minFlips(int a, int b, int c) {
        int res = 0;
        
        for(int i = 1, j = 0; j < 32; i = i<< 1, j++) {
        	//分别判断a,b,c的当前位是1 or 0
            int v1 = a & i;
            int v2 = b & i;
            int v3 = c & i;
            if(v3 != 0) {
            	//c的当前位为1
                if(v1 == 0 && v2 == 0) {
                    res++;
                }
            } else {
                if(v1 != 0 && v2 != 0) {
                    res += 2;
                }else if(v1 != 0 || v2 != 0) {
                    res++;
                }
            }    
        }
        
        return res;
    }
}
【Leetcode Medium】1318. Minimum Flips to Make a OR b Equal to c【Leetcode Medium】1318. Minimum Flips to Make a OR b Equal to c JellyFishDing 发布了31 篇原创文章 · 获赞 0 · 访问量 1394 私信 关注
上一篇:【HDOJ6595】Everything Is Generated In Equal Probability(期望DP)


下一篇:1053 Path of Equal Weight (30 分)(******)