最近面试官问了我这个问题:给定三个布尔型变量a、b和c,如果其中至少有两个是true,则返回true。
我的解决方案如下:
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if ((a && b) || (b && c) || (a && c)) {
return true;
}
else{
return false;
}
}
他说这还可以进一步改善,但如何呢?
最近面试官问了我这个问题:给定三个布尔型变量a、b和c,如果其中至少有两个是true,则返回true。
我的解决方案如下:
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if ((a && b) || (b && c) || (a && c)) {
return true;
}
else{
return false;
}
}
他说这还可以进一步改善,但如何呢?
这要看你所谓的“改进”是什么意思:
更清晰了吗?
boolean twoOrMoreAreTrue(boolean a, boolean b, boolean c)
{
return (a && b) || (a && c) || (b && c);
}
Terser是什么?
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.
哪个是“改善”的取决于具体情况。
以下是使用map/reduce实现的另一种方法。这适用于在分布式环境中处理数十亿个©布尔值。使用MongoDB:
创建一个名为values
的布尔类型数据库:
db.values.insert({value: true});
db.values.insert({value: false});
db.values.insert({value: true});
创建 map 和 reduce 函数:
编辑:我喜欢CurtainDog的答案,该答案关于应用于通用列表的 map/reduce,下面是一个 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;
}
运行 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;
}
结合目前这里的答案:
public class X
{
static boolean a(final boolean a, final boolean b, final boolean c)
{
return ((a && b) || (b && c) || (a && c));
}
static boolean b(final boolean a, final boolean b, final boolean c)
{
return a ? (b || c) : (b && c);
}
static boolean c(final boolean a, final boolean b, final boolean c)
{
return ((a & b) | (b & c) | (c & a));
}
static boolean d(final boolean a, final boolean b, final boolean c)
{
return ((a?1:0)+(b?1:0)+(c?1:0) >= 2);
}
}
然后通过反编译器运行它们(javap -c X > results.txt):
Compiled from "X.java"
public class X extends java.lang.Object{
public X();
Code:
0: aload_0
1: invokespecial #1; //Method java/lang/Object."<init>":()V
4: return
static boolean a(boolean, boolean, boolean);
Code:
0: iload_0
1: ifeq 8
4: iload_1
5: ifne 24
8: iload_1
9: ifeq 16
12: iload_2
13: ifne 24
16: iload_0
17: ifeq 28
20: iload_2
21: ifeq 28
24: iconst_1
25: goto 29
28: iconst_0
29: ireturn
static boolean b(boolean, boolean, boolean);
Code:
0: iload_0
1: ifeq 20
4: iload_1
5: ifne 12
8: iload_2
9: ifeq 16
12: iconst_1
13: goto 33
16: iconst_0
17: goto 33
20: iload_1
21: ifeq 32
24: iload_2
25: ifeq 32
28: iconst_1
29: goto 33
32: iconst_0
33: ireturn
static boolean c(boolean, boolean, boolean);
Code:
0: iload_0
1: iload_1
2: iand
3: iload_1
4: iload_2
5: iand
6: ior
7: iload_2
8: iload_0
9: iand
10: ior
11: ireturn
static boolean d(boolean, boolean, boolean);
Code:
0: iload_0
1: ifeq 8
4: iconst_1
5: goto 9
8: iconst_0
9: iload_1
10: ifeq 17
13: iconst_1
14: goto 18
17: iconst_0
18: iadd
19: iload_2
20: ifeq 27
23: iconst_1
24: goto 28
27: iconst_0
28: iadd
29: iconst_2
30: if_icmplt 37
33: iconst_1
34: goto 38
37: iconst_0
38: ireturn
}
您可以看到,?: 的效果略优于您原始代码的修复版本。最佳的那个避免了所有的分支语句。从较少指令的角度来看(在大多数情况下),这很好,并且对于CPU的分支预测部分来说也更好,因为分支预测的错误猜测会导致CPU停顿。另一个直接代码的示例:
int n = 0;
if (a) n++;
if (b) n++;
if (c) n++;
return (n >= 2);
显然,这不是最简洁的代码。
补充说明
这是一个稍微优化过的版本:
int n = -2;
if (a) n++;
if (b) n++;
if (c) n++;
return (n >= 0);
假设与0进行比较的代码比与2进行比较的代码更快(或者更少),那么这样做可能会略微提高运行速度。
n
),任何像样的编译器都将每个 ++
操作编译成单个 CPU 指令,无论是前缀还是后缀。 - David R Tribble最明显的改进集合包括:
// 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));
}
但是这些改进很小。
还有一种方法可以做到这一点,但并不是特别好的方法:
return (Boolean.valueOf(a).hashCode() + Boolean.valueOf(b).hashCode() + Boolean.valueOf(c).hashCode()) < 3705);
Boolean
的哈希码值对于 true 固定为 1231,而 false 则为 1237,因此也可以使用 <= 3699
我不喜欢三目运算符(来自顶部回答的return a ? (b || c) : (b && c);
),我认为我没有看到有人提到过它。它的写法是这样的:
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if (a) {
return b||c;
}
else {
return b&&C;
}
在Clojure中:
(defn at-least [n & bools]
(>= (count (filter true? bools)) n)
使用方法:
(at-least 2 true false true)
我们可以将布尔值转换为整数,然后执行这个简单的检查:
(int(a) + int(b) + int(c)) >= 2
a+b+c>=2
。 - dargaud我认为我还没有看到这个解决方案:
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;
}
它的优点在于一旦达到您要查找的数字,它就会停止。因此,如果这是“至少有100万个值中的2个是真实的”,而前两个确实是真实的,那么它应该比一些更“正常”的解决方案更快。
boolean ... boolValues
这种方式来使调用更加方便,但仍然需要传入一个数组。 - Stephen
atLeastTwo(iWantYou, iNeedYou, imEverGonnaLoveYou)
- Andrew GrimmatLeastTwo(0,2,0)
。请问您的看法? - Ken