一位面试官最近问了我这样一个问题:给定三个布尔变量a、b和c,如果三个变量中至少有两个为真,则返回true。

我的解决方案如下:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if ((a && b) || (b && c) || (a && c)) {
        return true;
    }
    else{
        return false;
    }
}

他说这还可以进一步改进,但如何改进呢?


当前回答

如果我把布尔值转换成一个数字,如果这个数字不是2的幂,它至少有两个真值。

a*4 + b*2 + c*1 = N
return( N != 0 && (N&(N-1)) != 0)

我只是给出了另一种选择。

其他回答

下面是使用map/reduce的另一个实现。在分布式环境中,这可以很好地扩展到数十亿布尔值©。使用MongoDB:

创建数据库的布尔值:

db.values.insert({value: true});
db.values.insert({value: false});
db.values.insert({value: true});

创建map, reduce函数:

编辑:我喜欢CurtainDog的回答有映射/减少适用于泛型列表,所以这里有一个地图函数,它接受一个回调,决定一个值是否应该被计数。

var mapper = function(shouldInclude) {
    return function() {
        emit(null, shouldInclude(this) ? 1 : 0);
    };
}

var reducer = function(key, values) {
    var sum = 0;
    for(var i = 0; i < values.length; i++) {
        sum += values[i];
    }
    return sum;
}

运行map / reduce:

var result = db.values.mapReduce(mapper(isTrue), reducer).result;

containsMinimum(2, result); // true
containsMinimum(1, result); // false


function isTrue(object) {
    return object.value == true;
}

function containsMinimum(count, resultDoc) {
    var record = db[resultDoc].find().next();
    return record.value >= count;
}

在Clojure中:

(defn at-least [n & bools]
  (>= (count (filter true? bools)) n)

用法:

(at-least 2 true false true)

总结一下。它被称为布尔代数是有原因的:

  0 x 0 = 0
  1 x 0 = 0
  1 x 1 = 1

  0 + 0 = 0
  1 + 0 = 1
  1 + 1 = 0 (+ carry)

如果你看那里的真值表,你可以看到乘法是布尔和,而简单的加法是异或。

回答你的问题:

return (a + b + c) >= 2

这真的取决于你对“改进”的定义:

清晰吗?

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.

哪一种是“改进”的,很大程度上取决于具体情况。

它应该是:

(a || b && c) && (b || c && a)

此外,如果true自动转换为1,false自动转换为0:

(a + b*c) * (b + c*a) > 0