当前位置：首页 > ds >正文

算法题（力扣每日一题）—改变一个整数能得到的最大差值

ds 2025/7/4 3:34:55

给你一个整数 num 。你可以对它进行以下步骤共计两次：

选择一个数字 x (0 <= x <= 9).
选择另一个数字 y (0 <= y <= 9) 。
数字 y 可以等于 x 。
将 num中所有出现 x 的数位都用 y 替换。
令两次对 num 的操作得到的结果分别为 a 和 b 。
请你返回 a 和 b 的最大差值。

注意，新的整数（a 或 b）必须不能含有前导 0，并且非 0。

思路

贪心
对于最大值a：
肯定是越高位越大越好，所以从最高位开始往后看，第一个不是9的位，这一位数全改成9。

比如 9868 —> 9969

对于最小值b：
肯定是越高位越小越好，
但是有个条件，不能为0，也不能有前置0，
所以不能直接从最高位开始看，要先看最高位是不是1，
①如果不是1，就直接把他和它相同的改成1就行了；
②如果是1，就从后看第一个不是1也不是0的改成0。（这里不能直接按不是0的都改成0来算，因为不是0也包括了1，要是1的话会把第一位的1也改成0，就有前置0了）

比如 120 —> 100，就不能把第一位的1改成0，要不然就是 020 有前置0了。
比如 110 —> 110，就不能把第二位的1改成0，要不然就是000了。

代码

①给的是int型的，因为要挨位访问，所以先转成String，再转成char[]，因为char[]访问效率比String高。
②然后因为有 “将num中所有出现 x 的数位都用 y 替换" 这个操作，可以单独封装一下，用String的replace方法，这个方法不会改变原String，只会返回新String。
③a和b要初始化都等于num，这样防止两次都没有操作的情况
比如 999、111、100

class Solution {public int replace(String str, char c, char toWhat){String temp = str.replace(c, toWhat);   // 不会改变原字符串return Integer.valueOf(temp);}public int maxDiff(int num) {String numStr = String.valueOf(num);char[] numChar = numStr.toCharArray();int a=num, b=num;     // 初始值num，防止999和000或者111之类的情况// 找最大for(char numC : numChar){if(numC != '9'){a = replace(numStr, numC, '9');break;}}// 找最小if(numChar[0] != '1'){b = replace(numStr, numChar[0], '1');}else{for(int i=1; i<numChar.length; i++){if(numChar[i]!='0' && numChar[i]!='1'){b = replace(numStr, numChar[i], '0');break;}}}return a-b;}
}