Java HashSet（长整型）

Question

我正在解决这个问题（来自 Project Euler 的 41），我注意到 contains 的 HashSet 方法对于 Long 与 Integer 的工作方式不同（我在这里可能错了，如果我错了请纠正我）。

问题是 -

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

我检查号码是否为 Pandigital 的代码是 -

private static boolean isPan(Long n) {
        HashSet<Long> list = new HashSet<Long>();
        int count = 0;
        while(n != 0){
            list.add(n%10);
            count++;
            n /= 10;
        }
        for(int i = 9; i>count; i--){
            if(list.contains(i)) return false;
        }
        for(int i = 1; i<= count; i++){
            if(!list.contains(i)) return false;
        }
        return true;
    }

这段代码给了我一个无限循环。所以，我像这样更改了我的代码 -

private static boolean isPan(Long n) {
        HashSet<Integer> list = new HashSet<Integer>();
        int count = 0;
        while(n != 0){
            list.add((int) (n%10));
            count++;
            n /= 10;
        }
        for(int i = 9; i>count; i--){
            if(list.contains(i)) return false;
        }
        for(int i = 1; i<= count; i++){
            if(!list.contains(i)) return false;
        }
        return true;
    }

我刚刚更改，HashSet<Long> 到 HashSet<Integer> 和 list.add(n%10) 到 list.add((int) n%10)。

这给了我正确的答案，7652413。所以，谁能解释为什么 contains 方法对 Long 和 Integer 的工作方式不同？

Answer 1

contains(Object o) 方法对 Long 和 Integer 的作用没有区别。它的工作原理完全相同，即

Returns true if this set contains the specified element. More formally, returns true if and only if this set contains an element e such that (o==null ? e==null : o.equals(e)).

但是请注意，该方法接受 Object 作为参数类型，而不是 E。这意味着您可以使用任何类型的对象调用它。当然，除 E 之外的任何对象类型都会导致它成为 return false，因为 equals() 对于不同类型的对象 会失败（有一些例外).

所以，当你调用 contains(x) 时，x 是一个 primitive，它将根据 [= 的类型自动装箱23=]，不是 E 的类型。因此，如果 x 是 int 并且 E 是 Long，它总是 return false.

当您将 Long 更改为 Integer 时，并不是 contains() 突然变得不一样了。通过将传递给 contains() 的值类型与集合中的元素类型正确匹配，您的代码会有所不同。

更新

您的代码效率不高：

它以一个Long作为参数，但是maxn本质上是9，而int可以存储9位没有溢出的数字，因此不需要使用 Long 和装箱。
它为每个被检查的值分配一个新的 HashSet，并自动装箱找到的每个数字，加上 contains() 调用的 9 次。

相反，这可以使用位操作来完成，因为 32 位 int 值可以轻松存储 10 个布尔值（标志），指示数字是否存在。

下面的代码将建立两个位掩码，found 和 expected，这将指示是否找到了一个数字，以及是否应该找到一个数字。由于解决方案应该只使用数字 1-n，我们将声称数字 0 存在并且预期 （使逻辑更简单，不必对 0 进行特殊检查）.

如果一个数字出现两次（或数字 0 出现一次），另一个预期的数字将丢失，并且 found 将不等于 expected。

private static boolean isPandigital(int number) {
    int found = 1, expected = 1;
    for (int n = number; n != 0; n /= 10, expected = (expected << 1) | 1)
        found |= 1 << (n % 10);
    return (found == expected);
}

Answer 2

如果您希望代码运行正确，请查看 list 为 HashSet<Long> 的代码：

for(int i = 1; i<= count; i++){
    if(!list.contains(i)) return false;
}

你可以把变量的类型i改成long，或者把if(!list.contains(i)) return false;改成if(!list.contains(Long.valueOf(i))) return false;

因为 contains 将通过元素的方法 equals 检查元素是否存在。在上面的代码中，变量 i 被自动装箱到 Integer 实例，因为变量 i 是原始的 int。并查看整数 equals:

public boolean equals(Object obj) {
    if (obj instanceof Integer) {
        return value == ((Integer)obj).intValue();
    }
    return false;
}

但是你的 list 元素的类型是 Long，所以行 if(!list.contains(i)) return false; 总是 return false。

Java HashSet（长整型）

Java HashSet (Long vs Integer)

java

hashset

long-integer