leetcode

HOT 100 Easy

1 两数之和：用数组位置查找数组值，O(1)；用数组值查找数组位置想要达到O(1)，用HashMap--常用技巧。

20 有效的括号： 【栈】。

21 合并两个有序链表：可以【循环】，也可以采用【递归】。

53 最大子序和： 一次循环，maxEndingHere储存以该点结尾的子序和，maxSoFar储存到该点的最大子序和。

70 爬楼梯： 循环，一次只储存两个值。

101 对称二叉树：日常递归。

104 二叉树的最大深度： 【一行递归】。

121 买卖股票的最佳时机：与目前最小值做差，求差的最大值，一次循环就够了。

136 只出现一次的数字：【异或的性质】, a^a=0, a^0=a。

141 环形链表: 快慢指针。

155 最小栈: 需要辅助栈。【同步栈】，【不同步栈】。

160 相交链表: 所有寻找同一节点链表题的本质（如相交，环），都是对加法交换律的花式运用。

169 多数元素：我将这种算法称为 【抱对自杀】，每当一个众数碰到一个非众数就会抱住，然后双双自杀。如果没有遇到足够的非众数，众数们就会等人到齐了再抱对自杀。最后留下来的当然是众数。

198 打家劫舍：看到这一道题第一反应是递归，但是简单递归会导致大量重复计算量，因此应该标记计算过的节点。但实际上，我们真的需要储存那么多中间值嘛？并不是，只用存前一个值和前前一个值就好，所以其实可以用【简单循环】解决这个问题--跟 70. 爬楼梯 是类似的。

206 反转链表：其实是 234. 回文链表 的一部分。

226 翻转二叉树：自身递归，“交换”左右子树时记得备份。

234 回文链表: 快慢指针（整除器），把剩下的一半变成逆序，再进行比较。注意奇偶情况讨论。

283 移动零：将非零元素依次交换到前面来。

437 路径总和 III ：经典划分：树 = 根节点+左子树+右子树。好的划分是递归的基础。

438 找到字符串中所有字母异位词：【滑动窗口】。

448 找到所有数组中消失的数字：把数字放到对应位置上去，最后依次找出没有正确摆放数字的位置。千万注意，调换的时候，数组的角标含义可能会发生变化。【我的代码】。

461 汉明距离：十进制向二进制转换技巧：整除/2，或右移>>1；异或^的用法。

538 把二叉搜索树转换为累加树：树的经典题，dfs，右孩子-根-左孩子。

543 二叉树的直径：dfs求节点到叶子节点的距离，叶子节点的到叶子节点距离定义为1。dfs遍历所有节点找出最大直径。

581 最短无序连续子数组：四遍循环。从左至右找无序子数组极小值，从右至左找无序子数组极大值，从左至右找无序子数组左边起始点，从右至左找无序子数组右边起始点。

617 合并二叉树：递归，经典划分：树=根+左子树+右子树，跟437 路径总和 III的思想是一样的。

HOT 100 Medium

2 两数相加：设置prev ListNode，不要过早退出循环。【我的代码】。

3 无重复字符的最长子串：用字符查找值常用技巧，一种是【我的代码】提到的，另一种是HashMap<Character, V>。这里也可以用后一种方法改写，但是会慢一些。我之前还写过一篇文章，专门讨论这题-- LeetCode 003 无重复字符的最长子串 - zhangyixing1007的文章 - 知乎

5 最长回文子串：注意要分奇偶情况分别讨论。【我的代码】。

11 盛最多水的容器：【左右指针】，每次移动短的那一根，显然这样更可能得到更大的结果。

15 三数之和：需要尤其注意去重，有些繁琐。【我的代码】。

17 电话号码的字母组合：【backtrack】。

19 删除链表的倒数第N个节点：【快慢指针】，一次循环。考虑特殊情况：删除的是第一个节点了。

链表常用技巧：快慢指针、整除器、prev 节点。

22 括号生成：【递归】，分只能添加“（”，只能添加“）”，和有可以添加“（”又能添加“）”三种情况。注意“）”的个数时时刻刻不能超过“（”。

31 下一个排列：把数组分成三段a,b,c。c是从左至右降序的，b是c左边的第一位，a是除去b和c剩下的部分。（a和b可能为空。如果是这样直接对称交换左右元素即可。）下一个排列就是把b与 c中所有比b大的数字中最小的一个 交换，然后再把交换后c字段所有的内容变成升序。【我的代码】。

