0

Facebook Hacker Competition に参加して、この質問の解決策を見つけました。私は 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]++;

はxlong ですが、配列のインデックスは int のみです。さらに、より重要なことに、getNextMinは を返しlongますが、プログラマーは値が実際にはint(つまり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 は long 値です。したがって、int にキャストする必要があります。

このコードは、配列マップからインデックス x の要素を取得し、値に 1 を追加します。

と同じ：

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

質問 2: このようなことを学ぶための最良の方法は何ですか? Javaを学ぶ最良の方法は？

購入し、読んで理解する:

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