訓練營算法題

第一周

數組,連結清單,跳表:

• Java 源碼分析（ArrayList）
• Linked List 的标準實作代碼
• Linked List 示例代碼
• Java 源碼分析（LinkedList）

• LRU Cache - Linked list： LRU 緩存機制

  * Redis - Skip List：跳躍表、為啥 Redis 使用跳表（Skip List）而不是使用 Red-Black？

  Array 實戰題目

• 兩數之和（近半年内，位元組跳動在面試中考查此題達到 152 次）
• 盛最多水的容器（騰訊、百度、位元組跳動在近半年内面試常考）
• 移動零（華為、位元組跳動在近半年内面試常考）
• 爬樓梯（阿裡巴巴、騰訊、位元組跳動在半年内面試常考）

• 三數之和（國内、國際大廠曆年面試高頻老題）

  Linked List 實戰題目

• 反轉連結清單（位元組跳動、亞馬遜在半年内面試常考）
• 兩兩交換連結清單中的節點（阿裡巴巴、位元組跳動在半年内面試常考）
• 環形連結清單（阿裡巴巴、位元組跳動、騰訊在半年内面試常考）
• 環形連結清單 II
• K 個一組翻轉連結清單（位元組跳動、猿輔導在半年内面試常考）

棧,隊列,優先隊列,雙端隊列

參考連結

• Java 的 PriorityQueue 文檔
• Java 的 Stack 源碼
• Java 的 Queue 源碼
• Python 的 heapq
• 高性能的 container 庫

實戰題目

• 有效的括号（亞馬遜、JPMorgan 在半年内面試常考）
• 最小棧（亞馬遜在半年内面試常考）
• 柱狀圖中最大的矩形（亞馬遜、微軟、位元組跳動在半年内面試中考過）
• 滑動視窗最大值（亞馬遜在半年内面試常考）

• 設計循環雙端隊列（Facebook 在 1 年内面試中考過）

  本周作業

  簡單：

• 删除排序數組中的重複項（Facebook、位元組跳動、微軟在半年内面試中考過）
• 旋轉數組（微軟、亞馬遜、PayPal 在半年内面試中考過）
• 合并兩個有序連結清單（亞馬遜、位元組跳動在半年内面試常考）
• 合并兩個有序數組（Facebook 在半年内面試常考）
• 兩數之和（亞馬遜、位元組跳動、谷歌、Facebook、蘋果、微軟在半年内面試中高頻常考）
• 移動零（Facebook、亞馬遜、蘋果在半年内面試中考過）

• 加一（谷歌、位元組跳動、Facebook 在半年内面試中考過）

  中等：

• 設計循環雙端隊列（Facebook 在 1 年内面試中考過）

  困難：

• 接雨水（亞馬遜、位元組跳動、高盛集團、Facebook 在半年内面試常考）

預習題目：

• 有效的字母異位詞
• 二叉樹的中序周遊
• 最小的 k 個數

第二周

哈希表,映射,集合

參考連結

• Java Set 文檔

• Java Map 文檔

  實戰題目 / 課後作業

• 有效的字母異位詞
• 字母異位詞分組（亞馬遜在半年内面試中常考）
• 兩數之和（近半年内，位元組跳動在面試中考查此題達到 152 次）

樹,二叉樹,二叉搜尋樹

參考連結

• 樹的周遊 Demo

  實戰題目 / 課後作業

• 二叉樹的中序周遊（亞馬遜、微軟、位元組跳動在半年内面試中考過）
• 二叉樹的前序周遊（谷歌、微軟、位元組跳動在半年内面試中考過）

堆和二叉堆

實戰例題

• 最小的 k 個數
• 滑動視窗最大值（亞馬遜在半年内面試常考）

課後作業

• HeapSort ：自學 https://www.geeksforgeeks.org/heap-sort/
• 醜數（位元組跳動在半年内面試中考過）

• 前 K 個高頻元素（亞馬遜在半年内面試中常考）

  2周作業

  簡單：

