【leetcode】33. 搜索旋转排序数组
题目内容 33. 搜索旋转排序数组 思路分析 本题是一道二分查找的进阶题目。 参考资料：官方题解 方法一：二分查找 做这道题目需要意识到一个性质：在搜索范围是旋转排序数组的情况下，二分的结果是左右两半有一半是有序的，有一半是乱序的。 而判断哪一部分乱序的方法为判断nums[0]和nums[mid]的大小： 若nu...
【leetcode】35. 搜索插入位置
题目内容 搜索插入位置 思路分析 本题其实就是C++的lower_bound函数的弱化版。 方法一：C++ STL 直接调lower_bound函数。 方法二：自己实现 直接按照模板来写，不同之处是如果没找到target的话需要返回插入的位置（left指针）。 代码 #include <vector>...
【leetcode】278. 第一个错误的版本
题目内容 278. 第一个错误的版本 思路分析 本题是一道二分查找题目，掌握二分查找的写法后写起来比较简单。关于二分查找的写法可以见我写了首诗，让你闭着眼睛也能写对二分搜索，可以说讲的非常清楚。 方法一：找左侧边界的二分查找 基本上按模板来就行，和模板不同的是本题的查找只有是和不是两种状态，而非平时的大于/小于/...
【leetcode】324. 摆动排序 II
题目内容 324. 摆动排序 II 思路分析 参考资料1---题解1---方法一、方法二、方法三 参考资料2---题解2--方法一 参考资料3---荷兰国旗问题wiki---方法二 参考资料4---【leetcode】75. 颜色分类 ---方法二 参考资料5---快速选择算法---方法二 参考资料6---时间复...
快速选择算法
资料 基于快排的快速选择算法 快速排序亲兄弟：快速选择算法 快速选择-维基百科，自由的百科全书 解读 快速选择其实是快排的变种，快排的思想就是以pivot为枢轴，交换两边的数字，交换完毕的最终效果是pivot左边都小于等于pivot，右边都大于pivot。设pivot的下标为p，则说明找到了数组中第p大元素。 若...
【leetcode】215. 数组中的第K个最大元素
题目内容 215. 数组中的第K个最大元素 思路分析 【方法一】参考资料--快速排序亲兄弟：快速选择算法 【方法一】力扣官方题解 方法一：快速选择 本题是快速选择的经典使用场景，就是在学习快速选择的过程中来顺便学习此题。 关于快速选择的学习笔记详见：快速选择算法 此外，快速选择也可以通过C++的nth_eleme...
【leetcode】376. 摆动序列
题目内容 376. 摆动序列 思路分析 方法一：贪心 参考资料1 参考资料2 参考资料3 贪心策略：只选极值点，而忽略中间的所有点。 可以贪的原因：只选极值点，可以增大后续元素被选中为摆动序列的概率。详见参考资料2和3中的图。 实际实现时，只需记录极值点的个数。可以按照参考资料1，默认最右端有一个极值点，最左端（...
【leetcode】283. 移动零
题目内容 283. 移动零 思路分析 参考资料1 参考资料2 本题和75. 颜色分类思想差不多。 方法一：双指针两次遍历 可以设置ptr指针，用来指示按原本的顺序排列的非0数。 第一次遍历：遇到非0数则对nums[ptr]赋nums[i]，同时将ptr+1。 第二次遍历：第一次遍历后，ptr以前的区域为按原本顺序...
【leetcode】75. 颜色分类
题目内容 75. 颜色分类 思路分析 参考资料 方法一：单指针 可以采用一个单指针ptr，来表征“头部区域”的范围。遍历两遍数组： 第一遍：遇到0则将0放进“头部区域”，即交换nums[i]和nums[ptr]，并将ptr+1； 第二遍：遇到1则将1放进“头部区域”，即交换nums[i]和nums[ptr]，并将...
【leetcode】88. 合并两个有序数组
题目内容 88. 合并两个有序数组 思路分析 参考资料 方法一：插入排序 看到本题，自己想的解法是进行插入排序。 与正常的插入排序一样，都是二分查找+插入的思路。只不过本题有一点点不同：数组一中用0预留出了数组二的位置，因此 数组一整体相当于不是有序的，如[1, 2, 3, 0, 0, 0]。不可以直接在begi...
【leetcode】228. 汇总区间
题目内容 228. 汇总区间 思路分析 本题的算法感觉就是个自然而然的算法，也没有什么技巧。但是自己写的代码好蠢，还分各种情况讨论。答案的代码又精简，又把所有的情况考虑进去了。向答案学习。 方法一：一次遍历 参考资料 本题目在以下两个情况下会产生新区间： 遍历到最后一个数，必须得输出一个新区间 数字不连续，即nu...
【leetcode】152. 乘积最大子数组
题目内容 152. 乘积最大子数组 思路分析 方法一：动态规划 本题与53. 最大子序和类似，但是本题是乘法运算，因此nums[i]的最大乘积不一定依赖于前一个数字（如[-1, 2, -3, 4]）。因此需要利用以下关系来进行动态规划： 当前最大值 = max(上一个数的最大值*当前数, 上一个数的最小值*当前数...
【leetcode】238. 除自身以外数组的乘积
题目内容 238. 除自身以外数组的乘积 思路分析 按理说比较容易想到的一个O(n)的解是把所有数乘起来，然后除以nums[i]。然而该方法遇到0会失效，且题目不允许用除法。最重要的是我连这种方法都想不到... 方法一：左右乘积列表 可以维护两个乘积列表left_multi和right_multi，该列表的第i个...
【leetcode】209. 长度最小的子数组
题目内容 209. 长度最小的子数组 思路分析 参考资料 方法一：前缀和+二分查找 由于题目所给的数组元素都是正整数，且要找到满足≥target的子序列。 因此，设题目所给数组的大小为n，可以创建一个大小为n+1的数组sums，其第i个元素为前i个数字的和，则问题转换为： 对于指定的下标i，求满足sums[j...
【leetcode】53. 最大子序和
题目内容 53. 最大子序和 思路分析 本题比较简单，可使用动态规划完成 方法一：动态规划 最大子序列和有以下特征： nums[i]的最大子序列和等于max(nums[i-1]的最大子序列和加nums[i], nums[i]) 因此nums[i]可利用nums[i-1]的计算结果，即可进行动态规划。 使用动态规划...
【leetcode】295. 数据流的中位数
题目内容 295. 数据流的中位数 思路分析 参考资料 方法一：两个堆 此方法十分巧妙，这里直接上个来自这里的图： 其实就是利用中位数是最中间的数字的特点，将数字按大小分为个数相等的两部分（或数字较小的部分元素个数可以比数字较大的部分多1）： bigger_nums：较大的一部分数字，它是一个堆顶为最小值的堆； ...
【leetcode】239. 滑动窗口最大值
题目内容 239. 滑动窗口最大值 思路分析 参考资料 方法一：优先队列 似乎这种最大值问题比较容易想到优先队列这种数据类型，优先队列可以维护一个最大或最小值，一般是由二叉堆实现的。关于二叉堆我专门写了一篇学习笔记。 优先队列可以自动帮我们得出前i个数的最大值，然而这个题目是个窗口问题，因此每次判断队列的最大值的...
【leetcode】57. 插入区间
题目内容 插入区间 思路分析 本题需要首先搞清楚题目的意思，一旦插入的区间与原本的区间有交集，就需要合并。 解题的核心在于考虑清楚插入区间与所遍历的区间的关系，以及考虑清楚所遇到的各种情况。 方法一：模拟 参考资料 设i_l、i_r为当前正在遍历区间的左右端点值，n_l、n_r为插入区间的左右端点值。则可以确定的...
【leetcode】327. 区间和的个数
题目内容 327. 区间和的个数 思路分析 TODO 看不懂 一个月内做这个题 代码 收获
【leetcode】287. 寻找重复数
题目内容 287. 寻找重复数 思路分析 本题由于二分查找的条件劝退，一连拖了好几天，拖的有点恶心了，就只好留了些坑把这个题先跳过了。 本题主要是要求使用O(n)的时间复杂度和O(1)的空间复杂度，这个要求卡死了很多解法。 除了这里用的二分法以外，常见的另一种方法还有快慢指针法，见方法二-参考资料一。 方法一：基...
【leetcode】164. 最大间距
题目内容 164. 最大间距 思路分析 本题仍然是一道排序题，题目的核心是对数字进行排序，排好序后就很简单了。而题目要求使用线性时空间复杂度，因此不能使用基于比较的排序方法。 解法参考资料 方法一：基数排序 基数排序资料 基数排序是一种非比较的排序方式，可以实现O(n)的时空复杂度排序。目前为止见过的另一种基于非...
【leetcode】42. 接雨水
题目内容 42. 接雨水 思路分析 本题的总体思路为从第二个柱子起，判断每个柱子左右两边柱子的最大高度，然后max(0, min(左右两边的最大高度)-当前柱子高度)即为当前柱子可以装的水量。 方法一：动态规划 参考资料（其中的解法3） 利用当前柱子及其左边所有柱子的最大高度max_left_height=max...
【leetcode】128. 最长连续序列
题目内容 128. 最长连续序列 思路分析 本题一上来的考虑是排序然后数一下连续的个数，但做出来以后发现会超时。正确的思路是使用哈希 方法一：排序（超时） 使用快排对数组进行排序，然后数连续的个数。 方法二：哈希 参考资料 内层循环： 将每个数num哈希存储（这里使用C++的unorderd_set，查找的时间复...
【leetcode】334. 递增的三元子序列
题目内容 334. 递增的三元子序列 思路分析 本题比较简单（没怎么思考，直接看的答案） 方法一：脑筋急转弯 设置两个变量small=INT_MAX和mid=INT_MAX，依次遍历数组，若小于等于small则更新small，若小于等于mid则更新mid。 注意一定要加上等于号的限制，等于号能保证遇到相等情况时能...
【leetcode】289. 生命游戏
题目内容 289. 生命游戏 思路分析 感觉本题最大的难点在于游戏规则，代码里很大一部分都是为了去描述游戏规则。其次如何把空间优化到O(1)也比较难想，本题的状态法就比较巧妙。 方法一：复制数组法 为避免新状态造成老状态的误判，直接将结果存至新的数组中。这样做一个很显然的缺点是很费空间，但是是可以通过的。 方法二...
【leetcode】11. 盛最多水的容器
题目内容 11. 盛最多水的容器 思路分析 看到本题目时，表示没有什么头绪，就只好暴力法硬刚，结果超时了... 看了各个题解，几乎全用的双指针法，其中感觉“缩小搜索空间”的这个说法深得我意，特别是那个表格图，感觉讲得非常非常清晰。 首先要明确的是，设下标为i和j，则此时容器的容积为(j - i) * min(he...
【leetcode】309. 最佳买卖股票时机含冷冻期
题目内容 309. 最佳买卖股票时机含冷冻期 思路分析 本题也是股票系列的一道题目。题目中提到： 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] 看到状态这个词就很明显的想到动态规划了（外加股票系列本来就动态规划用的多），虽然最后用的状态不是这个... 本题是自己定了状态仔细推导以后发现不对劲，又...
【leetcode】188. 买卖股票的最佳时机4
题目内容 188.买卖股票的最佳时机4 思路分析 本题是123. 买卖股票的最佳时机3 的更一般化，可直接由股票问题3的题解改编而来。 方法：动态规划 和股票问题3类似，使用一个大小为2k的数组cash来存储每一天的状态，令j为0,2,4,6...，则下标为j的元素代表某天买过j/2 + 1次，卖过j/2次；下标...
【leetcode】123. 买卖股票的最佳时机3
题目内容 123. 买卖股票的最佳时机3 思路分析 本题使用了动态规划的方法，状态比较多，比较难想到。 方法一：动态规划 参考链接1，参考链接2 每天交易完成后有5种状态： -1 不曾交易过 0 买过一次 1 买过一次，卖过一次 2 买过两次，卖过一次 3 买过两次，卖过两次 因为状态-1不会对现金产生影响，因此...
【leetcode】122. 买卖股票的最佳时机2
题目内容 122. 买卖股票的最佳时机2 思路分析 本题是股票系列的第二题，似乎一共有五六道题，做完以后就可以去炒股发家致富了🤣。 本题共有三种思路，拟人（方法一）、动态规划（方法二和三）和贪心（方法四）。其中方法一感觉也可以叫贪心。 感觉拟人和贪心比较容易想到，而动态规划，特别是二维动态规划，思路从何而来？感觉...
【leetcode】121. 买卖股票的最佳时机
题目内容 121. 买卖股票的最佳时机 思路分析 本题看起来很简单，但是自己做就是怎么都做不出来...自闭ing😶 本题共有两种思路，动态规划（方法一和方法二）和单调栈（方法三）。 方法一：动态规划 参考链接 选用动态规划的原因： 包含了重叠的子问题，买入和卖出股票的最佳时机是由之前的状态决定的，而之前的状态又是...
【leetcode】45. 跳跃游戏 II
题目内容 45. 跳跃游戏 II 思路分析 本题难度为困难，是55. 跳跃游戏的plus版。55题是让判断是否能到达，使用了贪心算法（尽量跳的远）。 第一眼看到这个题时，算法课学艺不精的我，打算用动态规划来做，感觉应该有可以重复利用的子问题，结果栈溢出，不断地迭代而不退出，翻车了.... 本题的正确解法应该为贪心...
【leetcode】55. 跳跃游戏
题目内容 55. 跳跃游戏 思路分析 一开始看到题目的时候，没什么思路，感觉可能要用动态规划，就直接去看了答案。看了答案感觉还是挺简单的，虽然说是贪心，但是没感觉贪心在哪了，只感觉是一种“聪明人”的做法。 翻评论的时候看到一句话 属于贪心，每一步都贪婪的计算最远到达位置。 那就勉强算贪心吧~ 具体思路如下： 维护...
【leetcode】217. 存在重复元素
题目内容 217. 存在重复元素 思路分析 本题是一道调节心态题（做完我又觉得我行了😂） 主要思路为使用一个set来记录每个数字出现的次数，当发现有数字的出现次数大于1时，则证明存在重复元素，返回true；遍历完数组还未返回，则证明不存在重复元素，返回false。 另外，看题目的评论区有人说 来了，来了。面试经典...
【leetcode】275. H指数2
本题的代码实测正确，但思路分析部分个人感觉还有点含糊，请谨慎查看思路分析部分。
【leetcode】274. H指数
本题的代码实测正确，但思路分析部分个人感觉还有点含糊，请谨慎查看思路分析部分。