字節(jié)-算法面試題：給定數(shù)字n和集合arr，求arr中的數(shù)字能組成小于n的最大整數(shù)靡挥，arr中的數(shù)字可以重復(fù)使用序矩。
例：n=5213，arr={0,3,5,2}跋破，返回結(jié)果應(yīng)該為5205簸淀。
解題思路
按位先正向后反向查找，使用遞歸實現(xiàn)功能毒返。
需要特別注意的是：首位和末位租幕，正向遞歸時判斷是否是末位，回溯時判斷是否是首位拧簸。
正向查找
根據(jù)n的位數(shù)劲绪，從大數(shù)位到小數(shù)位進(jìn)行遞歸：如果當(dāng)前數(shù)字可用，就將當(dāng)前數(shù)字放入該位置盆赤。
特殊情況：如果是最后一位贾富，需要將 比當(dāng)前數(shù)字更小的最大數(shù)字 放到該位置上。
無匹配
如果當(dāng)前數(shù)字無匹配牺六，將 比當(dāng)前數(shù)字更小的最大數(shù)字 放到該位置上颤枪，同時后續(xù)數(shù)位都填充最大數(shù)字。
回溯-反向查找
如果沒有 比當(dāng)前數(shù)字更小的最大數(shù)字淑际，則回溯到上一位置畏纲，將 比當(dāng)前數(shù)字更小的最大數(shù)字 放到該位置上，同時后續(xù)數(shù)位都填充最大數(shù)字春缕。
特殊情況：如果回溯到首位仍然沒有 比當(dāng)前數(shù)字更小的最大數(shù)字盗胀，則取消最大位，同時后續(xù)數(shù)位都填充最大數(shù)字淡溯。
編程思路
- 回溯時读整，一定會查找 比當(dāng)前數(shù)字更小的最大數(shù)字 是否存在，與“無匹配”的功能重復(fù)咱娶，所以可以寫到同1個函數(shù)中米间；
- 正向查找和回溯時，傳遞參數(shù)為當(dāng)前的位置膘侮，所以可以將當(dāng)前位置
position作為傳參屈糊； - 最后判斷
position的位置，并將之后的位置全部填充為可用的最大值琼了。
Python代碼
n = 5213
arr = {0,3,5,2}
arr_list_sort = sorted(list(arr)) # 排序可用數(shù)字逻锐，以便于查找 比當(dāng)前數(shù)字更小的最大數(shù)字
n = str(n)
n_len = len(n)
res = [arr_list_sort[0]] * n_len # 使用最小值初始化所有位置
def fan(position):
"""回溯-反向遞歸夫晌，并判斷是否存在比當(dāng)前數(shù)字更小的數(shù)字
position[int]: 當(dāng)前位置
"""
# print("position = ", position)
np = int(n[position])
if position == 0: # 回溯到首位
for arrr in arr_list_sort[::-1]:
if arrr<np: # 存在比當(dāng)前數(shù)字更小的數(shù)字
res[position] = arrr
return position
position = -1
res.pop(0)
return position
else:
for arrr in arr_list_sort[::-1]:
if arrr<np: # 存在比當(dāng)前數(shù)字更小的數(shù)字
res[position] = arrr
return position
return fan(position-1)
def zheng(position):
"""正向遞歸
position[int]: 當(dāng)前位置
"""
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位數(shù)字 且 arr中沒有比n更小的數(shù)字
res = "無結(jié)果！"
else:
if position != n_len-1: # 沒有處理到最后一位
position += 1
for _ in res[position:]: # 后續(xù)位置填充可用的最大值
res[position] = arr_list_sort[-1]
res = sum([pow(10,i)*j for i,j in enumerate(res[::-1])])
print(res)
個人原創(chuàng)昧诱，歡迎交流討論晓淀！