• 有效的字母異位詞
• 兩數之和（近半年内，位元組跳動在面試中考查此題達到 152 次）
• N 叉樹的前序周遊（亞馬遜在半年内面試中考過）

• HeapSort ：自學 https://www.geeksforgeeks.org/heap-sort/

  中等：

• 字母異位詞分組（亞馬遜在半年内面試中常考）
• 二叉樹的中序周遊（亞馬遜、微軟、位元組跳動在半年内面試中考過）
• 二叉樹的前序周遊（谷歌、微軟、位元組跳動在半年内面試中考過）
• N 叉樹的層序周遊（亞馬遜在半年内面試中考過）
• 醜數（位元組跳動在半年内面試中考過）

• 前 K 個高頻元素（亞馬遜在半年内面試中常考）

  下周預習

  預習題目：

• 爬樓梯（阿裡巴巴、騰訊、位元組跳動在半年内面試常考）
• 括号生成
• Pow(x, n)
• 子集
• N 皇後

第三周

泛型遞歸,樹的遞歸:

實戰題目

• 爬樓梯（阿裡巴巴、騰訊、位元組跳動在半年内面試常考）
• 括号生成
• 翻轉二叉樹 (谷歌、位元組跳動、Facebook 在半年内面試中考過)
• 驗證二叉搜尋樹（亞馬遜、微軟、Facebook 在半年内面試中考過）
• 二叉樹的最大深度（亞馬遜、微軟、位元組跳動在半年内面試中考過）
• 二叉樹的最小深度（Facebook、位元組跳動、谷歌在半年内面試中考過)

• 二叉樹的序列化與反序列化（Facebook、亞馬遜在半年内面試常考）

  每日一課

• 如何優雅地計算斐波那契數列

  課後作業

• 二叉樹的最近公共祖先（Facebook 在半年内面試常考）
• 從前序與中序周遊序列構造二叉樹（位元組跳動、亞馬遜、微軟在半年内面試中考過）
• 組合（微軟、亞馬遜、谷歌在半年内面試中考過）
• 全排列（位元組跳動在半年内面試常考）
• 全排列 II （亞馬遜、位元組跳動、Facebook 在半年内面試中考過）

分治,遞歸

實戰題目

• Pow(x, n)

• 子集

  實戰題目

• 多數元素 （亞馬遜、位元組跳動、Facebook 在半年内面試中考過）
• 電話号碼的字母組合（亞馬遜在半年内面試常考）

• N 皇後

  第三周作業

  本周作業

  中等：

• 二叉樹的最近公共祖先（Facebook 在半年内面試常考）
• 從前序與中序周遊序列構造二叉樹（位元組跳動、亞馬遜、微軟在半年内面試中考過）
• 組合（微軟、亞馬遜、谷歌在半年内面試中考過）
• 全排列（位元組跳動在半年内面試常考）

• 全排列 II （亞馬遜、位元組跳動、Facebook 在半年内面試中考過）

  下周預習

  預習題目：

• 二叉樹的層次周遊
• 分發餅幹
• 買賣股票的最佳時機 II
• 跳躍遊戲
• x 的平方根
• 有效的完全平方數

第四周

深度優先搜尋和廣度優先搜尋

參考連結

• DFS 代碼模闆（遞歸寫法、非遞歸寫法）
• BFS 代碼模闆

• 二叉樹的層次周遊

  實戰題目

• 二叉樹的層次周遊
• 最小基因變化

• 括号生成

  * 在每個樹行中找最大值（微軟、亞馬遜、Facebook 在半年内面試中考過）

  課後作業

• 單詞接龍（亞馬遜在半年内面試常考）
• 單詞接龍 II （微軟、亞馬遜、Facebook 在半年内面試中考過）
• 島嶼數量（近半年内，亞馬遜在面試中考查此題達到 350 次）
• 掃雷遊戲（亞馬遜、Facebook 在半年内面試中考過）

貪心算法:

參考連結

• coin change 題目

• 動态規劃定義

  課後作業

