leetcode
leetcode 1301 ~ 1350
改变一个整数能得到的最大差值

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

难度:

标签:

题目描述

代码结果

运行时间: 24 ms, 内存: 16.0 MB


// Java Stream Solution
// 思路与普通 Java 解法相同,这里使用 Stream 的方式实现。
// 第一次替换中,我们使用 replaceAll 将特定字符替换成 9。
// 第二次替换中,我们使用 replaceAll 将特定字符替换成 1(若可能为前导 0 则替换成 0)。

import java.util.stream.Collectors;

public class SolutionStream {
    public int maxDifference(int num) {
        String numStr = String.valueOf(num);
        // 第一次操作,替换成尽可能大的数字
        char maxReplaceChar = numStr.chars().mapToObj(c -> (char) c)
                .filter(c -> c != '9').findFirst().orElse(numStr.charAt(0));
        String a = numStr.replaceAll(String.valueOf(maxReplaceChar), "9");
        // 第二次操作,替换成尽可能小的数字
        char minReplaceChar = numStr.chars().mapToObj(c -> (char) c)
                .filter(c -> c != '1' && c != '0').findFirst().orElse(numStr.charAt(0));
        String b = (minReplaceChar == '1' || minReplaceChar == '0')
                ? numStr.replaceFirst("1", "0")
                : numStr.replaceAll(String.valueOf(minReplaceChar), "1");
        // 计算并返回最大差值
        return Integer.parseInt(a) - Integer.parseInt(b);
    }
}

解释

方法:

此题解的核心思路是通过两次替换操作生成两个整数a和b,然后计算它们的差值,以得到最大的差值。为了得到最大的a,应选择第一个非'9'的数字替换为'9'。而为了得到最小的b,首先检查首位数字是否为'1'。如果不是,将首位替换为'1';如果首位已经是'1',则找到第一个不是'0'或'1'的后续数字,将其替换为'0'。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在选择替换数字时,首选将非'9'的数字替换为'9'而不是其他数字?
将非'9'的数字替换为'9'是为了最大化整数的数值。'9'是单个数字中最大的,因此替换任何小于'9'的数字可以增加整数的值。这样的替换确保了得到的新数a尽可能大,从而最大化a和b的差值。
🦆
如果数字num的所有位都是'9',那么如何处理以确保仍然能正确执行替换操作并计算差值?
如果数字num的所有位都是'9',那么对于生成最大数a的替换操作,实际上不会发生任何更改,因为没有低于'9'的数字可替换。在这种情况下,数a保持不变。对于最小数b的生成,如果首位也是'9'(即整个数字都是'9'),按照题解策略,首位'9'将被替换为'1',使b尽可能小。计算差值时,使用修改后的b从未修改的a中减去。
🦆
在替换为最小值b的过程中,如果首位数字已经是'1',选择将后续第一个非'0'或'1'的数字替换为'0'的依据是什么?
当首位数字已经是'1'时,该位已经是可以取得的最小值,所以不需要更改。为了进一步减小整数的值,我们寻找后续位中第一个非'0'或'1'的数字,因为这些数字替换为'0'(最小的有效数字)可以最大程度地降低整数的值。这种策略旨在使b尽可能小,从而增大与a的差值。
🦆
替换操作是否考虑了可能出现的多次相同数字,会不会因为替换其中一个数字而影响到本该替换的其他同样的数字?
在题解中,使用字符串的replace方法直接替换所有匹配的字符,不仅限于首次出现的字符。这意味着如果一个数字在num中出现多次,一旦决定替换该数字,将会替换num中的所有此数字。这种方法确保了一致性和简化的逻辑处理,但也可能导致在某些情况下替换更多的数字比预期的更早地达到最大或最小值。

相关问题