数据结构

数据结构的存储方式只有两种：数组（顺序存储）和链表（链式存储）。

「队列」、「栈」这两种数据结构既可以使用链表也可以使用数组实现。

「图」的两种表示方法，邻接表就是链表，邻接矩阵就是二维数组。

「散列表」就是通过散列函数把键映射到一个大数组里。

「树」，用数组实现就是「堆」，因为「堆」是一个完全二叉树；用链表实现就是很常见的那种「树」，在这种链表「树」结构之上，又衍生出各种巧妙的设计，比如二叉搜索树、AVL 树、红黑树、区间树、B 树等等，以应对不同的问题。

数组和链表的区别

数据结构的基本操作：增删改查，如何遍历+访问呢？线性的和非线性的，线性就是 for/while 迭代为代表，非线性就是递归为代表。。

算法的本质是穷举：

1、如何穷举？

2、如何聪明地穷举？

数组

滑动窗口：快慢双指针，快慢指针中间就是滑动的「窗口」
一般求子序列，通过一定条件下 使用快指针扩展窗口， 使用慢指针收缩窗口

子串：原序列中必须连续的一段 子序列：原序列中可以不连续的一段 注意：无论是子串和子序列，元素的顺序都是原序列中的顺序

数组最大连续项的和
数组最大子项的和

链表

1、反转链表
双指针法和递归法
双指针法时间复杂度O(N)，空间复杂度O(1)
递归法时间复杂度O(N)，空间复杂度O(N)
使用pre，cur，保存cur.next，只需cur.next=pre，最后的pre即结果
2、两两交换链表中的节点
最好画图！
使用虚拟头结点，否则不方便返回结果
使用first，second，third三个变量调整指向，最后first=second；

双指针

二分搜索：两端向中心的双指针

回文串

二叉树

本质是穷举二（多）叉树，有机会的话通过剪枝或者备忘录的方式减少冗余计算，提高效率。

图论相关的算法也是二叉树算法的延续

回溯算法DFS

https://mp.weixin.qq.com/s/nMUHqvwzG2LmWA9jMIHwQQ

无重叠子问题穷举所有可能。(什么叫无重叠子问题，什么时候必须用回溯算法呢？)

解决一个回溯问题，实际上就是一个决策树的遍历过程。

1、路径：也就是已经做出的选择。

2、选择列表：也就是你当前可以做的选择。

3、结束条件

写backtrack函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。

  1. for 选择 in 选择列表:
  2.     //做选择
  3.     路径.add(选择)
  4.     backtrack(路径, 选择列表)
  5.     //撤销选择
  6.     路径.remove(选择)

动态规划

什么是动态规划：动态规划中每一个状态一定是由上一个状态推导出来的，然后得出全局最优。如果某一问题有很多重叠子问题，使用动态规划是最有效的。（而贪心没有状态推导，是从局部直接选最优的。）

动态规划五部曲：

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

先考虑自顶向下暴力解法（递归），得出状态转移方程（定义 dp 数组/函数的含义），加入备忘录消除重叠子问题，再将其转化为自顶向上的解法（迭代）。

背包问题

0-1背包

每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

  1. for(int i = 0; i < weight.size(); i++) { // 遍历物品
  2.     for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
  3.         dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  4.     }
  5. }

内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。

完全背包

每件物品都有无限个（也就是可以放入背包多次）

01背包和完全背包唯一不同就是体现在遍历顺序上

  1. // 先遍历物品，再遍历背包
  2. for(int i = 0; i < weight.size(); i++) { // 遍历物品
  3.     for(int j = weight[i]; j < bagWeight ; j++) { // 遍历背包容量
  4.         dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  6.     }
  7. }

排列背包

组合不强调顺序，(1,5)和(5,1)是同一个组合。

排列强调顺序，(1,5)和(5,1)是两个不同的排列。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

因为如果把遍历nums（物品）放在外循环，遍历target的作为内循环的话，举一个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合，因为nums遍历放在外层，3只能出现在1后面！

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

可以使用动态规划，也可以使用贪心算法

BFS

找到的路径一定是最短的

起点 步数 已访问路径 扩散结果队列 终点 【遍历扩散结果队列，并将队列里节点的相邻节点加入队列】

  1. // 计算从起点 start 到终点 target 的最近距离
  2. int BFS(Node start, Node target) {
  3.     Queue<Node> q; // 扩散结果队列
  4.     Set<Node> visited; // 已访问路径,避免走回头路
  6.     q.offer(start); // 将起点加入队列
  7.     visited.add(start);
  8.     int step = 0; // 记录扩散的步数
  10.     while (q not empty) {
  11.         int sz = q.size();
  12.         /* 将当前队列中的所有节点向四周扩散 */
  13.         for (int i = 0; i < sz; i++) {
  14.             Node cur = q.poll();
  15.             /* 划重点：这里判断是否到达终点 */
  16.             if (cur is target)
  17.                 return step;
  18.             /* 将 cur 的相邻节点加入队列 */
  19.             for (Node x : cur.adj())
  20.                 if (x not in visited) {
  21.                     q.offer(x);
  22.                     visited.add(x);
  23.                 }
  24.         }
  25.         /* 划重点：更新步数在这里 */
  26.         step++;
  27.     }
  28. }

例题：752 解开密码锁的最少次数

BFS空间复杂度高，若找最短路径的时候使用 BFS，其他时候还是 DFS 使用得多一些。

堆

双向BFS优化，提升效率，但必须知道终点在哪，不再使用队列，而是使用 HashSet 方便快速判断两个集合是否有交集。

贪心算法

https://mp.weixin.qq.com/s/NpEHIpemv4b74BUTOWekQw

手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。

贪心算法一般分为如下四步：

  • 将问题分解为若干个子问题
  • 找出适合的贪心策略
  • 求解每一个子问题的最优解
  • 将局部最优解堆叠成全局最优解

分治算法

https://mp.weixin.qq.com/s/fcCJFk89w953gXDjnlZFIA

最典型的分治算法就是归并排序了，核心逻辑如下：

  1. void sort(int[] nums, int lo, int hi) {
  2.     int mid = (lo + hi) / 2;
  3.     /****** 分 ******/
  4.     // 对数组的两部分分别排序
  5.     sort(nums, lo, mid);
  6.     sort(nums, mid + 1, hi);
  7.     /****** 治 ******/
  8.     // 合并两个排好序的子数组
  9.     merge(nums, lo, mid, hi);
  10. }

「对数组排序」是一个可以运用分治思想的算法问题，只要我先把数组的左半部分排序，再把右半部分排序，最后把两部分合并，不就是对整个数组排序了吗？

快速排序
https://mp.weixin.qq.com/s/8ZTMhvHJK_He48PpSt_AmQ

排序算法

一些特殊算法

LRU缓存算法

LCS最长公共子序列

子序列和子串的区别
最长公共子串