字节面试题：不大于n的最大的数

特此记录一下上次面试被问没写出来的这道题

题目描述：

给定一个数组A,利用A中的数字组合形成小于n的最大数，且A中的数字可以重复使用 例如 ：

1. A = [6,8] n = 100 那么得到的数字是88
2. n = 23121; A = {2,4,9}求由A中元素组成的、小于n的最大数,如小于23121的最大数为22999

代码解答

import java.util.*;

public class TestN {
    //题目是小于n的最大数所以不能等于n，如果要等于n，那么去掉这个getMax的部分即可
    //check是用来判断长度是否能和n一样的，这里minValue就是nums[0]
    static boolean check(String str, int minValue) {
        char c = str.charAt(0);
        if (minValue < c - '0') {
            return true;
        } else if (minValue == c - '0') {
            // 该位置相同,则递归往下查找
            return check(str.substring(1), minValue);
        } else {
            return false;
        }
    }
    
    //得到用nums中的数字能够拼出的数字的上限
    static int getMax(int[] nums, int n) {
        // 把n转成字符串,方便后面操作
        String s = String.valueOf(n);
        if (check(s, nums[0])) {
            // 长度可以和n一样
            return n - 1;
        } else {
            // 如果位数小1的话,那就直接都取nums数组中最大的那个元素拼接就行,只要位数-1
            return (int) Math.pow(10, s.length() - 1) - 1;
        }
    }

    // 二分查找，找到 <= target 的最大索引
    public static int binarySearch(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] <= target) l = mid + 1;
            else r = mid - 1;
        }
        return r; // r 是 <= target 的最大索引
    }

    // 返回 nums 中比 str[u] 小的最大索引
    public static int getIndex(int[] nums, String str, int u) {
        int cur = str.charAt(u) - '0';
        int index = binarySearch(nums, cur);
        // 如果当前位不能取 cur，选更小的
        while (index >= 0 && nums[index] > cur) index--;
        return index;
    }

    public static String getMaxBelowN(int[] nums, int n) {
        Arrays.sort(nums);
        int maxValue = getMax(nums,n);
        String s = String.valueOf(maxValue);
        StringBuilder res = new StringBuilder();
        boolean flag = false;

        for (int i = 0; i < s.length(); i++) {
            int index = getIndex(nums, s, i);
            if (index == -1) {  // 如果无法选择当前位，就回退
                while (res.length() > 0) {
                    int lastIndex = res.length() - 1;
                    int lastDigit = res.charAt(lastIndex) - '0';

                    int newIndex = binarySearch(nums, lastDigit) - 1;
                    if (newIndex >= 0) {
                        res.setCharAt(lastIndex, (char) ('0' + nums[newIndex]));
                        break;
                    }
                    res.deleteCharAt(lastIndex);
                }

                // 全部删除，返回最大可选数
                if (res.length() == 0) {
                    char[] maxNum = new char[s.length() - 1];
                    Arrays.fill(maxNum, (char) ('0' + nums[nums.length - 1]));
                    return new String(maxNum);
                }

                while (res.length() < s.length()) {
                    res.append(nums[nums.length - 1]);
                }

                return res.toString();
            }

            res.append(nums[index]);
            if (nums[index] < s.charAt(i) - '0') flag = true;
        }

        return res.toString();
    }

    public static void main(String[] args) {
        int[] nums;
        int n;

        nums = new int[]{1, 2, 4, 6, 8};
        n = 2411;
        System.out.println(getMaxBelowN(nums, n));  // 2288
        nums = new int[]{2, 4, 6, 8};
        n = 2411;
        System.out.println(getMaxBelowN(nums, n));  // 2288
        nums = new int[]{9, 8, 7, 6};
        n = 2411;
        System.out.println(getMaxBelowN(nums, n));  // 999
        nums = new int[]{8, 7, 6};
        n = 2411;
        System.out.println(getMaxBelowN(nums, n));  // 888
        nums = new int[]{4, 5, 6};
        n = 23;
        System.out.println(getMaxBelowN(nums, n));  // 6
    }
}