【LetMeFly】1432.改变一个整数能得到的最大差值：暴力模拟/贪心

力扣题目链接：https://leetcode.cn/problems/max-difference-you-can-get-from-changing-an-integer/

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

解题方法一：暴力模拟

从0到9模x，从0到9模拟y，(如果x出现过则)将所有x替换为y，就能得到一个新数字。

在所有的新数字中，返回其中最大数和最小数之差。

时间复杂度$O(C^2\log num)$，其中C=10
空间复杂度$O(1)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-06-15 22:35:58
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-06-17 23:50:02
 */
class Solution {
private:
    inline bool isIn(string s, char c) {
        for (char t : s) {
            if (t == c) {
                return true;
            }
        }
        return false;
    }

    inline string replace(string s, char a, char b) {
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == a) {
                s[i] = b;
            }
        }
        return s;
    }
public:
    int maxDiff(int num) {
        int m = 100000000, M = 0;
        string s = to_string(num);
        for (int a = 0; a < 10; a++) {
            if (!isIn(s, '0' + a)) {
                continue;
            }
            for (int b = 0; b < 10; b++) {
                string x = replace(s, '0' + a, '0' + b);
                if (x[0] == '0') {
                    continue;
                }
                int val = atoi(x.c_str());
                m = min(m, val);
                M = max(M, val);
            }
        }
        return M - m;
    }
};

解题方法二：贪心

如何将num变得尽可能大？

前面的数哪怕变大一点(8->9)也比后面的数变大很多(0->9)更优(80->90比80->89更优)。

所以只需要将num中第一个非9数字全部变为9即可。

如何将num变得尽可能小？

题目要求不能包含前导零。

如果num的最高位不是1，那么将所有值为num最高位的数变成1即可；

否则，将第一个大于1的数字全部变为0即可(首位是1，所以不能将1变成0，只能将大于1的数变成0)。

时间复杂度$O(\log num)$
空间复杂度$O(1)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-06-19 10:16:46
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-06-19 10:28:35
 */
// max->第一个非9的值全改为9
// min->第一位如果是1，将第一个大于1的值全改为0；否则，将第一位的值全改为1
class Solution {
private:
    int firstNot9(string& s) {
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != '9') {
                return i;
            }
        }
        return -1;
    }

    int firstNot01(string& s) {
        for (int i = 0; i < s.size(); i++) {
            if (s[i] > '1') {
                return i;
            }
        }
        return -1;
    }

    int change(string s, char a, char b) {
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == a) {
                s[i] = b;
            }
        }
        return atoi(s.c_str());
    }
public:
    int maxDiff(int num) {
        int M, m;
        string s = to_string(num);
        int index = firstNot9(s);
        M = index < 0 ? num : change(s, s[index], '9');
        if (s[0] != '1') {
            m = change(s, s[0], '1');
        } else {
            index = firstNot01(s);
            m = index < 0 ? num : change(s, s[index], '0');
        }
        return M - m;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-06-19 10:16:46
LastEditors: LetMeFly.xyz
LastEditTime: 2025-06-19 10:35:59
'''
# M: !9 -> 9
# m: first == 1 ? (!01 -> 0) : (first->1)
class Solution:
    def firstN9(self, s: str) -> int:
        for i, c in enumerate(s):
            if c != '9':
                return i
        return -1
    
    def firstN01(self, s: str) -> int:
        for i, c in enumerate(s):
            if c != '0' and c != '1':
                return i
        return -1
    
    def change(self, s: str, a: str, b: str) -> int:
        li = list(s)
        for i, c in enumerate(li):
            if c == a:
                li[i] = b
        return int(''.join(li))
    
    def maxDiff(self, num: int) -> int:
        M = m = 0
        s = str(num)
        index = self.firstN9(s)
        M = num if index < 0 else self.change(s, s[index], '9')
        if s[0] == '1':
            index = self.firstN01(s)
            m = num if index < 0 else self.change(s, s[index], '0')
        else:
            m = self.change(s, s[0], '1')
        return M - m

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-06-19 10:16:46
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-06-21 14:38:38
 */
// M: !9->9
// m: first==1 ? !01->0 : first->1
class Solution {
    private int not9(String s) {
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != '9') {
                return i;
            }
        }
        return -1;
    }

    private int not01(String s) {
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) > '1') {
                return i;
            }
        }
        return -1;
    }

    private int replace(String s, char a, char b) {
        return Integer.parseInt(s.replace(a, b));
    }
    public int maxDiff(int num) {
        int M, m;
        String s = String.valueOf(num);
        int index = not9(s);
        M = index == -1 ? num : replace(s, s.charAt(index), '9');
        if (s.charAt(0) == '1') {
            index = not01(s);
            m = index == -1 ? num : replace(s, s.charAt(index), '0');
        } else {
            m = replace(s, s.charAt(0), '1');
        }
        return M - m;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-06-19 10:16:46
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-06-21 11:33:06
 */
package main

import (
	"strconv"
	"strings"
)

// M: !9->9
// m: first==1 ? !01->0 : first->1
func maxDiff(num int) int {
    s := strconv.Itoa(num)  // 不可！： s := string(num)
    M, m := num, num
    change := func(s string, a, b byte) int {
        ans, _ := strconv.Atoi(strings.ReplaceAll(s, string(a), string(b)))
        return ans
    }
    for i := range s {
        if s[i] != '9' {
            M = change(s, s[i], '9')
            break
        }
    }
    if s[0] == '1' {
        for i := range s {
            if s[i] > '1' {
                m = change(s, s[i], '0')
                break
            }
        }
    } else {
        m = change(s, s[0], '1')
    }
    return M - m
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源

题解 > LeetCode

#题解 #中等 #数学 #贪心 #LeetCode

1432.改变一个整数能得到的最大差值：暴力模拟/贪心

https://blog.letmefly.xyz/2025/06/21/LeetCode 1432.改变一个整数能得到的最大差值/

作者

Tisfy

发布于

2025年6月21日

许可协议

域名转到国外注册商-备案实效风险折腾日记上一篇

3423.循环数组中相邻元素的最大差值：遍历(模拟) 下一篇