Wiki@桩白墨

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
===== 1 算法思想 =====
==== 双指针 ====
^ leetcode序号      ^ 题目       ^ 思路要点 ^
| 167    | 有序数组的 Two Sum     | 对撞 |
| 633    | 两数平方和 |对撞 |
| 345    | 反转字符串中的元音字符     |对撞 |
|680|回文字符串|对撞。子函数|
|88|归并两个有序数组|从后往前|
|141|判断链表是否存在环|快慢指针重合|
|524|最长子序列|子序列的判断方法（双指针，从左到右扫一遍）|

==== 排序 ====
^ leetcode序号      ^ 题目       ^ 思路要点 ^
|堆|||
| 215    | Kth Element     | 小顶堆 |
|桶排序|||
|347|出现频率最多的 k 个元素|算出频率、插入桶中、从后往前遍历桶。List<Integer>[] buckets = new ArrayList[nums.length + 1]|
|451|按照字符出现次数对字符串排序|同上|
|荷兰国旗问题|||
|75|按颜色进行排序|三路快排|

==== 贪心思想 ====
^ leetcode序号      ^ 题目       ^ 思路要点 ^
| 455    | 分配饼干     | 胃口升序、饼干升序、双指针 |
|435|不重叠的区间个数|根据结尾排序；若 start < 上次的 end，则判定为重合，跳过|
|452|投飞镖刺破气球|同上。对于边界情况，使用 Integer.compare 做比较|
|406|根据身高和序号重组队列|根据身高倒序、序号正序排序；以序号为索引位置，插入List<int[]>中；toArray(new int[n][2])|
|121|买卖股票最大收益|一次遍历。Math.max(max, price[i]-soFarMin)|
|122|买卖股票最大收益2|所有连续上升序列的差值之和|
|605|种植花朵|尽量靠前种花；每种一棵，计数&更新状态|
|392|判断是否为子序列|双指针|
|665|修改一个数成为非递减数组|只允许变一次（可以用count或flag）；发现异常时，尽量变前一个数，不行再变后一个数|
|53|子数组最大的和|只扫一遍；记录当前和与最大和，如果上次的当前和<0，则丢弃，取0|
|763|分隔字符串使同种字符出现在一起|记录每个字符最后一次出现的索引（int[26]）；双指针|

==== 二分查找 ====
边界问题非常多！
二分查找解析：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/er-fen-cha-zhao-suan-fa-xi-jie-xiang-jie-by-labula/

^ leetcode序号      ^ 题目       ^ 思路要点 ^
| 69    | 求开方     | 用除法防止越界；l<=r；return r|
|744|大于给定元素的最小元素|二分法变种|
|540|有序数组的 Single Element|异或；对偶数位进行搜索|
|278|第一个错误的版本| 左边界 |
|153|旋转数组的最小数字|如果nums[m] < nums[r]，那么最小值一定在前半部分；反之则反|
|34|查找区间|注意数组越界问题|


==== 分治 ====
^ leetcode序号      ^ 题目       ^ 思路要点 ^
| 241    | 给表达式加括号     | 遍历，找到每个操作符，一分为二；如果没找到操作符，则Integer.parseInt|
| 95| 不同的二叉搜索树 | 遍历，以每个节点作为root，一分为二 |

==== 搜索 ====
^ leetcode序号      ^ 题目       ^ 思路要点 ^
|BFS|||
| 1091    | 计算在网格中从原点到特定点的最短路径长度     | batchSize = queue.size()；打标记；DIRECTIONS|
| 279|组成整数的最小平方数数量|生成平方数序列，视为边；从n开始，到达0返回|
|127|最短单词路径|先构造一张图，然后寻找起点到终点的最短路径（效率较慢，以后再研究）|
|DFS|||
|695|查找最大的连通面积|遍历棋盘，一旦找到一个点位，就dfs求岛屿面积|
|200|矩阵中的连通分量数目|遍历棋盘，找到点位就+1，然后dfs清空连通区域|
|547|好友关系的连通分量数目|跟上面连通的方式不一样|
|130|填充封闭区域|对边界上的O进行dfs，打上不可变标记，再遍历一遍|
|417|能到达的太平洋和大西洋的区域|各用一个二维数组标记太平洋、大西洋连通点；从边界出发，逆流dfs|
|Backtracing|||
|17|数字键盘组合|sb.deleteCharAt(pos)|
|93|IP 地址划分|转换为树形问题，剪枝|
|79|在矩阵中寻找字符串|终止条件用 word.length() == 1|
|257|输出二叉树中所有从根到叶子的路径|add和remove成对出现；if (root == null) return;|
|46|排列|提前声明一个 visited 数组|
|47|含有相同元素求排列|先排序，然后在添加一个元素时，判断这个元素是否等于前一个元素，如果等于，并且前一个元素还未访问，那么就跳过这个元素|
|77|组合||
|39|组合求和||
|40|含有相同元素的组合求和||
|216|1-9数字的组合求和||
|78|子集||
|90|含有相同元素求子集||
|131|分割字符串使得每个部分都是回文数||
|37|数独|seeNext|
|51|N皇后||

