字节高频题 小于n的最大数

题目要求给定一个数n和一个集合s/数组nums求用集合/数组中的元素组成的小于n的最大整数。集合s中的元素可以重复选取。举例给一个数n 333和一个集合s {2,5,9}求用s组成的小于n的最大数那么这里答案应该为299。1.思路贪心 回溯带二分查找优化。1贪心选择贪心算法适合处理这种数字可重复使用的不可重复选择问题。在从左到右的选择过程中一旦在某个位置选择了小于n对应位的数字后面所有位的数字都要取允许集合中的最大值这样求得的结果就一定是在该前缀下的最大的。2回溯保证全局最优如果某一位找不到 原数字的允许数字说明这条路径不可行必须减小前一位。回溯过程要保持结果仍然是“小于n的最大数”。3如果没有办法构造一个和n的位数相同、但值小于n的数字那么就退一步构造一个比n少一位且每一位都取允许集合中的最大数字的数。也就是在“位数更少”的前提下能得到的最大值。2.举例说明1示例1n 333允许数字 {259}。过程第一位要找 3的最大允许数字 - 最大是2并且2 3所以第一位直接选2后面直接全部选允许集合中的最大值 得到299 333成功。这种情况属于长度相同且构造成功不需要减少长度。2示例2n 1000允许数字 {9}。过程第一位要找 1的最大允许数字 - 允许数字只有99 1没有数字可用。考虑回溯但是无法通过减少任何一位整串全是9都大于1000的任何前缀说明长度相同的数不可能构造出来。于是退而求其次返回3位比n少一位的最大数999。999就是所有位数 4的数中最大的这种情况属于长度不同且构造成功。3.复杂度分析1时间复杂度O(L*logD)其中L为n的位数D为负责构造结果的允许的数字种类数。由于允许数字种类数D 10因此因此时间复杂度也可视为O(L)。2空间复杂度O(L)只存储结果字符串。附代码class Solution { public String maxLessThanN(String n, int[] digits) { char[] chars n.toCharArray(); int len chars.length; char[] result new char[len]; // 对允许使用的数字从小到大排序 int[] sorted digits.clone(); Arrays.sort(sorted); // 贪心 回溯 for (int i 0; i len; i) { // 把当前位记作curDigit int curDigit chars[i] - 0; // 二分查找允许使用的数字中 curDigit的最大允许数字 int idx searchLastLessOrEqual(sorted, curDigit); // idx -1表示没找到 // 即允许使用的数字中没有 curDigit的最大允许数字 // 需要回溯 if (idx -1) { // found置为false表示没找到 boolean found false; for (int j i - 1; j 0; j--) { // 从当前位的上一位开始往前遍历每一位记作prevDigit // 从当前位的上一位开始依次往前找二分查找允许使用的数字中 prevDigit的最大允许数字 int prevDigit result[j] - 0; int prevIdx searchLastLess(sorted, prevDigit); // 往前遍历的过程中在某一位找到了 prevDigit的最大允许数字 if (prevIdx 0) { // 回溯成功把找到的j位置为 prevDigit的最大允许数字 result[j] (char) (sorted[prevIdx] 0); // 把结果数组res中 prevDigit的最大允许数字后的数字全部置为sorted数组中的最大数字 fillMaxFrom(j 1, result, sorted); // 回溯成功found更新为true found true; // 后位全部提前补全因此提前退出只有回溯失败会走完回溯倒退遍历for循环节省了时间 break; } } // 如果回溯成功返回res数组 if (found) { return new String(result); } else { // 回溯失败i位的前面的位中每一位都无法缩小 // 说明长度相同的数已不可能构造出结果 // 返回比目标位数小一位的可构造的最大数 return buildAllMax(len - 1, sorted); } } // 走到这说明没有提前return // 说明前面的代码执行很顺利没有走回溯逻辑 // 说明二分查找能找到允许使用的数字中 curDigit的最大允许数字 // 拿到要找的数chosen即允许使用的数字中 curDigit的最大允许数字 // 把结果数组res中当前位置i置为chosen int chosen sorted[idx]; result[i] (char) (chosen 0); // 如果拿到的chosen是小于curDigit的而非等于 // 那么后面的数字全部置为sorted数组中的最大数字return 结果 即可 if (chosen curDigit) { fillMaxFrom(i 1, result, sorted); return new String(result); } } // 走到这还没return说明完全匹配前面每一位都是chose curDigit // 那么说明res n允许使用的数字完全可以构成n // 但是题目要求是小于 for (int j len - 1; j 0; j--) { // 从当前位开始往前遍历去找允许使用的数字中 当前位curDigit的最大允许数字 int curDigit result[j] - 0; int idx searchLastLess(sorted, curDigit); // 如果能找到 if (idx 0) { // 把该位置为 该位curDight的最大允许数字 result[j] (char) (sorted[idx] 0); // 并把该位后面的位全部置为sorted数组中的最大数字return 结果 即可 fillMaxFrom(j 1, result, sorted); return new String(result); } } // 如果每一位都无法缩小那么也要返回比目标位数小一位的可构造的最大数 return buildAllMax(len - 1, sorted); } // 寻找 target的最大索引位置 private int searchLastLessOrEqual(int[] sorted, int target) { int left 0, right sorted.length - 1; // 默认值-1表示没找到 int idx -1; while (left right) { int mid (left right) / 2; if (sorted[mid] target) { // 每次找到一个合格的值就记录它但不立刻返回 // 不断二分缩小区间 idx mid; // left继续向右找看有没有更大的合格值 left mid 1; } else { right mid - 1; } } return idx; } // 寻找 target的最大索引位置 private int searchLastLess(int[] sorted, int target) { int left 0, right sorted.length - 1; // 默认值-1表示没找到 int idx -1; while (left right) { int mid (left right) / 2; if (sorted[mid] target) { // 每次找到一个合格的值就记录它但不立刻返回 // 不断二分缩小区间 idx mid; // left继续向右找看有没有更大的合格的值 left mid 1; } else { right mid - 1; } } return idx; } // 把start及后面的位全部置为sorted数组中的最后一个元素值最大值 private void fillMaxFrom(int start, char[] result, int[] sorted) { int maxDigit sorted[sorted.length - 1]; for (int i start; i result.length; i) { result[i] (char) (maxDigit 0); } } // 构建长度为len的全部由sorted数组的最后一位组成的数组此处的len即为n的长度len - 1 private String buildAllMax(int len, int[] sorted) { if (len 0) return ; int maxDigit sorted[sorted.length - 1]; char[] res new char[len]; Arrays.fill(res, (char) (maxDigit 0)); return new String(res); } }ACM模式import java.util.Scanner; import java.util.Arrays; class Solution { public String maxLessThanN(String n, int[] digits) { char[] chars n.toCharArray(); int len chars.length; char[] result new char[len]; // 对允许使用的数字从小到大排序 int[] sorted digits.clone(); Arrays.sort(sorted); // 贪心 回溯 for (int i 0; i len; i) { // 把当前位记作curDigit int curDigit chars[i] - 0; // 二分查找允许使用的数字中 curDigit的最大允许数字 int idx searchLastLessOrEqual(sorted, curDigit); // idx -1表示没找到 // 即允许使用的数字中没有 curDigit的最大允许数字 // 需要回溯 if (idx -1) { // found置为false表示没找到 boolean found false; for (int j i - 1; j 0; j--) { // 从当前位的上一位开始往前遍历每一位记作prevDigit // 从当前位的上一位开始依次往前找二分查找允许使用的数字中 prevDigit的最大允许数字 int prevDigit result[j] - 0; int prevIdx searchLastLess(sorted, prevDigit); // 往前遍历的过程中在某一位找到了 prevDigit的最大允许数字 if (prevIdx 0) { // 回溯成功把找到的j位置为 prevDigit的最大允许数字 result[j] (char) (sorted[prevIdx] 0); // 把结果数组res中 prevDigit的最大允许数字后的数字全部置为sorted数组中的最大数字 fillMaxFrom(j 1, result, sorted); // 回溯成功found更新为true found true; // 后位全部提前补全因此提前退出只有回溯失败会走完回溯倒退遍历for循环节省了时间 break; } } // 如果回溯成功返回res数组 if (found) { return new String(result); } else { // 回溯失败i位的前面的位中每一位都无法缩小 // 说明长度相同的数已不可能构造出结果 // 返回比目标位数小一位的可构造的最大数 return buildAllMax(len - 1, sorted); } } // 走到这说明没有提前return // 说明前面的代码执行很顺利没有走回溯逻辑 // 说明二分查找能找到允许使用的数字中 curDigit的最大允许数字 // 拿到要找的数chosen即允许使用的数字中 curDigit的最大允许数字 // 把结果数组res中当前位置i置为chosen int chosen sorted[idx]; result[i] (char) (chosen 0); // 如果拿到的chosen是小于curDigit的而非等于 // 那么后面的数字全部置为sorted数组中的最大数字return 结果 即可 if (chosen curDigit) { fillMaxFrom(i 1, result, sorted); return new String(result); } } // 走到这还没return说明完全匹配前面每一位都是chose curDigit // 那么说明res n允许使用的数字完全可以构成n // 但是题目要求是小于 for (int j len - 1; j 0; j--) { // 从当前位开始往前遍历去找允许使用的数字中 当前位curDigit的最大允许数字 int curDigit result[j] - 0; int idx searchLastLess(sorted, curDigit); // 如果能找到 if (idx 0) { // 把该位置为 该位curDight的最大允许数字 result[j] (char) (sorted[idx] 0); // 并把该位后面的位全部置为sorted数组中的最大数字return 结果 即可 fillMaxFrom(j 1, result, sorted); return new String(result); } } // 如果每一位都无法缩小那么也要返回比目标位数小一位的可构造的最大数 return buildAllMax(len - 1, sorted); } // 寻找 target的最大索引位置 private int searchLastLessOrEqual(int[] sorted, int target) { int left 0, right sorted.length - 1; // 默认值-1表示没找到 int idx -1; while (left right) { int mid (left right) / 2; if (sorted[mid] target) { // 每次找到一个合格的值就记录它但不立刻返回 // 不断二分缩小区间 idx mid; // left继续向右找看有没有更大的合格值 left mid 1; } else { right mid - 1; } } return idx; } // 寻找 target的最大索引位置 private int searchLastLess(int[] sorted, int target) { int left 0, right sorted.length - 1; // 默认值-1表示没找到 int idx -1; while (left right) { int mid (left right) / 2; if (sorted[mid] target) { // 每次找到一个合格的值就记录它但不立刻返回 // 不断二分缩小区间 idx mid; // left继续向右找看有没有更大的合格的值 left mid 1; } else { right mid - 1; } } return idx; } // 把start及后面的位全部置为sorted数组中的最后一个元素值最大值 private void fillMaxFrom(int start, char[] result, int[] sorted) { int maxDigit sorted[sorted.length - 1]; for (int i start; i result.length; i) { result[i] (char) (maxDigit 0); } } // 构建长度为len的全部由sorted数组的最后一位组成的数组此处的len即为n的长度len - 1 private String buildAllMax(int len, int[] sorted) { if (len 0) return ; int maxDigit sorted[sorted.length - 1]; char[] res new char[len]; Arrays.fill(res, (char) (maxDigit 0)); return new String(res); } } public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); String n scanner.nextLine().trim(); int m scanner.nextInt(); int[] digits new int[m]; for (int i 0; i m; i) { digits[i] scanner.nextInt(); } Solution solution new Solution(); String result solution.maxLessThanN(n, digits); System.out.println(result); scanner.close(); } }