# leetcode-1 **Repository Path**: ypsun/leetcode-1 ## Basic Information - **Project Name**: leetcode-1 - **Description**: 题目可以用三位题号搜索到，如“001”。稍后会全部更新为四位题号。 - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2020-12-23 - **Last Updated**: 2020-12-23 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 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。这里也可以用后一种方法改写，但是会慢一些。我之前还写过一篇文章，专门讨论这题-- 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种。 i1时，说明以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 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的情况需要单独讨论。详细内容可见【我的代码】 。