根据题目，分析数据，找到规律！！！！！！！！题目数量很多，要想基本都会，就必须多练多见。量变导致质变。

        “画图”帮助理解 Recursive Tree。

        程序员江湖有个传言：懂了《算法导论》的90%，就超越了90%的程序员。

        全局变量在部分题目中，有很大的用处。能直接降低算法的理解程度！例如题目285！

        为了降低空间复杂度，对于输入参数是数组的题目，可以考虑使用“交换元素”的思想，来达到输入参数的复用。比如题目41“全排列二”。

1）对于典型套路类算法题目，比如滑动窗口类题目，位运算类题目。解题关键：根据题意，分析数据，找到数据背后的有助于解题的规律。这些规律往往是一些数学上的递推式子。比如题目201、题目713.

        初步找到规律后，可以在深一步想想这个规律可以如何更高效的利用。这能更一步的提高算法效率。比如《剑指offer》专项突破版，面试题3“前n个数字二进制形式中1的个数”。一开始想到利用“i & (i-1)”这个规律可以求出单个数字中1的个数；如果再深一步，想到 i中1的个数 恰好是 “i & (i-1) ”中1的个数 加1，那能更一步降低算法时间复杂度。

2）Recursion相关的题目，如果Debug的时候，实在想不通哪里错了，可以画图。以一个例子画出递归树，然后纠正代码。比如，Backtrack Algorithm相关的题目可以画出“回溯树”来帮助写代码。

        就这么说吧，所有递归算法，无论它是干什么的，本质上都是在遍历一棵（递归）树，然后在节点（前中后序位置）上执行代码。你要写递归算法，本质上就是要告诉每个节点需要做什么。

3）学到新算法时，立即写代码实践，才能熟练。后期，就通过刷题，不断归纳总结，才能掌握，举一反三。

        新算法的学习，首先应该考虑实现上，哪些是重要的卡点，应该用什么方法来实现。更进一步，能够用怎样的巧妙数据结构来优化时间效率。这需要长期训练，形成条件反射。

4）在使用指针时，一定要注意区分“指针变量”与“指针所代表的地址”这两个不同的含义。在binary tree中，对于已知的节点指针 TreeNode* root，" root=nullptr "的操作，表示的是 root 这个指针变量变为了NULL，而不是对应的变量地址被置为NULL。这点需要尤其注意，我因此吃亏！！！！

        同时，对节点的指针进行赋值时，注意是否对原始节点的左右关系做了修改。这点我也吃过亏。

5）注意区别：Longest Common Substring 和 Longest Common Subsequence。Longest Common Subsequence 应该使用DP来解决，dp[i][j]表示字符串str1[i....]和字符串str2[j....]的最长公共子序列；而Longest Common Substring属于字符串类算法，使用双指针和哈希表可以轻松解题。

6）遇到一个算法题，如果想不出来简单方法，那可以先写出暴力解，即BF Version。然后，再基于此，思考如何优化。

7）“连续子数组”的求plus（minus或multiplies）的最值问题，可以考虑SlidingWindowMethod。目前遇到相关题目分为两种类型：一、数组全为正整数，或已排序，解法SlidingWindowMethod（剑指Offer II 008），或者双指针（剑指Offer II 006、007）；二、数组元素为有符号整数，解法使用unordered_map，具体是记录前n项的前缀，和出现的次数。剑指Offer II 010。

        单纯的数组内题目（往往形参只有一个数组），unorder_map往往涉及前缀和，它有很多妙用，用好了可以极大的提升算法性能。

