# 数据结构与算法

## 目录结构

一、常用数据结构

1. 数组、字符串

2. 链表

3. 栈

4. 队列

5. 双端队列

6. 树

二、高级数据结构

1. 优先队列

2. 图

3. 前缀树

4. 线段树

5. 树状数组

三、排序

1. 基本的排序算法

• 1.冒泡排序（Bubble Sort）
• 2. 插入排序（Insertion Sort）

2. 常考的排序算法

• 1. 归并排序（Merge Sort）
• 2. 快速排序（Quick Sort）
• 3. 拓扑排序（Topological Sort）

3. 其他排序算法

• 1. 堆排序（Heap Sort）
• 2. 桶排序（Bucket Sort)

四、递归与回溯

五、深度与广度优先搜索

六、动态规划

七、二分搜索与贪婪

八、大厂算法面试题

## 算法基础知识

## 一、常用数据结构

### 1. 数组、字符串

- 很多时候，在分析字符串相关面试题的过程中，我们往往要针对字符串当中的每一个字符进行分析和处理，甚至有时候我们得先把给定的字符串转换成字符数组之后再进行分析和处理

### 2. 链表

1. 单链表：链表中的每个元素实际上是一个单独的对象，而所有对象都通过每个元素中的引用字段链接在一起。

2. 双链表：与单链表不同的是，双链表的每个结点中都含有两个引用字段。

3. 链表的优点如下：

• 1. 链表能灵活地分配内存空间；
• 2. 能在 O(1) 时间内删除或者添加元素，前提是该元素的前一个元素已知，当然也取决于是单链表还是双链表，在双链表中，如果已知该元素的后一个元素，同样可以在 O(1) 时间内删除或者添加该元素。

4. 链表的缺点是：不像数组能通过下标迅速读取元素，每次都要从链表头开始一个一个读取；

• 1. 查询第 k 个元素需要 O(k) 时间。
• 2. 应用场景：如果要解决的问题里面需要很多快速查询，链表可能并不适合；如果遇到的问题中，数据的元素个数不确定，而且需要经常进行数据的添加和删除，那么链表会比较合适。而如果数据元素大小确定，删除插入的操作并不多，那么数组可能更适合。

5. 经典解题算法

• 1. 利用快慢指针（有时候需要用到三个指针）
• 2. 构建一个虚假的链表头

### 3. 栈

1. 特点：栈的最大特点就是后进先出（LIFO）。对于栈中的数据来说，所有操作都是在栈的顶部完成的，只可以查看栈顶部的元素，只能够向栈的顶部压⼊数据，也只能从栈的顶部弹出数据。

2. 实现：利用一个单链表来实现栈的数据结构。而且，因为我们都只针对栈顶元素进行操作，所以借用单链表的头就能让所有栈的操作在 O(1) 的时间内完成。

3. 应用场景：在解决某个问题的时候，只要求关心最近一次的操作，并且在操作完成了之后，需要向前查找到更前一次的操作。

### 4. 队列

1. 特点：和栈不同，队列的最大特点是先进先出（FIFO），就好像按顺序排队一样。对于队列的数据来说，我们只允许在队尾查看和添加数据，在队头查看和删除数据。

2. 实现：可以借助双链表来实现队列。双链表的头指针允许在队头查看和删除数据，而双链表的尾指针允许我们在队尾查看和添加数据。

3. 应用场景：直观来看，当我们需要按照一定的顺序来处理数据，而该数据的数据量在不断地变化的时候，则需要队列来帮助解题。在算法面试题当中，广度优先搜索（Breadth-First Search）是运用队列最多的地方，我们将在第 06 课时中详细介绍。

### 5. 双端队列

1. 特点：双端队列和普通队列最大的不同在于，它允许我们在队列的头尾两端都能在 O(1) 的时间内进行数据的查看、添加和删除。

2. 实现：与队列相似，我们可以利用一个双链表实现双端队列。

3. 应用场景：双端队列最常用的地方就是实现一个长度动态变化的窗口或者连续区间，而动态窗口这种数据结构在很多题目里都有运用。

### 6. 树

1. 树的结构十分直观，而树的很多概念定义都有一个相同的特点：递归，也就是说，一棵树要满足某种性质，往往要求每个节点都必须满足。例如，在定义一棵二叉搜索树时，每个节点也都必须是一棵二叉搜索树。

2. 树的形状

在面试中常考的树的形状有：普通二叉树、平衡二叉树、完全二叉树、二叉搜索树、四叉树（Quadtree）、多叉树（N-ary Tree）。

3. 树的遍历

