力扣算法题总结
lc253
题目：求最多重叠(x,y)的数量
思路：按y排序，把y放入优先队列，逐个比较x，x大于优先队列的堆顶元素就弹出堆顶。
lc148
题目：对链表排序
思路：归并排序。快慢指针找到链表中点，递归找下去，然后比较左右结点的值，创建一个链表头节点串起来。
lc41
题目：找出未排序数组中没有出现的最小的正整数
思路：原地哈希，将数值为i的数映射到下标为i-1的位置
lc1
题目：两数之和
思路：哈希表存，找与目标值的差值是否在哈希表中
lc49
题目：将字母构成相同的单词分成一类
思路1：给每个单词排序，把排序后相同的单词存入map，key为单词,value为存单词的列表。
思路2：遍历单词，用数组存单词的字母出现次数，遍历数组把大于0的字母拼接成字符串，作为哈希表的Key。
lc128
题目：找出数组中数值连续的最长序列，要求时间复杂度为O(n)
思路：用set存入每个数组元素，遍历set，当前元素为t，如果不存在t-1的元素在set中，就从t开始寻找连续的数值序列，寻找t+1是否在set中。
lc283
题目：原地将数组所有0移动到数组末尾
思路：双指针，一个i指向0，一个j指向非0，当j遇到非0时就与i交换数字。
lc11
题目：求数组中盛水最多的值。即两个下标的数值中的最小值与下标之差相乘，要得到这个积的最大值。
思路：双指针，left指开头，right指末尾，记录积的最大值后，判断下标left代表的数组元素数值大，还是right代表的数组元素数值大，哪个小就移动哪一个。
lc15
题目：三数之和。找出数组中三个加起来等于0的数，不能重复。
思路：排序，先定位一个数，再对另外两个数用双指针的方法找，加起来大于0就right–，加起来小于0就left++。为了保证不重复遍历的时候需要跳过相邻相等的数。
lc42
题目：接雨水
思路：按列求。先分别求左边的最大值数组和右边的最大值数组，再遍历数组，比较当前元素的左边最大值和右边最大值，取更小的那个值min，如果这个值min比当前元素cur的值大，则当前列的雨水为min-cur，加入总雨水值中。
lc3
题目：无重复字符的最长子串
思路：滑动窗口。用map存字母的下标位置，用right去遍历到，一个字母如果已经存在于map中，则更新left的位置，更新为map中已存的这个字母的下标+1和left旧位置中的最大值。每次遍历都要更新无重复子串的最大值，并且更新当前字母在map中的值。
lc662 （快手一面手撕）
题目：二叉树的最大宽度
思路：手撕没撕出来，很烦。正确做法应该是层次遍历，用队列去存每一层的结点，同时要保存结点的下标，左子结点为2i，右子节点为2i+1。队列首先弹出第一个元素，代表二叉树这一层的最开头的结点，记录下它的下标，然后一直执行弹出元素并添加元素子结点的操作，一直把这一层结点弹完（在弹第一个元素之前记录队列的大小，即为这一层的结点数量），记录最后一个结点的下标，与最开头结点下标相减，将结果与最大值比较并更新。
lc139
题目：单词拆分。给一个字符串s和一组字符串list，求一组字符串中是否能选出几个字符串组成s。
思路：动态规划。dp[i]表示s的前i个字符的子串s[0,i-1]是否能被list中的字符串组合。i从前往后遍历，对于每个i都需要枚举包含i-1的最后一个单词，看这个单词是否在list中。转移方程为dp[i] = dp[j] && check(s[j,i-1])。
lc438
题目：找到字符串中所有的字母异位词。
思路：滑动窗口。这种子串问题一遇到就要想到用滑动窗口。用一个map(need)存异位词的所有字符，用另一个map(window)存滑动窗口中的所有字符。当两个map存的某一个字符的数量相等时，将count++。当窗口的大小为异位词的长度时（right-left==p.length()），就判断count是否等于need的大小，如果等于说明此时窗口中已经包含异位词。此时就记录下left的位置，并将窗口右移，并将window中left位置的字符数量减一。
lc76
题目：最小覆盖子串。在s中找到一个最小的子串包含t中的所有字符。
思路：滑动窗口。与lc438类似，同样用两个map来存t的字符后窗口中的字符，差别是窗口收缩的条件变成count==map.size()。
lc239
题目：滑动窗口最大值。
思路：用双向队列实现单调队列，保证队列首部是窗口中的最大值，尾部是最小值。每次都要将元素和队列尾部元素比较，如果比队列尾部元素大，则弹出尾部元素，直到遇到比它大的尾部元素，再将当前元素添加到队列尾部，以此实现队列首部到尾部单调递减的单调队列。要注意的是，每次向右滑动窗口，要判断队列首部元素是不是要被删除的元素，是的话则弹出队列首部元素。
lc53
题目：最大子数组和
思路：用sum累加数组里面的元素，每次累加后更新最大值，sum小于0时把sum置为0。
lc56
题目：合并区间。合并有重叠的区间。
思路：用一个left来存已经遍历过的元素的x的最小值，用一个right来存已经遍历过的元素的y的最大值，如果right比当前元素的x大，则说明有重叠，更新right为当前元素的y。如果小，则将当前的(left，right)添加进结果集中，并将（left，right）更新为当前元素的(x，y)。
lc189
题目：轮转数组。将数组中的元素向右轮转k个元素。
思路：前k个元素翻转一遍，后k个元素翻转一遍，整体再翻转一遍。
(A-1 B-1)-1 = (B-1)-1(A-1)-1 = BA
lc 238
题目：除自身以外数组的乘积
思路：求出前缀积和后缀积，遍历一个元素时将该元素的前缀积和后缀积相乘即可。
lc54
题目：螺旋矩阵
思路：模拟。设定上下左右四个方向，按照右下左上的顺序走，从左到右走到尽头，将所遍历的行top加1，并判断是否大于行bottom。依次类推。
lc48
题目：旋转图像。顺时针旋转矩阵。
思路：先把矩阵变为它本身的转置，即（i，j）变成（j，i）。然后对每行元素进行逆序即可。
lc240
题目：搜索二维矩阵2。
思路：从右上角开始找，二分的思想，如果大于目标值就y–，如果小于就x++。
lc234
题目：回文链表
思路：快慢指针找到链表中点，然后翻转后半段，再与前半段比较。
lc142
题目：环形链表2。要求找到入环点。
思路：当慢指针遇到快指针时，慢指针再走一段距离能到入环点，这段距离与从起点到入环点的距离相等，所以当快慢指针相遇时，在定义两个指针，一个指向起点，一个指向快慢指针相遇的点，一起移动，当相遇时就说明到了入环点。
lc2
题目：两数相加。在链表上模拟加法。
思路：同时遍历两个链表，判断当前结点是否为空，为空则值为0，不为空则值为val，将两个链表当前结点的值加起来，为sum，并且要加上上一个值的进位，这个进位用一个变量carry保存下来。sum/10为这个结点的进位，将加给下一个结点的和，sum%10为新链表结点的val。遍历两个链表完后，要注意此时carry的值，如果为1要再创建一个结点保存。
lc24
题目：两两交换链表中的节点
思路：主要要控制好交换节点的前后链接。首先要创建一个新节点res连在头节点前面，方便最终返回结果。再创建一个指针pre指向res，一个指针cur指向head。遍历链表，首先保存hou = cur.next.next，因为交换节点后还要将后面那个节点链接到cur.next.next上。然后将pre指向cur.next，再将两个节点的后一个节点指向前一个节点，即cur.next.next = cur。再将两个节点的前一个节点指向hou，即cur.next = hou。再移动pre指针为cur（此时cur因为交换节点已经变成了两个节点的后一个节点），移动cur指针为hou。
lc25
题目：K个一组翻转链表
思路：与lc24类似，主要要保存好翻转链表后的前后节点，以便翻转后还能接回原链表。
lc138
题目：随机链表的复制。创建一个新链表保存旧链表的所有信息。
思路：用哈希表存旧链表的结点，key为旧链表的结点，value为新建的一个结点，用旧结点的val初始化。然后再遍历一遍旧链表，构建新链表结点的next和random两个指针的指向，即map.get(cur).next = map.get(cur.next)和map.get(cur).random = map.get(cur.random)。返回map.get(head)。
lc146
题目：LRU缓存
思路：LRU策略是要选择一个最近最少使用的元素删除，填上新来的元素。要实现这个策略的话，可以用一个链表来构建缓存区，按元素被使用的顺序存储键值对，靠近链表头部的键值对是最近使用的，靠近尾部的键值对是最久未使用的。
每次向缓存区增加新的元素，如果这个元素已经在缓存区，则把这个元素所在的结点移到链表最前面，如果不在缓存区，则新建一个结点放到链表最前面。增加一个结点后，还要判断链表长度是否大于缓存区的大小，如果大了则要删除链表最后一个结点。
此时问题就来了，怎么判断这个元素在不在缓存区呢？ 这时就可以用一个hashmap来存储元素所在的结点位置，key为元素值，value为元素所在的结点，通过map映射得到元素所在的结点后，如果要删除这个结点，就要得到这个结点的前面的结点和后面的结点，为了方便得到前后结点，链表可以使用双向链表，这样就方便进行删除结点的操作。如果要移动结点到链表最前头，直接删除后再在链表首部插入一个新建的结点就可以。
同时，为了方便在链表头部插入结点和在链表尾部删除结点，可以创建额外的头结点和尾结点，使得更好操作。
lc101
题目：对称二叉树
思路：同时遍历树的左节点和右节点，比较是否相等。
lc543
题目：二叉树的直径
思路：对于每一个结点，计算它的左右子结点的深度，取最大值+1（要加上子结点到本结点的路径长度1）返回给父结点，并用左右子结点的深度之和再+2（要加上左右子结点到本结点的路径长度）更新直径的最大值。
lc124
题目：二叉树的最大路径和
思路：与lc543类似，区别是这题求的路径中各节点值的总和得最大值，而lc543求得是路径的最大长度。
lc102
题目：二叉树的层序遍历
思路：用队列实现。重点是要知道哪些结点是同一层的，所以每次都要把队列上次存入的结点全部弹出去，这样这次存入的结点就是同一层的了，同一层结点的数量就是队列的大小，所以每次都要先记录下队列的大小size，每弹出一个结点，size就减1，直到为0，就说明这一层的结点统计完了。
lc98
题目：验证二叉搜索树
思路：看到二叉搜索树的题目要想到中序遍历，因为中序遍历二叉搜索树就是一个升序数列，利用这个特性来解题。要验证是不是二叉搜索树，只要判断中序遍历是不是一个升序数列，判断此时结点的数值是否大于前一个结点的数值就可以了，可以把前一个结点的数值用全局变量存下来。
lc230
题目：二叉搜索树中第K小的元素
思路：一样用中序遍历，遍历到第k个结点就行了。
lc199
题目：二叉树的右视图
思路：与层序遍历类似，用队列来存储每一层的结点，每一层最后那个结点就是右视图能看到的结点。
lc114
题目：二叉树展开为链表
思路：把结点的左子树放到右子树的位置，再把右子树放到左子树的最右边结点下。
lc105
题目：根据前序遍历和中序遍历构建二叉树
思路：对于二叉树而言，前序遍历的结果是：
[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
中序遍历的结果是：
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
用map存中序遍历元素的下标，用前序遍历元素去取map中的下标，每取一个，为当前的结点，然后对左右子树进行递归处理。左子树的前序遍历下标区间是[preLeft+1，preLeft+pIndex-inLeft]，中序遍历下标区间是[inLeft，pIndex-1]，右子树的前序遍历下标区间是[preLeft+pIndex-inLeft+1，preRight]，中序遍历下标区间是[pIndex+1，inRight]。
lc106
题目：根据后序遍历和中序遍历构建二叉树
思路：对于二叉树而言，后序遍历的结果是：
[ [左子树的前序遍历结果], [右子树的前序遍历结果], 根节点]
中序遍历的结果是：
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
可以看到后序遍历与前序遍历的区别就是根节点放到了尾部，所以从map中取元素时，从后序遍历的尾部开始取即可。除此之外，后序遍历的下标区间也与前序有一点不同，左右子树的区间下标都比前序遍历少1，因为根结点放到了最后。其它与lc105一致。
lc5
题目：最长回文子串
思路：动态规划。dp[i][j]代表字符串s的子串（j，i）是不是回文子串。状态由（j+1，i-1）的子串转移而来，如果子串（j+1，i-1）是回文子串同时s[i]==s[j]，那么子串（j，i）就是回文子串。
lc134
题目：加油站
思路：累加每经过一个加油站的剩余油量，如果当前的累加油量比之前还少，说明到这个加油站仍然是消耗量大于油量，如果当前的累加油量比之前多了，
说明到这个加油站的油量大于到这来的消耗量。如果最终的累加油量为负数，说明没办法跑完，如果为正数，起点就是累加油量第一次有上升趋势的那个结点。