数组数字组成比目标数小的最大数

作者： 作者的头像   大瓜娃子 ,  2024-11-17 17:27:37 ,  所有人可见 ,  阅读 5

0 


数组A中给定可以使用的1~9的数，返回由A数组中的元素组成的小于n的最大数。
例如A={1, 2, 4, 9}，x=2533，返回2499

暴力解法

import java.util.Scanner;
class Main {
    public static int res = Integer.MIN_VALUE;

    public static int getMax(int[] array, int target) {
        dfs(target, array, 0, 0);
        return res;
    }

    private static void dfs(int target, int[] array, int curVal, int index) {
        res = Math.max(res, curVal);
        if (index == array.length) return;
        for (int i = 0; i < array.length; i++) {
            curVal = curVal * 10 + array[i];
            if (curVal >= target) {
                continue;
            }
            index++;
            dfs(target, array, curVal, index);
            index--;
            curVal /= 10;
        }
    }
    public static void main(String[] args){
        int[] nums= {1, 2, 4, 9};
        int maxVal = 2533;
        System.out.println(getMax(nums, maxVal));
    }
}

1 评论

用户头像
大瓜娃子   6天前         踩      回复

deepseek写的双指针贪心：

import java.util.*;

public class MaxNumberLessThanN {

    public static int findMaxNumberLessThanN(int[] A, int n) {
        // 将目标数 n 转换为字符串
        String nStr = String.valueOf(n);
        int len = nStr.length();

        // 对数组 A 进行排序，方便后续查找
        Arrays.sort(A);

        // 用于存储结果的数组
        int[] result = new int[len];

        // 用于标记是否已经找到小于 n 的最大数
        boolean found = false;

        // 从高位到低位逐位尝试构建数字
        for (int i = 0; i < len; i++) {
            int digit = nStr.charAt(i) - '0';

            // 找到小于或等于当前位的最大数字
            int maxDigit = -1;
            for (int num : A) {
                if (num <= digit) {
                    maxDigit = Math.max(maxDigit, num);
                } else {
                    break;
                }
            }

            // 如果找到了合适的数字，则将其放入结果数组
            if (maxDigit != -1) {
                result[i] = maxDigit;
                if (maxDigit < digit) {
                    found = true;
                    // 如果当前位小于目标数的当前位，则后续位可以任意选择最大值
                    for (int j = i + 1; j < len; j++) {
                        result[j] = A[A.length - 1];
                    }
                    break;
                }
            } else {
                // 如果找不到合适的数字，则回溯
                while (i > 0 && result[i - 1] == A[0]) {
                    i--;
                }
                if (i == 0) {
                    // 如果回溯到最高位仍然无法找到合适的数字，则去掉最高位
                    result = new int[len - 1];
                    for (int j = 0; j < len - 1; j++) {
                        result[j] = A[A.length - 1];
                    }
                    break;
                } else {
                    // 回溯到上一位，尝试选择更小的数字
                    int prevDigit = result[i - 1];
                    for (int j = A.length - 1; j >= 0; j--) {
                        if (A[j] < prevDigit) {
                            result[i - 1] = A[j];
                            break;
                        }
                    }
                    // 后续位可以任意选择最大值
                    for (int j = i; j < len; j++) {
                        result[j] = A[A.length - 1];
                    }
                    break;
                }
            }
        }

        // 将结果数组转换为整数
        int finalResult = 0;
        for (int num : result) {
            finalResult = finalResult * 10 + num;
        }

        return finalResult;
    }

    public static void main(String[] args) {
        int[] A = {1, 2, 4, 9};
        int n = 2533;
        int result = findMaxNumberLessThanN(A, n);
        System.out.println(result); // 输出 2499
    }
}