https://houbb.github.io/2020/01/23/data-struct-learn-07-base https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/px2ds5/

数据对象操作 1）算术运算：加减乘除等运算 2）逻辑运算：或、且、非等运算 3）关系运算：大于、小于、等于、不等于等运算 4）数据传输：输入、输出、赋值等运算

结构： 递归 迭代

https://en.wikipedia.org/wiki/Algorithmic_paradigm 穷举法、分治法、动态规划、贪心法、回溯法、分枝定界法 剪枝搜索?

0.0.1 · 分治法(Divide-and-Conquer)：#

将原问题划分成n个规模较小而结构与原问题相似的子问题； 递归地解决这些子问题； 再合并其结果，就得到原问题的解。

分治模式在每一层递归上都有三个步骤：

1. 分解(Divide)：将原问题分解成一系列子问题；
2. 解决(Conquer)：递归地解决各个子问题。若子问题足够小，则直接求解。
3. 合并(Combine)：将子问题的结果合并成原问题的解。

合并排序(Merge Sort)是一个典型分治法的例子。其对应的直观的操作如下: 分解： 将n个元素分成各含n/2个元素的子序列； 解决：用合并排序法对两个子序列递归地排序； 合并：合并两个已排序的子序列以得到排序结果。

0.0.2 · 动态规划法

分治法是指将问题划分成一些独立的子问题，递归的求解各子问题，然后合并子问题的解而得到原问题的解。

与此不同，动态规划适用于子问题独立且重叠的情况，也就是各子问题包含公共的子子问题。 在这种情况下，若用分治法则会做许多不必要的工作，即重复地求解公共的子子问题。 动态规划算法对每个子子问题只求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。

动态规划算法的设计可以分为如下4个步骤：

1. 描述最优解的结构
2. 递归定义最优解的值
3. 按自底向上的方式计算最优解的值
4. 由计算出的结果构造一个最优解

适合采用动态规划方法的最优化问题中的两个要素：最优子结构和重叠子问题。

1. 最优子结构： 如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。
2. 重叠子问题： 适用于动态规划求解的最优子问题必须具有的第二个要素是子问题的空间要很小，也就是用来求解原问题的递归算法会反复地求解同样的子问题。 对两个子问题来说，如果它们确实是相同的子问题，只是作为不同问题的子问题出现的话，则它们是重叠的。

In a word, 分治法 —— 各子问题独立； 动态规划 —— 各子问题重叠。

算法导论： 动态规划要求其子问题既要独立又要重叠，这看上去似乎有些奇怪。 虽然这两点要求听起来可能矛盾的，但它们描述了两种不同的概念，而不是同一个问题的两个方面。 如果同一个问题的两个子问题不共享资源，则它们就是独立的。 对两个子问题俩说，如果它们确实是相同的子问题，只是作为不同问题的子问题出现的话，则它们是重叠的。

0.0.3 · 贪心算法

当前最优 —> 全局最优

贪心算法是使所做的选择看起来都是当前最佳的，期望通过所做的局部最优选择来产生出一个全局最优解。 贪心算法是通过做一系列的选择来给出某一问题的最优解，对算法中的每一个决策点，做一个当时看起来是最佳的选择。 贪心算法对大多数优化问题来说能产生最优解，但也不一定总是这样的。

贪心算法与动态规划与很多相似之处： 特别地，贪心算法适用的问题也是最优子结构。

贪心算法与动态规划显著的区别： 贪心算法通常是以自顶向下的方式使用最优子结构的，自顶向下地做出贪心选择，不断地将给定的问题实例归约为更小的问题。 贪心算法划分子问题的结果，通常是仅存在一个非空的子问题。

动态规划中，每一步都要做出选择，但是这些选择依赖于子问题的解，因此，解动态规划问题一般是自底向上，从小子问题处理至大子问题。 贪心算法会先做选择，在当时看起来是最优的选择，然后再求解上一步产生的一个结果子问题，而不是先寻找子问题的最优解，然后再做选择。 贪心算法只需考虑一个选择（即，贪心的选择）；在做贪心选择时，子问题之一必须是空的，因此只留下一个非空子问题。

0.0.4 · 回溯法 分支定界法

https://www.jianshu.com/p/c738c8262087

列出所有候选解，然后逐个检查，在检查所有或部分候选解之后，便可找到所需要的解。 回溯法和分支定界法是对候选解进行系统检查的两种方法。 这两种方法使最坏情况和一般情况下的求解时间大大减少。 事实上，这两种方法可以省去对很大一部分候选解的检查，同时还能够找到所需要的解。 一般回溯法使用深度优先方法搜索树，而分支定界法使用广度优先或最小耗费/最大收益的方式。 相对而言，分支定界法的空间需求比回溯法要大得多，因此当内存容量有限时，回溯法常常更容易成功。

0.0.5 · 回溯法

1. 定义一个解空间，它包含对问题实例的解；
2. 用适合于搜索的方式组织解空间；典型的组织方法是图或树；
3. 用深度优先方式搜索解空间，利用界定函数避免进入无解的子空间。

确定一个新到达的节点能否导致一个比当前最优解还要好的解，可加速对最优解的搜索过程。 如果不能，则移动到该节点的任何一颗子树都是无意义的，这个节点可被立即“杀死”。 用来杀死活动节点的策略称为界定函数（bounding function）。

