字节面试题目

[stayt2]

给定一个数n，如23121;给定一组数字A如{2,4,9}，求由A中元素组成的小于n的最大数，如小于23121的最大数为 22999

def find_max_less_than_n(n, A):
    # 将n转化为字符数组，方便处理每一位数字
    digits = list(str(n))
    # 对A进行排序，确保可以从大到小尝试
    A = sorted(A, reverse=True)

    def backtrack(index):
        if index < 0:
            # 如果回溯超出最高位，则返回A中最大元素组成的小于n的最大数
            return str(A[0]) * int(len(digits)-1)

        original = int(digits[index])  # 保存原始数字
        for a in A:
            # 从大到小尝试替换当前位的数字
            if a < original:
                digits[index] = str(a)
                # 将后面的所有位替换成A中最大的数字
                for i in range(index + 1, len(digits)):
                    digits[i] = str(A[0])
                return ''.join(digits)
        # 如果所有的数字都不能替换当前位
        # 那么回溯到上一位
        digits[index] = str(original)
        return backtrack(index - 1)

    # 从最高位开始回溯
    return backtrack(len(digits) - 1)

# 给定的数字
n = 23121
# 给定的数字集合A
A = [2, 4, 9]
# 打印结果
print(find_max_less_than_n(n, A))  # 输出应该是22999

# 对于第二个例子
n = 22121
print(find_max_less_than_n(n, A))  # 输出应该是9999