跳转至

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

题目描述

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

解法

方法一：贪心

要想得到最大差值，那么我们应该拿到最大值与最小值，这样差值最大。

因此，我们先从高到低枚举 $nums$ 每个位置上的数，如果数字不为 9，就将所有该数字替换为 9，得到最大整数 $a$。

接下来，我们再从高到低枚举 nums 每个位置上的数，首位不能为 0，因此如果首位不为 1，我们将其替换为 1；如果非首位，且数字不与首位相同，我们将其替换为 0，得到最大整数 $b$。

答案为差值 $a - b$。

时间复杂度 $O(\log num)$，空间复杂度 $O(\log num)$。其中 $num$ 为给定整数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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)

 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 {
    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);
    }
}

 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) {
        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);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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
}

评论