0.0.6 · 分支定界法（branch and bound）#

分枝定界（branch and bound）是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对节点的扩充方式。

在分支限界法中，每一个活结点只有一次机会成为扩展结点。 活结点一旦成为扩展结点，就一次性产生其所有儿子结点。 在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 然后，从活结点表中取下一节点（优先队列中最大或最小值）成为当前扩展结点，并重复上述扩展过程。 这个过程一直持续到找到所需的解或活结点表为空时为止。

有两种常用的方法可用来选择下一个节点（也可能存在其他的方法）：

1. 先进先出（FIFO） 即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活节点表的性质与队列相同。
2. 最小耗费或最大收益法 在这种模式中，每个节点都有一个对应的耗费或收益。 如果查找一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个 E-节点就是具有最小耗费的活节点； 如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个 E节点是具有最大收益的活节点。

一般来说，在内存利用方面，回溯法优于分支定界法。 回溯法需要的内存是O(解空间的最长路径长度)，而分支定界法所占用的内存为O(解空间大小)。 因此在实际应用中，在回溯法还没有超出时间的上限之前，分支定界法已经超出了内存的上限。

https://www.programiz.com/dsa https://www.tutorialspoint.com/data_structures_algorithms/algorithms_basics.htm

算法： 查找算法、排序算法、搜索算法 动态规划、回溯算法、贪心算法、分治算法 位运算、双指针、模拟、数学

常见的数据结构可分为「线性数据结构」与「非线性数据结构」，具体为：「数组」、「链表」、「栈」、「队列」、「树」、「图」、「散列表」、「堆」。 数据结构： 数组、链表、栈、队列、 字符串、树、图、堆、哈希表

学习算法，是为了深刻理解问题；

算法三阶段：

1. 用编程语言能够解决问题

2. 熟悉算法背后的逻辑，可以使用纸笔解释清楚，证明其准确性与计算与分析大O运行时：推荐做一些抽象实现，并在多个问题里重复实现；

3. 第一次提交前多做检查，尽可能保证准确

role-of-algorithms

Linear search, binary search, quadratic sorting, quick sort, merge sort, heap sort, binary heap, growable array (aka ArrayList, vector), doubly-linked list, binary search tree, avl tree, red-black tree, B-tree, splay tree, hash table (chaining and open addressing), depth first search, breadth first search, topological sort, strongly connected components, minimal spanning tree (Prim & Kruskal), shortest paths (bfs, Dijkstra, Floyd–Warshall, Bellman–Ford), substring search (quadratic, Rabin-Karp, Boyer-Moore, Knuth-Morris-Pratt), trie, Aho-Corasick, dynamic programming (longest common subsequence, edit distance).

0.1 · algo#

0.1.1 · 概览


0.1.1.1 · 数据结构：

数组和链表为基础，还有散列表、栈与队列、树、堆、图、跳表…

0.1.1.2 · 算法：

两种循环（#迭代、递归）：递归（重复调用自身、满足终止条件时逐层返回）、迭代（上次结果做本次初始值、计数器结束循环）

范式：穷举，#分治（子问题独立：分解、解决、合并），#动态规划（子问题重叠：多阶段的依据当前状态进行决策且改变状态），#贪心（近似求解：拆解、子问题最优解、合并），#回溯（隐式DFS），#分支限定（隐式BFS）

应用：排序、搜索

0.1.1.3 · 复杂度：

以时间或空间衡量算法效率

0.1.2 · 数据结构

线性：元素之间一对一 树形：元素之间一对多 图形：元素之间多对多

存储：连续（数组）、离散（链表）

栈：先进后出 队列：先进先出；双向队列（两个方向都可进出）

哈希：映射、解决冲突（链式、开放地址）

树：层序遍历BFS；前、中、后序遍历DFS；

堆：大/小顶堆（二叉树、节点值大于子节点值）

图：顶点和边的集合；BFS、DFS

跳表：多层级链表，顶层是子层的子集；

0.1.3 · 算法

0.1.3.1 · 迭代、递归

递归一定是自上而下的；

Any recursive code can be written as iterative code with a loop and a stack. 任何递归都可以通过循环加栈的迭代形式完成。 Any iterative loop can be rewritten as a recursive function. 任何迭代形式的循环都可以通过递归形式完成。 递归用于处理：类树形结构（子结构与父结构类似）、涉及回溯、不深（太深导致栈溢出）。

0.1.3.2 · 分治

1. 递归的分解问题为独立子问题，直至最小子问题；
2. 从最小子问题，自底向上的将子问题的解合并；

0.1.3.3 · 动态规划

1. 分解问题为重叠子问题；
2. 解决子问题，并存储子问题的解，避免重复计算；

自顶向下的记忆化搜索（备忘录），递归拆解子问题，记录子问题的解； 自底向上的动态规划，迭代构建更大子问题的解；

0.1.3.4 · 贪心

每个决策阶段选择当前最优解，期望获取全局最优解；

0.1.3.5 · 回溯

通常采用深度优先遍历；

0.1.3.6 · 分支限定

通常采用广度优先遍历；

