README.md

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

English Version

题目描述

给你一个整数 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 <= 108

解法

方法一：贪心

我们先将数字转为字符串 $s$。

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

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

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

时间复杂度 $O(\log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数字 $num$ 的大小。

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 + '';
    const min = Number(s.replace(new RegExp(s[0], 'g'), '0'));
    for (const c of s) {
        if (c !== '9') {
            return Number(s.replace(new RegExp(c, 'g'), '9')) - min;
        }
    }
    return num - min;
}

impl Solution {
    pub fn min_max_difference(num: i32) -> i32 {
        let s = num.to_string();
        let min = s.replace(char::from(s.as_bytes()[0]), "0").parse::<i32>().unwrap();
        for &c in s.as_bytes() {
            if c != b'9' {
                return s.replace(c, "9").parse().unwrap() - min;
            }
        }
        num - min
    }
}

int getLen(int num) {
    int res = 0;
    while (num) {
        num /= 10;
        res++;
    }
    return res;
}

int minMaxDifference(int num) {
    int n = getLen(num);
    int* nums = malloc(sizeof(int) * n);
    int t = num;
    for (int i = n - 1; i >= 0; i--) {
        nums[i] = t % 10;
        t /= 10;
    }
    int min = 0;
    for (int i = 0; i < n; i++) {
        min *= 10;
        if (nums[i] != nums[0]) {
            min += nums[i];
        }
    }
    int max = 0;
    int target = 10;
    for (int i = 0; i < n; i++) {
        max *= 10;
        if (target == 10 && nums[i] != 9) {
            target = nums[i];
        }
        max += nums[i] == target ? 9 : nums[i];
    }
    free(nums);
    return max - min;
}

方法二

impl Solution {
    pub fn min_max_difference(num: i32) -> i32 {
        let mut s = num.to_string().into_bytes();
        let first = s[0];
        for i in 0..s.len() {
            if s[i] == first {
                s[i] = b'0';
            }
        }
        let mi = String::from_utf8_lossy(&s).parse::<i32>().unwrap();

        let mut t = num.to_string().into_bytes();
        for i in 0..t.len() {
            if t[i] != b'9' {
                let second = t[i];

                for j in 0..t.len() {
                    if t[j] == second {
                        t[j] = b'9';
                    }
                }

                let mx = String::from_utf8_lossy(&t).parse::<i32>().unwrap();
                return mx - mi;
            }
        }

        num - mi
    }
}