0

番号があります。この数字は桁数が多いです。その数の数桁で構成される最大の数を返す関数を書きたいと思います。その最大数を取得している間、数字の順序は変更されるべきではありません。

int myFunction(int n, int cat){
   ...
   return max;   
}

関数がn = 38462637をcat = 3返す必要が86637ある場合、つまりcat = 3関数が5桁の数値を返すことが期待される場合8 - 3 = 5。元の番号には5桁の番号のバリエーションがたくさんありますが、可能な最大の番号は86637です。この場合、最も重要な要件は、数字がその場所を変更してはならないということです。

4

3 に答える 3

2

貪欲に-答えの左端にある最大の数字を選択します（この数字が表示される位置が複数ある場合は、左端の数字を選択します）。0でない場合、数字は左端にある可能性があり、その右側に少なくともn--cat-1桁あります。

その後、同じアルゴリズムを使用して、正確にn - cat - 1数字を持つこの数字の位置の右側に最大の数字を作成します。番号が作成されるまで繰り返します。最初の反復後に選択した桁がゼロになる可能性があることに注意してください（結果の数値の左端ではなくなるため）

編集：上記のアルゴリズムを使用する最良の解決策-範囲最小クエリを使用して、連続する各桁位置で可能な最大値を計算します。理論的には、これはクエリごとに一定時間で、線形事前計算を使用して線形追加メモリで実行できますが、アルゴリズムは非常に複雑で実装が難しいため、nの値が非常に大きい場合にのみ改善されます。個人的には、O（n * log（n））時間計算量になるセグメントツリーアプローチを使用することをお勧めします。

于 2012-07-02T13:14:20.963 に答える
0

コードにアクセスできる場合は、数値を区切り文字（スペース、コンマなど）を含む文字列として格納してから、文字列区切り関数を使用して、各数値（文字列文字）を独自の配列位置に配置します。文字列配列を解析し、整数配列を作成します。次に、アレイでクイックソートを実行します。それが終わったら、整数の最初のX個を取り、それがあなたの数です。

于 2012-07-02T13:07:56.800 に答える
0

これはおそらく少し複雑すぎますが、機能しているようです。

public static int myFunction(int n, int cat) {
    String numString = String.valueOf(n);
    int finalLength = numString.length() - cat;
    int[] positions = new int[finalLength];
    StringBuilder answer = new StringBuilder();
    for (int i = 0; i < finalLength; i++) {
        for (int j = (i == 0 ? i : positions[i - 1] + 1); j <= numString.length() - finalLength + i; j++) {
            if (positions[i] == 0 || numString.charAt(j) > numString.charAt(positions[i]) ) {
                positions[i] = j;
            }
        }
        answer.append(numString.charAt(positions[i]));
    }
    return Integer.parseInt(answer.toString());
}

[編集]String ：すべてのナンセンスのないよりクリーンなバージョン：

public static int myFunction(int n, int cat) {
    List<Integer> digits = new ArrayList<Integer>();
    int number = n;
    while (number > 0) {
        digits.add(number % 10);
        number /= 10;
    }
    int finalLength = digits.size() - cat;
    int lastIndex = digits.size();
    int answer = 0;
    for (int i = 0; i < finalLength; i++) {
        int highestDigit = -1;
        for (int j = lastIndex - 1; j >= finalLength - i - 1; j--) {
            if (digits.get(j) > highestDigit) {
                highestDigit = digits.get(j);
                lastIndex = j;
            }
        }
        answer = answer * 10 + highestDigit;
    }
    return answer;
}
于 2012-07-02T13:24:11.110 に答える