33 搜索旋转排序数组：先二分查找旋转点（迭代或者递推），再二分查找目标（递推）。二分查找可以用递归/循环，是很常见的写法。需注意分段和索引范围问题（没有必要为了排除某个别索引把分段弄得特别严谨）。【我的代码】。

34 在排序数组中查找元素的第一个和最后一个位置 ：最简单的做法【一次二分查找】，二分查找目标，以目标为中心往旁边扩散。也可以【两次二分查找】，分别查找左端点和右端点。前者在一般情况下比后者快一些。

39 组合总和：一共两层，一层元素，一层元素个数，可递归可循环。这里递归，+1-1 = 0， 共用栈，节约空间。【我的代码】。

46 全排列：递归，两次相同位置的轮换仍得到原排列，共用一个ArrayList，只在存结果的时候新建，节约空间。轮换方法，首位与各位依次轮换（包括自己），然后以第二位为首位再次进行上述操作，存下每一次的结果。【我的代码】。

48 旋转图像：将矩阵分成5个不交并的部分，一个部分在中心，不需旋转（若n为偶数，则只有4部分），剩下的4部分进行旋转。【我的代码】展示了其中一种划分，实际上有4种。

i<n/2, j<(n-1)/2+1 i<n/2, j<(n+1)/2 i<(n+1)/2, j<n/2, i<(n-1)/2+1, j<n/2.

49 字母异位词分组：字母异位词经过排序之后得到的字符串相同。所以可以先转化为char[]，再排序，再转化为String，获得字母异位词的“唯一表达”。这个表达可以作为HashMap的键。【我的代码】

55 跳跃游戏：显然是从尾至头循环，第一想法是【双层循环】，但这样太慢了，其实可以用【单层循环】。

56 合并区间：首先根据左端点排序，这样只需比较每一次合并后区间的右端点和起始的左端点即可。【我的代码】。

62 不同路径：要么【用数学递推公式】，

要么就根据定义【直接计算】。直接计算时需要注意

Java “/”的整除性质， 溢出， 乘除顺序。

64 最小路径和：其实到达某点的最小路径，只与该点数值、到达该点左边的最小路径、到达该点上边的最小路径有关。所以只要找到【正确循环顺序】，就可以避免所有的中间储存，两层循环即可。

75 颜色分类：【左右指针】，注意不要轻易移动目前正在比对的指针。

78 子集：运用【二进制的性质】。

79 单词搜索：日常【递归】。注意

需要标记走过的点，这里由于我们的字母集有限，只需挑选一个不属于字母集的character在自身数组上进行标记即可（否则就需要用boolean[][]进行标记）； 遍历上下左右的点时注意边界情况讨论。

94 二叉树的中序遍历：写成【递归】是很简单的，写成【循环】就需要用到Stack了。

96 不同的二叉搜索树：第一朴素的想法应该是递归，但是纯粹递归会导致大量重复计算，所以应是【记录值的递归】，进一步，这样的程序其实可以写成【循环】。

98 验证二叉搜索树：【递归】，又用到了树的经典划分：树=根+左子树+右子树。注意

这里左子树和右子树是包含于原树的范围的； 避免 Integer. MIN_VALUE 和 Integer.MAX_VALUE，否则一些特殊的测试用例就会挂掉--这也是我们使用Integer 而不是int作为上下限变量的原因。

102 二叉树的层次遍历：层次遍历和广度优先遍历其实是很像的，在循环中使用队列就好。唯一的不同是每一层单独一个list，因此我们就需要想想办法让每层分隔开，我使用的办法就是每次塞进去一个root作为分隔。【我的代码】。

105 从前序与中序遍历序列构造二叉树：前序的第一个元素一定是根，在中序中，根的左边是左子树，根的右边是右子树。根据中序中左子树右子树分布范围长短，可以推断出前序中左子树右子树分布。那么，怎么在中序中查找根呢？可以用最简单的【循环】，或者用神奇的【HashMap】。

114 二叉树展开为链表：最简单的想法是递归，【递归 1】，【递归 2】。

139 单词拆分：非常常见的题，【递归】或【循环】均可。

142 环形链表 II：快慢指针+Floyd算法。【我的答案】。

