670. Maximum Swap

leetcode medium

#array#csharp#leetcode#medium#string

Task

Дано целое число num. Вы можете поменять местами две цифры не более одного раза, чтобы получить число с наибольшим значением.

Верните число с наибольшим значением, которое можно получить.

Пример:

Input: num = 2736

Output: 7236

Explanation: Swap the number 2 and the number 7.

C# solution

matched/original

public class Solution {
    public int MaximumSwap(int num) {
        char[] A = num.ToString().ToCharArray();
        char[] ans = (char[])A.Clone();
        for (int i = 0; i < A.Length; i++) {
            for (int j = i + 1; j < A.Length; j++) {
                char tmp = A[i];
                A[i] = A[j];
                A[j] = tmp;
                for (int k = 0; k < A.Length; k++) {
                    if (A[k] != ans[k]) {
                        if (A[k] > ans[k]) {
                            ans = (char[])A.Clone();
                        }
                        break;
                    }
                }
                A[j] = A[i];
                A[i] = tmp;
            }
        }
        return int.Parse(new string(ans));
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaximumSwap(int num) {
        char[] A = num.ToString().ToCharArray();
        char[] ans = (char[])A.Clone();
        for (int i = 0; i < A.size(); i++) {
            for (int j = i + 1; j < A.size(); j++) {
                char tmp = A[i];
                A[i] = A[j];
                A[j] = tmp;
                for (int k = 0; k < A.size(); k++) {
                    if (A[k] != ans[k]) {
                        if (A[k] > ans[k]) {
                            ans = (char[])A.Clone();
                        }
                        break;
                    }
                }
                A[j] = A[i];
                A[i] = tmp;
            }
        }
        return int.Parse(new string(ans));
    }
}

Java solution

matched/original

class Solution {
    public int maximumSwap(int num) {
        char[] A = Integer.toString(num).toCharArray();
        char[] ans = Arrays.copyOf(A, A.length);
        for (int i = 0; i < A.length; i++) {
            for (int j = i + 1; j < A.length; j++) {
                char tmp = A[i];
                A[i] = A[j];
                A[j] = tmp;
                for (int k = 0; k < A.length; k++) {
                    if (A[k] != ans[k]) {
                        if (A[k] > ans[k]) {
                            ans = Arrays.copyOf(A, A.length);
                        }
                        break;
                    }
                }
                A[j] = A[i];
                A[i] = tmp;
            }
        }
        return Integer.valueOf(new String(ans));
    }
}

JavaScript solution

matched/original

var maximumSwap = function(num) {
    let A = num.toString().split('');
    let ans = [...A];
    for (let i = 0; i < A.length; i++) {
        for (let j = i + 1; j < A.length; j++) {
            [A[i], A[j]] = [A[j], A[i]];
            for (let k = 0; k < A.length; k++) {
                if (A[k] !== ans[k]) {
                    if (A[k] > ans[k]) {
                        ans = [...A];
                    }
                    break;
                }
            }
            [A[i], A[j]] = [A[j], A[i]];
        }
    }
    return parseInt(ans.join(''));
}

Python solution

matched/original

class Solution:
    def maximumSwap(self, num: int) -> int:
        A = list(str(num))
        ans = A[:]
        for i in range(len(A)):
            for j in range(i + 1, len(A)):
                A[i], A[j] = A[j], A[i]
                for k in range(len(A)):
                    if A[k] != ans[k]:
                        if A[k] > ans[k]:
                            ans = A[:]
                        break
                A[i], A[j] = A[j], A[i]
        return int(''.join(ans))

Go solution

matched/original

func maximumSwap(num int) int {
    A := []rune(strconv.Itoa(num))
    ans := make([]rune, len(A))
    copy(ans, A)
    for i := 0; i < len(A); i++ {
        for j := i + 1; j < len(A); j++ {
            A[i], A[j] = A[j], A[i]
            for k := 0; k < len(A); k++ {
                if A[k] != ans[k] {
                    if A[k] > ans[k] {
                        copy(ans, A)
                    }
                    break
                }
            }
            A[i], A[j] = A[j], A[i]
        }
    }
    result, _ := strconv.Atoi(string(ans))
    return result
}

Explanation

Algorithm

Сохраняем кандидатов как списки длины len(num). Для каждой пары позиций (i, j) выполняем обмен цифр, записываем кандидата, если он больше текущего ответа, затем возвращаем цифры обратно.

Проверяем, что не добавили ведущий ноль. Фактически, проверять это не нужно, так как изначальное число его не содержит.

Возвращаем максимальное значение из всех кандидатов.

😎