Java HashSet(长整型与整数)

Question

我正在解决这个问题(来自 Project Euler 的 41)，我注意到 HashSet 的 contains 方法对于 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 之外的任何对象类型会导致它返回 false ，自 equals()对于不同类型的对象会失败(有一些异常(exception))。

所以，当您调用contains(x)时，和x是一个基元，它将根据 x 的类型自动装箱。 ，不是 E 的类型。所以如果 x是 int和E是 Long ，它总是返回 false .

这不是contains()当你改变 Long 时，效果突然不同了至Integer 。通过正确匹配传递给 contains() 的值类型，您的代码会发挥不同的作用。集合中元素的类型。

<小时/>

更新

您的代码效率不是很高:

• 需要 Long作为参数，但 max n本质上是9 ，和 int可以存储9位数字而不会溢出，因此使用Long ，并且使用拳击，是不必要的。

• 它分配一个新的 HashSet对于每个被检查的值，并自动装箱找到的每个数字，加上 contains() 的 9 次来电。

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

下面的代码将建立两个位掩码，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);
}