暴力，贪心算法，三次遍历（倒序 + 正序 + 倒序），一次遍历（倒序），数字转列表（Array.from / str_split / []byte(strconv.Itoa()) / String.valueOf().toCharArray() / ToString().ToCharArray() / sprintf(s, "%d", num) / to_string / list(str())），列表转数字（+a.join('') / +implode('') / strconv.Atoi(string()) / Integer.parseInt(new String()) / int.Parse(new string()) / atoi / stoi / int(''.join())），交换变量（临时变量 / 指针交换 / 加减法 / 解构赋值 / 位运算 / 求和减赋值法），3 解法求解《670. 最大交换》
例题
670. 最大交换
给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例 1 :
输入: 2736
输出: 7236
解释: 交换数字2和数字7。
示例 2 :
输入: 9973
输出: 9973
解释: 不需要交换。
注意:
给定数字的范围是 [0, 108]
思路
- 找到左边 < 右边的最大值的位置
- 右边最大值有多个时：交换最右边的最大值（把左边的小数尽可能交换到最右边）
答案
贪心 · 三次遍历
倒序遍历：记录右边起，每个位置的最大值
正序遍历：当前数字 < 小于右边的最大值 倒序遍历：找到最大值索引，交换
var maximumSwap = function(num) {
const a = Array.from(String(num), v => +v), n = a.length, maxNums = new Uint8Array(n)
let maxNum = 0
for (let i = n; i-- > 1;) {
maxNum = Math.max(maxNum, a[i])
maxNums[i] = maxNum
}
for (let i = 0; i < n - 1; i++) {
if (a[i] < maxNums[i + 1]) {
const t = a[i]
a[i] = maxNums[i + 1]
for (let j = n; j-- > i;) {
if (a[j] === a[i]) {
a[j] = t
return +a.join('')
}
}
}
}
return num
};贪心 · 一次遍历
倒序遍历：
当前位置 > 右侧最大值：
- 更新右边最大值的索引为当前索引
当前位置 < 右侧最大值： - 更新左边要交换位置索引为当前索引
- 更新右边要交换位置索引为最大值索引
var maximumSwap = function(num) {
const a = Array.from(String(num), v => +v), n = a.length
let maxIndex = n - 1, j = -1, k = -1
for (let i = n - 1; i--;) {
if (a[i] > a[maxIndex]) maxIndex = i
else if (a[i] < a[maxIndex]) {
j = i
k = maxIndex
}
}
if (j === -1) return num
swap(a, j, k)
return +a.join('')
};
const swap = (nums, a, b) => { // 加减交换变量
nums[b] = nums[a] + nums[b] - (nums[a] = nums[b])
}function maximumSwap(num: number): number {
const a = Array.from(String(num), v => +v), n = a.length
let maxIndex = n - 1, j = -1, k = -1
for (let i = n - 1; i--;) {
if (a[i] > a[maxIndex]) maxIndex = i
else if (a[i] < a[maxIndex]) {
j = i
k = maxIndex
}
}
if (j === -1) return num
swap(a, j, k)
return +a.join('')
};
const swap = (nums, a, b) => { // 临时变量交换变量
nums[a] += nums[b]
nums[b] = nums[a] - nums[b]
nums[a] -= nums[b]
}class Solution {
function maximumSwap($num) {
$a = str_split($num);
$n = strlen($num);
$maxIndex = $n - 1;
$j = $k = -1;
for ($i = $n - 1; $i--;) {
if ($a[$i] > $a[$maxIndex]) $maxIndex = $i;
else if ($a[$i] < $a[$maxIndex]) {
$j = $i;
$k = $maxIndex;
}
}
if ($j === -1) return $num;
$this->swap($a, $j, $k);
return +implode('', $a);
}
function swap(&$nums, $a, $b) {
[$nums[$a], $nums[$b]] = [$nums[$b], $nums[$a]];
}
}func maximumSwap(num int) int {
a := []byte(strconv.Itoa(num))
n := len(a)
maxIndex, j, k := n - 1, -1, -1
for i := n - 2; i >= 0; i-- {
if a[i] > a[maxIndex] {
maxIndex = i
} else if a[i] < a[maxIndex] {
j, k = i, maxIndex
}
}
if j == -1 {
return num
}
swap(a, j, k)
t, _ := strconv.Atoi(string(a))
return t
}
func swap(nums []byte, a int, b int) {
nums[a], nums[b] = nums[b], nums[a]
}class Solution {
public int maximumSwap(int num) {
char[] a = String.valueOf(num).toCharArray();
int n = a.length, maxIndex = n - 1, j = -1, k = -1;
for (int i = n - 2; i >= 0; i--) {
if (a[i] > a[maxIndex]) maxIndex = i;
else if (a[i] < a[maxIndex]) {
j = i;
k = maxIndex;
}
}
if (j == -1) return num;
swap(a, j, k);
return Integer.parseInt(new String(a));
}
public void swap(char[] nums, int a, int b) {
nums[a] ^= nums[b];
nums[b] ^= nums[a];
nums[a] ^= nums[b];
}
}public class Solution {
public int MaximumSwap(int num) {
char[] a = num.ToString().ToCharArray();
int n = a.Length, maxIndex = n - 1, j = -1, k = -1;
for (int i = n - 2; i >= 0; i--) {
if (a[i] > a[maxIndex]) maxIndex = i;
else if (a[i] < a[maxIndex]) {
j = i;
k = maxIndex;
}
}
if (j == -1) return num;
swap(a, j, k);
return int.Parse(new string(a));
}
public void swap(char[] nums, int a, int b) {
nums[a] ^= nums[b];
nums[b] ^= nums[a];
nums[a] ^= nums[b];
}
}void swap(char* nums, int a, int b) { // 加减交换变量
nums[a] += nums[b];
nums[b] = nums[a] - nums[b];
nums[a] -= nums[b];
}
int maximumSwap(int num){
char* a = malloc(sizeof(char) * 9);
sprintf(a, "%d", num);
int n = strlen(a), maxIndex = n - 1, j = -1, k = -1;
for (int i = n - 1; i--;) {
if (a[i] > a[maxIndex]) maxIndex = i;
else if (a[i] < a[maxIndex]) {
j = i;
k = maxIndex;
}
}
if (j == -1) return num;
swap(a, j, k);
return atoi(a);
}void swap(char* a, char* b) { // 指针交换变量
char t = *a;
*a = *b;
*b = t;
}
int maximumSwap(int num){
char* a = malloc(sizeof(char) * 9);
sprintf(a, "%d", num);
int n = strlen(a), maxIndex = n - 1, j = -1, k = -1;
for (int i = n - 1; i--;) {
if (a[i] > a[maxIndex]) maxIndex = i;
else if (a[i] < a[maxIndex]) {
j = i;
k = maxIndex;
}
}
if (j == -1) return num;
swap(&a[j], &a[k]);
return atoi(a);
}class Solution {
public:
int maximumSwap(int num) {
string s = to_string(num);
int n = s.size(), maxIndex = n - 1, j = -1, k = -1;
for (int i = n - 1; i--;) {
if (s[i] > s[maxIndex]) maxIndex = i;
else if (s[i] < s[maxIndex]) {
j = i;
k = maxIndex;
}
}
if (j == -1) return num;
swap(s[j], s[k]);
return stoi(s);
}
};class Solution:
def swap(self, nums: list, a: int, b: int):
nums[a], nums[b] = nums[b], nums[a]
def maximumSwap(self, num: int) -> int:
a = list(str(num))
n = len(a)
maxIndex, j, k = n - 1, -1, -1
for i in range(n - 2, -1, -1):
if a[i] > a[maxIndex]: maxIndex = i
elif a[i] < a[maxIndex]: j, k = i, maxIndex
if j == -1: return num
self.swap(a, j, k)
return int(''.join(a))暴力
枚举所有可能交换的位置，更新最大值
var maximumSwap = function(num) {
const a = Array.from(String(num), v => +v), n = a.length
let r = num
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
swap(a, i, j)
r = Math.max(r, +a.join(''))
swap(a, j, i)
}
}
return r
};
const swap = (nums, a, b) => { // 临时变量
const t = nums[a]
nums[a] = nums[b]
nums[b] = t
}function maximumSwap(num: number): number {
const a = Array.from(String(num), v => +v), n = a.length
let r = num
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
swap(a, i, j)
r = Math.max(r, +a.join(''))
swap(a, j, i)
}
}
return r
};
const swap = (nums, a, b) => { // 位运算交换
nums[a] ^= nums[b]
nums[b] ^= nums[a]
nums[a] ^= nums[b]
}class Solution {
function maximumSwap($num) {
$a = str_split($num);
$n = strlen($num);
$r = $num;
for ($i = 0; $i < $n; $i++) {
for ($j = $i + 1; $j < $n; $j++) {
$this->swap($a, $i, $j);
$r = max($r, implode('', $a));
$this->swap($a, $j, $i);
}
}
return $r;
}
function swap(&$nums, $a, $b) {
list($nums[$a], $nums[$b]) = array($nums[$b], $nums[$a]);
}
}func maximumSwap(num int) int {
s := []byte(strconv.Itoa(num))
n, r := len(s), num
for i, _ := range s {
for j := i + 1; j < n; j++ {
swap(s, i, j)
t, _ := strconv.Atoi(string(s))
r = max(r, t)
swap(s, j, i)
}
}
return r
}
func swap(nums []byte, a int, b int) {
nums[a], nums[b] = nums[b], nums[a]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}class Solution {
public int maximumSwap(int num) {
char[] a = Integer.toString(num).toCharArray();
int n = a.length;
int r = num;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
swap(a, i, j);
r = Math.max(r, Integer.valueOf(new String(a)));
swap(a, j, i);
}
}
return r;
}
private void swap(char[] nums, int a, int b) {
char t = nums[a];
nums[a] = nums[b];
nums[b] = t;
}
}public class Solution {
public int MaximumSwap(int num) {
char[] a = num.ToString().ToCharArray();
int n = a.Length, r = num;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
swap(a, i, j);
r = Math.Max(r, int.Parse(new string(a)));
swap(a, j, i);
}
}
return r;
}
public void swap(char[] nums, int a, int b) {
char t = nums[a];
nums[a] = nums[b];
nums[b] = t;
}
}#define MAX(a, b) (a > b ? a : b)
void swap(char* nums, int a, int b) { // 加减交换变量
nums[a] += nums[b];
nums[b] = nums[a] - nums[b];
nums[a] -= nums[b];
}
int maximumSwap(int num){
char* a = malloc(sizeof(char) * 9);
sprintf(a, "%d", num);
int n = strlen(a), r = num;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
swap(a, i, j);
r = MAX(r, atoi(a));
swap(a, j, i);
}
}
return r;
}#define MAX(a, b) (a > b ? a : b) // 指针交换遍变量
void swap(char* a, char* b) {
char t = *a;
*a = *b;
*b = t;
}
int maximumSwap(int num){
char* a = malloc(sizeof(char) * 9);
sprintf(a, "%d", num);
int n = strlen(a), r = num;
for (int i = 1; i < n; i++) {
for (int j = i; j--;) {
swap(&a[i], &a[j]);
r = MAX(r, atoi(a));
swap(&a[j], &a[i]);
}
}
return r;
}class Solution {
public:
int maximumSwap(int num) {
string s = to_string(num);
int n = s.size(), r = num;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
swap(s[i], s[j]);
r = max(r, stoi(s));
swap(s[j], s[i]);
}
}
return r;
}
};class Solution:
def swap(self, nums: list, a: int, b: int):
nums[a], nums[b] = nums[b], nums[a]
def maximumSwap(self, num: int) -> int:
a, r = list(str(num)), num
for i in range(1, len(a)):
for j in range(0, i):
self.swap(a, i, j)
r = max(r, int(''.join(a)))
self.swap(a, j, i)
return r