给你一个整数 num
。你可以对它进行如下步骤恰好 两次 :
- 选择一个数字
x (0 <= x <= 9)
. - 选择另一个数字
y (0 <= y <= 9)
。数字y
可以等于x
。 - 将
num
中所有出现x
的数位都用y
替换。 - 得到的新的整数 不能 有前导 0 ,得到的新整数也 不能 是 0 。
令两次对 num
的操作得到的结果分别为 a
和 b
。
请你返回 a
和 b
的 最大差值 。
示例 1:
输入:num = 555 输出:888 解释:第一次选择 x = 5 且 y = 9 ,并把得到的新数字保存在 a 中。 第二次选择 x = 5 且 y = 1 ,并把得到的新数字保存在 b 中。 现在,我们有 a = 999 和 b = 111 ,最大差值为 888
示例 2:
输入:num = 9 输出:8 解释:第一次选择 x = 9 且 y = 9 ,并把得到的新数字保存在 a 中。 第二次选择 x = 9 且 y = 1 ,并把得到的新数字保存在 b 中。 现在,我们有 a = 9 和 b = 1 ,最大差值为 8
示例 3:
输入:num = 123456 输出:820000
示例 4:
输入:num = 10000 输出:80000
示例 5:
输入:num = 9288 输出:8700
提示:
1 <= num <= 10^8
方法一:贪心
要想得到最大差值,那么我们应该拿到最大值与最小值,这样差值最大。
因此,我们先从高到低枚举 9
,就将所有该数字替换为 9
,得到最大整数
接下来,我们再从高到低枚举 nums
每个位置上的数,首位不能为 0
,因此如果首位不为 1
,我们将其替换为 1
;如果非首位,且数字不与首位相同,我们将其替换为 0
,得到最大整数
答案为差值
时间复杂度
class Solution:
def maxDiff(self, num: int) -> int:
a, b = str(num), str(num)
for c in a:
if c != "9":
a = a.replace(c, "9")
break
if b[0] != "1":
b = b.replace(b[0], "1")
else:
for c in b[1:]:
if c not in "01":
b = b.replace(c, "0")
break
return int(a) - int(b)
class Solution {
public int maxDiff(int num) {
String a = String.valueOf(num);
String b = a;
for (int i = 0; i < a.length(); ++i) {
if (a.charAt(i) != '9') {
a = a.replace(a.charAt(i), '9');
break;
}
}
if (b.charAt(0) != '1') {
b = b.replace(b.charAt(0), '1');
} else {
for (int i = 1; i < b.length(); ++i) {
if (b.charAt(i) != '0' && b.charAt(i) != '1') {
b = b.replace(b.charAt(i), '0');
break;
}
}
}
return Integer.parseInt(a) - Integer.parseInt(b);
}
}
class Solution {
public:
int maxDiff(int num) {
auto replace = [](string& s, char a, char b) {
for (auto& c : s) {
if (c == a) {
c = b;
}
}
};
string a = to_string(num);
string b = a;
for (int i = 0; i < a.size(); ++i) {
if (a[i] != '9') {
replace(a, a[i], '9');
break;
}
}
if (b[0] != '1') {
replace(b, b[0], '1');
} else {
for (int i = 1; i < b.size(); ++i) {
if (b[i] != '0' && b[i] != '1') {
replace(b, b[i], '0');
break;
}
}
}
return stoi(a) - stoi(b);
}
};
func maxDiff(num int) int {
a, b := num, num
s := strconv.Itoa(num)
for i := range s {
if s[i] != '9' {
a, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[i]), "9"))
break
}
}
if s[0] > '1' {
b, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[0]), "1"))
} else {
for i := 1; i < len(s); i++ {
if s[i] != '0' && s[i] != '1' {
b, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[i]), "0"))
break
}
}
}
return a - b
}