1 · alg#

labuladong

目标，可以量化的目标，清楚知道自己每一天需要做什么；
明白，清晰明白自己的目标；

1.1 · must read#

1.1.1 · 框架思维

数据结构的储存方式： 数组(顺序存储)、链表(链式储存)
数组： 紧凑连续存储，可以随机访问，索引快速找到原因，相对节约空间； 一次性分配、扩容需整体复制、插入删除需移动很多元素；
链表： 元素不连续，依靠指针指向下一个元素； 不能随机访问，相对消耗更多空间(指针的空间)；

数据结构基本操作: 遍历+访问 ； 增删改查；
线性：for/while迭代 为代表
非线性： 递归 为代表

刷体指南：
数据结构是工具、算法是通过合适的工具解决特定问题；
！先刷二叉树，培养框架思维；

void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}

很多动态规划问题就是在遍历一棵树；
回溯算法是个N叉树的前后序遍历问题；

1.1.2 · 动态规划 DP#

DP问题的一般形式，求最值；DP是运筹学的一种最优化方法；

DP的核心问题： 穷举； 存在重叠的子问题，需要备忘录或DP table 优化穷举过程，避免不必要计算；
且DP问题具备最优子结构，通过子问题的值得到原问题的值；

DP核心思想：穷举求最值；列出正确的状态转移方程正确的穷举；

DP三要素： 重叠子问题，最优子结构，状态转移方程(难，思维框架:明确base case -> 明确状态 -> 明确选择 -> 定义DP数组/函数的含义)；

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

1. 斐波那契数列： 重叠子问题

   1. 暴力递归 自顶向下 O(2^n)
      画出递归树，分析算法复杂度；时间复杂度计算：子问题个数*解决子问题时间；
      可以知道暴力递归的问题是存在大量重复计算，也就是重叠子问题；

   2. 带备忘录的递归 自顶向下 O(n)
      解决重复计算: 造一个备忘录(使用数组或哈希表)，每次遇到子问题，先去备忘录查有没有答案，没有再计算子问题且保存到备忘录；

   3. DP数组的迭代 自底向上 脱离递归，由循环迭代完成
      备忘录独立出来一张表，叫DP table，由此表完成自底向上的推算；
      状态转移：f(n)的状态n 由状态n-1 与状态 n-2 相加转移而来；
      状态压缩：每次状态转移的只需要DP table的一部分，尝试压缩DP table 的大小，只记录必要的数据；

2. 凑零钱问题(k种面值硬币，c1 .. ck，每种无限，给一个目标总金额，求凑出的最少硬币数量)： 状态转移方程

   1. 暴力递归 自顶向下，多叉树； 状态转移方程： base case，目标金额为0时，需要0数量；状态，目标金额的改变，向base的靠近；选择，每选择一种金币，目标金额随之改变；明确dp函数/数组，这里是递归的dp函数，参数是状态(会改变)；

   2. 带备忘录递归 通过备忘录消除子问题；

   3. DP数组迭代 自底向上，状态从0开始(0就是base case)，当状态变大至目标状态的时候(状态转移)，根据不同的选择进而分解成不同的子问题(也就是先前更小的状态)；

总结：
穷举，思考如何穷举，如何聪明的穷举；

1.1.3 · 回溯 backtracking#

回溯，就是DFS，本质上暴力穷举；

决策树的遍历过程：1.路径(已经作出的选择) 2.选择列表(当作可以作的选择) 3.结束条件(到达无法选择的条件)

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择(`选择项`不能重复则同时删除已选的`选择项`)
        backtrack(路径, 选择列表)
        撤销选择(该选择走不通，撤销选择，如做选择时删除了该`选择项`，则加回)

1. 全排列问题 定义的bt函数像一个指针在决策树上游走，同时维护每个节点的属性(路径、选择)，到达树的底层时，路径就是一个全排列； DFS,选择某层某个节点后，进入下一层，遍历此层所有可选的节点重复前面的操作(选择节点(进入节点前)，进入下一层)，在某一层做完所有有效选择后，回撤((离开节点后)当前节点路径上删除此次选择)；

2. N皇后问题： N×N 的棋盘，让你放置 N 个皇后，使得它们不能互相攻击(可以攻击同一行、同一列、左上左下右上右) 棋盘N行，每一行对应决策树每一层，某一行的有效格子就是可选的选择项(放置一个皇后)； 如何判断有效： 列是否冲突、右上方是否冲突、左上方是否冲突；

总结：
回溯，多叉树遍历(做选择)，在先序遍历(进入节点前执行，当前节点路径记录选择)与后序遍历(离开节点后执行，当前节点路径删除该节点，回撤)的位置做操作；

bt的路径、选择列表、结束条件 与 dp 的状态、选择、base case 相对应，前者自顶向下，后者自底向上；

1.1.4 · BFS#

问题抽象成图，一个点开始，向四周扩散； 使用队列，将一个节点的相邻节点加入队列； 与DFS相比，路径短，但空间复杂度大；

常见场景：图内找到从start到target的最短路径；

// 计算从起点 start 到终点 target 的最近距离
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路

    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

1. 二叉树的最小高度 root节点为start，叶子节点(没有子节点)为target；