146 LRU缓存机制：【继承LinkedHashMap】，而LinkedHashMap的原理可参照【另一答案】。

148 排序链表：【merge sort + Floyd】 。

152 乘积最大子序列：跟53. 最大子序和非常类似，但是要注意负数的情况，负负得正，所以最小的负数也需要做记录。【我的答案】。

200 岛屿数量: 求连通分支个数【dfs】和 【union find】。这里使用unionfind的原理为：

顶点数-最小生成树连线数=连通分支个数。

207 课程表：可以使用【拓扑排序】 ，或者用【深度优先遍历dfs查找环】 。

208 实现 Trie (前缀树): 显然我们需要创造新的内部类 TrieNode，并且类似链表构建next。但此处next不止一个，所以可以【用HashMap做指针】或者【用TrieNode[]做指针】。

215 数组中的第K个最大元素: 【快速排序】。

221 最大正方形：可以用动态规划，以某点为右下角的最大正方形边长 只与 以该点上面、左边、左上相邻点为右下角的最大正方形边长有关，取最小+1的关系。用二维数组储存结果需要补充上边和左边的数组 2d dp，也可以用一位数组储存结果，更节约空间 1d dp。

236 二叉树的最近公共祖先：直接解释【我的代码】，dfs(root, p, q)返回值只有1和0。

1：以root为根节点的子树包含至少一个p或者q。

0：以root为根节点的子树既不包含p也不包含q。

当left+right+mid>1时，说明以root为根节点的子树的左孩子子树/右孩子子树/root中的2个部分分别包含p和q，此时是最短路径了，记录ancestor。再继续递归，p和q就不可避免地会长在以新的root节点为根的一棵子树上，此时再也无法出现left+right+mid>1的情况的了。

238 除自身以外数组的乘积: 对于每一个元素而言，左边的所有元素乘以右边的所有元素就能得到答案。注意，两次循环不能合并！【我的代码】。

240 搜索二维矩阵 II：从矩阵matrix左下角的元素出发，循环，如果该元素比搜索目标target要小，往右寻找；若大，往上寻找；相等就是找到了。需注意开头的筛选条件和循环退出条件。我的代码。

279 完全平方数: 【动态规划】dynamic programming 或者是 【广度优先遍历】BFS。

287 寻找重复数：与链表中入环位置142. 环形链表 II原理是一样的，重复的数字必定有大于1的入度，即它就是环开始的地方。【我的答案】。

300 最长上升子序列: 【动态规划】 dynamic programming, 或者【动态规划+二分查找】 dynamic programming + binary search。

309 最佳买卖股票时机含冷冻期: 重点在于【状态划分】，我们要确保这样的状态划分保证每一笔交易都有冷冻期。

sold：在当天卖出股票，必须由hold状态而来。 hold：当天持有股票，可能是当天买入，或者之前买入的。可以由rest或者hold状态而来。 rest：当天不持有股票，可能是前一天卖出的，也可能是更早卖出的。可以由sold或者rest状态而来。 这样的状态划分，我们可以看到，要从sold状态进入hold状态必须经过至少一次的rest，这就满足了冷冻期的要求。需要注意的是初始值的选取，可以通过对第一天情况代入来选取。这里sold选取的是0，但实际上只要取一个非负数就好。

322 零钱兑换：【动态规划】 dynamic programming，实际上思路和279. 完全平方数是一模一样的。这里仅给出第一种解法，实际上第二种用队列的广度优先遍历也是完全可以的。

337 打家劫舍 III：【自身递归】，写一个子函数，返回值为一个长度为2的数组，分别储存包含和不包含该节点的最大值。

338 比特位计数: 基本思想还是动态规划dynamic programming。【代码一】 是把该数字右移一位得到相应“1”的个数，再加上最右端的数字，得到原数字“1”的总个数。【代码二】 是利用 [公式] 得到去掉了最右端“1”的 [公式] ，再加上“1”。注意位运算的优先级低于加减乘除。

347 前 K 个高频元素：【代码一】 用HashMap统计出现频率，再用List[]统计每一频率下出现的数字，最后得出答案（list.addAll(list2))。以下为统计频率经典代码

    HashMap<Integer, Integer> map=new HashMap<>();
    for (int num:nums){
        map.put(num, map.getOrDefault(num,0)+1);
    }

【代码二】 使用优先队列PriorityQueue，重新定义排序方式。

