1432-改变一个整数能得到的最大差值

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

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

分析

要想使得 a 和 b 的差值尽可能大，我们应该找到从 num 可以得到的最大以及最小的整数分别作为 a 和 b。

方法一：枚举

根据题目的描述，我们可以任意选择两个数字 x 和 y，并将 num 中的所有 x 替换成 y。由于 x 和 y 的取值范围均为 [0, 9]，那么我们最多只有 10 \times 10 = 100 种不同的替换方法。

因此我们可以使用两重循环枚举所有的替换方法。在得到的所有新整数中，找出最大以及最小的赋予 a 和 b。

[sol1-C++]
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
class Solution {
public:
    int maxDiff(int num) {
        auto change = [&](int x, int y) {
            string num_s = to_string(num);
            for (char& digit: num_s) {
                if (digit - '0' == x) {
                    digit = '0' + y;
                }
            }
            return num_s;
        };

        int min_num = num;
        int max_num = num;
        for (int x = 0; x < 10; ++x) {
            for (int y = 0; y < 10; ++y) {
                string res = change(x, y);
                // 判断是否有前导零
                if (res[0] != '0') {
                    int res_i = stoi(res);
                    min_num = min(min_num, res_i);
                    max_num = max(max_num, res_i);
                }
            }
        }

        return max_num - min_num;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxDiff(self, num: int) -> int:
        def change(x, y):
            return str(num).replace(str(x), str(y))
        
        min_num = max_num = num
        for x in range(10):
            for y in range(10):
                res = change(x, y)
                # 判断是否有前导零
                if res[0] != "0":
                    res_i = int(res)
                    min_num = min(min_num, res_i)
                    max_num = max(max_num, res_i)
        
        return max_num - min_num
[sol1-Java]
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
class Solution {
    public int maxDiff(int num) {
        int min_num = num;
        int max_num = num;
        for (int x = 0; x < 10; ++x) {
            for (int y = 0; y < 10; ++y) {
                String res = change(num, x, y);
                // 判断是否有前导零
                if (res.charAt(0) != '0') {
                    int res_i = Integer.parseInt(res);
                    min_num = Math.min(min_num, res_i);
                    max_num = Math.max(max_num, res_i);
                }
            }
        }

        return max_num - min_num;
    }

    public String change(int num, int x, int y) {
        StringBuffer num_s = new StringBuffer(String.valueOf(num));
        int length = num_s.length();
        for (int i = 0; i < length; i++) {
            char digit = num_s.charAt(i);
            if (digit - '0' == x) {
                num_s.setCharAt(i, (char) ('0' + y));
            }
        }
        return num_s.toString();
    }
}

复杂度分析

  • 时间复杂度：O(d^2 \log (\textit{num}))，其中 d = 10，表示 num 是一个「十」进制数。我们使用两重循环枚举所有的替换方法，时间复杂度为 O(d^2)。对于每一种替换方法，我们将 num 转换成字符串后并进行替换操作，需要的时间与 num 的长度成正比，记为 O(\log (\textit{num}))。

  • 空间复杂度：O(1)。

方法二：贪心算法

思路

如果我们想要得到最大的整数，最好的办法应该是找到一个高位将它修改为 9。同理，如果我们想要得到最小的整数，最好的办法应该是找到一个高位将它修改为 0。

找到最大的数

要想得到最大的整数，我们从高到低依次枚举 num 中的每一个位置。如果当前枚举到的位置的数字不为 9，那么我们该数字全部替换成 9，即可得到最大的整数。

找到最小的数

要想得到最小的整数，我们从高到低依次枚举 num 中的每一个位置。如果当前枚举到的位置的数字不为 0，那么我们将该数字全部替换成 0，即可得到最小的整数。

等等，如果我们将数字替换成 0，是不是可能会出现「前导零」？举个例子，如果 num} = 123，我们会将最高位的 1 替换成 0，得到 023，这样就出现了前导零。因此我们必须要考虑前导零的问题：