2. 打开密码锁的最少次数

1.1.4.1 · 双向BFS优化#

双向BFS从起点和起点同时开始，当两边有交集的时候停止； 传统BFS单向，需要遍历整个树的节点，最后找到target；而双向BFS只遍历了半颗树就出现了交集，比传统高效；

1.1.5 · 二分搜索 binary search#

细节：mid 加一还是减一，while 判断用 <= 还是 < ；

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = left + (right - left) / 2;   // 与(left + right) / 2 结果相同，但防止left right都太大，相加导致溢出
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

1. 搜索一个元素： right的值是数组长度-1；使得两个区间都是左右都闭合 [left, right]的区间；
   while判断left<=right,终止条件是left==right+1,区间[right + 1, right]为空；若为等于，区间[right, right]不为空，漏了一个数；

   left = mid + 1，right = mid - 1 ：在之前已经判断过mid是否为target，无需mid了；

   缺陷：重复target出现，搜索target的左侧边界或右侧边界，无法处理；

2. target重复出现，搜索target的左、右边界：

   1. 左边界 right的值是数组长度； 每次的搜索区间都是左开右闭[left, right)； while判断left<right,终止条件left == right，搜索区间 [left, left) 为空； 返回left与right是一样的

      if (nums[mid] == target) {right = mid;} // 找到目标，定位为下一次搜索区间的右边界；由下面的left或right改变减小搜索区间；

      left = mid + 1，right = mid : 区间左开右闭，mid无意义；

      返回left；

      重新理解： 返回的值n(也就是left)，也就是数组下标n，在搜索左边界的时候，代表小于target的数字有n个(二分的前提是数组有序)； 所以n的取值区间是[0，数组长度]，n就是left，那left为数组长度的时候，就是target比所有数都大，返回-1；再判断定位到的某个区间是否等于target；

      明白搜索区间，保证区间内没有元素；

   2. 右边界
      大部分同左边界一致；

      if (nums[mid] == target) {left = mid + 1; } // 找到目标，定位为下一次搜索区间的左边界；由下面的left或right改变减小搜索区间；

      return left - 1; // while结束时， left = mid + 1 ，对应left下标的数组值一定不等于，left减1也就是mid可能等于；

总结：
划分搜索区间时，如果区间左右都闭，mid取值(left+right)/2;如果是左闭右开，mid为左时，需要排除，所以+1 ，而mid为右时，区间开的，不包括，所以直接用mid； 在判断是否结束时，也就是搜索区间内没有元素从而无法再划分时：区间左右都闭，终止条件为 left==right+1 (left<=right) ，左闭右开，终止条件为left==right (left<right)；搜索左右边界的时候，需要注意找不到越界的情况；

1.1.6 · 滑动窗口 sliding window#

链表、字串、数组 用双指针；

3种双指针： 快慢指针、左右指针、滑动窗口；

1. 快慢指针： #todo

2. 左右指针： #todo

3. 滑动窗口： 维护一个窗口，不断滑动，然后更新答案

// 不停移动右指针，当需要收缩窗口的时候，移动左指针； 时间复杂度是 O(N)
int left = 0, right = 0;