Queue q=new PriorityQueue<>((n1,n2)->map.get(n1)-map.get(n2));

394 字符串解码：需要用【两个栈】 Stack分别储存数字和字符串。如何一位一位读取数字呢？

        if(c>='0'&&c<='9'){
            mul=mul*10+Integer.parseInt(c+"");
        }

399 除法求值：与200. 岛屿数量类似，可以用【dfs】 或者 【union find】 。

406 根据身高重建队列：第二个数字仅与比本人高的人数有关，那么无论多少比本人矮的人排在前面或者后面都不会有任何影响。注意到List 的add(int index, E element）方法在插入时，会将所有的元素从插入处顺延一位，我们就从高个子开始插就好啦！那么怎么按照这个顺序来插入呢，显然我们需要自己写一个sort的方法。

Arrays.sort(people, (o1,o2)->(o1[0]==o2[0]? o1[1]-o2[1]:o2[0]-o1[0])); 详细内容可见【我的代码】 。

416 分割等和子集：思路和 279. 完全平方数、322. 零钱兑换 是类似的，实质都是解不定方程，只是这里不定方程的解只能为0或者1。对这种特殊情况，我们写如下漂亮的代码

    int[] dp = new int[sum+1];
    dp[0] = 1;
    for (int num : nums){
        for (int i = sum; i >= num; i--){
            dp[i] += dp[i-num];
        }
        if (dp[sum] != 0 ) return true;
    }

这个循环进行完毕之后，对于每一个不为0的i，dp[i]的值就是和为i的组合方式数目。详细内容可见【我的代码】 。

438 找到字符串中所有字母异位词：我们的老朋友【滑动窗口法】 。

494 目标和：一个朴素的想法是用【暴力破解】 ，枚举所有的正负组合方式，对每一次结果进行筛选，但是这样就超时了。这样的暴力破解法也可以写成【递归】 的形式（会导致一部分不可避免的重复运算）。但其实呢，我们可以把所有的数分为两部分，第一部分用加号，第二部分用减号，由此可以得出用加号部分的和。问题就被转化成了 416. 分割等和子集 ，即寻找子集使得和为某一特定数字，每一个数字仅能用1次。详细内容可见【我的代码】 。

560 和为K的子数组：一个朴素的想法--【暴力破解】 。看到“和为K”，仿佛这是一道和 494. 目标和 类似的题目了。但是我们这里需要的是子数组，即需要连续性。为了做到这一点，我们可以把研究的目标从元素转到元素的累加和来，只要元素的累加和之差是我们的目标k，那么我就找到了一个符合的结果。至此，问题就变成了“两数之差”问题。这时候就不得不求助于我们的老朋友【HashMap】 了，这也是 1. 两数之和 、15. 三数之和 中常用的办法。注意需要考虑我们的子数列从0开始的情况，因此需要特别添加以下这一行代码。

map.put(0,1);

621 任务调度器: 【公式法】 。我们首先排列频率最高的任务，再把频率次高的任务依次插到前者的缝隙中去。假设频率最高的任务是唯一的，记它的频率为 [公式] ，那么所需总时间为 [公式] 。若还存在同样频率的其他任务，那么多 [公式] 个这样的任务，总时间就要 [公式] 。有趣的是，这样求出来的答案，有时候会比task的长度还要短，所以最后我们就要取一个max。

647 回文子串：回文子串问题中经常需要考虑的就是对称中心的讨论--对称中心可能是某个字符，也可能位于某个字符中间。解决它的一种办法是统一在两两字符间插入一个字符串中永远不会出现的字符，如‘#’，然后统一用‘#’作为对称中心，见【代码一】 。另一种办法则是用子函数，看一下输入参数你就明白了，

        sum+=isPalindrome(ch, i, i);
        sum+=isPalindrome(ch, i, i+1);

什么，你不明白？？？那你可以看一下【我的代码】 。

739 每日温度：显然【暴力破解】在这里是可行的。但实际上，我们可以根据已知结果跳过一些元素的验证。我们可以从数组末端开始依次向前，如果我们比较的元素ans[j]比当下元素ans[i]还要小，那么我们知道至少还要经过ans[j]个元素才能碰到比ans[i]大的元素--那么我们就可以一次性跳过ans[j]个元素的逐一比较。注意这里可能会碰到为0的情况需要单独讨论。详细内容可见【我的代码】 。