劍指offer刷題筆記彙總

轉載請注明作者和出處： http://blog.csdn.net/john_bh/

文章目錄

• • 1. 劍指offer 介紹
  • 2. 題目分類
  • • 2.1 資料結構類
    • 2.2 具體算法類題目

1. 劍指offer 介紹

《劍指offer》剖析了80個典型的程式設計面試題，系統整理基礎知識、代碼品質、解題思路、優化效率和綜合能力這5個面試要點。

如果是單純的面試需求，劍指offer的優先級肯定是在Leetcode之前，總的說它有三個優點：

1. 很可能在面試中出現原題
2. 約66題，題量少，但是涵蓋的内容較全
3. 能培養一個良好的刷題習慣

缺點是：

1. 隻有66題，刷着容易過拟合
2. 動态規劃的題比較少，是以需要在Leetcode上專項訓練。

基本每道題都很精彩，是以這裡就不一一洗寫了，題解可以看看我的代碼倉庫或者讨論區的内容。

2. 題目分類

算法題主要分成資料結構和具體算法部分，簡單歸類如下。

2.1 資料結構類

LinkedList

• 003-從尾到頭列印連結清單
• 014-連結清單中倒數第k個結點
• 015-反轉連結清單
• 016-合并兩個或k個有序連結清單
• 025-複雜連結清單的複制
• 036-兩個連結清單的第一個公共結點
• 055-連結清單中環的入口結點
• 056-删除連結清單中重複的結點

Tree

• 004-重建二叉樹
• 017-樹的子結構
• 018-二叉樹的鏡像
• 022-從上往下列印二叉樹
• 023-二叉搜尋樹的後序周遊序列
• 024-二叉樹中和為某一值的路徑
• 026-二叉搜尋樹與雙向連結清單
• 038-二叉樹的深度
• 039-平衡二叉樹
• 057-二叉樹的下一個結點
• 058-對稱的二叉樹
• 059-按之字形順序列印二叉樹
• 060-把二叉樹列印成多行
• 061-序列化二叉樹
• 062-二叉搜尋樹的第k個結點

Stack & Queue

• 005-用兩個棧實作隊列
• 020-包含min函數的棧
• 021-棧的壓入、彈出序列
• 044-翻轉單詞順序列(棧)
• 064-滑動視窗的最大值(雙端隊列)

Heap

• 029-最小的K個數

Hash Table

• 034-第一個隻出現一次的字元

圖

• 065-矩陣中的路徑(BFS)
• 066-機器人的運動範圍(DFS)

2.2 具體算法類題目

斐波那契數列

• 007-斐波拉契數列
• 008-跳台階
• 009-變态跳台階
• 010-矩形覆寫

搜尋算法

• 003-二維數組查找
• 006-旋轉數組的最小數字（二分查找）
• 037-數字在排序數組中出現的次數（二分查找）

全排列

• 027-字元串的排列

動态規劃

• 030-連續子數組的最大和
• 052-正規表達式比對(我用的暴力)

回溯

• 065-矩陣中的路徑(BFS)
• 066-機器人的運動範圍(DFS)

排序

• 035-數組中的逆序對(歸并排序)
• 029-最小的K個數(堆排序)
• 029-最小的K個數(快速排序)

位運算

• 011-二進制中1的個數
• 012-數值的整數次方
• 040-數組中隻出現一次的數字

其他算法

• 004-替換空格
• 013-調整數組順序使奇數位于偶數前面
• 028-數組中出現次數超過一半的數字
• 031-整數中1出現的次數（從1到n整數中1出現的次數）
• 032-把數組排成最小的數
• 033-醜數
• 041-和為S的連續正數序列(滑動視窗思想)
• 042-和為S的兩個數字(雙指針思想)
• 043-左旋轉字元串(矩陣翻轉)
• 046-孩子們的遊戲-圓圈中最後剩下的數(約瑟夫環)
• 051-建構乘積數組

python 實作連結