while (right < s.size()) {`
    // 增大窗口
    window.add(s[right]);
    right++;

    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}

1. 最小覆盖子串 right移动到满足要求，找到可行解； left移动，缩小窗口直到不满足要求； 重复以上，直到right到s串尾；

   使用计数器，记录窗口的字符出现次数与目标字符的次数；

2. 字符串排列

3. 找所有字母异位词

4. 最长无重复字串

总结：
left移动(收缩窗口)促发的条件？如何更新答案？结束滑动的条件？

1.1.7 · leetcode 股票买卖问题#

使用状态机，实际上就是DP table；

题目：给定一个数组，第i个元素是一支股票第i天的价格。计算所获得的最大利润，最多k笔交易，不能多笔交易(再次购买需出售之前的股票)； 解法：利用状态穷举； 总共几种状态，每个状态对应的选择，穷举的目的是根据对应的选择更新状态；

dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 择优(选择1，选择2...)

当前问题，三种选择：买入、卖出、无操作；但 卖出 得在 买入 之前 ，买入 得在 卖出之后， 无操作两种 买入后无操作 卖出后无操作； 还有交易次数k的限制；
三个状态： 天数n、交易次数K、持有状态(1持有 or 0未持有) dp[n][k][0 or 1]； 最终状态dp[n-1][k][0],最后一天最多k次交易不持有了所获得的利润； 状态转移：每种状态有什么选择且状态如何更新:状态是每天的利润
dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]) 今天没持有，要不昨天没持有，要不昨天持有但今天卖了；
dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]) 今天持有，要不昨天持有，要不昨天未持有但今天买了；
base case：
dp[-1][k][0] = 0 天数0开始，-1没开始，利润为0
dp[-1][k][1] = -infinity 还没开始，不可能持有
dp[-1][0][0] = 0 k=0 不允许交易，利润为0 dp[-1][0][1] = -infinity不允许交易，不可能持有

1.1.8 · leetcode 打家劫舍问题#

1. 给定一个代表每个房屋存放金额的非负整数数组，相邻的房屋同一晚上闯入会触发报警装置；计算一天晚上能偷窃的最高金额；

房子的索引是状态，抢或不抢是选择；

base case [n]=0 ，不抢，去下家再看，抢，只能去下下家看； 自顶向下，使用递归，存在重叠子问题(不同方式到达同一个房屋)，使用备忘录;

自底向上，状态转移只与dp[i]最近的两个状态有关；

2. 与题1基本一样，但是房子是一个圈；

三种情况，首尾都不抢，抢首不抢尾，抢尾不抢首；

比较情况中值最大的，事实考虑 抢首不抢尾 抢尾不抢首 即可，因为选择的余地更大；

3. 房子是一棵二叉树；

int rob(TreeNode root) {
    int[] res = dp(root);
    return Math.max(res[0], res[1]);
}

/* 返回一个大小为 2 的数组 arr
arr[0] 表示不抢 root 的话，得到的最大钱数
arr[1] 表示抢 root 的话，得到的最大钱数 */
int[] dp(TreeNode root) {
    if (root == null)
        return new int[]{0, 0};
    int[] left = dp(root.left);
    int[] right = dp(root.right);
    // 抢，下家就不能抢了
    int rob = root.val + left[0] + right[0];
    // 不抢，下家可抢可不抢，取决于收益大小
    int not_rob = Math.max(left[0], left[1])
                + Math.max(right[0], right[1]);

    return new int[]{not_rob, rob};
}

1.1.9 · 三道区间

区间问题，就是线段问题，合并所有线段、找出线段交集等等； 使用排序、画图的技巧；

1. 区间覆盖 给一个区间列表，删除列表中被其他区间所覆盖的区间(包含关系，删除被包含的)；

   排序(按照起点升序排列，起点相同时降序排列,保证更长者在上面)后，相邻区间三种关系：覆盖(前者包含后者)、相交、不相交，分别处理； 覆盖，结果+1；相交，合并；不相交，更新起点终点(循环新的开始)；

2. 区间合并 给出一个区间集合，合并所有重叠区间； 先排序，再观察规律； 几个相交区间的x ，x.start 一定是几个区间中最小的start ，x.end一定是几个区间中最大的end；

3. 区间交集 给定两个有一些闭区间组成的列表，每个区间列表成对不相交，且已经排序，返回者两个区间列表的交集； A [a1,a2] B[b1,b2]

if b2 < a1 or a2 < b1:
    [a1,a2] 和 [b1,b2] 无交集

# 上面逻辑的否命题是存在交集的条件 , 不等号取反，or 也要变成 and
if b2 >= a1 and a2 >= b1:
    [a1,a2] 和 [b1,b2] 存在交集

画出四种交集可能，交集区间是[c1,c2],规律c1=max(a1,b1)，c2=min(a2,b2)

两个数组的下标如何移动，区间尾对比大小；

1.1.10 · nSum 问题#

1. 2Sum:
   结果只有一对：排序，双指针；
   结果有多对且不能重复时：排序，双指针，找到满足的结果时，需要跳过相同的元素；

2. 3Sum:
   包含n个整数的数组nums，nums中三个元素a b c，使得a+b+c=0? 找出所有满足且不重复的三元组； 穷举，确定第一个数后，剩下的两个数就是2Sum问题了；

3. 4Sum： 穷举，确定第一个数后，剩下的三个数就是3Sum问题了；

4. nSum： 穷举第一个数，然后递归调用(n-1)Sum;

1.1.11 · 二叉树

/* 二叉树遍历框架 */
void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}

快速排序就是二叉树的前序遍历，归并排序就是二叉树的后续遍历；
快速排序：

void sort(int[] nums, int lo, int hi) {
    /****** 前序遍历位置 ******/
    // 通过交换元素构建分界点 p
    int p = partition(nums, lo, hi);
    /************************/

    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}

归并排序：

void sort(int[] nums, int lo, int hi) {
    int mid = (lo + hi) / 2;
    sort(nums, lo, mid);
    sort(nums, mid + 1, hi);

    /****** 后序遍历位置 ******/
    // 合并两个排好序的子数组
    merge(nums, lo, mid, hi);
    /************************/
}

递归算法：明确函数的定义，利用定义推导最终结果。清楚当前root节点应该做什么，在递归调用子节点；

二叉树，基本基于递归，先清楚root需要做什么，根据要求选择前序，中序，后序；

1. 翻转二叉树 把二叉树上的每一个节点的左右子节点进行交换，放在前序遍历的位置，后序也可以；

2. 填充完美二叉树节点的next右侧指针(同一层，右侧节点) 问题：跨父节点的两个相邻节点：增加函数参数，一个节点做不到，我们就给他安排两个节点，「将每一层二叉树节点连接起来」可以细化成「将每两个相邻节点都连接起来」；

// 定义：输入两个节点，将它俩连接起来
void connectTwoNode(Node node1, Node node2) {
    if (node1 == null || node2 == null) {
        return;
    }
    /**** 前序遍历位置 ****/
    // 将传入的两个节点连接
    node1.next = node2;

    // 连接相同父节点的两个子节点
    connectTwoNode(node1.left, node1.right);
    connectTwoNode(node2.left, node2.right);
    // 连接跨越父节点的两个子节点
    connectTwoNode(node1.right, node2.left);
}

3. 将二叉树展开为单链表 展开左节点，接着展开右节点，再把展开的右链接到左链后面，后序遍历；

1.1.12 · 0-1背包问题变体#

背包问题： 可装重量W的包，和N个物品，每个物品有重量和价值，第i个物品重量wt[i]，价值val[i]，求背包最多能装的价值？

分割等和子集：
给定一个包含正整数的非空数组，分割成两个子集，使得两个子集的元素和相等；
如何化解为背包问题， 数组sum/2 和 n个数，求是否有装法？
状态：背包的容量，可选的物品；选择：装进背包与否； dp数组： dp[i][j] = x表示，对于前i个物品，当前背包的容量为j时，若x为true，则说明可以恰好将背包装满，若x为false，则说明不能恰好将背包装满。
最终答案就是dp[n][sum/2], base case : dp[..][0] = true和dp[0][..] = false
选择： 当前容量为j的情况下，如果不把第i个物品放进包，能否装满取决于第i-1个物品；如果把第i个放进背包，能否装满取决于减去第i个的重量能否在i-1个时装满；
状态压缩：无论放不放，都取决于i-1，i可以省略；

1.2 · 数据结构

二分图：拥有特殊性质的图，使用两种颜色为所有定点着色，使任何一条边的两个定点颜色不同；常见操作如何判定；

1.2.1 · 链表

递归反转链表：不要跳进递归，使用明确的定义实现，将子问题看作已完成的状态，最后再补充base case；

1. 递归反转整个链表：

ListNode reverse(ListNode head) {
    if (head.next == null) return head;
    ListNode last = reverse(head.next); //箭头变化由 ->变为 <-
    head.next.next = head; // 将当前节点处理为 尾部节点
    head.next = null;
    return last;
}

2. 递归反转前N个节点 记录第N个节点，在前N个反转完成后，将尾部指针指向第N个节点；

3. 反转部分节点 m，n 前进到m-1，进行递归反转前N个节点；

ListNode reverseBetween(ListNode head, int m, int n) {
    // base case
    if (m == 1) {
        return reverseN(head, n);
    }
    // 前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

每K个一组进行反转：
与递归反转前N个节点相似，注意每一组反转后的指针连接；

// 迭代反转
// 反转以 a 为头结点的链表
ListNode reverse(ListNode a) {
    ListNode pre, cur, nxt;
    pre = null; cur = a; nxt = a;
    while (cur != null) {
        nxt = cur.next;
        // 逐个结点反转
        cur.next = pre;
        // 更新指针位置
        pre = cur;
        cur = nxt;
    }
    // 返回反转后的头结点
    return pre;
}

判断回文链表： 寻找的核心思想，从中心向两端拓展；
判断的核心思想，双指针，两端向中间逼近；

1. 判断回文单链表 1.单链表无法倒着遍历，无法使用双指针，可以反转后，再判断两者是否一致； 也可以使用遍历入栈，再出栈比较，利用栈的先进后出； 2.借助二叉树的后序遍历，不需显式反转能可以倒序遍历，

// 左侧指针
ListNode left;

boolean isPalindrome(ListNode head) {
    left = head;
    return traverse(head);
}

boolean traverse(ListNode right) {
    if (right == null) return true;
    boolean res = traverse(right.next);
    // 后序遍历代码
    res = res && (right.val == left.val);
    left = left.next;
    return res;
}

1.2.2 · 二叉树

根节点需要做什么，前/中/后序再处理其他；
二：

1. 数组构造最大二叉树： 根是数组最大元素，左子树是数组最大元素左边的最大二叉树，右子树是右边；

2. 通过前序、中序遍历结果构造二叉树；

3. 通过后序、中序遍历结果构造二叉树；

三：

1. 寻找重复的子树，给定二叉树，返回所有重复的子树，同一类的重复子树，返回任意一棵的根节点；
   后序遍历某节点，知道以自己为根的子树长什么样，lft，right，root序列化二叉树，#表示null空指针；
   借助外部数据，把每个节点子树序列化结果保存；保存的时候同时查询是否出现，即是否有重复；

二叉搜索树：BST, 节点值大于左子树，小于右子树，同时左右子树也是BST； 基于BST有AVL树 红黑树 B+树 线段树等等；
BST中序遍历为升序的；
一：

1. 二叉搜索树中第K小的元素；
   中序遍历后找第k个元素，时间复杂度为n； 第二种办法，节点记录额外信息size，以自己为根有多少节点，可以通过node.left的大小推导自己的排名，去对应子树进行查找，从而将时间复杂度降低为logn；

2. BST 转化累加树(node的值=原树中大于或等于node值的和) 利用二叉搜索树，中序遍历结果有序，先遍历右节点，再遍历左节点，结果为大->小；

二：
BST判断合法性、增、删、查；

1. 判断合法性 /* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */ boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {}

2. 插入 查找到插入位置，进行插入；

3. 删除 找到后，进行删除；但不能破坏BST的性质，修改调整； 1.删除的为末端节点，直接删除；
   2.删除的有一个非空子节点，接替自己的位置；
   3.删除的有两个非空子节点，找到左子树中最大节点、或者右子树最小节点，接替自己的位置；

4. 查找 遍历穷举；
   第二种办法，二分查找思想：

二叉树序列化：
遍历；前序、后序、层级迭代，重要的是反序列化的时候定位root节点；

对多叉树的理解：
迭代器惰性求值，先求出部分结果；

二叉树最近公共祖先：给定两个指定节点，找到最近公共祖先；
git rebase;

// 注意p,q必然存在树内, 且所有节点的值唯一!!!
// 递归思想, 对以root为根的(子)树进行查找p和q, 如果root == null || p || q 直接返回root
// 表示对于当前树的查找已经完毕, 否则对左右子树进行查找, 根据左右子树的返回值判断:
// 1. 左右子树的返回值都不为null, 由于值唯一左右子树的返回值就是p和q, 此时root为LCA
// 2. 如果左右子树返回值只有一个不为null, 说明只有p或q存在于左或右子树中, 返回回去，直到满足1
// 3. 左右子树返回值均为null, p和q均不在树中, 返回null
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // base case
    if (root == null) return null;
    if (root == p || root == q) return root;

    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // 情况 1
    if (left != null && right != null) {
        return root;  //注意是后序遍历，从下往上
    }
    // 情况 2
    if (left == null && right == null) {
        return null;
    }
    // 情况 3
    return left == null ? right : left;
}

根节点到达p、q的路径，装换为链边的公共节点问题；

完全二叉树节点数： 完全二叉树，每一层紧凑靠左；满二叉树，每一层都是满的； 满二叉树，节点数量和高度呈指数关系，时间复杂负O(logN)；
完全二叉树，结合满二叉树与普通二叉树；

// 时间复杂度 O(logN*logN)
public int countNodes(TreeNode root) {
    TreeNode l = root, r = root;
    // 记录左、右子树的高度
    int hl = 0, hr = 0;
    while (l != null) {
        l = l.left;
        hl++;
    }
    while (r != null) {
        r = r.right;
        hr++;
    }
    // 如果左右子树的高度相同，则是一棵满二叉树
    if (hl == hr) {
        return (int)Math.pow(2, hl) - 1;
    }
    // 如果左右高度不同，则按照普通二叉树的逻辑计算
    return 1 + countNodes(root.left) + countNodes(root.right);
}

1.2.3 · 数组

二分搜索：有序数组中搜索给定的某个目标值的索引；通过二分减枝；

1. KoKo吃香蕉 N堆香蕉，第i堆有piles[i]根香蕉，K根/小时吃，每个小时选一堆吃，此堆小于K，则吃完就行，在H小时内吃完，求最小K？
   暴力：K从1到最多香蕉的那堆香蕉数，遍历，满足情况则返回；遍历是线性的，可以用二分查找；

2. 货物运输 传送带上第i个包裹重量为weights[i]，每天按重量顺序装载包裹，求D天内的最低运载能力? 暴力：确认最小值(单个包裹最大)与最大值(所有包裹重量和+1)，然后遍历；遍历是线性的，用二分查找；

双指针：
快慢指针(主要是链表问题)、左右指针(主要是数组问题)、滑动窗口； 快慢指针：

1. 判断链表中是否含有环
   一快一慢，有环就会相遇；

2. 已知链表中含有环，返回这个环的起始位置 第一次相遇，快指针走2k，慢指针走k，环长k，任意一个点回到链表头重新出发，另一个从相遇点出发，再次相遇就是环起点；

3. 寻找链表的中点 一快一慢，快到达尾部，慢到达中部；

4. 寻找链表倒数第K个元素 快先走K，到达尾部时，慢在倒数第K个；

左右指针：

1. 二分查找
2. 两数之和
3. 反转数组
4. 滑动窗口

结合哈希表和数组，使得数组的删除和查找操作的时间复杂度为O(1);

1. 常数时间插入、删除、获取随机元素 将待操作元素与数组尾部元素进行交换；

2. 避开黑名单的随机数，等概率选区； 将黑名单元素移动到数组末尾；如果数组末尾也有黑名单，用hash存储黑名单的值，移动的时候进行判断；

数组去重：

1. 去除重复字母，不能打断字符出现的相对顺序，字典序最小(a-z);
   栈放入，数组记录是否在栈中，出栈顺序是反的，需要反转；满足去重与字符相对顺序； 插入时，判断待插入与栈顶元素大小，待插入元素大于栈顶 且 栈顶元素后面会再次出现(使用计数器)，则弹出栈顶，循环进行，最后放入待插入元素；

栈，先进后出，允许立即操作刚插入的字符；

原地修改数组：

1. 删除排序数组中的重复项 快慢指针
2. 删除有序列表的重复项 同上，快慢指针
3. 移除数组元素，原地移除数值等于val的元素； 快慢指针，fast遇到val，则天国，否则，赋值，同时slow+1;
4. 移动零，数组，原地修改，所有零到末尾； 移除所有0，再把后面的元素全部赋值为0；

2Sum核心思想： 无序的时候，利用hash表； 或者，在add一个新元素的时候，把其与其他元素的和全计算出来加进hash表，直接查询即可；

1.2.4 · 设计数据结构

Union-Find并查集：解决图论中的动态连通性；
连通：自反性、对称性、传递性； 实现API：q、p是否连通；图中有多少个连通分量；
数组模拟森林，节点 x 的父节点是 parent[x] ，利用while (parent[x] != x) x = parent[x];找到x的根节点；
优化平衡性： 在合并的时候，小树连接到大树的下面； 额外一个数组，记录以某节点为根的树的节点数；亦可以路径压缩parent[x] = parent[parent[x]];，缩短树的高度； 应用： 将原问题转化成图的动态连通性问题；

1. DFS替代方案 给你一个 M×N 的二维矩阵，其中包含字符X和O，让你找到矩阵中完全被X围住的O，并且把它们替换成X。
   二维转一维，（x,y）-> x * n + y ; 增加虚拟节点dummy(m*n)，将首行，末行，首列，末列的0与dummy相连；遍历所有节点，等于0的，如果上下左右有0，则让两者相连，最终会与dummy相连； int[][] d = new int[][]{{1,0}, {0,1}, {0,-1}, {-1,0}}; // 方向数组 d 是上下左右搜索的常用手法 x+1 y+1 y-1 x-1

主要思路是适时增加虚拟节点，想办法让元素「分门别类」，建立动态连通关系。

2. 判定合法算式 a==b或者a!=b 先遍历==，建立连通关系；在遍历！=，看是否存在连通，则不合法；

LRU：Least Recently Used
哈希链表；

LFU：Least frequently used
key-freq；freq-key；key-val表；变量minFreq

数据流的中位数：

有序数据结构；使用两个优先级队列；大顶堆、小顶堆(large堆的堆顶元素>=small堆的堆顶元素)(利用堆特性，保证两个堆的元素数量之差不大于 1)；

public void addNum(int num) {
    if (small.size() >= large.size()) {
        small.offer(num);
        large.offer(small.poll());
    } else {
        large.offer(num);
        small.offer(large.poll());
    }
}

design twitter:timeline
合并多个有序列表、面向对象设计； api: postTweet, getNewsFeed, follow, unfollow;

把用户各自的推文储存在链表里，每个链表节点储存文章id、时间戳，按time有序，如果某个用户关注了k个用户，那就可以合并k个有序链表；
实现合并k个有序链表的算法需要用到优先级队列，是二叉堆的重要应用： 可以将优先级队列，理解为对插入的元素自动排序,乱序的元素插入其中就被放在了正确的位置,可以从大到小或从小到大有序取出元素；

单调栈：
每次新元素入栈，站内的元素保持有序；

1. 下一个更大的元素
   给一个数组，返回一个等长数组，对应index储存着下一个更大的元素，如果没有，就存-1；

vector<int> nextGreaterElement(vector<int>& nums) {
    vector<int> res(nums.size()); // 存放答案的数组
    stack<int> s;
    // 倒着往栈里放
    for (int i = nums.size() - 1; i >= 0; i--) {
        // 判定个子高矮
        while (!s.empty() && s.top() <= nums[i]) {
            // 矮个起开，反正也被挡着了。。。
            s.pop();
        }
        // nums[i] 身后的 next great number
        res[i] = s.empty() ? -1 : s.top();
        //把自身放进去，被自己前面的数比较 
        s.push(nums[i]);
    }
    return res;
}

2. 一个月有多少天
   给一个数组T，存放着近几天的天气气温，返回一个等长数组，对于每一天，还需要等几天才能等到更加温和的气温，如果没有，就0；
   与1相似，但求距离；
   存储索引，相减得距离；

3. 环形数组，下一个更大的元素 数组使用%求余，获得下标，从而达到环形效果； 常用套路，数组长度翻倍；

单调队列：
队列中的元素单调递增或单调递减的；

1. 滑动窗口最大值：给定一个数组nums，和一个正整数k，又一个大小为k的窗口在nums上从左至右滑动，输出每次移动，k个元素中的最大值；

使用双链表实现单调队列，支持在头部、尾部进行插入和删除；
每一个元素入队时，当队尾的元素小于入队元素时，删除队尾元素；
那么头部元素一定是最大的；

二叉堆:实现优先级队列；
binary heap: sink swim; 堆排序，优先级队列； 完全二叉树，储存在数组里； 数组指针作索引； 数组index 0 空着不用， parent：index/2 left: index2 right: index2+1
最大堆、最小堆；

delMax：堆顶与最后一个元素对调，删除最后一个元素，然后让堆顶下沉； insert：添加在最后一个元素后面，然后让其上升；

栈实现队列，队列实现栈: 栈，先进后出； 队列，先进先出；

双栈实现队列；

队列实现栈，直接暴力把队首取出放队尾；

1.3 · DP 动态规划#

最优子结构: 从子问题的最优结果，推导出更大规模问题的最优结果；子问题之间互相独立，可以改造问题，使问题等价化，求各种最值；

DP数组遍历:
遍历过程中，所需的状态必须是已经计算出来的； 遍历的终点是存储结果的位置。

状态压缩: 二维dp数组，如果计算dp[i][j]需要相临的状态，可以使用状态压缩，降低空间复杂度。 核心思想，将二维数组，投影到一维数组(去掉某个维度)，将无法投影的值，使用临时变量存储；`