Ответ 1

Это рекурсивная функция, которая сортирует возможные значения swap для каждой цифры (current-max):

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)
}

Ответ 2

Я думаю, что недостающая часть состоит в том, что после выполнения K swaps, как в алгоритме, описанном OP, вы остаетесь с некоторыми номерами, которые вы можете менять между собой. Например, для номера 87949 после начального алгоритма мы получим 99748. Однако после этого мы можем бесплатно заменить 7 и 8 ", т.е. Не потреблять ни один из K-свопов. Это означало бы:" Я бы предпочел не поменять 7 со вторым 9, а с первым".

Итак, чтобы получить максимальное число, можно было бы выполнить алгоритм, описанный OP, и запомнить числа, которые были перемещены вправо, и позиции, в которые они были перемещены. Затем отсортируйте эти числа в порядке убывания и поместите их в позиции слева направо.

Это что-то вроде разделения алгоритма в два этапа - в первом вы выбираете, какие числа должны идти спереди, чтобы максимизировать первые K-позиции. Затем вы определяете порядок, в котором вы бы поменяли их номерами, позиции которых они занимали, так что остальная часть числа также максимизируется.

Не все детали понятны, и я не уверен на 100%, что он правильно обрабатывает все случаи, поэтому, если кто-то может сломать его - продолжайте.

Ответ 3

Это все псевдокод, но он легко конвертируется в другие языки. Это решение нерекурсивно и работает в режиме наихудшего случая и среднего времени.

Вам предоставляются следующие функции:

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

Изменить:

Это не относится к вопросу правильно. Если у меня будет время позже, я исправлю это, но я не сейчас.

Ответ 4

Как бы я это сделал (в псевдо-c - ничего необычного), предполагая, что массив целых чисел fantasy передается там, где каждый элемент представляет одну десятичную цифру:

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;
}

Сверху моей головы, так что, если кто-нибудь заметил какой-то фатальный недостаток, сообщите мне.

Изменить: на основании других ответов, размещенных здесь, я, вероятно, грубо неправильно понял проблему. Кто-нибудь хочет уточнить?

Ответ 5

Вы начинаете с 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()
}

Ответ 6

Здесь мой подход (он не дурацкий, но охватывает основные случаи). Сначала нам понадобится функция, которая извлекает каждый DIGIT INT в контейнер:

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, поскольку он возвращает итератор в максимальный элемент контейнера, но если есть больше, вы хотите, чтобы последний из них. Итак, давайте реализовать собственный алгоритм max:

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);
}

Есть необработанные угловые шкафы, но я оставлю это до вас.

Ответ 7

M = 132 K = 1 output = 312
M = 132 K = 2 output = 321
M = 7899 k = 2 output = 9987

Алго:

• Возьмите первую цифру и замените ее максимальным (остальные элементы)

Для экземпляра я беру 132, первую цифру → 1, max {3,2} = 3, swap (1,3) 132 → 312, K = 1.

Аналогично, 7899: k = 1, swap [7, max {8,9,9}] → 9789                  k = 2, swap [8, max {8,7,9}] → 9987

Псевдокод:

int i = 0;
while(k > 0 && i < arr.length){
int index = findMaxIndex(arr,i);
if(i != index){
    swap(arr,i ,index);
    k--;
}
i++;
}

Ответ 8

Я предположил, что K = 2, но вы можете изменить значение!

Код Java

public class Solution {
    public static void main (String args[]) {
        Solution d = new Solution();
        System.out.println(d.solve(1234));
        System.out.println(d.solve(9812));
        System.out.println(d.solve(9876));
    }
    public int solve(int number) {
        int[] array = intToArray(number);
        int[] result = solve(array, array.length-1, 2);
        return arrayToInt(result);
    }
    private int arrayToInt(int[] array) {
        String s = "";
        for (int i = array.length-1 ;i >= 0; i--) {
            s = s + array[i]+"";
        }
        return Integer.parseInt(s);
    }
    private int[] intToArray(int number){
        String s = number+"";
        int[] result = new int[s.length()];
        for(int i = 0 ;i < s.length() ;i++) {
            result[s.length()-1-i] = Integer.parseInt(s.charAt(i)+"");
        }
        return result;
    }
    private int[] solve(int[] array, int endIndex, int num) {
        if (endIndex == 0)
            return array;
        int size = num ;
        int firstIndex = endIndex - size;
        if (firstIndex < 0)
            firstIndex = 0;
        int biggest = findBiggestIndex(array, endIndex, firstIndex);
        if (biggest!= endIndex) {
            if (endIndex-biggest==num) {
                while(num!=0) {
                    int temp = array[biggest];
                    array[biggest] = array[biggest+1];
                    array[biggest+1] = temp;
                    biggest++;
                    num--;
                }
                return array;
            }else{
                int n = endIndex-biggest;
                for (int i = 0 ;i < n;i++) {
                    int temp = array[biggest];
                    array[biggest] = array[biggest+1];
                    array[biggest+1] = temp;
                    biggest++;
                }
                return solve(array, --biggest, firstIndex);
            }
        }else{
            return solve(array, --endIndex, num);
        }
    }
    private int findBiggestIndex(int[] array, int endIndex, int firstIndex) {
        int result = firstIndex;
        int max = array[firstIndex];
        for (int i = firstIndex; i <= endIndex; i++){
            if (array[i] > max){
                max = array[i];
                result = i;
            }
        }
        return result;
    }
}