• 1. 前序遍历（Preorder Traversal）
• 2. 方法：先访问根节点，然后访问左子树，最后访问右子树。在访问左、右子树的时候，同样，先访问子树的根节点，再访问子树根节点的左子树和右子树，这是一个不断递归的过程。
• 3. 应用场景：运用最多的场合包括在树里进行搜索以及创建一棵新的树。

4. 中序遍历（Inorder Traversal）

• 1. 方法：先访问左子树，然后访问根节点，最后访问右子树，在访问左、右子树的时候，同样，先访问子树的左边，再访问子树的根节点，最后再访问子树的右边。
• 2. 应用场景：最常见的是二叉搜索树，由于二叉搜索树的性质就是左孩子小于根节点，根节点小于右孩子，对二叉搜索树进行中序遍历的时候，被访问到的节点大小是按顺序进行的。

5. 后序遍历（Postorder Traversal）

• 1. 方法：先访问左子树，然后访问右子树，最后访问根节点。
• 2. 应用场景：在对某个节点进行分析的时候，需要来自左子树和右子树的信息。收集信息的操作是从树的底部不断地往上进行，好比你在修剪一棵树的叶子，修剪的方法是从外面不断地往根部将叶子一片片地修剪掉。

## 二、高级数据结构

### 1. 优先队列

1. 特点

1. 能保证每次取出的元素都是队列中优先级别最高的。优先级别可以是自定义的，例如，数据的数值越大，优先级越高；或者数据的数值越小，优先级越高。优先级别甚至可以通过各种复杂的计算得到。

2. 应用场景

1. 从一堆杂乱无章的数据当中按照一定的顺序（或者优先级）逐步地筛选出部分乃至全部的数据。

3. 优先队列最基本的操作有两个。

• 1. 向上筛选（sift up / bubble up）
• 2. 向下筛选（sift down / bubble down）

4. 初始化

1. 优先队列的初始化是一个最重要的时间复杂度，是分析运用优先队列性能时必不可少的，也是经常容易弄错的地方。

### 2. 图

#### 2.1 基本知识点

1. 阶（Order）、度：出度（Out-Degree）、入度（In-Degree）

2. 树（Tree）、森林（Forest）、环（Loop）

3. 有向图（Directed Graph）、无向图（Undirected Graph）、完全有向图、完全无向图

4. 连通图（Connected Graph）、连通分量（Connected Component）

5. 存储和表达方式：邻接矩阵（Adjacency Matrix）、邻接链表（Adjacency List）

#### 2.2 围绕图的算法

1. 图的遍历：深度优先、广度优先

2. 环的检测：有向图、无向图

3. 拓扑排序

4. 最短路径算法：Dijkstra、Bellman-Ford、Floyd Warshall

5. 连通性相关算法：Kosaraju、Tarjan、求解孤岛的数量、判断是否为树

6. 图的着色、旅行商问题等

#### 2.3 必须掌握

1. 图的存储和表达方式：邻接矩阵（Adjacency Matrix）、邻接链表（Adjacency List）

2. 图的遍历：深度优先、广度优先

3. 二部图的检测（Bipartite）、树的检测、环的检测：有向图、无向图

4. 拓扑排序

5. 联合-查找算法（Union-Find）

6. 最短路径：Dijkstra、Bellman-Ford

### 3. 前缀树

1. 应用场景

1. 前缀树被广泛地运用在字典查找当中，也被称为字典树。

2. 前缀树最基本的操作就是两个：创建和搜索。

1. 创建

2. 搜索

### 4. 线段树 - 参考附录1

### 5. 树状数组 - 参考附录1

## 三、排序 - 参考附录2

### 1. 基本的排序算法

1. 冒泡排序（Bubble Sort）

2. 插入排序（Insertion Sort）

### 2. 常考的排序算法

1. 归并排序（Merge Sort）

2. 快速排序（Quick Sort）

3. 拓扑排序（Topological Sort）

### 3. 其他排序算法

4. 堆排序（Heap Sort）

5. 桶排序（Bucket Sort)

## 四、递归与回溯

### 递归算法

1. 算法思想

1. 递归算法是一种调用自身函数的算法（二叉树的许多性质在定义上就满足递归）。

2. 分析递归算法推荐两种方法：

1. 迭代法

2. 公式法

### 回溯算法

1. 算法思想

1. 回溯实际上是一种试探算法，这种算法跟暴力搜索最大的不同在于，在回溯算法里，是一步一步地小心翼翼地进行向前试探，会对每一步探测到的情况进行评估，如果当前的情况已经无法满足要求，那么就没有必要继续进行下去，也就是说，它可以帮助我们避免走很多的弯路。

