2566. 替换一个数字后的最大差值

题目描述

给你一个整数 num 。你知道 Danny Mittal 会偷偷将 0 到 9 中的一个数字替换成另一个数字。

请你返回将 num 中 恰好一个 数字进行替换后，得到的最大值和最小值的差为多少。

注意：

当 Danny 将一个数字 d1 替换成另一个数字 d2 时，Danny 需要将 nums 中所有 d1 都替换成 d2 。
Danny 可以将一个数字替换成它自己，也就是说 num 可以不变。
Danny 可以将数字分别替换成两个不同的数字分别得到最大值和最小值。
替换后得到的数字可以包含前导 0 。
Danny Mittal 获得周赛 326 前 10 名，让我们恭喜他。

示例 1：

输入：num = 11891
输出：99009
解释：
为了得到最大值，我们将数字 1 替换成数字 9 ，得到 99899 。
为了得到最小值，我们将数字 1 替换成数字 0 ，得到 890 。
两个数字的差值为 99009 。

示例 2：

输入：num = 90
输出：99
解释：
可以得到的最大值是 99（将 0 替换成 9），最小值是 0（将 9 替换成 0）。
所以我们得到 99 。

提示：

1 <= num <= 10⁸

解法

方法一：贪心

我们先将数字转为字符串 \(s\)。

要得到最小值，我们只需要将找到字符串 \(s\) 的第一个数字 \(s[0]\)，然后把字符串中所有的 \(s[0]\) 替换成 \(0\) 即可。

要得到最大值，我们需要找到字符串 \(s\) 中第一个不是 \(9\) 的数字 \(s[i]\)，然后把字符串中所有的 \(s[i]\) 替换成 \(9\) 即可。

最后返回最大值和最小值的差即可。

时间复杂度 \(O(\log n)\)，空间复杂度 \(O(\log n)\)。其中 \(n\) 为数字 \(\textit{num}\) 的值。

Python3JavaC++GoTypeScriptRustJavaScriptC

class Solution:
    def minMaxDifference(self, num: int) -> int:
        s = str(num)
        mi = int(s.replace(s[0], '0'))
        for c in s:
            if c != '9':
                return int(s.replace(c, '9')) - mi
        return num - mi

class Solution {
    public int minMaxDifference(int num) {
        String s = String.valueOf(num);
        int mi = Integer.parseInt(s.replace(s.charAt(0), '0'));
        for (char c : s.toCharArray()) {
            if (c != '9') {
                return Integer.parseInt(s.replace(c, '9')) - mi;
            }
        }
        return num - mi;
    }
}

class Solution {
public:
    int minMaxDifference(int num) {
        string s = to_string(num);
        string t = s;
        char first = s[0];
        for (char& c : s) {
            if (c == first) {
                c = '0';
            }
        }
        int mi = stoi(s);
        for (int i = 0; i < t.size(); ++i) {
            if (t[i] != '9') {
                char second = t[i];
                for (int j = i; j < t.size(); ++j) {
                    if (t[j] == second) {
                        t[j] = '9';
                    }
                }
                return stoi(t) - mi;
            }
        }
        return num - mi;
    }
};

func minMaxDifference(num int) int {
    s := []byte(strconv.Itoa(num))
    first := s[0]
    for i := range s {
        if s[i] == first {
            s[i] = '0'
        }
    }
    mi, _ := strconv.Atoi(string(s))
    t := []byte(strconv.Itoa(num))
    for i := range t {
        if t[i] != '9' {
            second := t[i]
            for j := i; j < len(t); j++ {
                if t[j] == second {
                    t[j] = '9'
                }
            }
            mx, _ := strconv.Atoi(string(t))
            return mx - mi
        }
    }
    return num - mi
}

function minMaxDifference(num: number): number {
    const s = num.toString();
    const mi = +s.replaceAll(s[0], '0');
    for (const c of s) {
        if (c !== '9') {
            const mx = +s.replaceAll(c, '9');
            return mx - mi;
        }
    }
    return num - mi;
}

impl Solution {
    pub fn min_max_difference(num: i32) -> i32 {
        let s = num.to_string();
        let mi = s.replace(s.chars().next().unwrap(), "0").parse::<i32>().unwrap();
        for c in s.chars() {
            if c != '9' {
                let mx = s.replace(c, "9").parse::<i32>().unwrap();
                return mx - mi;
            }
        }
        num - mi
    }
}

/**
 * @param {number} num
 * @return {number}
 */
var minMaxDifference = function (num) {
    const s = num.toString();
    const mi = +s.replaceAll(s[0], '0');
    for (const c of s) {
        if (c !== '9') {
            const mx = +s.replaceAll(c, '9');
            return mx - mi;
        }
    }
    return num - mi;
};

int minMaxDifference(int num) {
    char s[12];
    sprintf(s, "%d", num);

    int mi;
    {
        char tmp[12];
        char t = s[0];
        for (int i = 0; s[i]; i++) {
            tmp[i] = (s[i] == t) ? '0' : s[i];
        }
        tmp[strlen(s)] = '\0';
        mi = atoi(tmp);
    }

    for (int i = 0; s[i]; i++) {
        char c = s[i];
        if (c != '9') {
            char tmp[12];
            for (int j = 0; s[j]; j++) {
                tmp[j] = (s[j] == c) ? '9' : s[j];
            }
            tmp[strlen(s)] = '\0';
            return atoi(tmp) - mi;
        }
    }

    return num - mi;
}

2566. 替换一个数字后的最大差值

题目描述

解法

方法一：贪心

评论