Easy

题目描述

给你一个整数 num。你知道 Bob 会偷偷地将 10 个可能的数字（0 到 9）中的一个重新映射为另一个数字。

返回 Bob 通过重新映射 num 中的恰好一个数字能够得到的最大值和最小值之间的差值。

注意：

  • 当 Bob 将数字 d1 重新映射为另一个数字 d2 时，Bob 会将 num 中所有出现的 d1 替换为 d2。
  • Bob 可以将一个数字映射为它自身，在这种情况下 num 不会改变。
  • Bob 可以分别重新映射不同的数字来获得最小值和最大值。
  • 重新映射后的结果数字可以包含前导零。

示例 1：

输入：num = 11891
输出：99009
解释：
为了获得最大值，Bob 可以将数字 1 重新映射为数字 9，得到 99899。
为了获得最小值，Bob 可以将数字 1 重新映射为数字 0，得到 890。
这两个数字之间的差值是 99009。

示例 2：

输入：num = 90
输出：99
解释：
函数能返回的最大值是 99（如果将 0 替换为 9），能返回的最小值是 0（如果将 9 替换为 0）。
因此，我们返回 99。

提示：

  • 1 <= num <= 10^8

算法提示：

  • 尝试将第一个非 9 的数字重新映射为 9 来获得最大数字。
  • 尝试将第一个非 0 的数字重新映射为 0 来获得最小数字。

解题思路

解题思路

这是一道关于数字操作的贪心题目。我们需要通过重新映射一个数字来分别获得最大值和最小值，然后计算它们的差值。

获得最大值的策略： 从左到右遍历数字的每一位，找到第一个不是 9 的数字，将其替换为 9。这样可以让高位数字尽可能大，从而获得最大值。如果所有数字都是 9，则无需替换。

获得最小值的策略： 有两种情况需要考虑：

  1. 如果第一位数字不是 1，将第一位替换为 0（但这会导致前导零）
  2. 如果第一位是 1，则从第二位开始找第一个不是 0 且不是 1 的数字，将其替换为 0

实际上，为了简化逻辑，我们可以统一处理：从左到右找第一个既不是 0 也不等于第一位数字的数字，将其替换为 0。这样既避免了第一位变成 0 的问题，也能获得最小值。

实现方法：

  1. 将数字转换为字符串便于操作
  2. 分别计算最大值和最小值
  3. 返回两者的差值

时间复杂度为 O(log num)，空间复杂度为 O(log num)。

代码实现

class Solution {
public:
    int minMaxDifference(int num) {
        string s = to_string(num);
        
        // 计算最大值：找第一个非9的数字替换为9
        string maxStr = s;
        for (char& c : maxStr) {
            if (c != '9') {
                char target = c;
                for (char& ch : maxStr) {
                    if (ch == target) ch = '9';
                }
                break;
            }
        }
        
        // 计算最小值：找第一个非第一位且非0的数字替换为0
        string minStr = s;
        char firstChar = s[0];
        for (char& c : minStr) {
            if (c != '0' && c != firstChar) {
                char target = c;
                for (char& ch : minStr) {
                    if (ch == target) ch = '0';
                }
                break;
            }
        }
        
        int maxVal = stoi(maxStr);
        int minVal = stoi(minStr);
        
        return maxVal - minVal;
    }
};

class Solution:
    def minMaxDifference(self, num: int) -> int:
        s = str(num)
        
        # 计算最大值：找第一个非9的数字替换为9
        max_str = s
        for c in s:
            if c != '9':
                max_str = s.replace(c, '9')
                break
        
        # 计算最小值：找第一个非第一位且非0的数字替换为0
        min_str = s
        first_char = s[0]
        for c in s:
            if c != '0' and c != first_char:
                min_str = s.replace(c, '0')
                break
        
        return int(max_str) - int(min_str)

public class Solution {
    public int MinMaxDifference(int num) {
        string s = num.ToString();
        
        // 计算最大值：找第一个非9的数字替换为9
        string maxStr = s;
        foreach (char c in s) {
            if (c != '9') {
                maxStr = s.Replace(c, '9');
                break;
            }
        }
        
        // 计算最小值：找第一个非第一位且非0的数字替换为0
        string minStr = s;
        char firstChar = s[0];
        foreach (char c in s) {
            if (c != '0' && c != firstChar) {
                minStr = s.Replace(c, '0');
                break;
            }
        }
        
        int maxVal = int.Parse(maxStr);
        int minVal = int.Parse(minStr);
        
        return maxVal - minVal;
    }
}

/**
 * @param {number} num
 * @return {number}
 */
var minMaxDifference = function(num) {
    const s = num.toString();
    
    // 计算最大值：找第一个非9的数字替换为9
    let maxStr = s;
    for (let c of s) {
        if (c !== '9') {
            maxStr = s.replaceAll(c, '9');
            break;
        }
    }
    
    // 计算最小值：找第一个非第一位且非0的数字替换为0
    let minStr = s;
    const firstChar = s[0];
    for (let c of s) {
        if (c !== '0' && c !== firstChar) {
            minStr = s.replaceAll(c, '0');
            break;
        }
    }
    
    const maxVal = parseInt(maxStr);
    const minVal = parseInt(minStr);
    
    return maxVal - minVal;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log num)需要遍历数字的每一位，数字的位数为 log num
空间复杂度O(log num)需要存储数字的字符串表示