字节社招一面算法记录

题目：给定一个数字n和数组numbers，求由numbers中元素组成的不大于n的最大数

思路：为了保证最终结果ans最大，需要尽量保证ans的高位和n的高位一致，ans的低位小于n的低位，这里存在三个需要注意的点

1. numbers中不存在小于等于n最高位的数字，此时需要使用numbers中最大数，组成一个位数小于n的数字
2. 对于n中某一位数，numbers中不存在小于等于该数的数字，那么该数的高位就需要小于n中对应数位的数
3. 对于当高位存在了ans小于n的情况时，后续低位需要填充numbers中最大数

代码：

def func(n, numbers):
    """
    :param n: 整数n
    :param numbers: 0-9的number组成的数组
    :return: 由numbers中元素组成的不大于n的最大数
    """
    n_list = [int(i) for i in list(str(n))]
    numbers.sort()
    n_set = set(n_list)

    # cache 用于存储numbers中小于等于n中数字的元素
    cache = {}
    for num in n_set:
        left = 0
        right = len(numbers)-1
        while left <= right:
            mid = (left+right)//2
            if numbers[mid]>num:
                # right右侧的都大于num
                right = mid-1
            else:
                # numbers[mid]<=num,left左侧的都小于等于num
                left = mid+1
        cache[num] = numbers[:left]
    print(cache)

    def dfs(n_index):
        """
        #n_index表示位数
        #返回None:表示低位无法更小，高位需要减小
        #返回列表：表示低位拼出了更小的值
        """

        # 超出了位数 或者 numbers中所有值均大于该位数，那么必须高位使用较小值
        if n_index == len(n_list) or not cache.get(n_list[n_index]):
            return None
        # temp为numbers中小于该位数的所有元素，升序排列
        temp = cache[n_list[n_index]]
        # 当该数位在numbers中存在相等元素时，尝试让低位更小
        if temp[-1] == n_list[n_index]:
            rest = dfs(n_index + 1)
            if rest:
                return [temp[-1]]+rest
            else:
                # 低位无法更小时，尝试将本位修改为小于本位的最大值
                for index in range(1, len(temp)+1):
                    if temp[-index]<n_list[n_index]:
                        return [temp[-index]]
                # 本位也无法减小时，返回None，让高位尝试减小
                return None
        else:
            # 本位无法找到相等元素，选取小于本位的最大值，后续低位使用Numbers最大值填充
            return [temp[-1]]

    ans_list = dfs(0)

    ans = 0
    if not ans_list:
        # ans_list为None表示,numbers中不存在元素，小于等于n的最高位，此时减小ans的位数
        for i in range(len(n_list)-1):
            ans = ans*10+numbers[-1]
    else:
        for number in ans_list:
            ans = ans*10+number
        # 高位已经存在减小，低位填充number中的最大元素
        for _ in range(len(n_list) - len(ans_list)):
            ans = ans*10+numbers[-1]
    return ans

面试的时候思路错误写了错误的算法，面试结束后才发现写错了，不知道现在的写法是否有误，如果有误请大家指出