题目：给定数组nums, 只从1~9之间取数的数组，给定一个n =2599 （可变），求从nums中组合(可重复选取)出小于n的最大数。
最优解法(网上说最优)：贪心 + 二分，终于被我啃下来了。
记录一下，有帮助点个赞。
搭配食用视频：字节算法面试题：拼出小于limit的最大数（递归）_哔哩哔哩_bilibili
视频是C++版本，且用offset直接提取int的每位数。
这里是python版本，并将limit转成字符串利用index下标索引提取。总体而言肯定是上述方法是更优的，但是转成字符串处理方便些，面试应该也十分足够了。最后面再赋一个暴力解法(回溯暴力法)。【如果发现代码任何问题 十分欢迎评论区交流】
回溯暴力方法：
# 给定一个整数n，给一个数组nums，找到nums中排列组合数比n大的数中最小的数 nums中的数可以被使用多次
# 这里nums中不可以有0
# 比如 n = 22, nums = [1, 2] 答案 111
class my_num():
def __init__(self):
self.maxres = float('-inf')
self.res = 0
def dfs(self, nums, n):
# 不需要排序
if self.res < n:
self.maxres = max(self.maxres, self.res)
if self.res >= n:
# 小于n的最大数 不是遇到小于后就回溯 而是要遇到大于时回溯
return
# 单层递归
for i in range(len(nums)):
self.res = self.res * 10 + nums[i]
self.dfs(nums, n)
self.res = self.res // 10
def fin_min_maxNum(self, nums, n):
self.dfs(nums, n)
return self.maxres
a = my_num()
nums=[2,8,8,6,7]
n = 88888
print(a.fin_min_maxNum(nums, n))贪心＋二分：
# 贪心思想 要求小于n中的最大数 则自然想让与n的高位尽可能匹配
# 因此思路是
# 从最高位开始
# 1. 从nums中选数进行追平 n-1
# 2. 若追平不成功，则从nums中选小一个的进行减小，若减小成功->后面位全用最大值拼
# 3. 若当前位减小不成功(即nums中找不到比它小的数)，则让当前位变成前一位，让前一位减小(成功则后面全用最大，不成功则继续往前寻找能减小的当前位)
def nearCur(nums,cur):
# 二分法从nums中找小于等于cur的最大数的【下标】,若找不到(即全部数都大于cur)则返回-1 ---这里用二分法的左闭右开区间 这时是要一直找 而不是找到就返回。
left, right = 0, len(nums)
result = -1 # 只要找到小于cur的数就覆盖掉 一直检索 这样就可以找到小于cur的最大数 若找不到就覆盖不了 所以最终返回result即可
while left < right:
middle = left + (right - left) // 2 # 用这种写法可以防止溢出
if nums[middle] <=cur:
# 则nums[middle]有可能是小于等于cur的最大数 或者最大数有可能在右区间 因此更新右区间 一直检索
result = middle
left = middle + 1
else:
# 这是nums[middle] > cur -> 则小于cur的在左边
right = middle
return result
def process2(nums, limit, index):
# 拼出来的数字要与limit一样长且尽量大 用前面提到的高位贪心。 若与其等长的拼不出来，则返回-1
# 递归函数
# 终止条件 -- 即没有数字要处理了 也就是每个数字都可以齐平
if index == len(limit):
return limit
# 单层递归逻辑 处理当前位 提取当前位
cur = int(limit[index])
# 在nums中对当前位进行试图追平 例如cur为6 1)刚好追平6 2)4 3)没有合适数字 -1 要对三种不同情况做不同过的处理 [这里near返回的是下标]
near = nearCur(nums, cur)
if near == -1:
# 即找不到合适的下标 返回了-1
# 如果当前位追不平 则要返回上一层告知
return -1
elif nums[near] == cur:
# 说明当前位追平了！那么继续追平下一位
ans = process2(nums, limit, index + 1) # 这里index+1其实就暗含了回溯 但是这里不写详细了。
# 这里就是用来接收下一层的结果的 如果为-1就说明下一层追不平了
if ans != -1:
return int(ans)
else:
# 这时候说明后一个没有追平 则当前位要缩小 若能缩小则缩小 若不能缩小 则找前一位缩小
if near > 0:
# near大于0 说明能缩小 则进行缩小 缩小后后面的直接用最大值补齐
near -= 1
# 说明当前位在nums中还可以缩小 这时直接缩小 后面全取最大返回即可
# 这里注意当前位是index，到这里了说明index之前的都追平了。
return limit[:index] + str(nums[near]) + str(nums[-1]) * (len(limit) - index - 1)
else:
# 这时说明当前位不能缩小 则要找前一位缩小
return -1
else:
# 这种情况是从nums中只拿到比当前位小的数 这时候直接将后面的拼成最大就可以返回结果
return limit[:index] + str(nums[near]) + str(nums[-1]) * (len(limit) - index -1)
def findTargetnum(nums, limit):
limit -= 1 # 这里将limit = limit -1 则最终目标只需要是追平limit即可。
# 将limit转成字符串 方便提取每个字符
limit = str(limit)
# process2是用来寻找与limit追平的同位数的数。ans指若能追平则返回值的字符串形式 若不能追平则返回-1告知，这时就退位最大值填充
ans = process2(nums, limit, 0)
if ans != -1:
return int(ans)
else:
# 此时ans==-1 则说明找不到与limit位数一样长的，此时就缩小一位 全取最大值
rest, m = '', len(limit)-1
while m:
rest += str(nums[-1])
m -= 1
# 这一句话是指如果都找不到比这几个数小的 则返回-1
return int(rest) if rest else -1
if __name__ == '__main__':
nums = [5,8,9]
limit = 78
nums.sort()
res = findTargetnum(nums, limit)
print(res)
