0

嘿，我参加了 Facebook 黑客竞赛，我得到了这个问题的解决方案。我以 O(K^2) 的顺序解决了这个问题，但这个人在 O(^K) 中解决了这个问题。请解释一下代码在做什么。

    import java.io.File;
    import java.util.Scanner;

     public class FindTheMin {

private long getNextMin(long[] map, long start, long k) {
    while (map[(int)(start)] > 0)
        start++;
    return start;
}

public long findNth(long n, long k, long a, long b, long c, long r) {
    long[] cache = new long[100010];
    long[] map = new long[100010];
    long pre = a;
    for (int i = 0; i < k; i++) {
        long num;
        if (i == 0)
            num = a;
        else
            num = (b * pre + c) % r;
        cache[i] = num;
        if (num <= k + 1)
            map[(int) num]++;
        pre = num;
    }

    pre = getNextMin(map, 0, k);
    cache[(int)k] = pre;
    map[(int)pre]++;
    for (int i = 0; i <= (int)k; i++) {
        long deque = cache[i];
        if (deque > k) {
            long x = getNextMin(map, pre, k);
            cache[i] = x;
            map[(int)x]++;
            pre = x;
        } else {
            if (deque < pre) {
                if(map[(int)deque] == 1) {
                    cache[i] = deque;
                    pre = deque;
                    continue;
                }
            }
            map[(int)deque]--;
            long x = getNextMin(map, pre, k);
            cache[i] = x;
            pre = x;
            map[(int)x]++;
        }
    }

    return cache[(int)((n - 1) % (k + 1))];
}

public static void main(String[] args) {
    try {
        Scanner s = new Scanner(new File("in.txt"));
        int m = s.nextInt();
        FindTheMin f = new FindTheMin();

        for (int i = 1; i <= m; i++) {
            int n, k, a, b, c, r;
            n = s.nextInt();
            k = s.nextInt();
            a = s.nextInt();
            b = s.nextInt();
            c = s.nextInt();
            r = s.nextInt();
            System.out.println("Case #" + i + ": " + f.findNth(n, k, a, b, c, r));
        }
    } catch (Exception e) {
        e.printStackTrace();
    }
}

}

学习这样的东西的最佳方法是什么。学习java最好的方法？这是问题 https://www.facebook.com/hackercup/problems.php?pid=494433657264959&round=185564241586420

4

3 回答 3

2

map[(int)x]++与以下内容相同：

int index = (int) x;
map[index]++;
于 2013-02-05T20:53:39.810 回答
1

在

long x = getNextMin(map, pre, k);
cache[i] = x;
map[(int)x]++;

Whilex是 long，数组的索引只能是 int。此外，更重要的是，虽然getNextMin返回 a long，但程序员知道该值实际上是一个int(ie x <= Integer.MAX_VALUE)，否则可能会溢出导致负值，x从而导致 ArrayIndexOutOfBoundsException 异常。

现在因为 java 是静态类型的，尽管返回的值getNextMin适合int; 你仍然必须告诉编译器你打算将它用作int; 否则编译器会假设它是一个long. 这就是你看到的原因(int)x——因为数组索引必须是类型int

对于代码本身

map[(int)x]++;

可以写成

map[(int)x] =  map[(int)x] + 1;

或作为

int y = (int) x
map[y]++; // or as map[y] = map[y] + 1

同样，如果返回的值getNextMin大于Integer.MAX_VALUE代码将抛出异常。因此，程序员没有处理潜在的异常可能是一个设计缺陷。

于 2013-02-06T04:44:53.943 回答
1

它的作用是map[(int)x]++;什么？

java 中的数组只接受整数索引，但代码中的 x 是一个长值。因此必须将其转换为 int：

此代码从数组映射中获取索引 x 处的元素并将值加 1：

如同：

map[ix]++;  // where ix = (int) x;

问题 2：学习这类东西的最佳方法是什么。学习java最好的方法？

购买、阅读和理解：

Robert Sedgewick, Algorithms Fourth Edition
于 2013-02-05T20:55:32.353 回答