• 檸檬水找零（亞馬遜在半年内面試中考過）
• 買賣股票的最佳時機 II （亞馬遜、位元組跳動、微軟在半年内面試中考過）
• 分發餅幹（亞馬遜在半年内面試中考過）
• 模拟行走機器人
• 跳躍遊戲 （亞馬遜、華為、Facebook 在半年内面試中考過）
• 跳躍遊戲 II （亞馬遜、華為、位元組跳動在半年内面試中考過）

二分查找

參考連結

• 二分查找代碼模闆

• Fast InvSqrt() 擴充閱讀

  實戰題目

• x 的平方根（位元組跳動、微軟、亞馬遜在半年内面試中考過）

• 有效的完全平方數（亞馬遜在半年内面試中考過）

  課後作業

• 搜尋旋轉排序數組（Facebook、位元組跳動、亞馬遜在半年内面試常考）
• 搜尋二維矩陣（亞馬遜、微軟、Facebook 在半年内面試中考過）
• 尋找旋轉排序數組中的最小值（亞馬遜、微軟、位元組跳動在半年内面試中考過）

• 使用二分查找，尋找一個半有序數組 [4, 5, 6, 7, 0, 1, 2] 中間無序的地方

  說明：同學們可以将自己的思路、代碼寫在學習總結中

  第4周作業

  簡單：

• 檸檬水找零（亞馬遜在半年内面試中考過）
• 買賣股票的最佳時機 II （亞馬遜、位元組跳動、微軟在半年内面試中考過）
• 分發餅幹（亞馬遜在半年内面試中考過）
• 模拟行走機器人

中等：

• 單詞接龍（亞馬遜在半年内面試常考）
• 單詞接龍 II （微軟、亞馬遜、Facebook 在半年内面試中考過）
• 島嶼數量（近半年内，亞馬遜在面試中考查此題達到 350 次）
• 掃雷遊戲（亞馬遜、Facebook 在半年内面試中考過）
• 跳躍遊戲 （亞馬遜、華為、Facebook 在半年内面試中考過）
• 跳躍遊戲 II （亞馬遜、華為、位元組跳動在半年内面試中考過）
• 搜尋旋轉排序數組（Facebook、位元組跳動、亞馬遜在半年内面試常考）
• 搜尋二維矩陣（亞馬遜、微軟、Facebook 在半年内面試中考過）
• 尋找旋轉排序數組中的最小值（亞馬遜、微軟、位元組跳動在半年内面試中考過）

第 6 周預習

預習題目：

• 最長公共子序列題目
• 三角形最小路徑和
• 最大子序和
• 打家劫舍

第六周

動态規劃:

參考連結

• 不同路徑（Facebook、亞馬遜、微軟在半年内面試中考過）
• 不同路徑 II （谷歌、美團、微軟在半年内面試中考過）
• 最長公共子序列（位元組跳動、谷歌、亞馬遜在半年内面試中考過）

• MIT 動态規劃課程最短路徑算法

  實戰題目

• 爬樓梯（阿裡巴巴、騰訊、位元組跳動在半年内面試常考）
• 三角形最小路徑和（亞馬遜、蘋果、位元組跳動在半年内面試考過）
• 三角形最小路徑和高票回答： https://leetcode.com/problems/triangle/discuss/38735/Python-easy-to-understand-solutions-(top-down-bottom-up)
• 最大子序和（亞馬遜、位元組跳動在半年内面試常考）
• 乘積最大子數組（亞馬遜、位元組跳動、谷歌在半年内面試中考過）

• 零錢兌換（亞馬遜在半年内面試中常考）

  實戰題目

• 打家劫舍（位元組跳動、谷歌、亞馬遜在半年内面試中考過）
• 打家劫舍 II （位元組跳動在半年内面試中考過）
• 買賣股票的最佳時機（亞馬遜、位元組跳動、Facebook 在半年内面試中常考）
• 買賣股票的最佳時機 II （亞馬遜、位元組跳動、微軟在半年内面試中考過）
• 買賣股票的最佳時機 III （位元組跳動在半年内面試中考過）
• 最佳買賣股票時機含冷凍期（谷歌、亞馬遜在半年内面試中考過）
• 買賣股票的最佳時機 IV （谷歌、亞馬遜、位元組跳動在半年内面試中考過）
• 買賣股票的最佳時機含手續費

