23

最近面接を受けて、こんな質問をされました。質問を適切に説明しましょう。

数値 M (N 桁の整数) と K 個のスワップ操作 (スワップ操作は 2 桁をスワップできます) が与えられた場合、可能な最大整数を取得するアルゴリズムを考案しますか?
例:
M = 132 K = 1 出力 = 312
M = 132 K = 2 出力 = 321
M = 7899 k = 2 出力 = 9987

私の解決策（疑似コードのアルゴリズム）。max-heap を使用して、各 K 操作で N 桁から最大桁を取得し、適切に交換しました。 

for(int i = 0; i<K; i++)
{
    int max_digit_currently = GetMaxFromHeap();
    // The above function GetMaxFromHeap() pops out the maximum currently and deletes it from heap

    int index_to_swap_with = GetRightMostOccurenceOfTheDigitObtainedAbove();
    // This returns me the index of the digit obtained in the previous function  
    // .e.g If I have 436659 and K=2 given,   
    // then after K=1 I'll have 936654 and after K=2, I should have 966354 and not 963654.

    // Now, the swap part comes. Here the gotcha is, say with the same above example, I have K=3.
    // If I do GetMaxFromHeap() I'll get 6 when K=3, but I should not swap it, 
    // rather I should continue for next iteration and 
    // get GetMaxFromHeap() to give me 5 and then get 966534 from 966354.

    if (Value_at_index_to_swap == max_digit_currently)
        continue;
    else
        DoSwap();
}

時間の複雑さ: O(K*( N + log_2(N) ))
// K 回 [ヒープから数をポップアウトするための log_2(N) & スワップする最も右のインデックスを取得するための N]

この例では、上記の戦略は失敗します:
M = 8799 および K = 2
私の戦略に従うと、K=1 の後に M = 9798 が得られ、K=2 の後に M = 9978 が得られます。ただし、取得できる最大値は、K = 2 の後で M = 9987 です。

私は何を取りこぼしたか？
また、問題を解決する他の方法と、ソリューションを最適化する方法を提案してください。

4

7 に答える 7

1

これは再帰関数であり、各 (現在の最大) 桁の可能なスワップ値を並べ替えます。

function swap2max(string, K) {
    // the recursion end:
    if (string.length==0 || K==0)
        return string

    m = getMaxDigit(string)
    // an array of indices of the maxdigits to swap in the string
    indices = []
    // a counter for the length of that array, to determine how many chars
    // from the front will be swapped
    len = 0
    // an array of digits to be swapped
    front = []
    // and the index of the last of those:
    right = 0
    // get those indices, in a loop with 2 conditions:
    // * just run backwards through the string, until we meet the swapped range
    // * no more swaps than left (K)
    for (i=string.length; i-->right && len<K;)
        if (m == string[i])
            // omit digits that are already in the right place
            while (right<=i && string[right] == m)
                right++
            // and when they need to be swapped
            if (i>=right)
                front.push(string[right++])
                indices.push(i)
                len++
    // sort the digits to swap with
    front.sort()
    // and swap them
    for (i=0; i<len; i++)
        string.setCharAt(indices[i], front[i])
    // the first len digits are the max ones
    // the rest the result of calling the function on the rest of the string
    return m.repeat(right) + swap2max(string.substr(right), K-len)
}
于 2012-08-29T17:32:31.660 に答える
1

欠けている部分は、OP で説明されているアルゴリズムのように K スワップを実行した後、それらの間で交換できるいくつかの数値が残っていることだと思います。たとえば、数値 87949 の場合、最初のアルゴリズムの後で 99748 が得られます。ただし、その後は 7 と 8 を「無料で」スワップできます。つまり、K スワップを消費しません。これは、「7 を 2 番目の 9 と交換するのではなく、最初の 9 と交換したい」という意味です。

したがって、最大数を取得するには、OP で説明されているアルゴリズムを実行し、右に移動した数値とそれらが移動した位置を記憶します。次に、これらの数値を降順に並べ替え、左から右の位置に配置します。

これは、アルゴリズムを 2 つの段階に分けたようなものです。最初の段階では、最初の K の位置を最大化するためにどの数値を前に置くかを選択します。次に、残りの数も同様に最大化されるように、それらが取った位置の数字と交換する順序を決定します。

すべての詳細が明確になっているわけではなく、すべてのケースを正しく処理できるとは 100% 確信が持てません。

于 2012-08-29T20:42:50.867 に答える
0

これが私のアプローチです（絶対確実ではありませんが、基本的なケースをカバーしています）。まず、INT の各 DIGIT をコンテナーに抽出する関数が必要です。

std::shared_ptr<std::deque<int>> getDigitsOfInt(const int N)
{
    int number(N);
    std::shared_ptr<std::deque<int>> digitsQueue(new std::deque<int>());
    while (number != 0)
    {
        digitsQueue->push_front(number % 10);
        number /= 10;
    }
    return digitsQueue;
}

明らかにこれの逆を作成したいので、そのようなコンテナーを INT に変換します。

const int getIntOfDigits(const std::shared_ptr<std::deque<int>>& digitsQueue)
{
    int number(0);
    for (std::deque<int>::size_type i = 0, iMAX = digitsQueue->size(); i < iMAX; ++i)
    {
        number = number * 10 + digitsQueue->at(i);
    }
    return number;
}

