LEETCODE 1432. 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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1432

解题思路分析:

  1. 首先取得num中每一位上的数字,存储至List。
  2. 同时取得num中所有不重复的数字,存储至Set。
  3. 建立2层循环,第一层循环Set中所有数字,即相当于题目中的x,第二层循环数字0到9,即相当于题目中的y,我们尝试用每一个y替换掉x,并得出一个替换后的最大数和最小数。
  4. 注意如果当前x是num的最高位,同时y是0时,说明替换后num的最高位是0,但题目要求替换后的数字不能存在前导零,因此遇到这种情况时跳过当前循环即可。
  5. 最大数与最小数的差即是答案。

实现代码:

int max=0;
int min=Integer.MAX_VALUE;
public int maxDiff(int num) {
    // 记录num中每一位上的数字
    List<Integer> nums = new ArrayList<>();
    // 记录num中不重复的所有数字
    Set<Integer> uniqueNums = new HashSet<>();
    // 循环num中每一位
    while(num > 0){
        uniqueNums.add(num%10);
        nums.add(num%10);
        num/=10;
    }
    // num最高位上的数字
    int firstNum = nums.get(nums.size()-1);
    // 循环num中所有不重复的数字
    for(int x : uniqueNums){
        // 循环数字0-9
        for(int y=0;y<=9;y++){
            // 如果x是num最高位并且y是0
            // 说明num最高位会变为0,跳过
            if(x==firstNum && y==0) continue;
            // 将num中的x替换为y
            change(nums,x,y);
        }
    }
    return max-min;
}
// 将num中的x替换为y
void change(List<Integer> nums, int x, int y){
    int res=0; // 替换后结果
    int index=1; // 当前位(最低位)
    // 循环num每一位上的数字(由低位到高位)
    for(int num : nums){
        // 如果当前位上数字是x,替换为y
        if(num==x) num=y;
        // 将当前数字乘以位数后加入返回结果
        res+=num*index;
        // 位数乘10
        index*=10;
    }
    // 更新最大值与最小值
    max=Math.max(max, res);
    min=Math.min(min, res);
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 76.14% of Java online submissions for Max Difference You Can Get From Changing an Integer.

Memory Usage: 36.7 MB, less than 100.00% of Java online submissions for Max Difference You Can Get From Changing an Integer.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1432-max-difference-you-can-get-from-changing-an-integer-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。