刷題實戰筆記：演算法工程師求職加分的祕笈


	快速掌握演算法思維　　應對求職時IT公司的各種演算法面試題　　用範本和框架思維解決問題，以不變應萬變　　本書的最大功效　　逐步指導讀者大量演練演算法題目，以及各種演算法題型的樣式和框架，快速掌握演算法思維，以應對求職時IT公司的各種演算法面試題，或是增進讀者編寫程式的技巧。　　本書並不適合純新手來閱讀　　如果你對基本的資料結構還一竅不通，那麼你需要先花幾天的時間看一本介紹基礎的資料結構書，去瞭解諸如佇列、堆疊、陣列、鏈結串列等基本資料結構。不需要非常精通，只需大致瞭解它們的特點和用法即可。我想大學時期學過資料結構課程的讀者，閱讀本書應該不會有什麼問題。　　如果你學過資料結構　　由於種種現實原因開始在刷題平台上演練，卻又覺得無所適從、心亂如麻，那麼本書可以解決你的燃眉之急。當然，如果你只是單純的演算法愛好者，以刷題為樂，本書也會給你不少啟發，讓你的演算法功力更上一層樓。　　本書有許多題目都參考自LeetCode這個題目平台　　題目解法的程式碼形式遵循該平台的標準。因此如果你習慣在LeetCode平台上演練演算法題目，那麼閱讀本書會更加遊刃有餘。當然，即使你沒有這個習慣也無妨，因為演算法的解題技巧都是通用的。　　本書混用Python、C++和Java三種程式語言　　筆者認為演算法題目的重點是在養成一種思維模式，不應該局限於具體的程式語言。不必擔心有的語言你不熟悉，演算法根本用不到程式語言層面的技巧，本書也會有意避開所有語言特性，而且後面會統一介紹三種語言的基本操作。


	目錄本書約定語言基礎第 1 章核心技巧篇 1.1 學習演算法和刷題的概念框架 1.1.1 資料結構的儲存方式 1.1.2 資料結構的基本操作 1.1.3 演算法刷題指南 1.1.4 最後總結 1.2 動態規劃解題範本框架 1.2.1 費波那契數列（費氏數列） 1.2.2 湊零錢問題 1.2.3 最後總結 1.3 回溯演算法解題範本框架 1.3.1 全排列問題 1.3.2 N 皇后問題 1.3.3 最後總結 1.4 BFS演算法範本框架 1.4.1 演算法框架 1.4.2 二元樹的最小高度 1.4.3 解開密碼鎖的最少次數 1.5 雙指標技巧範本框架 1.5.1 快、慢指標的常用演算法 1.5.2 左、右指標的常用演算法 1.6 我寫了首詩，保證你閉著眼睛都能寫出二分搜尋演算法 1.6.1 二分搜尋框架 1.6.2 找尋一個數（基本的二分搜尋） 1.6.3 尋找左側邊界的二分搜尋 1.6.4 尋找右側邊界的二分搜尋 1.6.5 邏輯統一 1.7 我寫了一個範本，把滑動視窗演算法變成了默寫題 1.7.1 最小覆蓋字串 1.7.2 字串排列 1.7.3 找所有字母異位詞 1.7.4 最長無重覆字串第 2 章動態規劃系列 2.1 動態規劃設計：最長遞增子序列 2.1.1 動態規劃解法 2.1.2 二分搜尋解法 2.2 二維遞增子序列：信封嵌套問題 2.2.1 題目概述 2.2.2 思路分析 2.2.3 最後總結 2.3 最大子陣列問題 2.3.1 思路分析 2.3.2 最後總結 2.4 動態規劃解疑：最佳子結構及dp巡訪方向 2.4.1 最佳子結構詳解 2.4.2 dp陣列的巡訪方向 2.5 經典動態規劃：最長公用次序列 2.6 經典動態規劃：編輯距離 2.6.1 思路分析 2.6.2 程式碼詳解 2.6.3 動態規劃最佳化 2.6.4 擴展延伸 2.7 子序列問題解題範本：最長迴文子序列 2.7.1 兩種思路 2.7.2 最長迴文子序列 2.7.3 程式碼實作 2.8 狀態壓縮：對動態規劃進行降維操作 2.9 以最小插入次數建構迴文串 2.9.1 思路分析 2.9.2 狀態轉移方程 2.9.3 程式碼實作 2.10 動態規劃之正規運算式 2.10.1 思路分析 2.10.2 動態規劃解法 2.11 不同的定義產生不同的解法 2.11.1 第一種思路 2.11.2 第二種思路 2.11.3 最後總結 2.12 經典動態規劃：高樓扔雞蛋 2.12.1 解析題目 2.12.2 思路分析 2.12.3 疑難排解 2.13 經典動態規劃：高樓扔雞蛋（進階） 2.13.1 二分搜尋最佳化 2.13.2 重新定義狀態轉移 2.13.3 還可以再最佳化 2.14 經典動態規劃：戳氣球問題 2.14.1 回溯思路 2.14.2 動態規劃思路 2.14.3 寫出程式碼 2.15 經典動態規劃：0-1 背包問題 2.16 經典動態規劃：子集背包問題 2.16.1 問題分析 2.16.2 思路分析 2.16.3 進行狀態壓縮 2.17 經典動態規劃：完全背包問題 2.18 題目千百變，範本不會變 2.18.1 線性排列情況 2.18.2 環形排列情況 2.18.3 樹形排列情況 2.19 動態規劃和回溯演算法，到底是什麼關係 2.19.1 回溯思路 2.19.2 消除重疊子問題 2.19.3 動態規劃第 3 章資料結構系列 3.1 一步步教你撰寫LRU快取淘汰演算法 3.1.1 LRU演算法描述 3.1.2 LRU演算法設計 3.1.3 程式碼實作 3.2 層層拆解，帶你動手撰寫LFU演算法 3.2.1 演算法描述 3.2.2 思路分析 3.2.3 程式碼框架 3.2.4 LFU核心邏輯 3.3 二元搜尋樹操作集錦 3.3.1 判斷BST的合法性 3.3.2 在BST找尋一個數是否存在 3.3.3 在BST插入一個數 3.3.4 在BST刪除一個數 3.4 為什麼那麼難算完全二元樹的節點數 3.4.1 思路分析 3.4.2 複雜度分析 3.5 利用各種巡訪框架序列化和反序列化二元樹 3.5.1 題目描述 3.5.2 前序巡訪解法 3.5.3 後序巡訪解法 3.5.4 中序巡訪解法 3.5.5 層級巡訪解法 3.6 Git原理之二元樹最低共用源始 3.6.1 二元樹的最低共用源始 3.6.2 思路分析 3.7 特殊資料結構：單調堆疊 3.7.1 單調堆疊解題範本 3.7.2 題目變形 3.7.3 如何處理迴圈陣列 3.8 特殊資料結構：單調佇列 3.8.1 建置解題框架 3.8.2 實作單調佇列資料結構 3.8.3 演算法複雜度分析 3.9 如何判斷迴文鏈結串列 3.9.1 判斷迴文單向鏈結串列 3.9.2 最佳化空間複雜度 3.9.3 最後總結 3.10 秀操作之純遞迴反轉鏈結串列 3.10.1 遞迴反轉整個鏈結串列 3.10.2 反轉鏈結串列前N個節點 3.10.3 反轉鏈結串列的一部分 3.10.4 最後總結 3.11 秀操作之k個一組反轉鏈結串列 3.11.1 分析問題 3.11.2 程式碼實作 3.11.3 最後總結第 4 章演算法思維系列 4.1 回溯演算法解決子集、組合、排列問題 4.1.1 子集 4.1.2 組合 4.1.3 排列 4.2 回溯演算法最佳實踐：解數獨 4.2.1 直觀感受 4.2.2 程式碼實作 4.3 回溯演算法最佳實踐：括弧產生 4.4 BFS演算法暴力破解各種智力題 4.4.1 題目解析 4.4.2 思路分析 4.5 2Sum問題的核心觀念 4.5.1 2Sum I 4.5.2 2Sum II 4.5.3 最後總結 4.6 一個函數解決 nSum 問題 4.6.1 2Sum 問題 4.6.2 3Sum 問題 4.6.3 4Sum 問題 4.6.4 100Sum 問題 4.7 拆解複雜問題：實作計算器 4.7.1 字串轉整數 4.7.2 處理加減法 4.7.3 處理乘除法 4.7.4 處理括弧 4.7.5 最後總結 4.8 攤煎餅也得有點遞迴思維 4.8.1 思路分析8 4.8.2 程式碼實作 4.9 字首和技巧解決子陣列問題 4.9.1 什麼是字首和 4.9.2 最佳化解法 4.9.3 最後總結 4.10 扁平化巢狀串列 4.10.1 題目描述 4.10.2 解題思路 4.10.3 進階思路第 5 章常見面試系列 5.1 如何有效尋找質數 5.2 如何有效進行模冪運算 5.2.1 如何處理陣列指數 5.2.2 如何處理mod運算 5.2.3 如何有效求冪 5.3 如何運用二分搜尋演算法 5.3.1 問題分析 5.3.2 擴展延伸 5.4 如何有效解決接雨水問題 5.4.1 核心思路 5.4.2 備忘錄最佳化 5.4.3 雙指標解法 5.5 如何去除有序陣列的重覆元素 5.6 如何尋找最長迴文子字串 5.6.1 思考 5.6.2 程式碼實作 5.7 如何運用貪婪概念玩跳躍遊戲 5.7.1 跳躍遊戲 I 5.7.2 跳躍遊戲 II 5.8 如何運用貪婪演算法做時間管理 5.8.1 問題概述 5.8.2 貪婪解法 5.8.3 應用範例 5.9 如何判斷括弧合法性 5.9.1 處理一種括弧 5.9.2 處理多種括弧 5.10 如何調度考生的座位 5.10.1 思路分析 5.10.2 簡化問題 5.10.3 進階問題 5.10.4 最後總結 5.11 Union-Find演算法詳解 5.11.1 問題描述 5.11.2 基本思路 5.11.3 平衡性最佳化 5.11.4 路徑壓縮 5.11.5 最後總結 5.12 Union-Find演算法應用 5.12.1 DFS的替代方案 5.12.2 判斷合法等式 5.12.3 最後總結 5.13 一行程式碼就能解決的演算法題目 5.13.1 Nim遊戲 5.13.2 石頭遊戲 5.13.3 電燈開關問題