字节高频算法面试题：小于 n 的最大数

问题描述（感觉n的位数需要大于等于2，因为n的位数=1的话会有点问题，“且无重复”是指nums中存在重复，但是最后返回的小于n最大数是可以重复使用nums中的元素的）：

思路：

先对nums倒序排序 + 暴力回溯 + 剪枝优化

代码（含详细注释）：

class Solution {public int ans = 0;public int getMaxNum(int[] nums, int n) { // 默认n的位数大于等于2// ① 降序排序Arrays.sort(nums);int left = 0, right = nums.length - 1;while (left < right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;left++;right--;}// ② 试图寻找一个小于n的整数（位数和n一样）String nStr = String.valueOf(n);boolean isFound = dfs(nums, nStr, new ArrayList<>(), true);// ③ 比如这种情况，nums: 9 8 7, n: 123，nums中最小的数都比n要大，那么isFound是falseif (!isFound) {for (int i = 0; i < nStr.length() - 1; i++) {ans = ans * 10 + nums[0]; // 比n少一位，然后由nums的最大元素组装而成}}return ans;}public boolean dfs(int[] nums, String nStr, List<Integer> path, boolean preIsEqual) {if (path.size() == nStr.length()) { // 递归出口。如果当前路径的数字已经达到整数n的位数了long pathSum = 0;for (int i = 0; i < path.size(); i++) {pathSum = pathSum * 10 + path.get(i);}// 如果 path: 444, n: 444 全部位置的数字相等也不行if (pathSum < Integer.parseInt(nStr)) {ans = (int) pathSum;return true; // 表示已经找到了}return false; // 有可能是, path: 444, n: 444，全部位置的数字相等也不行}for (int i = 0; i < nums.length; i++) {if (preIsEqual) { // 如果前面几位的数字，path对应的数和n对应位的数相等, 如: path:44_, n:444// 如果前面几位的数字，path对应的数和n对应位的数相等，且当前位数字nums[i]>n对应的位的数，那就剪枝if (nums[i] > nStr.charAt(path.size()) - '0') continue;// 否则可以加入路径path.add(nums[i]);boolean curFlag = dfs(nums, nStr, path, nums[i] == nStr.charAt(path.size()-1) - '0');if (curFlag) return true; // 找到了，直接返回path.remove(path.size() - 1);} else { // 如果前面几位的数字，path对应的数和n对应位的数完全不相等或者不都相等, 如: path:44_, n:543path.add(nums[i]);// 如果前面几位的数字，path对应的数和n对应位的数完全不相等或者不都相等, 那么后面的递归都将是不相等的boolean curFlag = dfs(nums, nStr, path, false);if (curFlag) return true; // 找到了，直接返回path.remove(path.size() - 1);}}return false; // 没找到}
}

测试

测试类

class SolutionTest {public static void test(int[] nums, int n, int expected) {Solution solution = new Solution();int result = solution.getMaxNum(nums, n);if (result != expected) {System.out.println("测试失败！");System.out.println("输入数组: " + arrayToString(nums));System.out.println("目标数: " + n);System.out.println("期望结果: " + expected);System.out.println("实际结果: " + result);System.out.println("------------------------");} else {System.out.println("测试通过: " + arrayToString(nums) + " -> " + n + " = " + result);}}private static String arrayToString(int[] arr) {StringBuilder sb = new StringBuilder("[");for (int i = 0; i < arr.length; i++) {sb.append(arr[i]);if (i < arr.length - 1) {sb.append(", ");}}sb.append("]");return sb.toString();}public static void main(String[] args) {// 基本测试test(new int[]{1, 2, 9, 8}, 100, 99);test(new int[]{4, 5}, 445, 444);test(new int[]{4, 5}, 45, 44);// 边界情况test(new int[]{1, 9}, 10, 9);test(new int[]{9, 8}, 9, 8);test(new int[]{9}, 100, 99);// 所有数字都大于目标数test(new int[]{9, 8, 7}, 123, 99);test(new int[]{9, 8, 7}, 12, 9);// 复杂数字组合test(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}, 3000, 2999);test(new int[]{1, 2, 8, 9}, 2990, 2989);// 相同数字test(new int[]{4}, 445, 444);test(new int[]{4}, 45, 44);test(new int[]{4}, 4445, 4444);// 大数测试test(new int[]{9}, 100000, 99999);test(new int[]{8, 9}, 99000, 98999);// 特殊数字组合test(new int[]{1, 2, 3}, 300, 233);test(new int[]{2, 8}, 290, 288);test(new int[]{2, 8, 9}, 289, 288);// 多位数测试test(new int[]{6, 7, 8, 9}, 9877, 9876);test(new int[]{6, 7, 8, 9}, 9868, 9867);// 相邻数字test(new int[]{8, 9}, 1000, 999);test(new int[]{8, 9}, 999, 998);// 混合数字test(new int[]{5, 9}, 6000, 5999);test(new int[]{5, 8, 9}, 5990, 5989);test(new int[]{5, 8, 9}, 5900, 5899);// 包含零test(new int[]{0, 9}, 100, 99);test(new int[]{0, 9}, 1000, 999);// 特殊序列test(new int[]{1, 2, 3, 4, 5, 6}, 54322, 54321);test(new int[]{0, 2, 3, 4, 5, 6}, 54321, 54320);// 重复数字test(new int[]{6, 6, 6, 6}, 6667, 6666);test(new int[]{5, 6}, 6666, 6665);// 极限情况test(new int[]{9}, 1000000, 999999);test(new int[]{9}, 100000, 99999);// 连续数字test(new int[]{1, 2, 3, 4, 5}, 12346, 12345);test(new int[]{1, 2, 3, 4}, 12345, 12344);}
}

结果