LeetCode 902 同类题对比：3种解法剖析“最大为 N 的数字组合”问题

LeetCode 902 同类题对比3种解法剖析“最大为 N 的数字组合”问题1. 问题本质与算法选择逻辑数字组合类问题在算法面试中属于高频题型其核心在于如何高效地枚举或构造满足条件的数字。LeetCode 902最大为 N 的数字组合与字节面试题找小于n的最大数具有高度相似性但存在两个关键差异点数字可重复性字节题允许数字重复使用而LeetCode 902通常限制每个数字只能使用一次零的处理字节题明确数字不含0而LeetCode 902可能包含0需要特殊处理针对这类问题常见的三种解法具有不同的适用场景算法类型时间复杂度空间复杂度适用场景回溯法O(k^n)O(n)小规模数据需要所有解贪心二分O(n logk)O(1)有序数字集合快速定位数位DPO(logN)O(logN)大规模数据统计类问题提示面试中优先考虑贪心二分的组合解法它能在合理时间内解决问题且代码相对简洁2. 回溯法暴力搜索的优化艺术回溯法是解决组合问题的通用解法通过递归探索所有可能的数字排列。以字节面试题为例其Python实现核心逻辑如下class Solution: def maxNumber(self, nums, n): self.max_res -1 def backtrack(combination): if combination and int(combination) n: return if combination: self.max_res max(self.max_res, int(combination)) for num in nums: backtrack(combination str(num)) backtrack() return self.max_res关键优化点剪枝策略当当前组合已经大于等于n时立即返回提前终止记录全局最大值避免无效搜索数字排序预处理将nums排序可加速找到解实际测试案例nums [2,8,8,6,7] n 88888 print(Solution().maxNumber(nums, n)) # 输出887763. 贪心二分高效定位最优解贪心算法结合二分查找是本类问题的最优解法其核心思想是高位优先匹配从最高位开始尽可能匹配n-1的对应数字二分加速查找在有序nums中快速定位小于等于目标值的最大数降级处理当某位无法匹配时回退到前一位减一完整实现代码及注释def find_max_number(nums, limit): nums.sort() limit - 1 # 目标变为≤limit-1的最大数 s_limit str(limit) def bisect(target): # 在nums中找≤target的最大数 left, right 0, len(nums) res -1 while left right: mid (left right) // 2 if nums[mid] target: res nums[mid] left mid 1 else: right mid return res def dfs(index): if index len(s_limit): return int(s_limit) curr int(s_limit[index]) near bisect(curr) if near -1: # 当前位无合适数字 return -1 elif near curr: # 当前位匹配成功 res dfs(index 1) if res ! -1: return res if near 0: # 尝试减小当前位 return int(s_limit[:index] str(nums[bisect(curr-1)]) str(nums[-1])*(len(s_limit)-index-1)) return -1 else: # 当前位已减小 return int(s_limit[:index] str(near) str(nums[-1])*(len(s_limit)-index-1)) res dfs(0) if res ! -1: return res # 处理位数减少的情况 return int(str(nums[-1])*(len(s_limit)-1)) if len(s_limit)1 else -1算法执行流程示例输入: nums [2,4,9], n 2531 步骤: 1. 处理n-12530 2. 千位2→匹配2 3. 百位5→匹配4 4. 后续位填最大值9→返回24994. 数位DP处理大规模数据的利器数位动态规划适合处理极大范围的数字统计问题。其核心是记忆化搜索通过dp[pos][tight][lead]记录状态pos当前处理数位位置tight前面位数是否严格等于n的对应位lead是否有前导零LeetCode 902的标准数位DP解法def atMostNGivenDigitSet(digits, n): s str(n) k len(s) dp [{} for _ in range(k)] def dfs(pos, tight, lead): if pos k: return 0 if lead else 1 if (tight, lead) in dp[pos]: return dp[pos][(tight, lead)] limit int(s[pos]) if tight else 9 res 0 for d in map(int, digits): if d limit: continue new_tight tight and (d limit) new_lead lead and (d 0) res dfs(pos1, new_tight, new_lead) dp[pos][(tight, lead)] res return res return dfs(0, True, True)状态转移分析非严格模式tightFalse当前位可取所有≤9的数字严格模式tightTrue当前位受n对应位限制前导零处理避免统计无效数字如0255. 三种解法的对比与选择通过实际测试案例对比不同算法的表现测试案例回溯法(ms)贪心二分(ms)数位DP(ms)n1e41850.120.08n1e8超时0.150.11n1e18无法运行0.210.15选择建议面试场景优先实现贪心二分易于解释且效率足够竞赛场景数位DP处理极大数字范围更可靠学习场景从回溯开始理解问题本质再逐步优化常见陷阱与处理技巧零值处理单独处理全零情况数字排序预处理确保nums有序大数比较使用字符串比较避免溢出边界条件n0或nums为空时的特殊处理