0

我有一个关于编码的问题。我想就下面的问题从你那里得到一些指示。有一个整数数组。这些数组数字表示人的年龄。如果列表中有一个人的年龄正好是其他人的两倍，则编写一个函数返回 true，否则该函数返回 false。

以下是约束。

  • Age 是一个整数，取值范围为 0 到 50
  • 您只能使用数字类型的变量（没有数组/切片/映射）
  • 必须具有线性时间复杂度，只有一个循环
  • 您不得使用加法、减法、乘法、除法或模运算符
  • 该函数不能包含超过 15 行代码
  • 该函数不能调用其他函数

假设列表已排序，我可以提出以下功能

// Go 函数：假设，年龄列表已排序。

func isPersonTwiceOldAsOthers(person []Person) bool {
    if len(person) < 2 {
        fmt.Printf("Need minimum 2 person's age to continue\n")
        return false
    }
    seen := make(map[int]bool, 15)
    for index, _ := range person {
        if seen[person[index].Age] {
            return true
        }
        seen[person[index].Age*2] = true
    }
    return false
}

我正在寻找使用上面列出的约束编写代码的帮助。任何帮助，将不胜感激。

4

1 回答 1

0

您可以使用按位运算符。

由于年龄限制为最大 50，因此只有 25 个不同的对，其中一个是另一个的两倍：(0, 0), (1, 2), ... (25, 50)。这 25 种可能性中的每一种都可以是（32 位）整数中的一位。

您可以使用一个整数来标记您遇到的年龄介于 0 到 25 之间的位（对于该对的第一部分），并使用另一个整数来标记您遇到偶数年龄的位：您将首先将年龄减半，然后设置相应的位。

当这两个整数有一个共同的位集时，答案是肯定的。这是一个逻辑与。

有一种特殊情况：0 的双倍是 0，所以如果我们遇到单个 0，那么两个整数的第一位都会被设置为 1。但要求是有“另一个”具有双倍年龄的人，所以这会产生误报。所以，解决方案是区别对待 0，只计算你是否有两个。

这是 JavaScript 中的一个实现：

function isPersonTwiceOldAsOthers(persons) {
    let smalls = 0, halves = 0, numZeroes = 0;
    for (let age of persons) {
        if (age == 0) numZeroes++;
        if (age > 0 && age <= 25) smalls |= (1 << age);
        if (age > 0 && (age & 1) == 0) halves |= (1 << (age >> 1));
    }
    return numZeroes > 1 || (smalls & halves) != 0;
}

// Demo
let res;
res = isPersonTwiceOldAsOthers([4, 9, 34, 12, 18, 37]);
console.log(res); // true

res = isPersonTwiceOldAsOthers([4, 7, 34, 12, 18, 37]);
console.log(res); // false

res = isPersonTwiceOldAsOthers([4, 0, 34, 12, 18, 37]);
console.log(res); // false

res = isPersonTwiceOldAsOthers([4, 0, 34, 12, 18, 0]);
console.log(res); // true

注意：在 C 类型和许多其他语言中，代码行数是主观的。

在 Go 中，它可能看起来像这样：

func isPersonTwiceOldAsOthers(person []int) bool {
    var smalls, halves, numZeroes int;
    for _, age := range person {
        if age == 0 {
            numZeroes++; 
        }
        if age > 0 && age < 26 {
            smalls |= (1 << age);
        }
        if age > 0 && (age & 1) == 0 {
            halves |= (1 << (age >> 1));
        }
    }
    return numZeroes > 1 || (smalls & halves) != 0;
}

func main() {
    res := isPersonTwiceOldAsOthers([]int{4, 9, 34, 12, 18, 37});
    println(res); // true
    
    res = isPersonTwiceOldAsOthers([]int{4, 7, 34, 12, 18, 37});
    println(res); // false

    res = isPersonTwiceOldAsOthers([]int{4, 0, 34, 12, 18, 37});
    println(res); // false

    res = isPersonTwiceOldAsOthers([]int{4, 0, 34, 12, 18, 0});
    println(res); // true  
}
于 2020-10-10T20:14:33.040 回答