经典笔试题 小于 n 的最大整数 贪心 回溯 剪枝 全排列

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

👨‍🏫 参考视频

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。
         */

        // 示例1
        int[] a1 = {1, 2, 9, 4};
        int[] n1 = {2, 5, 3, 3};
        System.out.println("示例1：" + getMaxLessNum(a1, n1) + " (应返回2499)");

        // 示例2
        int[] a2 = {1, 2, 5, 4};
        int[] n2 = {2, 5, 4, 3};
        System.out.println("示例2：" + getMaxLessNum(a2, n2) + " (应返回2542)");

        // 示例3
        int[] a3 = {1, 2, 5, 4};
        int[] n3 = {2, 5, 4, 1};
        System.out.println("示例3：" + getMaxLessNum(a3, n3) + " (应返回2525)");

        // 示例4
        int[] a4 = {1, 2, 9, 4};
        int[] n4 = {2, 1, 1, 1};
        System.out.println("示例4：" + getMaxLessNum(a4, n4) + " (应返回1999)");

        // 示例5
        int[] a5 = {5, 9};
        int[] n5 = {5, 5, 5, 5};
        System.out.println("示例5：" + getMaxLessNum(a5, n5) + " (应返回999)");
    }

    /**
     * 获取由数组nums中的元素组成的数字，且小于n的最大值
     * @param nums 数组中的元素都在0~9之间
     * @param n 目标数字数组
     * @return 由nums中的元素组成的数字，且小于n的最大值
     */
    public static String getMaxLessNum(int[] nums, int[] n) {
        // 对nums数组进行排序，方便后续查找最大值
        Arrays.sort(nums);

        // 用于存储结果数字的字符串
        StringBuilder s = new StringBuilder();
        // 深度优先搜索，寻找最大值
        dfs(true, s, nums, n, 0);

        return s.toString();
    }

    /**
     * 深度优先搜索，寻找最大值
     * @param equal 当前位是否与目标数字相等
     * @param s 用于存储结果数字的字符串
     * @param nums 数组中的元素都在0~9之间
     * @param n 目标数字数组
     * @param index 当前处理的位索引
     * @return 是否找到符合条件的数字
     */
    private static boolean dfs(boolean equal, StringBuilder s, int[] nums, int[] n, int index) {
        // 如果是最后一位，则需要判定是否有小于n的数
        if (index == n.length - 1) {
            if (!equal) {
                // 如果前面已经有不相等的位，则直接取nums的最大值
                s.append(nums[nums.length - 1]);
                return true;
            } else {
                // 否则需要寻找小于n最后一位的最大值
                for (int i = nums.length - 1; i >= 0; i--) {
                    if (nums[i] < n[n.length - 1]) {
                        s.append(nums[i]);
                        return true;
                    }
                }
                return false;
            }
        }

        // 前面有不相等的，后面都取nums的最大值即可
        if (!equal) {
            for (int i = index; i < n.length; i++) {
                s.append(nums[nums.length - 1]);
            }
            return true;
        }

        // 前面都相等，优先取和n[index]相同的值，深度优先遍历，如果后面组成的数小于n，则找到了最大的值。如果当前值小于n[index]，则后面都取nums的最大值即可
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] == n[index]) {
                s.append(nums[i]);
                boolean result = dfs(true, s, nums, n, index + 1);
                if (result) {
                    return true;
                } else {
                    s.deleteCharAt(s.length() - 1); // 回溯，删除最后一个字符
                }
            }

            if (nums[i] < n[index]) {
                s.append(nums[i]);
                dfs(false, s, nums, n, index + 1); // 后续位都取最大值
                return true;
            }
        }

        // 如果前面都不满足，删除第一位即可
        if (index == 0) {
            dfs(false, s, nums, n, index + 1);
            return true;
        }

        return false;
    }
}

👨‍🏫 参考博客