题目
给你一个整数 num 。你知道Danny Mittal 会偷偷将0到9 中的一个数字 替换成另一个数字。
请你返回将 num 中 恰好一个 数字进行替换后，得到的最大值和最小值的差为多少。
注意：
- 当 Danny 将一个数字 d1 替换成另一个数字 d2 时，Danny 需要将 nums 中所有 d1 都替换成 d2 。
- Danny 可以将一个数字替换成它自己，也就是说 num 可以不变。
- Danny 可以将数字分别替换成两个不同的数字分别得到最大值和最小值。
- 替换后得到的数字可以包含前导 0 。
提示：
- 1 <= num <= 108
示例 1：
输入：num = 11891
输出：99009
解释：
为了得到最大值，我们将数字 1 替换成数字 9 ，得到 99899 。
为了得到最小值，我们将数字 1 替换成数字 0 ，得到 890 。
两个数字的差值为 99009 。
示例 2：
输入：num = 90
输出：99
解释：
可以得到的最大值是 99（将 0 替换成 9），最小值是 0（将 9 替换成 0）。
所以我们得到 99 。
思路
最大值思路：从最高位往最低位搜索，找到第一个非9数字，将所有该数字替换成9
最小值思路：找到最高位数字，将所有该数字替换成0
Python代码
class Solution:
def minMaxDifference(self, num: int) -> int:
# 1、把num中每个数字保存到列表中，注意：最高位在最后面
num_list = []
temp_num = num
while temp_num > 0:
i = temp_num % 10 # 取出最低位
num_list.append(i)
temp_num //= 10
# 2、从最高位开始遍历，找到第一个非9数字
n = len(num_list)
change_num = -1
for j in range(n - 1, -1, -1):
if num_list[j] != 9:
change_num = num_list[j]
break
# 3、替换数字
max_num = int(str(num).replace(str(change_num), "9"))
min_num = int(str(num).replace(str(num_list[n-1]), "0"))
return max_num - min_num
C代码
int minMaxDifference(int num) {
char s[16], t[16];
sprintf(s, "%d", num);
strcpy(t, s);
int pos = 0;
while (s[pos] != '\0' && s[pos] == '9') {
pos++;
}
if (s[pos] != '\0') {
char a = s[pos];
for (int i = 0; s[i] != '\0'; i++) {
if (s[i] == a) {
s[i] = '9';
}
}
}
char b = t[0];
for (int i = 0; t[i] != '\0'; i++) {
if (t[i] == b) {
t[i] = '0';
}
}
return atoi(s) - atoi(t);
}
复杂度
- 时间复杂度O(log num)
- 空间复杂度O(log num)