8）有时候题目会限制我们算法的时间复杂度，这种信息其实也暗示着一些东西。

        比如，要求我们的算法复杂度是 O(N logN)，你想想怎么才能搞出一个对数级别的复杂度呢？肯定得用到“二分搜索” 或者 二叉树相关的数据结构，比如TreeMap，PriorityQueue之类的对吧。

        再比如，有时候题目要求你的算法时间复杂度是 O(M N），这可以联想到什么？可以大胆猜测，常规解法是用 “回溯算法” 暴力穷举，但是更好的解法是动态规划，而且是一个二维动态规划，需要一个 M*N 的二维 dp数组，所以产生了这样一个时间复杂度。

1、双指针类题目

        概念：当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从O(N²）减少至O(N)。这是因为在枚举的过程每一步中，「左指针」会向右移动一个位置，而「右指针」会向左移动若干个位置，这个与数组的元素有关，但我们知道它一共会移动的位置数为O(N)。均摊下来，每次也向左移动一个位置，因此时间复杂度为O(N)。例如，[题目167]、[题目15]。

2、dynamic programing类题目

        15分钟内，如果自己没有解出来，就直接看官方解答。但要注意的是，一边看答案一边套用labuladong关于动态规划的解题技巧来理解。这样做能加深对动态规划类题目的一般套路理解。

        还要一点尤其注意的是，一定要在对题目给出的数据做了分析的情况下，再来使用DP算法。不然，盲目的套用DP，不会写出理想的代码。

        如果DP类题目涉及到多个table来寻找最值情况，即一个表对应一个状态转移方程，多个表就对应多个状态转移方程。这种分类的动态规划，难度就瞬间上去了。做这类题的关键是，一定要把这多个表都找到，把每个位置的各个状态都准确找到。例如题目1567.

3、Greedy类题目

        解题策略：你自己设计一种寻找最值的思路，通过遍历来搜索理想的最值。这种思路就是greedy策略的选择，这也是该类题目的难点所在。相关的题目有乐扣题目11（盛最多水的容器）、图中的最短路径问题。

        Greedy策略在Graph Theory的search类算法中有很多的实践。比如，DFS中，每次都使用与当前节点相连的首节点进行搜索；BFS中，每次都等遍历完当前节点的所有直接相连节点之后，在搜索下一层的节点；MST之prim算法中，每次都选取cross edges中代价最小的边；MST之kruskal算法中，每次都选取所有未访问边中的代价最小者进行判断；shortest path中，每访问到一个新的节点都更新一次每个节点到目标节点的最小代价值。

        事实上，DFS、BFS、MST、shortPath都可以归为一类算法：PFS——priority first search。

3、字符类题目

        1、可以直接视作int[26]进行hash映射了。都可以不用Map了。这牺牲了小部分空间，但是极大地节省了时间复杂度。

        2、看到字符串类题目，应该首先想到哈希表。它在字符串比较类题目中，是解题最基本的数据结构。比如字符串的变位词类题目，比如题目567（变位词）；含有相同字符的子字符串类题目。

        2、快速比较“两个字符串是否有相同字符”的一种方法：通过将字符串的字符转换到二进制位1，实现将字符串转换成一个整数。实现方式，左移运算 + ‘或’运算。然后，利用‘与’运算，可以快速判断“是否有相同字符”。       （这个思路充分体现了“位运算”的高效性，毕竟这是二进制运算）

        3、“两个字符串判断是否变位词的问题”，难点在字符串中可能出现相同字符，因此，不能使用“2”中的技巧。可以用HashTable来存储字符串中不同字符出现的次数，然后比较两个HashTable中的值是否全等。对于全是小写字母的字符串，可以利用字符的整数表示特性，使用动态数组替换HashTable。例如题目567（变位词），题目438。使用了“SlidingWindows”或“Two-Pointer”来求解问题。

        4、回文串类问题：直接使用原始字符串上的双指针最高效。比如题目125、题目680。难点在“回文串”相关的动态规划。

4、binary tree

        相关的题目在解题时，应该建立一种基于子树操作的recursion来解决问题的思想，即通过写一个对当前子树的操作函数，基于它的recursion来实现对所有子树的操作，从而解决问题。最终会发现，BT类问题的代码始终没有逃出“前/中/后序的遍历框架”。（这实际上是一种“递归的结构化”思维，一开始可能难以理解，一旦理解，会发现解题思路明确，代码相对也简单！但对“穷举”类题目不适用，“穷举类”题目属于深度优先搜索框架下）。

        BT类问题的难点是，如何把题目的要求细化成每个节点需要做的事情。然后剩下的事情交给“基于子树的递归函数”就可以了。

        其次，需要注意的一点是，对节点进行“增删查改”时，不要忘记维护节点之间的前后继承关系，这是我在做 BinarySearchTree 相关题目时经常容易出错的点。同时，也要注意区分“指针变量”与“变量存储的地址”。

1）平衡二叉搜索树（AVL树）具有的性质：

•         平衡二叉搜索树中每个结点的左子树和右子树的高度最多相差1；
•         平衡二叉搜索树的子树也是平衡二叉搜索树
•         一棵存有n个结点的平衡二叉搜索树的高度是O(log n)。