  • 如果我们枚举的是最高位，那么我们只能将其替换成 1，否则就会有前导零了；

  • 如果我们枚举的是其它的数位：

    • 如果当前的数字与最高位的数字不相等，那么我们就可以将其替换成 0；

    • 如果当前的数字与最高位的数字相等，那么我们直接跳过这个数位，这是因为当我们在枚举最高位时，我们已经处理过这个数字了。既然在枚举最高位遇到相同的数字时没有选择替换，那么说明这个数字一定就是 1，由于前导零的限制我们也不能将其替换成 0，因此就可以直接跳过了。

至此，我们通过贪心找高位的方法得到了最大以及最小的数，这样也就得到了最终的答案。

[sol2-C++]
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
37
38
39
40
41
42
43
class Solution {
public:
    int maxDiff(int num) {
        auto replace = [](string& s, char x, char y) {
            for (char& digit: s) {
                if (digit == x) {
                    digit = y;
                }
            }
        };

        string min_num = to_string(num);
        string max_num = to_string(num);

        // 找到一个高位替换成 9
        for (char digit: max_num) {
            if (digit != '9') {
                replace(max_num, digit, '9');
                break;
            }
        }

        // 将最高位替换成 1
        // 或者找到一个与最高位不相等的高位替换成 0
        for (int i = 0; i < min_num.size(); ++i) {
            char digit = min_num[i];
            if (i == 0) {
                if (digit != '1') {
                    replace(min_num, digit, '1');
                    break;
                }
            }
            else {
                if (digit != '0' && digit != min_num[0]) {
                    replace(min_num, digit, '0');
                    break;
                }
            }
        }

        return stoi(max_num) - stoi(min_num);
    }
};
[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def maxDiff(self, num: int) -> int:
        min_num, max_num = str(num), str(num)

        # 找到一个高位替换成 9
        for digit in max_num:
            if digit != "9":
                max_num = max_num.replace(digit, "9")
                break

        # 将最高位替换成 1
        # 或者找到一个与最高位不相等的高位替换成 0
        for i, digit in enumerate(min_num):
            if i == 0:
                if digit != "1":
                    min_num = min_num.replace(digit, "1")
                    break
            else:
                if digit != "0" and digit != min_num[0]:
                    min_num = min_num.replace(digit, "0")
                    break

        return int(max_num) - int(min_num)
[sol2-Java]
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
37
38
39
40
41
42
43
44
45
46
class Solution {
    public int maxDiff(int num) {
        StringBuffer min_num = new StringBuffer(String.valueOf(num));
        StringBuffer max_num = new StringBuffer(String.valueOf(num));

        // 找到一个高位替换成 9
        int max_length = max_num.length();
        for (int i = 0; i < max_length; ++i) {
            char digit = max_num.charAt(i);
            if (digit != '9') {
                replace(max_num, digit, '9');
                break;
            }
        }

        // 将最高位替换成 1
        // 或者找到一个与最高位不相等的高位替换成 0
        int min_length = min_num.length();
        for (int i = 0; i < min_length; ++i) {
            char digit = min_num.charAt(i);
            if (i == 0) {
                if (digit != '1') {
                    replace(min_num, digit, '1');
                    break;
                }
            }
            else {
                if (digit != '0' && digit != min_num.charAt(0)) {
                    replace(min_num, digit, '0');
                    break;
                }
            }
        }

        return Integer.parseInt(max_num.toString()) - Integer.parseInt(min_num.toString());
    }

    public void replace(StringBuffer s, char x, char y) {
        int length = s.length();
        for (int i = 0; i < length; ++i) {
            if (s.charAt(i) == x) {
                s.setCharAt(i, y);
            }
        }
    }
}

复杂度分析

  • 时间复杂度：O(\log (\textit{num}))，我们最多只需要枚举 num 的每个数位一次。

  • 空间复杂度：O(1)。

 Comments
On this page
1432-改变一个整数能得到的最大差值