• 一個方法團滅 6 道股票問題

  *完全平方數（亞馬遜、谷歌在半年内面試中考過)

• 編輯距離 （重點）
• 跳躍遊戲（亞馬遜在半年内面試中考過）
• 跳躍遊戲 II （亞馬遜、華為位元組跳動在半年内面試中考過）
• 不同路徑（Facebook、亞馬遜、微軟在半年内面試中考過）
• 不同路徑 II （谷歌、美團、微軟在半年内面試中考過）
• 不同路徑 III （谷歌在半年内面試中考過）
• 零錢兌換（亞馬遜在半年内面試中常考）

• 零錢兌換 II （亞馬遜、位元組跳動在半年内面試中考過）

  第6周作業

  中等

• 最小路徑和（亞馬遜、高盛集團、谷歌在半年内面試中考過）
• 解碼方法（亞馬遜、Facebook、位元組跳動在半年内面試中考過）
• 最大正方形（華為、谷歌、位元組跳動在半年内面試中考過）
• 任務排程器（Facebook 在半年内面試中常考）

• 回文子串（Facebook、蘋果、位元組跳動在半年内面試中考過）

  困難

• 最長有效括号（位元組跳動、亞馬遜、微軟在半年内面試中考過）
• 編輯距離 （重點）
• 青蛙過河（亞馬遜、蘋果、位元組跳動在半年内面試中考過）

第七周

進階搜尋

參考連結

• DFS 代碼模闆
• BFS 代碼模闆
• AlphaZero Explained

• 棋類複雜度

  剪枝實戰題目解析

  實戰題目

• 爬樓梯（阿裡巴巴、騰訊、位元組跳動在半年内面試常考）
• 括号生成
• N 皇後
• 有效的數獨（亞馬遜、蘋果、微軟在半年内面試中考過）

• 解數獨（亞馬遜、華為、微軟在半年内面試中考過）

  啟發式搜尋

  參考連結

  * A* 代碼模闆

• 二進制矩陣中的最短路徑的 A* 解法

  實戰題目

• 二進制矩陣中的最短路徑（亞馬遜、位元組跳動、Facebook 在半年内面試中考

  第7周作業

  簡單

• 爬樓梯（阿裡巴巴、騰訊、位元組跳動在半年内面試常考）

  中等

• 朋友圈（亞馬遜、Facebook、位元組跳動在半年内面試中考過）
• 島嶼數量（近半年内，亞馬遜在面試中考查此題達到 361 次）
• 被圍繞的區域（亞馬遜、eBay、谷歌在半年内面試中考過）
• 有效的數獨（亞馬遜、蘋果、微軟在半年内面試中考過）
• 括号生成（亞馬遜、Facebook、位元組跳動在半年内面試中考過）
• 單詞接龍（亞馬遜、Facebook、谷歌在半年内面試中考過）

• 最小基因變化（谷歌、Twitter、騰訊在半年内面試中考過）

  困難

• 單詞搜尋 II （亞馬遜、微軟、蘋果在半年内面試中考過）
• N 皇後（亞馬遜、蘋果、位元組跳動在半年内面試中考過）

• 解數獨（亞馬遜、華為、微軟在半年内面試中考過）

  下周預習題目

• LRU 緩存機制

• 有效的字母異位詞

  位運算實戰:

  參考連結

• N 皇後位運算代碼示例

  實戰題目 / 課後作業

• 位 1 的個數（Facebook、蘋果在半年内面試中考過）
• 2 的幂（谷歌、亞馬遜、蘋果在半年内面試中考過）
• 颠倒二進制位（蘋果在半年内面試中考過）
• N 皇後（位元組跳動、亞馬遜、百度在半年内面試中考過）
• N 皇後 II （亞馬遜在半年内面試中考過）
• 比特位計數（位元組跳動、Facebook、MathWorks 在半年内面試中考過）

