题目描述
给你一个整数 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 。
提示：
解法
方法一：贪心
我们先将数字转为字符串 $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
|
1
2
3
4
5
6
7
8
9
10
11
12 | 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | 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;
}
|
1
2
3
4
5
6
7
8
9
10
11
12 | 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
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 | 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;
}
|
方法二