字节-算法面试题：给定数字n和集合arr，求arr中的数字能组成小于n的最大整数，arr中的数字可以重复使用。
例：n=5213，arr={0,3,5,2}，返回结果应该为5205。
解题思路
按位先正向后反向查找，使用递归实现功能。
需要特别注意的是：首位和末位，正向递归时判断是否是末位，回溯时判断是否是首位。
正向查找
根据n的位数，从大数位到小数位进行递归：如果当前数字可用，就将当前数字放入该位置。
特殊情况：如果是最后一位，需要将 比当前数字更小的最大数字 放到该位置上。
无匹配
如果当前数字无匹配，将 比当前数字更小的最大数字 放到该位置上，同时后续数位都填充最大数字。
回溯-反向查找
如果没有 比当前数字更小的最大数字，则回溯到上一位置，将 比当前数字更小的最大数字 放到该位置上，同时后续数位都填充最大数字。
特殊情况：如果回溯到首位仍然没有 比当前数字更小的最大数字，则取消最大位，同时后续数位都填充最大数字。
编程思路
- 回溯时，一定会查找 比当前数字更小的最大数字 是否存在，与“无匹配”的功能重复，所以可以写到同1个函数中；
- 正向查找和回溯时，传递参数为当前的位置，所以可以将当前位置
position作为传参； - 最后判断
position的位置，并将之后的位置全部填充为可用的最大值。
Python代码
n = 5213
arr = {0,3,5,2}
arr_list_sort = sorted(list(arr)) # 排序可用数字，以便于查找 比当前数字更小的最大数字
n = str(n)
n_len = len(n)
res = [arr_list_sort[0]] * n_len # 使用最小值初始化所有位置
def fan(position):
"""回溯-反向递归，并判断是否存在比当前数字更小的数字
position[int]: 当前位置
"""
# print("position = ", position)
np = int(n[position])
if position == 0: # 回溯到首位
for arrr in arr_list_sort[::-1]:
if arrr<np: # 存在比当前数字更小的数字
res[position] = arrr
return position
position = -1
res.pop(0)
return position
else:
for arrr in arr_list_sort[::-1]:
if arrr<np: # 存在比当前数字更小的数字
res[position] = arrr
return position
return fan(position-1)
def zheng(position):
"""正向递归
position[int]: 当前位置
"""
np = int(n[position])
if position < n_len-1:
if np not in arr:
position = fan(position)
return position
else:
res[position] = np
return zheng(position+1)
else: # 最后一位
position = fan(position)
return position
position = zheng(position=0)
lenres = len(res)
if lenres == 0: # n为1位数字 且 arr中没有比n更小的数字
res = "无结果！"
else:
if position != n_len-1: # 没有处理到最后一位
position += 1
for _ in res[position:]: # 后续位置填充可用的最大值
res[position] = arr_list_sort[-1]
res = sum([pow(10,i)*j for i,j in enumerate(res[::-1])])
print(res)
个人原创，欢迎交流讨论！
