7.1题目 241. 为运算表达式设计优先级

【分治】x op y (op为运算符),它的结果取决于x和y的结果组合数，该问题子问题就是x op y中的x和y：以运算符分割的左右侧算式解，分治算法三步走:分解成左右两部分分别求解，递归求子问题的解，合并左右两部分的解得出最后解。

7.2题目 871. 最低加油次数

【贪心】1.计算当前位置与上一个位置的距离之差，根据该距离之差得到从上一个位置行驶到当前位置需要使用的汽油量，将使用的汽油量从剩余的汽油量中减去。2.剩余油量小于0说明无法从上一个位置行驶到当前位置，取出优先队列中的最大元素加到剩余的汽油量，并将加油次数加 1，重复该操作直到剩余的汽油量大于等于 0 或优先队列变为空。3.如果优先队列变为空时，剩余的汽油量仍小于 0，则表示在所有经过的加油站加油之后仍然无法到达当前位置，返回 -1。4.如果当前位置是加油站，则将当前加油站的加油量添加到优先队列中，并使用当前位置更新上一个位置。

7.3题目 556. 下一个更大元素 III

【数学】从n开始，不断比较其最低位数字和次地位数字的大小，如果次地位数字不低于最低位数字，则一处最低位数字，继续循环，循环结束后的n就对应方法以的下标i，即nums的前i + 1个字符。

7.4题目 1200. 最小绝对差

【排序 + 一次遍历】对arr升序排序，最小绝对差只能由有序数组相邻的两个元素构成。用一个delta变量存遇到的最小差。

7.5题目 729. 我的日程安排表 I

【遍历】区间如果没有交集，说明s1 > e2 or s2 > e1。

【二分】起点≥end的第一个区间[l1,r1)，和前一个区间[l2, r2)，如果r2 ≤ start < end < l1则可以预定。

【线段树】预定的区间中每个元素标记为1，每次调用book时，需检测区间内元素是否标记位1，不必世纪开辟10**9的数组，可以用动态线段树，懒标记lazy标记[l,r]已经被预定。

7.6题目 736. Lisp 语法解析

【递归解析】递归解析表达式——下一个字符!='('，去掉左括号后下一个字符是'|'、'a'、'm'。

7.7题目 648. 单词替换

【哈希集合】将dic所有词放入哈希集合中，对于每个单词，从短至长遍历它所有前缀，如果这个前缀出现在哈希集合中，则找到了当前最短词根，可以用这个词根替换原来的单词，最后返回拼接的句子。

7.8题目 1217. 玩筹码

【贪心】移动到偶数位置的最小开销就是初始奇数位置筹码数量，移动到奇数位置的最小开销就是初始偶数位置筹码数量。

7.9题目 873. 最长的斐波那契子序列的长度

【暴力】每次从arr中找前两个数，然后查看后续符合斐波那契的数在arr中有没有。

7.10题目 741. 摘樱桃

【DP】假设两人同时出发，且速度相同，设两人的坐标为（x1，1）和（x2，2），则x1+1=x2+2=k。那么当x1=x2时，必然有y1=y2，即两个人到达了同一个格子。枚举A和B上一步的走法，来计算f[k] [x1] [x2]，有四种情况。

7.11题目 676. 实现一个魔法字典

【枚举】把字典中的所有字符串存储在数组中，而当进行search 操作时，我们将待查询的字符串和数组中的字符串依次进行比较。

【字典树】我们也可以使用字典树代替数组，将所有字符串进行存储。这一部分需要的时间是相同的。在查询时，我们可以使用递归+回潮的方法，使用递归函数dfs(ode, pos, modified).

7.12题目 1252. 奇数值单元格的数目

【模拟】用n×m的矩阵存操作结果，对每一对[r_i,c_i]模拟。

【模拟空间优化】用rows和cols记录每一行和每一列被增加的次数。出位置（x，y）位置的计数即为rows[x] + cols[y]。

【计数优化】矩阵中位于（x，y）位置的数为奇数，当且仅当rows[z和cols划中恰好有一个为奇数，一个为偶数。设rows有odd个奇数，cols有odd个奇数。综上我们可以得到奇数的数目为odd×（n-odd）+（m-odd）x oddy.

7.13题目 735. 行星碰撞

【栈模拟】st模拟行星，alive记录是否还存在，只判断一个方向：默认把向右的全入栈（向右的无需判断)，向左的需要判断是否爆炸，不爆炸就入栈。(alive = st[-1] < -a 省了if判断)

7.14题目 745. 前缀和后缀搜索

