字节手撕题小于 n 的最大整数贪心回溯剪枝全排列

给定一个数字字符串S和一个数组nums，数组中的元素都在0~9之间，问从数组中选择元素组成的数字，小于N的最大值是多少？
例如：S = “24378”，nums:{2,3,9}，组成的最大值为23999。

👨‍🏫 参考视频

java">import java.util.Arrays;public class Main {public static void main(String[] args) {/*示例 1：A={1, 2, 9, 4}，n=2533，返回 2499。示例 2：A={1, 2, 5, 4}，n=2543，返回 2542。示例 3：A={1, 2, 5, 4}，n=2541，返回 2525。示例 4：A={1, 2, 9, 4}，n=2111，返回 1999。示例 5：A={5, 9}，n=5555，返回 999。*/// 示例1int[] a1 = {1, 2, 9, 4};int n1 = 2533 ;System.out.println("示例1：" +Arrays.toString(a1)+"," + n1 + " : "+ getMaxLessNum(a1, n1) + " (应返回2499)");// 示例2int[] a2 = {1, 2, 5, 4};int n2 = 2543;System.out.println("示例2：" +Arrays.toString(a2)+"," + n2 + " : "+ getMaxLessNum(a2, n2) + " (应返回2542)");// 示例3int[] a3 = {1, 2, 5, 4};int n3 = 2541;int m = 2541;System.out.println("示例3：" +Arrays.toString(a3)+"," + n3 + " : "+ getMaxLessNum(a3, n3) + " (应返回2525)");// 示例4int[] a4 = {1, 2, 9, 4};int n4 = 2111;System.out.println("示例4：" +Arrays.toString(a4)+"," + n4 + " : "+ getMaxLessNum(a4, n4) + " (应返回1999)");// 示例5int[] a5 = {5, 9};int n5 = 5555 ;System.out.println("示例5：" +Arrays.toString(a5)+"," + n5 + " : " + getMaxLessNum(a5, n5) + " (应返回999)");int[] a6 = {5};int n6 = 2 ;System.out.println("示例6：" +Arrays.toString(a6)+"," + n6 + " : "+ getMaxLessNum(a6, n6) + " (不存在)");}static int[] nums;/*** 获取由数组nums中的元素组成的数字，且小于n的最大值*/public static String getMaxLessNum(int[] a, int b) {// 对nums数组进行排序，方便后续查找最大值nums = a;Arrays.sort(nums);int[] n = String.valueOf(b).chars().map(c -> c - '0').toArray();// 用于存储结果数字的字符串// 深度优先搜索，寻找最大值StringBuilder ans = new StringBuilder();dfs(true, ans,n, 0);return ans.length() == 0 ? "不存在" :ans.toString();}/*** 深度优先搜索，寻找最大值* @param equal：*              true 表示前面的都相等*              false 表示前面有小于 nums 的位后面都可以取最大* @param n 表示的是最大数* @param idx 表示最大数枚举到的下标*/private static boolean dfs(boolean equal, StringBuilder ans, int[] n,  int idx) {// 如果是最后一位，则需要判定是否有小于n的数if (idx == n.length - 1) {if (!equal) {// 如果前面已经有不相等的位，则直接取nums的最大值ans.append(nums[nums.length - 1]);return true;} else { // 说明前面的数位都相等，当前数位必须取一个小于 n 对应数位的值，找不到返回 false// 否则需要寻找小于n最后一位的最大值for (int i = nums.length - 1; i >= 0; i--) {if (nums[i] < n[n.length - 1]) {ans.append(nums[i]);return true;}}return false;}}// 前面有不相等的，后面都取nums的最大值即可if (!equal) {for (int i = idx; i < n.length; i++) {ans.append(nums[nums.length - 1]);}return true;}// 前面都相等，优先取和n[idx]相同的值(因为高位大才是真的大)，深度优先遍历，如果后面组成的数小于n，则找到了最大的值。// 如果当前值小于n[idx]，则后面都取nums的最大值即可for (int i = nums.length - 1; i >= 0; i--) {if (nums[i] == n[idx]) {ans.append(nums[i]);boolean result = dfs(true,ans, n, idx + 1);if (result) {return true;} else {ans.deleteCharAt(ans.length() - 1); // 回溯，删除最后一个字符}}if (nums[i] < n[idx]) {ans.append(nums[i]);dfs(false,ans, n, idx + 1); // 后续位都取最大值return true;}}// 神之一笔，所有都不满足，直接取减少一位// 如果前面都不满足，删除第一位即可if (idx == 0) {dfs(false,ans,  n, idx + 1);return true;}return false;}
}