丰县住房和城乡建设局网站,西安网站设设,网站开发与app差距,百度搜索推广优化师工作内容给你一个整数 num 。你可以对它进行以下步骤共计 两次#xff1a; 选择一个数字 x (0 x 9). 选择另一个数字 y (0 y 9) 。 数字 y 可以等于 x 。 将 num中所有出现 x 的数位都用 y 替换。 令两次对 num 的操作得到的结果分别为 a 和 b 。 请你返回 a 和 b… 给你一个整数 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 anum, bnum; // 初始值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 i1; inumChar.length; i){if(numChar[i]!0 numChar[i]!1){b replace(numStr, numChar[i], 0);break;}}}return a-b;}
}时间复杂度O(logN) 空间复杂度O(logN)