【遍历 + 哈希表】预先计算出每个单词的组合可能性，用特殊符号连接。

7.15题目 558. 四叉树交集

【分治】假设当前操作的两个节点分别为node1和node2，node1为叶子节点时，如果node1的值为1，那么node1 | node2 = node1，否则node1 | node2=node2。node2为叶子节点与之相反。两者都不是叶子节点时：那么分别对两者的四个子节点来进行对应的分治处理一分别进行合并操作。

7.16题目 剑指 Offer II 041. 滑动窗口的平均值

【列表】按题意模拟。

【队列】队列中数字=滑动窗口的大小，移除队首的数字 就 将滑动窗口的数字之和中减去。计算滑动窗口的数字之和与队列中的数字个数之商。

7.17题目 565. 数组嵌套

【图】遍历数组，从i向nums连边，可以得到一张有向图。由于题目保证nums中不含有重复的元素，因此有向图中每个点的出度和入度均为1。在这种情况下，有向图必然由一个或多个环组成。我们可以遍历nums，找到节点个数最大的环。代码实现时需要用一个vis数组来标记访问过的节点。

【原地标记】可证一定有环，找最大的环，优化:省掉vis数组，放置n作为标记点，当 nums[i] == n时，说明到环起点了。

7.18题目 749. 隔离病毒

【BFS】遍历到is Infected中的一个1时，就从这个1对应的位置开始进行广度优先搜索，这样就可以得到连续的一块被病毒感染的区域.如果当前是第idx（idx≥1）块被病毒感染的区域，我们就把这些1都赋值成-idx，这样就可以防止重复搜索.

7.19题目 731. 我的日程安排表 II

【遍历】检查区间有没有交集。

【差分数组】需要用到python的Map/TreeMap 数据结构，sortedcontainers库。

【线段树】区间更新 + 动态线段树懒标记。

7.20题目 1260. 二维网格迁移

【一维展开】每次迁移操作都相当于将该一维数组向右循环移动一次，那么k次迁移操作之后，grid[x] [y]的下标idx = (index + k) mod (m × n)。

7.21题目 814. 二叉树剪枝

【递归】后序遍历的时候，递归地pruneTree。

7.22题目 757. 设置交集大小至少为2

【贪心】从该区间左边界开始往后添加不在交集集合中的元素，并往前进行更新需要更新的区间，重复该过程直至该区间与交集元素集合有m个元素相交。右端点从小到大，保证贪心处理边缘点的正确性，同时右端点一样的时候优先处理长度最短的区间，因为该区间可选点最少同时会覆盖其他区间，由于我们是单调递增添加元素，维护当前集合前二大的元素即可判断是否需要添加新的，如果区间左端点也在当前最大元素的右边，说明需要从该区间添加两个新点(可以理解为递归，前面的不再起作用)，贪心取最大的两个点。

7.23题目 剑指 Offer II 115. 重建序列

【拓扑排序】根据有向边计算每个结点的入度，然后将所有入度为0的结点添加到队列中，进行拓扑排序。如果队列中的元素个数大于1，则超序列的下一个数字不唯一，因此nums不是唯一的最短超序列，返回false；如果队列中的元素个数等于1，则超序列的下一个数字是队列中唯一的数字。将该数字从队列中取出，将该数字指向的每个数字的入度减1，并将入度变成0的数字添加到队列中。

7.24题目 1184. 公交站间的距离

【一次遍历】distance = min(start to distance, start to 0)。

7.25题目 919. 完全二叉树插入器

【队列】可以使用一个队列存储上述提到的这些可以添加子节点的节点。队列中的存储顺序为：首先从左往右存储倒数第二层最右侧的节点，再「从左往右」存储最后一层的全部节点。

7.26题目 1206. 设计跳表

【直接构造】search、add、erase.

7.27题目 592. 分数加减运算

【调库】 fractions模块提供了处理分数的方法。

7.28题目 1331. 数组序号转换

【排序 + 哈希表】首先用一个数组保存排序完的原数组，然后用一个哈希表保存各元素的序号，最后将原属组的元素替换为序号后返回。

7.29题目 593. 有效的正方形

【数学】正方形判定定理.

7.30题目 952. 按公因数计算最大组件大小

【并查集】可以使用并查集实现组件的计算。初始时，每个数分别属于不同的组件。如果两个正整数满足其中一个正整数是另一个正整数的因数，则这两个正整数属于同一个组件，将这两个正整数的组件合并。

7.31题目 1161. 最大层内元素和

【BFS】我的层序遍历模板。