- 正确答案：该题实际考察的是“构造不大于n的最大整数，且满足某些隐含约束条件（如：各位数字严格递增/不重复/无连续重复/仅由给定数字集合组成/不含某子串等）”，但题干中“不大于n的最大整数”本身是平凡的（答案就是n），因此“字节经典第一次见”这一提示强烈暗示——这是一道**带约束的贪心构造题**，典型变体为：给定一个正整数n（以字符串或整数形式给出），以及一个允许使用的数字集合digits（如["1","3","5","7"]），要求返回由digits中的数字组成的、不超过n的最大整数（可重复使用数字，允许前导零？通常不允许；结果必须是有效整数，即不能全为0且长度>1）。或更经典的字节跳动真题变体： “给定n（字符串），求不大于n的、各位数字互不相同的最大整数”（即：no repeated digits, maximize value ≤ n）。本题标准解法是：贪心尝试高位填最大可能数字 + 回溯处理不可行路径。以最常考版本为例——【构造不大于n的、各位数字互不相同的最大整数】：输入：n = "231" → 输出："231"（本身无重复，合法）输入：n = "222" → 输出："219"（222有重复，贪心填'2'后第二位不能填'2'，尝试'1'，第三位填最大可用数字'9'）输入：n = "100" → 输出："98"（首位填'1'后，剩余位无法构造两位不重复数 ≤ "00" → 回溯，首位降为'0'不合法，故退到一位数，选最大不重复一位数'9'，但需注意：若n=100，结果应为98而非9，因98<100且比9大；严格说，所有位数少一位的候选中取最大，即98、97…→最大是98） - 解答思路： 1. 将n转为字符数组s，长度为len。 2. 使用DFS回溯 + 贪心剪枝：从高位i=0开始，尝试填入尽可能大的数字d（从9到0），满足： - d未被使用（visited[d]=false） - 若此前所有高位已严格匹配n的前缀（tight=true），则d ≤ s[i]；否则d可取0~9任意未用数字 - 若d < s[i] 且 tight=true，则后续位不再受约束（tight=false），可直接贪心填剩余最大可用数字（无需继续DFS） 3. 关键优化：一旦在某位找到一个可行d，优先尝试最大的d；若该分支成功返回非空结果，则直接返回（贪心保证最优）；若失败（如填d后后续无法构造），则尝试次小d。 4. 边界：当i == len，说明构造出len位合法数，返回当前路径；若i < len但无数字可填，返回空（触发回溯）。 5. 特殊处理位数更少的情况：若len位无法构造，则枚举所有len-1位不重复数的最大值（即从9876543210中取前len-1位降序排列，如len=3则max 2-digit = 98）。 - 深度知识讲解：本题本质是**带约束的数位DP（Digit DP）的构造版本**，但不用统计个数，而是构造最大值。核心知识点包括：（1）数位DP状态设计：通常为dfs(pos, tight, started, mask)，其中： - pos：当前处理到第几位（0-indexed） - tight：是否仍受n的前缀约束（即之前每位都等于n对应位） - started：是否已开始填非零数字（用于处理前导零，本题因要最大整数，前导零必然不优，可忽略或强制started=true） - mask：状态压缩记录已用数字（10位bit，mask & (1< str: if not n: return "" s = list(n) L = len(s) # 预计算所有更短位数的最大值：k位最大不重复数 = 从9开始降序取k个不同数字 def max_k_digit(k): if k == 0: return "" if k > 10: return None # 最多10个不同数字 digits = [str(i) for i in range(9,-1,-1)] return "".join(digits[:k]) # DFS：返回以pos开始、在tight约束下、已用mask数字时，能构造的最大字符串；None表示失败 from functools import lru_cache @lru_cache(None) def dfs(pos, tight, mask): if pos == L: return "" # 成功构造L位 res = None # 枚举当前位可填数字d（0~9），但若pos==0且d==0则跳过（避免前导零，除非L==1） start_d = 0 if pos == 0 and L > 1: start_d = 1 # 贪心：从大到小尝试d for d in range(9, start_d-1, -1): if mask & (1 << d): continue # d已用 digit_char = str(d) if tight and d > int(s[pos]): continue # 超过上限 new_tight = tight and (d == int(s[pos])) new_mask = mask | (1 << d) # 若new_tight为False，后续位可贪心填最大可用数字，无需DFS if not new_tight: # 剩余位数rem = L - pos - 1 rem = L - pos - 1 # 从9到0找rem个未用数字，降序排列 available = [] for cand in range(9,-1,-1): if not (new_mask & (1<

tiktok shop二面

全站热榜

创作者周榜