- 正确答案：这是一个典型的贪心 + DFS（或动态规划）结合的构造性问题。核心策略是：从高位到低位逐位确定数字，每一步在满足“整体结果仍小于 n”的前提下，尽可能选择 A 中最大的可用数字；若某一位无法填入任何 A 中元素（即填入后已超过 n 的对应前缀），则需回溯，尝试更小的数字；若所有选择都导致后续无法构造合法数，则退位减一并重新填充低位。最优解法通常采用 DFS 回溯（带剪枝）或 BFS 枚举（适用于位数较少场景），但更高效、可扩展的解法是“贪心构造 + 降位补最大”策略，时间复杂度 O(len(n) × |A|)，空间 O(len(n))。 - 解答思路：设 n 的字符串表示为 s，长度为 L。目标是构造一个长度 ≤ L 的数字（允许前导零？注意：题目未限定是否允许前导零，但“小于 n 的最大数”隐含不允许前导零——除非 n=10, A={0}，此时 0 是合法答案；因此需明确处理长度 < L 的情况）。分两阶段考虑：（1）先尝试构造长度 = L 的数，且字典序 ≤ s（数值 < n）；（2）若无法构造长度为 L 的合法数，则取长度 = L−1 的最大可能数（即用 A 中最大数字重复 L−1 次，前提是 A 中存在非零数字；若 A 只含 0，则仅当 n > 0 时答案为 0，否则无解——但题设保证有解）。对于阶段（1），采用贪心+回溯：从左到右枚举每一位 i（0-indexed），维护当前已选前缀 pre（字符串或整数），以及一个标志 tight（表示前缀是否严格等于 s[0:i]，即后续位是否受 s[i:] 约束）。对第 i 位，在 A 中从大到小遍历候选数字 d： • 若 tight 为真：d 必须 ≤ s[i]；若 d < s[i]，则后续不再 tight，可自由填最大数字；若 d == s[i]，则继续 tight； • 若 tight 为假：d 可任选，直接选 A 中最大值即可。一旦找到一个完整 L 位构造方案（且不以 '0' 开头），即为最优解；否则进入阶段（2）。关键细节： - 需预处理 A 并去重、排序（降序），便于贪心选取； - 需特判：若 A 中无非零元素（即 max(A)==0），则唯一可能结果是 "0"（当 n > 0）； - 若 n 是个位数（如 n=5），则答案是 A 中 <5 的最大元素，若不存在则为 ""？但题目要求“组成的数”，应返回 -1 或 0？按常规理解，返回 A 中小于 n 的最大元素，若无则返回 None —— 但题干说“求...最大数”，默认保证有解，故 A 中必存在 d2 均满足 tight 条件，则选 d1 后，剩余位可填的最大值 ≥ 选 d2 后的最大值（因高位越大，整体越大，且低位空间相同），故贪心从大到小试选是安全的。（3）回溯必要性：贪心并非总成功。例：n=210，A={2,1,0}。第一位选 2（tight=True），第二位若贪心选 1 → 前缀 "21"，第三位最大可选 0 → "210" 不小于 n（等于），非法；此时需第二位改选 0 → "20?"，第三位可选 1 → "201" < 210，合法。故需回溯机制。（4）优化方向：可改用记忆化DFS（状态：pos, tight, started），其中 started 表示是否已开始填非零数字（用于控制前导零），时间复杂度 O(L × 2 × 2 × |A|) = O(L×|A|)。但校园面试中手写 DFS 回溯更直观。 - 伪代码（Python风格，带详细注释）： def largestNumberLessThanN(n, A): if not A: return None s = str(n) L = len(s) A_sorted = sorted(set(A), reverse=True) # 去重降序 max_digit = max(A) min_digit = min(A) # 特殊：若 A 中无正数，只能组成 0（当 n > 0） if max_digit == 0: return 0 if n > 0 else None # 尝试构造 L 位数（无前导零） res = [] def dfs(pos, tight, started): # pos: 当前要填的位置（0 ~ L） # tight: 前缀是否与 s[:pos] 完全相等 # started: 是否已选非零数字（控制前导零） if pos == L: return True # 成功填满 # 确定当前位可选数字范围 candidates = [] if not started: # 首位：不能选0（除非 A 只有0，但已处理） candidates = [d for d in A_sorted if d != 0] else: candidates = A_sorted for d in candidates: digit_char = str(d) if tight: if digit_char > s[pos]: continue # 超过上限，跳过 elif digit_char == s[pos]: # 继续 tight，且若 d!=0 则 started=True（其实started已为True，或此处首次赋值） new_started = started or (d != 0) res.append(d) if dfs(pos+1, True, new_started): return True res.pop() else: # digit_char < s[pos] # 此后不再 tight，剩余位可填最大数字 res.append(d) # 填充剩余 L-pos-1 位：每位选 A 中最大数字（注意：若未started且d==0，但此处d!=0因首位已处理，后续started恒True） for _ in range(L - pos - 1): res.append(max_digit) return True else: # 不受约束：直接选最大数字 res.append(max_digit) for _ in range(L - pos - 1): res.append(max_digit) return True return False # 先尝试 L 位 if dfs(0, True, False): return int(''.join(map(str, res))) # 失败：构造 L-1 位最大数 if L == 1: # n 是个位数，找 A 中 0 for a in A): return 0 # 全零，只能是0 # 构造 L-1 位最大数：首位选 A 中最大非零，其余选 A 中最大 first_digit = max(a for a in A if a > 0) rest_digit = max_digit return int(str(first_digit) + str(rest_digit) * (L-1)) # 注意：上述 dfs 实现为简化版，实际需修正 started 逻辑和回溯细节。更鲁棒实现如下（推荐面试手写版本）： def solve(n, A): s = str(n) L = len(s) A = sorted(set(A)) # 预计算最大数字（用于填充） max_a = max(A) # Case 1: 尝试构造长度为 L 的数 # 使用回溯，从高位到低位 path = [] def backtrack(i, tight): if i == L: return True # 当前位可选范围 low = 0 high = int(s[i]) if tight else 9 # 从大到小试，贪心 for d in reversed(A): # A 已升序，reversed 即降序 if d < low or d > high: continue # 首位不能为0 if i == 0 and d == 0: continue path.append(d) new_tight = tight and (d == int(s[i])) if backtrack(i+1, new_tight): return True path.pop() return False if backtrack(0, True): return int(''.join(map(str, path))) # Case 2: 构造长度为 L-1 的最大数 if L == 1: # n 是个位，找 A 中 0] if not non_zero: return 0 first = max(non_zero) rest = [max_a] * (L-1) return int(str(first) + ''.join(map(str, rest))) # 示例调用： # solve(210, [0,1,2]) → 202? 错，应为 201（因 202>210? 不，202<210，但 210 中 A 有2,1,0，202 合法且大于 201；但 202 是否由 A 组成？是。那为何不是 202？因为 202 < 210，且比 201 大。所以算法需修正：在非 tight 分支，应填最大可能，而非固定 max_a —— 因为 max_a 可能是 2，但 202 是合法的。所以上述 backtracking 在 tight 失败后，应尝试非 tight 的最大构造：即当某位确定 d < s[i] 后，剩余位应填 A 中最大数字（不是全局 max_a，而是每个位置独立选 A 中最大，允许重复）。故在 backtrack 中，当 d < int(s[i]) 时，后续位无需递归，直接填充 max_a 即可。 # 修正 backtrack 中的剪枝： # 在 tight 为 True 且 d < int(s[i]) 时，立即填充剩余位并返回 True。 # 最终推荐面试手写代码（简洁鲁棒）： def largestNumberLessThanN(n, A): if not A: return None s = str(n) L = len(s) A = sorted(set(A)) max_digit = max(A) # Step 1: Try to build L-digit number res = [] def dfs(i, tight): if i == L: return True upper = int(s[i]) if tight else 9 # Try digits from large to small for d in reversed(A): if d > upper: continue if i == 0 and d == 0: continue # no leading zero if tight and d == upper: res.append(d) if dfs(i+1, True): return True res.pop() elif d < upper: # now free to fill max_digit for rest res.append(d) res.extend([max_digit] * (L - i - 1)) return True return False if dfs(0, True): return int(''.join(map(str, res))) # Step 2: Build (L-1)-digit max number if L == 1: return max([a for a in A if a < n] or [-1]) # Find largest non-zero for first digit first_choices = [a for a in A if a > 0] if not first_choices: return 0 first = max(first_choices) return int(str(first) + str(max_digit) * (L-1))

字节大模型算法二面 好难

全站热榜

创作者周榜

字节大模型算法二面好难