LRU Cache的實作和題解

參考連結

• Understanding the Meltdown exploit

  * 替換算法總攬

• LRU Cache Python 代碼示例

  實戰題目 / 課後作業

• LRU 緩存機制（亞馬遜、位元組跳動、Facebook、微軟在半年内面試中常考）

第八周

排序算法

參考連結

• 十大經典排序算法
• 快速排序代碼示例
• 歸并排序代碼示例

• 堆排序代碼示例

  參考連結

• 十大經典排序算法
• 9 種經典排序算法可視化動畫

• 6 分鐘看完 15 種排序算法動畫展示

  實戰題目 / 課後作業

• 數組的相對排序（谷歌在半年内面試中考過）
• 有效的字母異位詞（Facebook、亞馬遜、谷歌在半年内面試中考過）
• 力扣排行榜（Bloomberg 在半年内面試中考過）
• 合并區間（Facebook、位元組跳動、亞馬遜在半年内面試中常考）
• 翻轉對（位元組跳動在半年内面試中考過）

第8周作業

簡單

• 位 1 的個數（Facebook、蘋果在半年内面試中考過）
• 2 的幂（谷歌、亞馬遜、蘋果在半年内面試中考過）
• 颠倒二進制位（蘋果在半年内面試中考過）
• 用自己熟悉的程式設計語言，手寫各種初級排序代碼，送出到學習總結中。
• 數組的相對排序（谷歌在半年内面試中考過）

• 有效的字母異位詞（Facebook、亞馬遜、谷歌在半年内面試中考過）

  中等

• LRU 緩存機制（亞馬遜、位元組跳動、Facebook、微軟在半年内面試中常考）
• 力扣排行榜（Bloomberg 在半年内面試中考過）

• 合并區間（Facebook、位元組跳動、亞馬遜在半年内面試中常考）

  困難

• N 皇後（位元組跳動、亞馬遜、百度在半年内面試中考過）
• N 皇後 II （亞馬遜在半年内面試中考過）

• 翻轉對（位元組跳動在半年内面試中考過）

  下周預習題目：

• 不同路徑
• 最小路徑和

第九周

進階動态規劃

參考連結

• 爬樓梯（阿裡巴巴、騰訊、位元組跳動在半年内面試常考）
• 不同路徑（亞馬遜、微軟、Facebook 在半年内面試中考過）
• 打家劫舍（位元組跳動、谷歌、蘋果在半年内面試中考過）
• 最小路徑和（位元組跳動、谷歌、亞馬遜在半年内面試中考過）

• 股票買賣（位元組跳動、亞馬遜、Facebook 在半年内面試常考）

  課後作業

  在學習總結中，寫出不同路徑 2 這道題目的狀态轉移方程。

  參考連結

• 爬樓梯（阿裡巴巴、騰訊、位元組跳動在半年内面試常考）
• 使用最小花費爬樓梯（亞馬遜在半年内面試中考過）

• 編輯距離（位元組跳動、亞馬遜、谷歌在半年内面試中考過）

  課後作業

• 最長上升子序列（位元組跳動、亞馬遜、微軟在半年内面試中考過）
• 解碼方法（Facebook、亞馬遜、位元組跳動在半年内面試中考過）
• 最長有效括号（華為、亞馬遜、位元組跳動在半年内面試中考過）
• 最大矩形（谷歌、微軟、位元組跳動在半年内面試中考過）
• 不同的子序列（MathWorks 在半年内面試中考過）
• 賽車（谷歌在半年内面試中考過）

字元串相關

字元串基礎知識和引申題目:

參考連結

• 不可變字元串

• Atoi 代碼示例

  字元串基礎問題

• 轉換成小寫字母（谷歌在半年内面試中考過）
• 最後一個單詞的長度（蘋果、谷歌、位元組跳動在半年内面試中考過）
• 寶石與石頭（亞馬遜在半年内面試中考過）

