java - jsp自定义标签




检查三个布尔中至少有两个是否为真 (20)

面试官最近问我这个问题:给出三个布尔变量a,b和c,如果三个中至少有两个是真的,则返回true。

我的解决方案是:

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

他表示,这可以进一步改善,但如何?


AC解决方案。

int two(int a, int b, int c) {
  return !a + !b + !c < 2;
}

或者你可能更喜欢:

int two(int a, int b, int c) {
  return !!a + !!b + !!c >= 2;
}

卡诺图可以解决这类问题:

      | C | !C
------|---|----
 A  B | 1 | 1 
 A !B | 1 | 0
!A !B | 0 | 0
!A  B | 1 | 0

从中推断出第一排需要一组,第一栏需要两组,以获得多能渗透剂的最佳解决方案:

(C && (A || B)) || (A && B)  <---- first row
       ^
       |
   first column without third case

As an addition to @TofuBeer TofuBeer's excellent post, consider @pdox pdox's answer:

static boolean five(final boolean a, final boolean b, final boolean c)
{
    return a == b ? a : c;
}

Consider also its disassembled version as given by "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's answer compiles to less byte code than any of the previous answers. How does its execution time compare to the others?

one                5242 ms
two                6318 ms
three (moonshadow) 3806 ms
four               7192 ms
five  (pdox)       3650 ms

At least on my computer, pdox's answer is just slightly faster than @moonshadow moonshadow's answer, making pdox's the fastest overall (on my HP/Intel laptop).


He's probably not looking for anything convoluted like bitwise comparison operators (not normally convoluted but with booleans, it's extremely odd to use bitwise operators) or something that is very roundabout like converting to int and summing them up.

The most direct and natural way to solve this is with an expression like this:

a ? (b || c): (b && c)

Put it in a function if you prefer, but it's not very complicated. The solution is logically concise and efficient.


In Ruby:

[a, b, c].count { |x| x } >= 2

Which could be run in JRuby on the JavaVM. ;-)


The simplest way (IMO) that is not confusing and easy to read:

// Three booleans, check if two or more are true

return ( a && ( b || c ) ) || ( b && c );

只是为了使用异或来回答一个相对直接的问题...

return a ^ b ? c : a

可读性应该是目标。 阅读代码的人必须立即理解你的意图。 所以这是我的解决方案。

int howManyBooleansAreTrue =
      (a ? 1 : 0)
    + (b ? 1 : 0)
    + (c ? 1 : 0);

return howManyBooleansAreTrue >= 2;

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

我不喜欢三元论( return a ? (b || c) : (b && c);从最上面的答案),我认为我没有见过任何人提及它。 它是这样写的:

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

我不认为我已经看到这个解决方案了:

boolean atLeast(int howMany, boolean[] boolValues) {
  // check params for valid values

  int counter = 0;
  for (boolean b : boolValues) {
    if (b) {
      counter++;

      if (counter == howMany) {
        return true;
      }
    }
  }
  return false;
}

它的优点是,一旦达到您要查找的数量,就会中断。 因此,如果这是“这1,000,000个值中至少有两个是真实的”,其中前两个是真实的,那么它应该比一些更“正常”的解决方案更快。


最明显的一组改进是:

// There is no point in an else if you already returned.
boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if ((a && b) || (b && c) || (a && c)) {
        return true;
    }
    return false;
}

接着

// There is no point in an if(true) return true otherwise return false.
boolean atLeastTwo(boolean a, boolean b, boolean c) {
    return ((a && b) || (b && c) || (a && c));
}

但是这些改进很小。


由于没有规定如何改进代码,因此我会努力通过使代码更有趣来改进代码。 这是我的解决方案:

boolean atLeastTwo(boolean t, boolean f, boolean True) {
    boolean False = True;
    if ((t || f) && (True || False)) 
        return "answer" != "42";
    if (t && f) 
        return !"France".contains("Paris");
    if (False == True) 
        return true == false;
    return Math.random() > 0.5;
}

如果有人想知道这段代码是否有效,下面是使用相同逻辑的简化:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if ((a || b) && (c)) 
        return true;
    if (a && b) 
        return true;
    if (true) 
        return false;
    // The last line is a red herring, as it will never be reached:
    return Math.random() > 0.5; 

}

这可以进一步归结为以下几点:

return ((a || b) && (c)) || (a && b);

但现在它不再有趣了。


而不是写作:

if (someExpression) {
    return true;
} else {
    return false;
}

写:

return someExpression;

至于表达本身,就像这样:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    return a ? (b || c) : (b && c);
}

或者这个(无论你发现哪一个更容易理解):

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    return a && (b || c) || (b && c);
}

它测试ab恰好一次,而c最多只测试一次。

参考


还有另一种方式来做到这一点,但不是一个很好的方法:

return (Boolean.valueOf(a).hashCode() + Boolean.valueOf(b).hashCode() + Boolean.valueOf(c).hashCode()) < 3705);

布尔哈希码值固定为1231为真,1237为假,因此可以同样使用<= 3699


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

创建布尔values的数据库values

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

创建地图,减少功能:

编辑 :我喜欢CurtainDog关于将map / reduce应用到泛型列表CurtainDog answer ,所以这里使用了一个map函数,它需要一个回调函数来确定值是否应该被计数。

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;
}

运行地图/缩小:

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;
}

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

更清晰?

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.

哪一个“改进”在很大程度上取决于情况。


boolean atLeastTwo(boolean a, boolean b, boolean c) 
{
  return ((a && b) || (b && c) || (a && c));
}

return (a==b) ? a : c;

说明:

如果a==b ,那么两者都是真的或两者都是假的。 如果两者都是真的,我们找到了两个真正的布尔值,并且可以返回true(通过返回a )。 如果两者都是假的,即使c为真,也不能有两个真正的布尔值,所以我们返回false(通过返回a )。 这是(a==b) ? a 一部分。 那么: c ? 那么如果a==b是假的,那么aba必须是真,所以我们找到了第一个真布尔值,唯一剩下的就是如果c也是真的,所以我们返回c作为答案。





boolean-logic