- 正确答案：该问题本质是构造一个由给定数字集合（允许重复使用）组成的、位数不超过n的位数、且严格小于n的最大整数。需分两阶段处理：先尝试构造与n等长的数字（贪心逐位匹配+回溯），若不可行则取集合中小于n最高位的最大数字，后续所有位填集合中最大数字；若连一位都构不成（如集合中无小于n最高位的数字），则退化为位数少一位，此时每位均取集合中最大数字（前提是集合非空且不全为0）。最终结果需排除前导零（除非结果为0本身且0在集合中）。 - 解答思路： 1. 将n转为字符串s，长度为len_s；数字集合转为有序去重列表digits（升序），便于二分查找和取最大。 2. 特殊情况处理：若digits为空，返回None；若digits仅含0，且n>0，则唯一合法数字是0（当n>1时01，则该数实际位数不足len_s，属于“降位”情形，应统一归入b)分支处理。因此，等长构造时首位必须从非零digits中选（除非digits中只有0）。 - 边界case深度覆盖： * n=1，digits=[0] → 0<1，返回0； * n=10，digits=[9] → 9<10，返回9（1位）； * n=99，digits=[9] → 等长99不合法（不严格小于），降位取9 → "9"； * n=100，digits=[0,9] → 首位可选0或9；选9则第二位需≤0，但digits中无≤0的非负数（0存在），故90？但90<100，且90是首位9、次位0、末位可填9→909？错：n=100是3位，所以构造3位数。首位选9<1，立刻成功，后两位填max_d=9 → "999"？但999>100，错误！关键点：当n=100（字符串"100"），首位s[0]='1'，digits中≤'1'的有'0','1'；若选'1'，则继续；若选'0'，则前缀"0"，剩余2位填max_d=9 → "099"，整数值99<100，合法。但"099"不是3位数，其数值是99。而"99"是2位数，也合法。但题目要求“最大数字”，99 vs 99？一样。然而，若选首位'0'得"099"=99；若降位取2位最大数"99"=99；相同。但若digits=[0,5,9]，n=100，则首位选0→"099"=99；选1不可行（因digits无1）；故直接降位，取"99"。可见，等长构造中选小于s[0]的digit时，其后全填max_d，得到的数一定小于n（因首位已小），且是该首位下的最大可能。 * 因此，算法核心是：对i从0到len_s-1，尝试在digits中找最大的d满足d < s[i]（若存在），则res = s[0:i] + d + (max_d)*(len_s-1-i)，返回；若不存在，则检查d == s[i]是否在digits中，若不在则必须回溯；若在，则继续。回溯时，从i-1位开始，找小于s[i-1]的次大d，然后填充。若i=0时就无d < s[0]，则只能降位。数据结构选择：digits用sorted list，配合bisect模块；max_d = digits[-1]（若digits非空）。 - 伪代码： def largest_number_less_than_n(n, digits): if not digits: return None s = str(n) len_s = len(s) digits_sorted = sorted(set(int(d) for d in digits)) # 去重排序，元素为int digits_str = [str(d) for d in digits_sorted] max_d_str = digits_str[-1] # 特殊：若n为个位数，且digits中有小于n的数，直接取最大那个 if len_s == 1: candidates = [d for d in digits_str if int(d) < n] return int(max(candidates)) if candidates else None # 尝试构造等长 res_chars = [] # 预处理：digits_str中每个字符对应int值，用于比较 # 对每一位i for i in range(len_s): # 在digits_str中找小于s[i]的最大字符 # 用线性扫描（因k小）或二分：找右边界插入位置，取前一个 pos = -1 for j in range(len(digits_str)-1, -1, -1): if digits_str[j] < s[i]: pos = j break if pos != -1: # 找到d < s[i]，则前缀+该d+后面全max_d_str candidate = ''.join(res_chars) + digits_str[pos] + max_d_str * (len_s - i - 1) # 转int去前导零，但candidate作为字符串可能有前导零，但int()会处理 return int(candidate) # 否则，检查s[i]是否在digits_str中 if s[i] not in digits_str: # 当前位无法匹配，需要回溯 break res_chars.append(s[i]) else: # 全部匹配，得到等于n的数，不合法，需回溯 pass # 回溯：从最后一位往前找可减小的位置 for i in range(len_s-1, -1, -1): # 在res_chars[i]处找小于它的最大digit curr_char = res_chars[i] pos = -1 for j in range(len(digits_str)-1, -1, -1): if digits_str[j] < curr_char: pos = j break if pos != -1: # 构造：res_chars[0:i] + digits_str[pos] + max_d_str*(len_s-i-1) prefix = ''.join(res_chars[:i]) candidate = prefix + digits_str[pos] + max_d_str * (len_s - i - 1) return int(candidate) # 回溯失败：无法构造等长，降位 if len_s == 1: return None # 取len_s-1位，每位都是max_d_str if max_d_str == '0': # 全0，即0 return 0 candidate_short = max_d_str * (len_s - 1) return int(candidate_short) 注意：上述伪代码未处理前导零导致位数不足的问题。更健壮的做法是，在构造等长时，若首位选'0'，则实际数位减少，但数值仍有效（如"099"=99），而int("099")=99，正确。因此，直接拼接后转int是安全的。 - 扩展知识：该问题可视为“受限数字系统下的前驱查找”，与数位DP（Digit DP）密切相关。标准数位DP用于统计[a,b]内满足条件的数字个数，而本题是构造最大前驱。可扩展为：求小于n的第k大数字、或支持动态添加删除digits、或digits带权重（如使用次数限制）。底层还可联系到Trie树：将所有可能数字（不超过n位）插入Trie，然后DFS找最右路径小于n，但空间爆炸，故贪心更优。另外，若digits包含负数？题目隐含非负（数字集合通常指0-9子集），但若扩展，需重新定义“数字”和比较逻辑。工程实践中，该算法用于验证码生成、密码字典裁剪、数据库索引优化（如范围查询的边界估算）等场景。

字节AI应用开发一面

全站热榜

创作者周榜