1. 項目概述遞歸算法實戰(zhàn)與錯題復(fù)盤百煉OJ平臺上的2787號題目算24是遞歸算法的經(jīng)典練習(xí)題也是許多算法學(xué)習(xí)者的絆腳石。這道題要求通過四則運算將4個給定數(shù)字組合出24點看似簡單卻暗藏遞歸思維的精妙之處。作為系列錯題本的第三卷我將結(jié)合自己三次提交失敗的經(jīng)歷拆解遞歸解法中的思維陷阱與實現(xiàn)細(xì)節(jié)。這道題的核心價值在于訓(xùn)練分治回溯的算法思維——如何將復(fù)雜問題拆解為相同結(jié)構(gòu)的子問題以及如何處理運算符優(yōu)先級帶來的計算順序問題。在互聯(lián)網(wǎng)大廠的技術(shù)面試中類似題目經(jīng)常作為考察候選人基礎(chǔ)算法能力的試金石這也是近期算法崗位薪資普調(diào)背景下值得重點掌握的技能。2. 問題分析與遞歸建模2.1 題目要求解析給定四個1-13范圍內(nèi)的整數(shù)通過加/減/乘/除和括號組合最終結(jié)果等于24。每個數(shù)字必須且只能使用一次除法運算為實數(shù)除法而非整數(shù)除法。例如輸入[1,5,5,5]合法解為5*(5-1/5)24。2.2 遞歸樹構(gòu)建思路核心遞歸模型是每次從剩余數(shù)字中選取兩個數(shù)用四種運算符組合成一個新數(shù)將新數(shù)與剩余數(shù)字組成更小的集合遞歸處理。遞歸終止條件是數(shù)字集合只剩1個數(shù)且等于24成功數(shù)字集合只剩1個數(shù)但不等于24失敗無可選數(shù)字對失敗需要注意的邊界條件除法運算時除數(shù)不能為0浮點數(shù)比較需考慮精度誤差如abs(result-24)1e-6運算符優(yōu)先級通過括號隱式處理3. 實現(xiàn)細(xì)節(jié)與優(yōu)化策略3.1 基礎(chǔ)遞歸框架def solve(nums): if len(nums) 1: return abs(nums[0] - 24) 1e-6 for i in range(len(nums)): for j in range(len(nums)): if i j: continue # 生成新數(shù)字集合 new_nums [nums[k] for k in range(len(nums)) if k ! i and k ! j] # 嘗試四種運算 for op in [,-,*,/]: if op / and nums[j] 0: continue res calculate(nums[i], nums[j], op) if solve(new_nums [res]): return True return False3.2 關(guān)鍵優(yōu)化技巧去重優(yōu)化通過限制ij避免(ab)與(ba)的重復(fù)計算剪枝策略當(dāng)中間結(jié)果超過24*4時提前終止最大可能值約束運算順序優(yōu)化乘除優(yōu)先于加減計算減少遞歸深度記憶化存儲對已計算過的數(shù)字組合緩存結(jié)果重要提示浮點精度問題必須使用epsilon比較直接判斷會導(dǎo)致大量誤判4. 典型錯解分析與修正4.1 第一次提交失敗忽略運算順序# 錯誤示范未考慮括號優(yōu)先級 def calculate(a, b, op): if op : return a b elif op -: return a - b # 此處會導(dǎo)致計算順序錯誤 elif op *: return a * b else: return a / b修正方案在遞歸過程中保持運算的原子性每次只處理一個運算符4.2 第二次提交失敗浮點精度處理不當(dāng)# 錯誤示范直接比較浮點數(shù) if nums[0] 24: # 錯誤應(yīng)該用epsilon比較 return True修正方案使用相對誤差閾值epsilon 1e-6 if abs(nums[0] - 24) epsilon: return True4.3 第三次提交失敗除數(shù)零檢查遺漏# 錯誤示范未處理除零異常 res a / b # 當(dāng)b0時拋出異常修正方案添加顯式檢查if op /: if abs(b) epsilon: continue res a / b5. 完整AC代碼與測試用例5.1 優(yōu)化后的Python實現(xiàn)def judgePoint24(nums): def dfs(arr): if len(arr) 1: return abs(arr[0] - 24) 1e-6 for i in range(len(arr)): for j in range(len(arr)): if i j: continue new_arr [arr[k] for k in range(len(arr)) if k ! i and k ! j] for op in [,-,*,/]: if (op or op *) and i j: continue # 去重 if op / and abs(arr[j]) 1e-6: continue if op : res arr[i] arr[j] elif op -: res arr[i] - arr[j] elif op *: res arr[i] * arr[j] else: res arr[i] / arr[j] if dfs(new_arr [res]): return True return False return dfs(nums)5.2 典型測試案例集測試輸入預(yù)期結(jié)果關(guān)鍵考察點[4,1,8,7]True基本組合能力[1,1,1,1]False無解情況處理[3,3,8,8]True分?jǐn)?shù)運算精度[0,0,0,0]False邊界值處理[1,5,5,5]True運算順序控制6. 遞歸算法的工程實踐思考在實際開發(fā)中遞歸算法雖然代碼簡潔但需要注意兩個關(guān)鍵問題棧溢出風(fēng)險Python默認(rèn)遞歸深度約1000層對于更大規(guī)模問題需要改寫成迭代或尾遞歸形式性能優(yōu)化通過lru_cache裝飾器實現(xiàn)記憶化可以顯著減少重復(fù)計算對于面試場景建議在寫出遞歸解法后主動討論如何改為迭代實現(xiàn)時間/空間復(fù)雜度分析可能的優(yōu)化方向我在實際刷題中發(fā)現(xiàn)這類題目往往有解題模式可循。例如24點問題的通用解決框架可以抽象為選擇兩個操作數(shù)應(yīng)用運算符生成新操作數(shù)縮減問題規(guī)模遞歸解決子問題回溯嘗試其他可能性掌握這種思維模式后類似的問題如算21點、目標(biāo)值組合等都可以迎刃而解。這也是為什么大廠面試官特別青睞此類題目——它能同時考察候選人的算法思維、編碼能力和問題分析能力。