该题目在网上目前的答案很多，但是要么很长难以理解，要么答案根本就不对。最近看到了这位博主的博文：字节面试题：给定数字n，数组arr={1,3,5,2}，求arr中的数字能组成小于n的最大整数_斯文流氓骚刚的博客-CSDN博客
深受启发，但原文仍有瑕疵，最终的答案可以等于N，而且有不必要的搜索。本文作了修改，使用python语言重写。
题目要求：给定一个数组arr=[2,3,4,5],N=2345,求使用arr中的数字，组成一个不大于N的最大的数字。arr中的数字可以多次使用。
思路：
首先将arr数组排序，之后使用深搜+贪心的思想，从第一位开始，尽量使用与对应位置相等的数字。如果有任意一位没有使用相等的数字，那在后面的所有位中都直接使用最大的数字即可。
递归终止条件：
1.已经考虑完了所有的位，那么应该返回0
2.在之前选择的基础上，此位置没有满足条件的选择，应当返回-1
边界情况：
1.如果前面都是用了相等的数字，那么最后一位选用的数字必须小于对应的数字。
2.如果在找第一位时，就发现都不相等，那不要立刻返回-1，而是应该放弃第一位，将后面的位都选择最大值。
代码如下：
from typing import List
"""
arr:可使用数字的数组
nums:目标数字对应的整数数组
preEq:之前是否每一位都使用了相等的值
index:当前考虑到了第几位，从0开始
函数语义：返回第index位后可组成的最大的数字，包括第index位
"""
def dfs(arr, nums, preEq, index):
#如果考虑完了最后一位，那么能组成的最大值为0
if index==len(nums):
return 0
if preEq:#如果前面使用的都是相等的数字
for i in range(len(arr)-1,-1,-1):#从最大的往下排
if index==len(nums)-1:
if arr[i]<nums[index]:#在前面使用的都是相同的数字，那么最后一位的数字不能是相等的，这个看具体面试官的要求
temp = dfs(arr, nums, arr[i] == nums[index], index + 1)
if temp==-1:#向下深搜发现没有满足要求的值，则选用更小的数字
continue
# 向下深搜发现了满足要求的值，那说明我们找到结果了，把这一层的结果加进去，之后层层返回即可
return arr[i] * pow(10,len(nums)-index-1) + temp
else:
if arr[i]<=nums[index]:#非最后一位的数字是可以相等的
temp = dfs(arr, nums, arr[i] == nums[index], index + 1)
if temp == -1:
continue
return arr[i] * pow(10, len(nums) - index - 1) + temp
#如果上面的for循环走完都没有return的话，那就说明这一层所有的数字都不满足要求
#如果是第一个数字都无法满足的话，那就直接从第二位开始，将preEq置为False递归
if index==0:
return dfs(arr, nums, False, index + 1)
# 如果上面的for循环走完都没有return的话，而且也不是第一位，那就返回-1，回退递归
return -1
else:
#如果前面不是都选用了相等的数字，那就直接每次挑最大的数字就行了。
return arr[len(arr)-1] * pow(10, len(nums) - index - 1) + dfs(arr, nums, False, index + 1)
def find(N,arr: List[int]) -> int:
arr.sort()
nums = [int(i) for i in str(N)]
#递归的初始条件，preEq=True，index=0
return dfs(arr,nums,True,0)
arrInputList = [
[2,3,4,5],
[2,3,4,5],
[2,3,4,5],
[2,3,4,5]
]
NList = [1234,2234,2231,2134]
ansList = [555, 2233,2225,555]
for i in range(len(NList)):
ans = find(NList[i], arrInputList[i])
print(NList[i], arrInputList[i],ans)以下内容无意义，因为CSDN说文章质量低。
沈腾，1979年10月23日出生于黑龙江省齐齐哈尔市，中国内地男演员、影视导演、编剧，开心麻花舞台剧签约艺人，毕业于解放军艺术学院戏剧表演系。
2003年出演开心麻花第一部舞台剧《想吃麻花现给你拧》 [1] 。2004年参演电视剧《青春正步走》。2006年出演话剧《我在天堂等你》。2012年首次登上央视春晚，并在春晚上表演小品《今天的幸福》，凭借小品中饰演的“郝建”获得广泛关注 [2] 。2013年再次登上央视春晚，并表演小品《今天的幸福2》；同年获得第2届中国大学生微电影节最佳男主角奖 [17] ；4月25日获得第四届现代戏剧谷2013壹戏剧大赏年度新锐男演员奖 [3-4] 。2014年第三次登上央视春晚，表演小品《扶不扶》 [5] ；4月参与电视剧《你是我的眼》的拍摄，在剧中饰演男主角张三斤 [6] 。2015年第四次登上央视春晚表演小品《投其所好》。2015年参加《欢乐喜剧人》第一季，并获得冠军 [7] ；9月30日与马丽领衔主演的喜剧电影《夏洛特烦恼》上映 [312] 。文章来源：https://www.toymoban.com/news/detail-627510.html
2016年特别出演的电影《王牌逗王牌》公映 [313] 。2017年在央视春晚上表演小品《一个女婿半个儿》 [9] ；同年参演开心麻花第三部电影《羞羞的铁拳》 [10] 。2018年特别出演动作电影《龙虾刑警》 [314] ；7月27日主演的电影《西虹市首富》全国公映 [11] 。2019年大年初一主演的电影《飞驰人生》 [12] 、《疯狂的外星人》同步上映 [13] 。2020年主演爆笑喜剧《创客联盟》；8月27日名列《2020福布斯中国名人榜》第28位 [14-15] ；同年主演电影《独行月球》 [315] 。2021年大年初一主演的电影《你好，李焕英》上映 [316] ；同年主演电影《光天化日》 [317] 。文章来源地址https://www.toymoban.com/news/detail-627510.html
到了这里，关于字节面试题-小于N的最大数字的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