2. 回溯算法的特点在于，当出现非法的情况时，算法可以回退到之前的情景，可以是返回一步，有时候甚至可以返回多步，然后再去尝试别的路径和办法。这也就意味着，想要采用回溯算法，就必须保证，每次都有多种尝试的可能。

2. 解题模板

• 1. 判断当前情况是否非法，如果非法就立即返回；
• 2. 当前情况是否已经满足递归结束条件，如果是就将当前结果保存起来并返回；
• 3. 当前情况下，遍历所有可能出现的情况并进行下一步的尝试；
• 4. 递归完毕后，立即回溯，回溯的方法就是取消前一步进行的尝试。

## 五、深度与广度优先 - 参考附录1

### 深度优先

### 广度优先

## 六、动态规划 - 参考附录1

## 七、二分查找与贪婪算法 - 参考附录1

# 大厂算法面试题解析

字节，腾讯，百度，阿里，美团算法题，一共有500多道，都有详细的分析及答案，目录如下

## 一、动态规划

493. 动态规划解打家劫舍III

492. 动态规划和贪心算法解买卖股票的最佳时机II

490. 动态规划和双指针解买卖股票的最佳时机

486. 动态规划解最大子序和

477. 动态规划解按摩师的最长预约时间

465. 递归和动态规划解三角形最小路径和

430. 剑指 Offer-动态规划求正则表达式匹配

423. 动态规划和递归解最小路径和

413. 动态规划求最长上升子序列

411. 动态规划和递归求不同路径 II

409. 动态规划求不同路径

407. 动态规划和滑动窗口解决最长重复子数组

395. 动态规划解通配符匹配问题

376. 动态规划之编辑距离

370. 最长公共子串和子序列

## 二、回溯算法

498. 回溯算法解活字印刷

491. 回溯算法解将数组拆分成斐波那契序列

478. 回溯算法解单词搜索

451. 回溯和位运算解子集

450. 什么叫回溯算法，一看就会，一写就废

448. 组合的几种解决方式

446. 回溯算法解黄金矿工问题

442. 剑指 Offer-回溯算法解二叉树中和为某一值的路径

420. 剑指 Offer-回溯算法解矩阵中的路径

391. 回溯算法求组合问题

## 三、贪心算法

501. 贪心算法解分发饼干

489. 柠檬水找零

## 四，DFS和BFS相关算法

473. BFS解单词接龙

470. DFS和BFS解合并二叉树

455. DFS和BFS解被围绕的区域

453. DFS和BFS解求根到叶子节点数字之和

445. BFS和DFS两种方式解岛屿数量

422. 剑指 Offer-使用DFS和BFS解机器人的运动范围

417. BFS和DFS两种方式求岛屿的最大面积

## 五、双指针相关

497. 双指针验证回文串

466. 使用快慢指针把有序链表转换二叉搜索树

449. 快慢指针解决环形链表

447. 双指针解旋转链表

398. 双指针求无重复字符的最长子串

397. 双指针求接雨水问题

396. 双指针求盛最多水的容器

## 六、二叉树相关

488. 二叉树的Morris中序和前序遍历

485. 递归和非递归两种方式解相同的树

483. 完全二叉树的节点个数

474. 翻转二叉树的多种解决方式

471. 二叉搜索树中的插入操作

464. BFS和DFS解二叉树的所有路径

458. 填充每个节点的下一个右侧节点指针 II

457. 二叉搜索树的最近公共祖先

456. 解二叉树的右视图的两种方式

444. 二叉树的序列化与反序列化

441. 剑指 Offer-二叉搜索树的后序遍历序列

440. 剑指 Offer-从上到下打印二叉树 II

439. 剑指 Offer-从上到下打印二叉树

435. 剑指 Offer-对称的二叉树

434. 剑指 Offer-二叉树的镜像

433. 剑指 Offer-树的子结构

414. 剑指 Offer-重建二叉树

403. 验证二叉搜索树

401. 删除二叉搜索树中的节点

400. 二叉树的锯齿形层次遍历

399. 从前序与中序遍历序列构造二叉树

388. 先序遍历构造二叉树

387. 二叉树中的最大路径和

375. 在每个树行中找最大值

374. 二叉树的最小深度

372. 二叉树的最近公共祖先

367. 二叉树的最大深度

## 七、链表相关

463. 判断回文链表的3种方式

462. 找出两个链表的第一个公共节点

461. 两两交换链表中的节点

