一位面试官最近问了我这样一个问题:给定三个布尔变量a、b和c,如果三个变量中至少有两个为真,则返回true。
我的解决方案如下:
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if ((a && b) || (b && c) || (a && c)) {
return true;
}
else{
return false;
}
}
他说这还可以进一步改进,但如何改进呢?
下面是一个测试驱动的通用方法。虽然不像目前提供的大多数解决方案那样“高效”,但是清晰、经过测试、有效且通用。
public class CountBooleansTest extends TestCase {
public void testThreeFalse() throws Exception {
assertFalse(atLeastTwoOutOfThree(false, false, false));
}
public void testThreeTrue() throws Exception {
assertTrue(atLeastTwoOutOfThree(true, true, true));
}
public void testOnes() throws Exception {
assertFalse(atLeastTwoOutOfThree(true, false, false));
assertFalse(atLeastTwoOutOfThree(false, true, false));
assertFalse(atLeastTwoOutOfThree(false, false, true));
}
public void testTwos() throws Exception {
assertTrue(atLeastTwoOutOfThree(false, true, true));
assertTrue(atLeastTwoOutOfThree(true, false, true));
assertTrue(atLeastTwoOutOfThree(true, true, false));
}
private static boolean atLeastTwoOutOfThree(boolean b, boolean c, boolean d) {
return countBooleans(b, c, d) >= 2;
}
private static int countBooleans(boolean... bs) {
int count = 0;
for (boolean b : bs)
if (b)
count++;
return count;
}
}
这真的取决于你对“改进”的定义:
清晰吗?
boolean twoOrMoreAreTrue(boolean a, boolean b, boolean c)
{
return (a && b) || (a && c) || (b && c);
}
反之亦然?
boolean moreThanTwo(boolean a, boolean b, boolean c)
{
return a == b ? a : c;
}
更一般的?
boolean moreThanXTrue(int x, boolean[] bs)
{
int count = 0;
for(boolean b : bs)
{
count += b ? 1 : 0;
if(count > x) return true;
}
return false;
}
更多的可伸缩的吗?
boolean moreThanXTrue(int x, boolean[] bs)
{
int count = 0;
for(int i < 0; i < bs.length; i++)
{
count += bs[i] ? 1 : 0;
if(count > x) return true;
int needed = x - count;
int remaining = bs.length - i;
if(needed >= remaining) return false;
}
return false;
}
更快呢?
// Only profiling can answer this.
哪一种是“改进”的,很大程度上取决于具体情况。
作为@TofuBeer TofuBeer精彩帖子的补充,考虑@pdox pdox的回答:
static boolean five(final boolean a, final boolean b, final boolean c)
{
return a == b ? a : c;
}
再考虑一下它的分解版本,如"javap -c"所给出的:
static boolean five(boolean, boolean, boolean);
Code:
0: iload_0
1: iload_1
2: if_icmpne 9
5: iload_0
6: goto 10
9: iload_2
10: ireturn
Pdox的答案编译成的字节代码比之前的任何答案都要少。它的执行时间与其他的相比如何?
one 5242 ms
two 6318 ms
three (moonshadow) 3806 ms
four 7192 ms
five (pdox) 3650 ms
至少在我的电脑上,pdox的回答比@moonshadow moonshadow的回答稍微快一点,使得pdox的回答是最快的(在我的惠普/英特尔笔记本电脑上)。