また、MAX_DIGIT を見つける必要があります。std::max_element を使用すると、コンテナの最大要素へのイテレータが返されるため、使用すると便利ですが、それ以上の要素がある場合は、最後の要素が必要です。それでは、独自の最大アルゴリズムを実装しましょう。

int getLastMaxDigitOfN(const std::shared_ptr<std::deque<int>>& digitsQueue, int startPosition)
{
    assert(!digitsQueue->empty() && digitsQueue->size() > startPosition);
    int maxDigitPosition(0);
    int maxDigit(digitsQueue->at(startPosition));
    for (std::deque<int>::size_type i = startPosition, iMAX = digitsQueue->size(); i < iMAX; ++i)
    {
        const int currentDigit(digitsQueue->at(i));

        if (maxDigit <= currentDigit)
        {
            maxDigit = currentDigit;
            maxDigitPosition = i;
        }
    }
    return maxDigitPosition;
}

ここから、あなたがしなければならないことはかなり簡単です。スワップできるようになるまで、一番右 (最後) の MAX DIGITS をそれぞれの場所に置きます。

const int solution(const int N, const int K)
{
    std::shared_ptr<std::deque<int>> digitsOfN = getDigitsOfInt(N);

    int pos(0);
    int RemainingSwaps(K);
    while (RemainingSwaps)
    {
        int lastHDPosition = getLastMaxDigitOfN(digitsOfN, pos);
        if (lastHDPosition != pos)
        {
            std::swap<int>(digitsOfN->at(lastHDPosition), digitsOfN->at(pos));

            ++pos;
            --RemainingSwaps;
        }
    }

    return getIntOfDigits(digitsOfN);
}

未処理のコーナーケースがありますが、それはお任せします。

于 2014-10-04T13:52:06.663 に答える
0

から始めmax-number(M, N, 1, K)ます。

max-number(M, N, pos, k)
{
    if k == 0
        return M
    max-digit = 0
    for i = pos to N
        if M[i] > max-digit
            max-digit = M[i]
    if M[pos] == max-digit
        return max-number(M, N, pos + 1, k)
    for i = (pos + 1) to N
        maxs.add(M)
        if M[i] == max-digit
            M2 = new M
            swap(M2, i, pos)
            maxs.add(max-number(M2, N, pos + 1, k - 1))
    return maxs.max()
}
于 2012-08-29T18:47:53.290 に答える
0

これはすべて疑似コードですが、他の言語への変換はかなり簡単です。このソリューションは非再帰的であり、線形の最悪のケースと平均的なケースの時間で動作します。

次の機能が提供されます。

function k_swap(n, k1, k2):
    temp = n[k1]
    n[k1] = n[k2]
    n[k2] = temp

int : operator[k]
    // gets or sets the kth digit of an integer

property int : magnitude
    // the number of digits in an integer

次のようなことができます。

int input = [some integer] // input value

int digitcounts[10] = {0, ...} // all zeroes
int digitpositions[10] = {0, ...) // all zeroes
bool filled[input.magnitude] = {false, ...) // all falses

for d = input[i = 0 => input.magnitude]:
    digitcounts[d]++ // count number of occurrences of each digit

digitpositions[0] = 0;
for i = 1 => input.magnitude:
    digitpositions[i] = digitpositions[i - 1] + digitcounts[i - 1] // output positions

for i = 0 => input.magnitude:
    digit = input[i]
    if filled[i] == true:
        continue
    k_swap(input, i, digitpositions[digit])
    filled[digitpositions[digit]] = true
    digitpositions[digit]++

番号で説明しますinput = 724886771

computed digitcounts:
{0, 1, 1, 0, 1, 0, 1, 3, 2, 0}

computed digitpositions:
{0, 0, 1, 2, 2, 3, 3, 4, 7, 9}

swap steps:
swap 0 with 0: 724886771, mark 0 visited
swap 1 with 4: 724876781, mark 4 visited
swap 2 with 5: 724778881, mark 5 visited
swap 3 with 3: 724778881, mark 3 visited
skip 4 (already visited)
skip 5 (already visited)
swap 6 with 2: 728776481, mark 2 visited
swap 7 with 1: 788776421, mark 1 visited
swap 8 with 6: 887776421, mark 6 visited

output number: 887776421

編集：

これは質問に正しく対処していません。後で時間があれば修正しますが、今はしていません。

于 2012-08-29T17:53:19.067 に答える
0

各要素が 10 進数の 1 桁を表すファンタジー整数配列が渡されると仮定すると、(疑似 c で - 空想的なものは何もありません) どのようにそれを行うか:

int[] sortToMaxInt(int[] M, int K) {
    for (int i = 0; K > 0 && i < M.size() - 1; i++) {
        if (swapDec(M, i)) K--;
    }
    return M;
}

bool swapDec(int[]& M, int i) {
    /* no need to try and swap the value 9 as it is the 
     * highest possible value anyway. */
    if (M[i] == 9) return false;

    int max_dec = 0;
    int max_idx = 0;
    for (int j = i+1; j < M.size(); j++) {
        if (M[j] >= max_dec) {
            max_idx = j;
            max_dec = M[j];
        }
    }

    if (max_dec > M[i]) {
        M.swapElements(i, max_idx);
        return true;
    }
    return false;
}

私の頭の上から、誰かが致命的な欠陥を見つけたら、私に知らせてください.

編集：ここに投稿された他の回答に基づいて、おそらく問題をひどく誤解していました。誰か詳しく説明したいですか？

于 2012-08-29T18:15:45.013 に答える