原题链接
题目描述
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;
}
}
JellyFishDing
发布了31 篇原创文章 · 获赞 0 · 访问量 1394
私信
关注