460. 快慢指针解环形链表 II

459. 删除链表的倒数第N个节点的3种方式

432. 剑指 Offer-反转链表的3种方式

431. 剑指 Offer-链表中倒数第k个节点

429. 剑指 Offer-删除链表的节点

410. 剑指 Offer-从尾到头打印链表

386. 链表中的下一个更大节点

381. 合并两个有序链表（易）

## 八，栈相关

500. 验证栈序列

438. 剑指 Offer-栈的压入、弹出序列

437. 剑指 Offer-包含min函数的栈

416. 剑指 Offer-用两个栈实现队列

## 九、其他经典算法

426，什么是递归，通过这篇文章，让你彻底搞懂递归

394，经典的八皇后问题和N皇后问题

389，两个超级大数相加

371，背包问题系列之-基础背包问题

366，约瑟夫环

362，汉诺塔

356，青蛙跳台阶相关问题

## 十、位运算相关

499. 位运算解只出现一次的数字III

495. 位运算等多种方式解找不同

494. 位运算解只出现一次的数字

476. 根据数字二进制下1的数目排序

469. 位运算求最小的2的n次方

425. 剑指 Offer-二进制中1的个数

383. 不使用“+”,“-”,“×”,“÷”实现四则运算

361. 交替位二进制数

364. 位1的个数系列（一）

385. 位1的个数系列（二）

402. 位1的个数系列（三）

357. 交换两个数字的值

## 十一、常见数据结构

348. 数据结构-1,数组

352. 数据结构-2,链表

359. 数据结构-3,队列

363. 数据结构-4,栈

368. 数据结构-5,散列表

373. 数据结构-6,树

378. 数据结构-7,堆

## 十二、常见排序算法

101. 排序-冒泡排序

102. 排序-选择排序

103. 排序-插入排序

104. 排序-快速排序

105. 排序-归并排序

106. 排序-堆排序

107. 排序-桶排序

108. 排序-基数排序

109. 排序-希尔排序

110. 排序-计数排序

111. 排序-位图排序

112. 排序-其他排序

## 十三、常见查找算法

201. 查找-顺序查找

202. 查找-二分法查找

203. 查找-插值查找

204. 查找-斐波那契查找

205. 查找-分块查找

206. 查找-哈希查找

207. 查找-其他查找

## 十四、其他算法

496. 字符串中的第一个唯一字符

487. 重构字符串

484. 打家劫舍 II

482. 上升下降字符串

481. 用最少数量的箭引爆气球

480. 移动零

479. 递归方式解打家劫舍

475. 有效的山脉数组

472. 插入区间

468. 提莫攻击的两种解决方式

467. 递归和非递归解路径总和问题

454. 字母异位词分组

452. 跳跃游戏

443. 滑动窗口最大值

436. 剑指 Offer-顺时针打印矩阵

428. 剑指 Offer-打印从1到最大的n位数

427. 剑指 Offer-数值的整数次方

424. 剑指 Offer-剪绳子

421. 在排序数组中查找元素的第一个和最后一个位置

419. 剑指 Offer-旋转数组的最小数字

418. 剑指 Offer-斐波那契数列

415. 最佳观光组合

412. 判断子序列

408. 剑指 Offer-替换空格

406. 剑指 Offer-二维数组中的查找

405. 换酒问题

404. 剑指 Offer-数组中重复的数字

393. 括号生成

390. 长度最小的子数组

384. 整数反转

382. 每日温度的5种解题思路

380. 缺失的第一个正数（中）

379. 柱状图中最大的矩形（难）

377. 调整数组顺序使奇数位于偶数前面

369. 整数替换

365. 消除游戏

360. 等差数列划分

358. 移掉K位数字

355. 两数相加 II

354. 字典序排数

353. 打乱数组

351. 最少移动次数使数组元素相等 II

350. 有序矩阵中第K小的元素

349. 组合总和 Ⅳ

347. 猜数字大小 II

346. 查找和最小的K对数字

345. 超级次方

344. 最大整除子集

343. 水壶问题

342. 计算各个位数不同的数字个数

## 附录（参考学习资料）

- 附录1：拉勾教育-300分钟搞定数据结构与算法

- 附录2：[买什么数据结构与算法，这里有：动态图解十大经典排序……](
https://www.toutiao.com/a6626655319999119876)

- 附录3：[数据结构和算法试题大全](
https://www.toutiao.com/i6903421300237353476/)

- 附录4：头条账号：动画学编程

- 附录5：《数据结构与算法分析：Java语言描述（原书第3版）》

- 附录6：《算法导论》