leetcode
leetcode 2251 ~ 2300
替换一个数字后的最大差值

替换一个数字后的最大差值

难度:

标签:

题目描述

You are given an integer num. You know that Bob will sneakily remap one of the 10 possible digits (0 to 9) to another digit.

Return the difference between the maximum and minimum values Bob can make by remapping exactly one digit in num.

Notes:

  • When Bob remaps a digit d1 to another digit d2, Bob replaces all occurrences of d1 in num with d2.
  • Bob can remap a digit to itself, in which case num does not change.
  • Bob can remap different digits for obtaining minimum and maximum values respectively.
  • The resulting number after remapping can contain leading zeroes.

 

Example 1:

Input: num = 11891
Output: 99009
Explanation: 
To achieve the maximum value, Bob can remap the digit 1 to the digit 9 to yield 99899.
To achieve the minimum value, Bob can remap the digit 1 to the digit 0, yielding 890.
The difference between these two numbers is 99009.

Example 2:

Input: num = 90
Output: 99
Explanation:
The maximum value that can be returned by the function is 99 (if 0 is replaced by 9) and the minimum value that can be returned by the function is 0 (if 9 is replaced by 0).
Thus, we return 99.

 

Constraints:

  • 1 <= num <= 108

代码结果

运行时间: 20 ms, 内存: 16.1 MB


/*
 * Problem Statement:
 * Given an integer num, Danny Mittal will secretly replace one digit (0-9) with another digit (0-9).
 * Return the difference between the maximum value and the minimum value that can be obtained by replacing exactly one digit.
 * 
 * Approach:
 * 1. Convert the number to a string to easily manipulate individual digits.
 * 2. For the maximum value, replace the first non-9 digit with 9.
 * 3. For the minimum value, if the first digit is not 1, replace the first non-0 digit with 0.
 * 4. Calculate the difference between the maximum and minimum values.
 */

import java.util.stream.Collectors;

public class Solution {
    public int maxDifference(int num) {
        String numStr = String.valueOf(num);
        String maxStr = numStr;
        String minStr = numStr;

        // Find maximum value by replacing the first non-9 digit with 9
        maxStr = numStr.chars()
                        .mapToObj(c -> (char) c)
                        .map(c -> c != '9' ? numStr.replace(c, '9') : numStr)
                        .findFirst()
                        .orElse(numStr);

        // Find minimum value by replacing the first non-0 digit with 0
        if (numStr.charAt(0) != '1') {
            minStr = numStr.replace(numStr.charAt(0), '0');
        } else {
            minStr = numStr.chars()
                           .skip(1)
                           .mapToObj(c -> (char) c)
                           .filter(c -> c != '0' && c != '1')
                           .map(c -> numStr.replace(c, '0'))
                           .findFirst()
                           .orElse(numStr);
        }

        int maxNum = Integer.parseInt(maxStr);
        int minNum = Integer.parseInt(minStr);

        return maxNum - minNum;
    }
}

解释

方法:

为了解决问题,首先需要生成num的最大可能值和最小可能值。对于最大值,从num的最左侧开始,找到第一个不是'9'的数字,将其以及所有相同的数字都替换成'9'。这样可以确保得到最大的可能值。对于最小值,需要将num的最高位数字替换成'0'(如果最高位不是'0'的话),这样做可以得到最小的可能值。然后计算这两个值的差值,即为所求。该方法通过直接替换字符串中的字符来避免处理多次迭代和复杂的逻辑判断。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在寻找最大值时选择替换第一个非'9'的数字,而不是替换出现次数最多的非'9'数字?
替换第一个非'9'的数字是一种策略,它便于实现且效果显著。替换最左侧的非'9'数字能立即增加数字的大小,因为数字的值由左至右逐位减小。虽然替换出现次数最多的非'9'数字在理论上可能提供更大的增幅,但这种策略计算复杂,并不总是必要的,尤其是在数字长度较短时。此外,最左侧的非'9'数字对整个数值的影响最大,因此优先替换它可以快速达到增大数值的目的。
🦆
当num的最高位是'1'时,替换成'0'可能导致数字位数减少,例如从1000变成000,这种情况下如何正确处理?
确实,直接将最高位的'1'替换为'0'会导致数字前导零的问题,从而使数字的有效位数减少。为了避免这个问题,我们应该判断如果数字的最高位是'1',并且该数字不是唯一一位,那么它的有效替换应该是将它替换为'1'之后的最小有效数字,而不是'0'。例如,如果数字为1000,我们应该将最高位的'1'替换为'0',然后从数学的角度忽略前导零,视为0。实际操作时,可以通过字符串处理技术去除前导零,或者采用条件判断避免这种替换。
🦆
题解中替换最小值时只考虑了替换最高位,如果最高位已经是'0',如何进一步减小数字的值?
如果最高位已经是'0',那么最高位的数字已经是可能的最小值了,此时应考虑替换第一个非'0'的数字为'0',以便进一步减小数值。例如,对于数字0203,最高位已是'0',所以我们可以考虑将'2'替换为'0',得到0003,即3。这种情况下,处理前导零的方式依然是将其从数学计算的角度忽略。
🦆
在进行数字替换时,如何确保替换结果不会产生非法的数字格式,例如前导零?
为了确保替换结果不产生非法的数字格式,如前导零,我们在替换后应该将结果字符串转换为整数。整数类型自然会去除前导零。例如,将字符串'0003'转换为整数后,它就会变成3。在编程实现时,可以通过字符串到整数的转换来自动处理前导零的问题,确保所有操作和计算都在有效的整数上进行。

相关问题