==== 动态规划 ====
^ leetcode序号      ^ 题目       ^ 思路要点 ^
|斐波那契数列|||
| 70    | 爬楼梯     | |
|198|强盗抢劫||
|213|强盗在环形街区抢劫||
| |信件错排||
| |母牛生产||
|矩阵路径|||
|64|矩阵的最小路径和||
|62|矩阵的总路径数||
|数组区间|||
|303|数组区间和||
|413|数组中等差递增子区间的个数||
|分割整数|||
|343|分割整数的最大乘积||
|279|按平方数来分割整数||
|91|分割整数构成字母字符串||
|最长递增子序列|||
|300|最长递增子序列||
|646|一组整数对能够构成的最长链||
|376|最长摆动子序列||
|最长公共子序列|||
|1143|最长公共子序列||
|0-1背包|||
|416|划分数组为和相等的两部分||
|494|改变一组数的正负号使得它们的和为一给定数||
|474|01 字符构成最多的字符串||
|322|找零钱的最少硬币数||
|518|找零钱的硬币数组合||
|139|字符串按单词列表分割||
|377|组合总和||
|股票交易|||
|309|需要冷却期的股票交易||
|714|需要交易费用的股票交易||
|123|只能进行两次的股票交易||
|188|只能进行 k 次的股票交易||
|字符串编辑|||
|583|删除两个字符串的字符使它们相等||
|72|编辑距离||
|650|复制粘贴字符||




==== 数学 ====
^ leetcode序号      ^ 题目       ^ 思路要点 ^
|最大公约数最小公倍数|||
|204|生成素数序列||
| |最大公约数||
| |使用位操作和减法求解最大公约数||
|进制转换|||
|504|7进制||
|405|16进制||
|168|26进制||
|阶乘|||
|172|统计阶乘尾部有多少个0||
|字符串加法减法|||
|67|二进制加法||
|415|字符串加法||
|相遇问题|||
|462|改变数组元素使所有的数组元素都相等||
|多数投票问题|||
|169|数组中出现次数多于 n / 2 的元素||
|其他|||
|367|平方数||
|326|3 的 n 次方||
|238|乘积数组||
|628|找出数组中的乘积最大的三个数||

===== 2 数据结构相关 =====
==== 链表 ====
^ leetcode序号      ^ 题目       ^ 思路要点 ^
|160|找出两个链表的交点|如果不存在交点，l1 和 l2 会同时为 null，从而退出循环。|
|206|链表反转|pre，cur，next；pre = null|
|21|归并两个有序的链表|归并排序|
|83|从有序链表中删除重复节点|略|
|19|删除链表的倒数第n个节点|双指针|
|24|交换链表中的相邻节点|pre,cur,next; pre = dummyHead|
|445|链表求和|用栈倒序|
|234|回文链表|快慢指针切成两半，把后面的反转|
|725|分隔链表|如果链表有N 个结点，则分隔的链表中每个部分中都有n/k 个结点，且前N%k 部分有一个额外的结点。|
|328|链表元素按奇偶聚集|分割奇偶链；找到奇数链的尾部；连接两条链|

