每天一到早上我打開力扣第一件事就是看今天的“每日力扣4”計劃完成了沒。這個系列我從半年前開始做規(guī)則非常簡單粗暴每天雷打不動刷4道力扣題一道熱題100里沒做過的一道高頻經(jīng)典但容易忘的一道按專題選的專項訓練最后再補一道之前錯過的題。堅持下來之后最明顯的變化不是AC數(shù)漲了多少而是面對陌生題目的時候腦子里不再是一片空白而是能快速定位到“這題我見過類似的考的是哈希表”或者“這題典型的動態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移應該是這樣”。今天這篇文章我就把“每日力扣4”這套打法的完整邏輯、今天選中的4道題含面試出現(xiàn)過三次的買股票最佳時機、蠻有意思的1875將雇員相同的分組以及熱題100里的兩數(shù)之和和反轉(zhuǎn)鏈表怎么一步步啃下來的過程連同我踩過的坑和排查思路一次講清楚。適合準備算法面試的人、刷力扣熱題100但老是三天打魚兩天曬網(wǎng)的人、還有想用Python刷題但不知道從哪下手的同學。1. 這個系列背后的設計思路為什么偏偏是每天4道一開始我也走過“一天刷10道、周末刷50道”的彎路結果就是周一信心滿滿周三開始做不動周末直接擺爛下周從頭再來反復循環(huán)了快一個月進度還是只有那么十幾道題。后來我認真想了一下問題不在于懶也不在于題難而是在于節(jié)奏不對。1.1 四道題的分配其實是按記憶曲線和面試需求來的每天4道不是隨機抓4道題而是分成四個角色。第一道是“新題”我從力扣熱題100和每日一題里挑一道沒做過的。這道題的作用是保證每天都能接觸新知識點維持那種“接著學”的狀態(tài)。第二道是“舊題復刷”專門挑一道前段時間做過但當時覺得模糊的題隔幾天重新做一遍。這個安排很關鍵刷題最怕的就是“刷過就忘”復刷就是對抗遺忘曲線最直接的辦法。我試過一周前AC過的一道中等難度題隔一周再寫居然卡了20分鐘才想起來核心思路從那以后復刷就變成了固定項。第三道是“專題專項”比如這周我定的專題是哈希表那第三道題就一定會和哈希表相關。專題輪換一般是兩周一個數(shù)組、雙指針、二分、鏈表、二叉樹、動態(tài)規(guī)劃、貪心、圖論一個一個輪過去。第四道是“錯題重刷”翻出過去一周里做錯或者看了題解才寫出來的題重做一遍。這一道才真正決定刷題有沒有效果因為它逼著你直面自己的薄弱點而不是一直做那些順手的題自我感動。1.2 這道題選什么標準題目池怎么搭建很多人刷力扣的第一步就是打開題庫從1開始按順序刷這個操作我極其不建議。按序號刷的結果通常是一道簡單題磨40分鐘做了30道就被勸退。我的題目池只有三個來源。第一個是力扣熱題100這是最核心的池子里面每一道都是高頻中的高頻覆蓋了絕大多數(shù)面試題型。第二個是力扣題庫里按“頻率”排序后前方的中等題。第三個是自己收藏夾里積累的錯題和經(jīng)典題。這樣一來“每日力扣4”就變成了一套有輸入、有消化、有復盤的小系統(tǒng)而不是單純地消耗題目數(shù)量。2. 今日4道題全解析從讀題到AC的真實過程下面我直接進入今天的4道題這4道題分別代表了我前面說的四個角色。我會把每一道題從讀題、思路分析到落地的完整過程拆開來講包括代碼和復雜度。2.1 力扣121 買股票的最佳時機貪心和動態(tài)規(guī)劃到底怎么選先說高頻中的高頻題力扣121買股票的最佳時機。題目描述很簡單給定一個數(shù)組pricesprices[i]表示第i天的股票價格你只能選擇某一天買入并在之后的某一天賣出求能獲得的最大利潤。我第一次做這道題的時候第一反應是兩層循環(huán)枚舉每一天買入、每一天賣出算最大差值。這個解法寫起來三分鐘但一提交就超時了因為prices數(shù)組最長有10萬的長度O(n2)級別在極限數(shù)據(jù)下要跑上億次運算。這道題的經(jīng)典解法是貪心思想核心用一個變量記錄歷史最低價同時不斷計算“今天賣出能賺多少”取最大值。用生活化的話說我每天只需要記住過去最便宜的價格是多少然后每天收盤時看看當天賣出能賺多少錢把賺最多的那天記下來就行。def maxProfit(prices): if not prices: return 0 min_price prices[0] max_profit 0 for price in prices[1:]: if price min_price: min_price price else: max_profit max(max_profit, price - min_price) return max_profit時間復雜度O(n)一次遍歷搞定空間復雜度O(1)。這道題還有一種寫法是動態(tài)規(guī)劃。定義dp[i]表示到第i天為止能獲得的最大利潤狀態(tài)轉(zhuǎn)移就是dp[i] max(dp[i-1], prices[i] - min_price)。你會發(fā)現(xiàn)貪心解法其實就是動態(tài)規(guī)劃把空間壓縮掉之后的樣子因為dp[i]只依賴于dp[i-1]所以只需要一個變量就夠了。面試的時候這道題最常被追問的變種有兩個。一是允許多次買賣力扣122這時候貪心的思路變成“只要明天比今天貴就賺差價”二是只允許完成兩筆交易力扣123這就真的要用動態(tài)規(guī)劃還得維護四個狀態(tài)變量。我建議把這三道題放在一起刷因為它們層層遞進是理解貪心和動態(tài)規(guī)劃區(qū)別的絕佳素材。2.2 力扣1875 將雇員相同的分組哈希表分組題的實戰(zhàn)價值接下來是今天最有意思的一道力扣1875 將雇員相同的分組。題目的要求是把員工按照工資進行分組工資相同的人分到同一組最后按照工資升序返回分組每組內(nèi)部按員工信息升序排列。這道題是典型的哈希表分組題和力扣49字母異位詞分組是同一種套路。核心思路就兩步第一步遍歷所有員工信息把工資作為key員工信息組成的列表作為value裝進一個字典第二步把字典的key排序按key從小到大輸出value列表。def groupEmployees(employees): groups {} for name, salary in employees: groups.setdefault(salary, []).append(name) result [] for salary in sorted(groups.keys()): groups[salary].sort() result.append([salary] groups[salary]) return result這道題我為什么單獨拉出來講因為它在實際工作和面試中對應的場景太常見了分組處事的邏輯在真實業(yè)務里到處都是。比如財務系統(tǒng)里按工資段對員工分組電商后臺按商品類目對SKU分組統(tǒng)計系統(tǒng)里按地區(qū)對用戶分組本質(zhì)都是“選一個屬性當key把同類的對象歸類”。很多人會忽略的一個細節(jié)是分組后的排序。如果題目要求“按工資升序返回分組”那sorted(groups.keys())這一步就漏不得。還有一個容易踩的坑是key的選擇如果分組依據(jù)不是單個字段而是多個字段的組合那就得把多個字段拼接成一個元組當作key絕對不能直接拼接字符串否則容易因為字段邊界不清而分錯組。比如兩個員工分別來自部門“12”和部門“34”如果直接把部門和工號拼在一起可能產(chǎn)生歧義。用元組(tuple)當key是最安全的選擇Python的字典完全支持元組作為鍵。2.3 力扣熱題100里的兩數(shù)之和簡單的題才是分水嶺第三道是我從熱題100里挑的“兩數(shù)之和”。在很多有經(jīng)驗的人眼里這題簡單得都不好意思拿出來講但我的體會是恰恰是這種最簡單的高頻題才最能看出一個人是不是真的理解了算法而不是背住了模板。題目給定一個整數(shù)數(shù)組nums和一個整數(shù)目標值target請你在該數(shù)組中找出和為目標值的兩個整數(shù)并返回它們的數(shù)組下標。暴力解法是O(n2)的雙層循環(huán)這個解法放到現(xiàn)在已經(jīng)不合格了面試的時候你要是上來就寫暴力解面試官大概率會追問“能不能優(yōu)化到O(n)”。優(yōu)化思路的核心是遍歷數(shù)組的時候我每看到一個數(shù)x我真正關心的是前面已經(jīng)出現(xiàn)過的數(shù)里有沒有target - x。所以用一個哈希表存“值-下標”的映射每次先查target - x在不在哈希表里不在就把當前x存進去在就直接返回。def twoSum(nums, target): seen {} for i, num in enumerate(nums): complement target - num if complement in seen: return [seen[complement], i] seen[num] i return []同樣一道題暴力解只體現(xiàn)“會循環(huán)”哈希表解法才體現(xiàn)“把遍歷過的信息存下來復用”的意識。這種意識在力扣刷題里幾乎貫穿始終緩存、記憶化搜索、前綴和、滑動窗口本質(zhì)上都是在利用已經(jīng)處理過的信息。所以我給刷題新手的建議是遇到一道題先想“我能不能在遍歷一遍的過程中把當前需要判斷的信息用哈希表提前維護好”這個思維習慣一旦養(yǎng)成很多題目都能立刻找到突破口。2.4 力扣206 反轉(zhuǎn)鏈表迭代和遞歸的取舍第四道題是鏈表專題里的反轉(zhuǎn)鏈表。這道題我面試時候被要求手寫過不下五次幾乎每次都是“先寫迭代版再講講遞歸版怎么理解”。迭代版的思路是準備一個prev指針指向Nonecur指針指向頭節(jié)點然后每次循環(huán)做四步先把cur.next存到tmp里防止丟失把cur.next指回prev把prev移動到cur把cur移動到tmp。直到cur走到Noneprev就是新鏈表的頭。def reverseList(head): prev None cur head while cur: tmp cur.next cur.next prev prev cur cur tmp return prev這段代碼寫完很多初學者會有一個困惑為什么最后返回的是prev而不是cur因為循環(huán)結束的條件是cur為空說明cur已經(jīng)走過了所有節(jié)點此時prev恰好停在新鏈表的最后一個節(jié)點上也就是原鏈表的最后一個節(jié)點它才是反轉(zhuǎn)后的頭節(jié)點。遞歸版的寫法簡潔到讓人懷疑人生但理解起來稍微繞一些。遞歸的核心思想是先把head后面的整條鏈表反轉(zhuǎn)得到一個新頭然后把head接到新鏈表的尾部。這里的難點在于“head.next.next head”這一步意思是讓head的下一個節(jié)點反過來指向head相當于完成了一次反向連接。def reverseListRecursive(head): if not head or not head.next: return head new_head reverseListRecursive(head.next) head.next.next head head.next None return new_head鏈表題的通病就是指針丟掉。我見過太多人寫反轉(zhuǎn)鏈表寫到一半head.next原來的后續(xù)節(jié)點找不到了就是因為在修改指針之前沒有用臨時變量保存。這個習慣不只出現(xiàn)在鏈表題里凡是涉及修改數(shù)據(jù)結構內(nèi)部引用關系的題目第一步一定是先備份。3. 刷題過程中的崩潰瞬間真實踩坑與排查思路刷題半年我踩過的坑比做對的題還多。這里我挑幾個有代表性的、很多人都會遇到的坑把排查思路一并寫出來。3.1 超時的真正原因不是循環(huán)太多而是數(shù)據(jù)結構選錯前面提到的121題我第一次用O(n2)跑測試用例小數(shù)組秒過一旦數(shù)組長度上萬就開始卡頓幾乎可以百分百確定問題出在復雜度上。但有意思的是很多人遇到超時以后的第一反應是“優(yōu)化循環(huán)里面的邏輯”比如把range換成enumerate或者把不必要的分支抽出來——這些操作只能把運行時間縮小一個常數(shù)本質(zhì)還是O(n2)換個更狠的用例照樣超時。我的排查方法論是拿到一道題先看數(shù)據(jù)范圍數(shù)組長度到10的4次方以上基本可以放棄O(n2)到10的5次方只考慮O(n log n)或O(n)10的6次方以上只有O(n)甚至O(log n)才可能通過。這個判斷是刷題的基本功比背模板重要得多。3.2 分組題最容易踩的三個邊界1875這道題看著簡單但邊界條件非常陰間。第一個是空輸入employees列表為空時你的分組字典是空的排序輸出也是空列表邏輯上沒錯但如果你在遍歷之前就用了employees[0]這種取下標操作直接就IndexError。第二個是只有一個員工的情況group里只有一個元素排序和輸出都要能正確處理。第三個是key不是單一字段時如果拼接key用了字符串連接就好比我前面說的“部門12工號3”被誤讀成“部門1工號23”這種錯非常隱蔽測試用例大概率能過但一到真實業(yè)務里就出大問題。我的建議是涉及分組的題目一律使用元組作為字典key拒絕字符串拼接。這是從慘痛教訓里總結出來的硬性規(guī)定。3.3 Python刷題的效率問題什么時候該逃出Python換語言Python寫算法題確實快代碼量少調(diào)試舒服。但Python有個天生的短板是運行速度慢常數(shù)大。同樣的O(n log n)算法C和Java能過Python可能就超時尤其是涉及大數(shù)組排序、嵌套哈希表和頻繁增刪的操作。我的應對策略是能用內(nèi)置函數(shù)絕對自己寫列表操作比如sorted、dict.get、collections.Counter、defaultdict這些都會比你手動實現(xiàn)快很多能用集合運算就用集合運算遇到性能瓶頸時優(yōu)先考慮減少循環(huán)層數(shù)而不是微調(diào)循環(huán)內(nèi)部。真遇上Python頂不住的題我會換個思路想有沒有O(n)的數(shù)學解法比如很多前綴和問題其實可以用“哈希表存最早出現(xiàn)下標”的方式優(yōu)化掉排序。3.4 面試官視角為什么刷題不能只滿足于AC這個問題是我做了幾次模擬面試之后才徹底想明白的。你在力扣上把題目AC了只說明你寫出了一個能通過所有測試用例的解法但面試官要考察的不只是“能不能寫出來”還包括“能不能說清楚為什么”。同樣的121題AC的人很多但面試官一問“貪心解法為什么是正確的”很多人就卡住了。原因是他們寫代碼的時候只記住了“維護最小價格、取最大差值”這個模板沒有真正理解每一步為什么能保證最優(yōu)解。我的經(jīng)驗是刷每一道題AC之后必須能回答三個問題這個算法為什么正確時間復雜度為什么是這樣如果數(shù)據(jù)范圍擴大十倍還成立嗎回答不出來這道題就等于沒刷透。4. 讓“每日4題”真正堅持下去的操作系統(tǒng)刷題這件事技術難點反而小真正的難點是堅持。我給自己搭了一套簡單的“刷題操作系統(tǒng)”今天就把它全部分享出來。4.1 每周計劃與時間安排我每天的4道題不是找一個整塊時間一次性做完而是拆成三個時段。早上起床后花15-20分鐘做第一道新題利用早上腦子清醒的時候啃硬骨頭中午午休后花15分鐘復刷昨天的舊題這時候人容易困做舊題壓力小晚上下班后集中精力做專題訓練和錯題重刷大概40-60分鐘。這樣全天加起來的刷題時間在一個半小時左右但分攤到三個時段里心理負擔會小很多不會覺得“今天又要刷兩個小時題”。每周我會固定留一天做周回顧不刷新題只把這周做過的所有舊題和錯題重新過一遍。這個動作看起來只是復習實際上它才是知識內(nèi)化的關鍵環(huán)節(jié)。我用的是最簡單的辦法手機備忘錄里建一個“力扣復盤”清單每周日晚上把本周所有AC過的題目標題寫下來先不看題解純靠記憶復述思路復述不出來的題下周就標記為“必復習題”。4.2 錯題復盤模板一道錯題該記錄什么很多人刷題有一個通病錯題看完題解AC之后就再也不管了結果就是同一道題能錯三次。我給自己定了一個復盤模板每道錯題記錄五個字段題目名稱和編號、錯誤類型思路錯誤還是代碼錯誤、正確思路一句話總結、關鍵數(shù)據(jù)結構和復雜度、下次重刷日期。這個模板最有價值的地方就在于“正確思路一句話總結”。寫這句話的時候你被迫把一整段題解壓縮成自己理解了的核心思想。比如121題的總結我寫的是“維護歷史最低價用當前價減最低價更新最大利潤”兩數(shù)之和的總結寫的是“遍歷時用哈希表存已出現(xiàn)的值找補數(shù)”。這種壓縮后的總結在面試前非常有用翻一遍就能快速激活記憶。4.3 從每日刷題到面試講題如何把AC能力轉(zhuǎn)成表達力這里必須承認一個殘酷的事實有些人刷了300道題面試的時候還是掛得很慘因為表達能力跟不上。力扣刷題讓你會做但面試需要你會講。所以我給自己增加了一個練習環(huán)節(jié)每天做完4道題之后挑其中一道用兩三分鐘的時間假裝面前坐著面試官把題目讀一遍、講思路、分析復雜度、說邊界條件整個過程錄音或者在心里過一遍。這個練習一開始非常別扭講起來顛三倒四。但堅持了兩周之后我發(fā)現(xiàn)自己的表達結構開始變得清晰先說什么、再說什么、哪里需要強調(diào)、哪里一句話帶過都有了肌肉記憶。面試的時候面試官問的其實并不是“你AC了沒”而是“你怎么思考的”。這個思考過程能否清晰表達出來才是決定面試結果的關鍵。4.4 關于“題目刷不完”的心態(tài)問題我經(jīng)?？吹接腥藛枴傲垲}庫幾千題刷得完嗎”。我的看法是刷題的目標從來就不是把題庫刷穿而是建立一種識別題目模式的能力。當你把熱題100和常見專題刷過兩三遍之后再看到新題你會發(fā)現(xiàn)絕大多數(shù)題目都是“舊瓶裝新酒”——考察的還是滑動窗口、雙指針、哈希表、動態(tài)規(guī)劃那幾板斧。所以每天4道題這個數(shù)量不在于多而在于穩(wěn)定。跑馬拉松的人都知道配速比沖刺重要得多。我剛定下這個系列的時候給自己定的規(guī)矩就一條今天哪怕只做一道簡單的題也比徹底不做好。這個最低標準的存在讓我在加班到晚上十點、累到不想動筆的日子也能保持這個系列不斷檔。5. 刷題高頻問題速查表別人踩過的坑我?guī)湍阆炔茸詈笪野堰@半年刷題過程中評論區(qū)、交流群里出現(xiàn)頻率最高的問題整理成一個速查表附帶我的處理經(jīng)驗。5.1 力扣題目編號和題解版本變化怎么應對力扣的題目編號是固定的但題解區(qū)的內(nèi)容動態(tài)更新非常快幾年前的高贊題解可能已經(jīng)不適合現(xiàn)在的數(shù)據(jù)范圍。我的處理辦法是看題解優(yōu)先看“思路講解”跳過“完整代碼”先自己嘗試把思路落地卡住了再回來看代碼。因為你現(xiàn)在看別人代碼看懂了不代表你能寫出來只有親手敲一遍合適代碼思路才會變成自己的。5.2 Python和C刷題怎么選從面試角度講如果目標公司明確要求某一種語言那就直接用那種語言刷。如果沒有限定自己最熟什么語言就用什么語言。不過我想多說一句Python刷題有它獨有的優(yōu)勢代碼量少、數(shù)據(jù)結構封裝完整、可以快速驗證想法非常利于面試中快速和面試官對齊思路但Python的常數(shù)偏大有些對性能要求極高的題目可能會吃虧。所以我的建議是日常刷題用Python練思路每周抽一兩道題用手寫C或者Java再實現(xiàn)一遍兩種語言的切換能力是加分項。5.3 刷題時到底要不要看題解看題解不是恥辱瞎刷才是。我的規(guī)則是一道題獨立思考30分鐘沒有推進就去看題解。關鍵是看完題解之后必須合上題解自己完整寫一遍并且過兩天再復刷一次。只看不寫等于白看這個環(huán)節(jié)偷懶的話刷題數(shù)量再多也沒法轉(zhuǎn)化成真正的能力。5.4 熱題100和每日一題怎么搭配每日一題是相對隨意的題目流非常適合當作“新題接入點”但它無法覆蓋完整的知識結構。熱題100是精選題目集適合系統(tǒng)學習。我的做法是熱題100作為主線按專題推進每日一題作為支線隨機補充。主線保證知識體系完整支線保證視野不局限于專題。兩者的交叉點就在于我前面說的四道題分配法主線出兩道支線出一道錯題復盤出一道。我個人這半年刷下來最有價值的收獲不是AC了將近500道題而是建立了一套屬于自己的思考方式看到題目先想數(shù)據(jù)范圍、再想時間復雜度、再匹配數(shù)據(jù)結構、最后落代碼。每天4道這個節(jié)奏讓我在忙碌的工作和生活之間找到了一個平衡點。如果你也想開始刷題或者正在刷題但堅持不下來不妨試試這套打法。先別想太多從今天的一道新題開始明年的今天你會感謝現(xiàn)在的自己。