Сложность: medium
Дано целое число num. Вы можете поменять местами две цифры не более одного раза, чтобы получить число с наибольшим значением.
Верните число с наибольшим значением, которое можно получить.
Пример:
Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.
👨💻 Алгоритм:
1⃣Сохраняем кандидатов как списки длины len(num). Для каждой пары позиций (i, j) выполняем обмен цифр, записываем кандидата, если он больше текущего ответа, затем возвращаем цифры обратно.
2⃣Проверяем, что не добавили ведущий ноль. Фактически, проверять это не нужно, так как изначальное число его не содержит.
3⃣Возвращаем максимальное значение из всех кандидатов.
😎 Решение:
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));
}
}Ставь 👍 и забирай 📚 Базу знаний