东莞工信部网站,vs html5网站开发,上海微信网站公司哪家好,沈阳曙光医院看男科怎么样问题描述#xff08;感觉n的位数需要大于等于2#xff0c;因为n的位数1的话会有点问题#xff0c;“且无重复”是指nums中存在重复#xff0c;但是最后返回的小于n最大数是可以重复使用nums中的元素的#xff09;#xff1a; 思路#xff1a;
先对nums倒序排序 暴力回…问题描述感觉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: 123nums中最小的数都比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, ListInteger 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);}
}结果
