替换一个数字后的最大差值
难度:
标签:
题目描述
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
innum
withd2
. - 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'数字?
▷🦆
当num的最高位是'1'时,替换成'0'可能导致数字位数减少,例如从1000变成000,这种情况下如何正确处理?
▷🦆
题解中替换最小值时只考虑了替换最高位,如果最高位已经是'0',如何进一步减小数字的值?
▷🦆
在进行数字替换时,如何确保替换结果不会产生非法的数字格式,例如前导零?
▷