• 字元串中的第一個唯一字元

  （亞馬遜、微軟、Facebook 在半年内面試中考過）

• 字元串轉換整數 (atoi) （亞馬遜、微軟、Facebook 在半年内面試中考過）

  字元串操作問題

• 最長公共字首（亞馬遜、谷歌、Facebook 在半年内面試中考過）
• 反轉字元串（亞馬遜、谷歌、蘋果在半年内面試中考過）
• 反轉字元串 II （亞馬遜在半年内面試中考過）
• 翻轉字元串裡的單詞（微軟、位元組跳動、蘋果在半年内面試中考過）
• 反轉字元串中的單詞 III （微軟、位元組跳動、華為在半年内面試中考過）

• 僅僅反轉字母（位元組跳動在半年内面試中考過）

  異位詞問題

• 有效的字母異位詞

  （Facebook、亞馬遜、谷歌在半年内面試中考過）

• 字母異位詞分組（亞馬遜在半年内面試中常考）

• 找到字元串中所有字母異位詞（Facebook 在半年内面試中常考）

  回文串問題

• 驗證回文串（Facebook 在半年内面試中常考）
• 驗證回文字元串 Ⅱ（Facebook 在半年内面試中常考）
• 最長回文子串（亞馬遜、位元組跳動、華為在半年内面試中常考）

進階字元串算法:

最長子串、子序列問題

• 最長公共子序列（亞馬遜、位元組跳動、谷歌在半年内面試中考過）
• 編輯距離（亞馬遜、位元組跳動、谷歌在半年内面試中考過）

• 最長回文子串（亞馬遜、華為、位元組跳動在半年内面試常考）

  字元串 +DP 問題

• 正規表達式比對（Facebook、微軟、位元組跳動在半年内面試中考過）
• 題解： https://leetcode-cn.com/problems/regular-expression-matching/solution/ji-yu-guan-fang-ti-jie-gen-xiang-xi-de-jiang-jie-b/
• 通配符比對（Facebook、微軟、位元組跳動在半年内面試中考過）
• 不同的子序列（MathWorks 在半年内面試中考過）

字元串比對算法:

參考連結

• Boyer-Moore 算法
• Sunday 算法
• 字元串比對暴力法代碼示例
• Rabin-Karp 代碼示例
• KMP 字元串比對算法視訊
• 字元串比對的 KMP 算法

第9周作業

簡單

• 字元串中的第一個唯一字元

  （亞馬遜、微軟、Facebook 在半年内面試中考過）

• 反轉字元串 II （亞馬遜在半年内面試中考過）
• 翻轉字元串裡的單詞（微軟、位元組跳動、蘋果在半年内面試中考過）
• 反轉字元串中的單詞 III （微軟、位元組跳動、華為在半年内面試中考過）
• 僅僅反轉字母（位元組跳動在半年内面試中考過）
• 同構字元串（谷歌、亞馬遜、微軟在半年内面試中考過）

• 驗證回文字元串 Ⅱ（Facebook 在半年内面試中常考）

  中等

• 在學習總結中，寫出不同路徑 2 這道題目的狀态轉移方程。
• 最長上升子序列（位元組跳動、亞馬遜、微軟在半年内面試中考過）
• 解碼方法（位元組跳動、亞馬遜、Facebook 在半年内面試中考過）
• 字元串轉換整數 (atoi) （亞馬遜、微軟、Facebook 在半年内面試中考過）
• 找到字元串中所有字母異位詞（Facebook 在半年内面試中常考）

• 最長回文子串（亞馬遜、位元組跳動、華為在半年内面試中常考）

  困難

• 最長有效括号（亞馬遜、位元組跳動、華為在半年内面試中考過）
• 賽車（谷歌在半年内面試中考過）
• 通配符比對（Facebook、微軟、位元組跳動在半年内面試中考過）
• 不同的子序列（MathWorks 在半年内面試中考過）