==== 树 ====
^ leetcode序号      ^ 题目       ^ 思路要点 ^
|递归|||
|104|树的高度|Math.max(leftDepth, rightDepth) + 1|
|110|平衡树|还是求最大深度，多了一次比较和状态记录|
|543|两节点的最长路径|等于两子树的最大深度之和|
|226|反转树|反转左右子树；交换位置|
|617|归并两棵树|略|
|112|判断路径和是否等于一个数|略|
|437|统计路径和等于一个数的路径数量|pathSumStartsWithRoot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum)|
|572|子树|<code>isSubtreeStartsWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t)</code>注意子树的定义|
|101|树的对称|isMirror(root.left, root.right)|
|111|最小路径|当 root 节点左右孩子有一个为空时，返回不为空的孩子节点的深度；当 root 节点左右孩子都不为空时，返回左右孩子较小深度的节点值|
|404|统计左叶子节点的和|略|
|687|相同节点值的最大路径长度||
|337|间隔遍历||
|671|找出二叉树中第二小的节点||
|层次遍历|||
|637|一棵树每层节点的平均数||
|513|得到左下角的节点||
|前中后序遍历|||
|144|非递归实现二叉树的前序遍历||
|145|非递归实现二叉树的后序遍历||
|94|非递归实现二叉树的中序遍历||
|BST|||
|669|修剪二叉查找树||
|230|寻找二叉查找树的第 k 个元素||
| |把二叉查找树每个节点的值都加上比它大的节点的值||
|235|二叉查找树的最近公共祖先||
|236|二叉树的最近公共祖先||
|108|从有序数组中构造二叉查找树||
|109|根据有序链表构造平衡的二叉查找树||
|653|在二叉查找树中寻找两个节点，使它们的和为一个给定值||
|530|在二叉查找树中查找两个节点之差的最小绝对值||
|501|寻找二叉查找树中出现次数最多的值||
|Trie|||
|208|实现一个 Trie||
|677|实现一个 Trie，用来求前缀和||

==== 栈和队列 ====
^ leetcode序号      ^ 题目       ^ 思路要点 ^
|232|用栈实现队列|当 sOut 空的时候，一次性把 sIn 加到 sOut 上|
|225|用队列实现栈|两个队列；push 的时候，把元素插入临时队列的前面，然后把主队列一一插过去；交换两个队列的名字|
|155|最小值栈|多使用一个minStack，同步更新|
|20|用栈实现括号匹配|左括号入栈，右括号出栈|
|739|数组中元素与下一个比它大的元素之间的距离|一次遍历。用栈记录已经遇到的索引，一旦遇到更大的值，就持续出栈，计算结果|
|503|循环数组中比当前元素大的下一个元素|int i = 0; i < n * 2; i++。只在 i<n 时入栈|

==== 哈希表 ====
^ leetcode序号      ^ 题目       ^ 思路要点 ^
|1|数组中两个数的和为给定值|<needNum:currentIndex>|
|217|判断数组是否含有重复元素|多种算法，略|
|594|最长和谐序列|构造freqMap，遍历此map|
|128|最长连续序列|<num, length>；forward 递归计算从每个num出发的length|

==== 字符串 ====
^ leetcode序号      ^ 题目       ^ 思路要点 ^
| |字符串循环移位包含||
| |字符串循环移位||
| |字符串中单词的翻转||
|242|两个字符串包含的字符是否完全相同||
|409|计算一组字符集合可以组成的回文字符串的最大长度||
|205|字符串同构||
|647|回文子字符串个数||
|9|判断一个整数是否是回文数||
|696|统计二进制字符串中连续 1 和连续 0 数量相同的子字符串个数||

==== 数组与矩阵 ====
^ leetcode序号      ^ 题目       ^ 思路要点 ^
|283|把数组中的 0 移到末尾||
|566|改变矩阵维度||
|485|找出数组中最长的连续 1||
|240|有序矩阵查找||
|378|有序矩阵的 Kth Element||
|645|一个数组元素在 [1, n] 之间，其中一个数被替换为另一个数，找出重复的数和丢失的数||
|287|找出数组中重复的数，数组值在 [1, n] 之间||
|667|数组相邻差值的个数||
|697|数组的度||
|766|对角元素相等的矩阵||
|565|嵌套数组||
|769|分隔数组||

==== 图 ====
^ leetcode序号      ^ 题目       ^ 思路要点 ^
|二分图|||
|785|判断是否为二分图||
|拓扑排序|||
|207|课程安排的合法性||
|210|课程安排的顺序||
|并查集|||
|684|冗余连接||

==== 位运算 ====
^ leetcode序号      ^ 题目       ^ 思路要点 ^
|461|统计两个数的二进制表示有多少位不同||
|136|数组中唯一一个不重复的元素||