完整的题目描述

题目：最大的交换

给定一个非负整数，你可以至多交换一次数字中的两个不同数位上的数字。你的目标是得到可能的最大数。

注意：

• 输入的数不包含前导零。
• 你可以假设除了数字 0 之外，不存在其他含前导零的情况。

示例 1:

输入: 2736
输出: 7236
解释: 交换数字2和数字7。

示例 2:

输入: 9973
输出: 9973
解释: 不需要交换。

示例 3:

输入: 9861
输出: 9816
解释: 交换数字6和数字1。

PHP 示例代码

function maximumSwap($num) {
    $digits = str_split($num);
    $n = count($digits);
    $maxDigitPos = array_fill(0, $n, -1); // 记录每个位置之后最大的数字及其位置
    $maxDigit = PHP_INT_MIN;

    // 从右向左遍历，找到每个位置之后最大的数字及其位置
    for ($i = $n - 1; $i >= 0; $i--) {
        if ($digits[$i] > $maxDigit) {
            $maxDigit = $digits[$i];
        }
        $maxDigitPos[$i] = $maxDigit;
    }

    // 从左向右遍历，寻找可以交换的最大数字
    for ($i = 0; $i < $n; $i++) {
        if ($digits[$i] !== $maxDigitPos[$i]) {
            // 找到第一个不等于当前位置之后最大数字的位置，进行交换
            for ($j = $n - 1; $j >= 0; $j--) {
                if ($digits[$j] == $maxDigitPos[$i]) {
                    // 交换
                    list($digits[$i], $digits[$j]) = array($digits[$j], $digits[$i]);
                    return implode('', $digits);
                }
            }
        }
    }

    // 如果没有找到可以交换的位置，则返回原数字
    return $num;
}

// 测试
echo maximumSwap(2736); // 输出 7236
echo maximumSwap(9973); // 输出 9973
echo maximumSwap(9861); // 输出 9816

Python 示例代码

def maximumSwap(num):
    digits = list(str(num))
    n = len(digits)
    max_digit_pos = [-1] * n  # 记录每个位置之后最大的数字及其位置
    max_digit = float('-inf')

    # 从右向左遍历，找到每个位置之后最大的数字及其位置
    for i in range(n - 1, -1, -1):
        if digits[i] > max_digit:
            max_digit = digits[i]
        max_digit_pos[i] = max_digit

    # 从左向右遍历，寻找可以交换的最大数字
    for i in range(n):
        if digits[i] != max_digit_pos[i]:
            for j in range(n):
                if digits[j] == max_digit_pos[i]:
                    digits[i], digits[j] = digits[j], digits[i]
                    return int(''.join(digits))

    # 如果没有找到可以交换的位置，则返回原数字
    return num

# 测试
print(maximumSwap(2736))  # 输出 7236
print(maximumSwap(9973))  # 输出 9973
print(maximumSwap(9861))  # 输出 9816

JavaScript 示例代码

function maximumSwap(num) {
    const digits = num.toString().split('');
    const n = digits.length;
    const maxDigitPos = new Array(n).fill(-1); // 记录每个位置之后最大的数字及其位置
    let maxDigit = -Infinity;

    // 从右向左遍历，找到每个位置之后最大的数字及其位置
    for (let i = n - 1; i >= 0; i--) {
        if (digits[i] > maxDigit) {
            maxDigit = digits[i];
        }
        maxDigitPos[i] = maxDigit;
    }

    // 从左向右遍历，寻找可以交换的最大数字
    for (let i = 0; i < n; i++) {
        if (digits[i] !== maxDigitPos[i]) {
            for (let j = n - 1; j >= 0; j--) {
                if (digits[j] === maxDigitPos[i]) {
                    // 交换
                    [digits[i], digits[j]] = [digits[j], digits[i]];
                    return parseInt(digits.join(''));
                }
            }
        }
    }

    // 如果没有找到可以交换的位置，则返回原数字
    return num;
}

// 测试
console.log(maximumSwap(2736)); // 输出 7236
console.log(maximumSwap(9973)); // 输出 9973
console.log(maximumSwap(9861)); // 输出 9816

码小课网站中有更多相关内容分享给大家学习，涵盖了各种算法和数据结构的深入解析与实战应用。