Day1

88. 合并两个有序数组（简单）

直接合并后排序

• 善于使用sort排序（很方便）

双指针

• 这个题很容易想到双指针，有两个数组，一个指针指向数组1，另一个指针指向数组2

• 如果我们从前往后遍历不重新开数组的话，nums1是容易被覆盖的，那么怎么解决？

逆向双指针法

• 如果没有多余的额外空间，可以从后往前来，就算num2的所有值都原封不动的放到num1后面，num1的数据也一定不会因为被覆盖而消失。

1. 两数之和（简单）

暴力枚举

• 一般来讲暴力法可取，也最容易想到，但是往往会因为超时而pass不了
• 所以我们只需要有思路即可，尽可能的想办法去优化两层的遍历即可

哈希表

• 哈希表常可以解决这类问题，记录一对一对的数据，常常想到map或者set
• 这里我常用的是unordered_map和unordered_set，由于这个题需要记录一下下标，所以我选用unordered_map

• 每次我们记录一下每个元素出现（类似于标记了），如果寻找到互补元素就输出就可以

• 运行提交之后时间从64ms变成了4ms，虽然多用了一点空间，但无关紧要

Day2

283. 移动零（简单）

双指针

485. 最大连续 1 的个数（简单）

一次遍历

• 数组的最后一个元素可能是 1，且最长连续 1 的子数组可能出现在数组的末尾，最后需要再比较一下

双指针

• 这个是我第一个想到的方法

645. 错误的集合（简单）

排序

• 这是我第一时间想到的方法，先排序再说

哈希表

• 重复的数字在数组中出现 2 次，丢失的数字在数组中出现 0 次，其余的每个数字在数组中出现 1 次。

• 因此可以使用哈希表记录每个元素在数组中出现的次数，然后遍历从 1 到 n 的每个数字，分别找到出现 2 次和出现 0 次的数字，即为重复的数字和丢失的数字。

• 这个思路就是非常巧妙，没有那么多的需要考虑的边界条件

Day3

287. 寻找重复数（中等）

修改下nums，怎么解（非题解）

• 其实可以先排序做的，之后用两个变量就可以，很简单

时间复杂度不为O(1)，怎么解（非题解）

• 最简单的就是用哈希表，很容易理解

二分查找（满足题意）

• 查找有范围的整数我们可以考虑二分查找
• 这个视频比官方题解讲的好多了
8-9 「力扣」第 287 题：寻找重复数_哔哩哔哩_bilibili
视频对应的文字描述与参考代码请见算法吧之「二分查找」专题：https://suanfa8.com/binary-search/。公众号：算法不好玩（谢绝商业推广）。知识星球（免费）：https://wx.zsxq.com/dweb2/index/group/51122882811144。, 视频播放量 2652、弹幕量 2、点赞数 84、投硬币枚数 62、收藏人数 43、转发人数 11, 视频作者 liweiwei1419, 作者简介 《算法不好玩》继续更新，感谢朋友们支持！，相关视频：8-1 「二分查找」的基本思想，8-2「力扣」第 704 题：二分查找，8-7 「二分查找」阶段总结，8-4 查找升序数组中 target 第一次出现的位置（中），【全348集】清华大佬终于把数据结构与算法整理成动画片了，通俗易懂，2024最新版！一周刷爆LeetCode，学完即可面试上岗！这还学不会，我直接退出IT圈！！，8-3 查找升序数组中 target 第一次出现的位置（上），8-6 「力扣」第 69 题：x 的平方根，6-1 快速排序的基本思想，8-8 while (left < right) 不一定表示搜索区间为「左闭右开」，6-6 三路快排

https://www.bilibili.com/video/BV1eT411u7oD/?spm_id_from=333.999.0.0&vd_source=8d4c0bb6f04271cbe95d70f568c88555

快慢指针（满足题意）

• 如果单纯两层循环必定会超时（前车之鉴，一定要优化

• 这个优化的思路非常的难想（需要利用快慢指针）（超级难）这里不做过多解释建议去看这两个题解 - 有两个题解写的不错：

287. 寻找重复数 - 力扣（LeetCode）

287. 寻找重复数 - 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。   示例 1： 输入：nums = [1,3,4,2,2] 输出：2 示例 2： 输入：nums = [3,1,3,4,2] 输出：3 示例 3 : 输入：nums = [3,3,3,3,3] 输出：3     提示： * 1 <= n <= 105 * nums.length == n + 1 * 1 <= nums[i] <= n * nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次   进阶： * 如何证明 nums 中至少存在一个重复的数字? * 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

https://leetcode.cn/problems/find-the-duplicate-number/solutions/58841/287xun-zhao-zhong-fu-shu-by-kirsche/

287. 寻找重复数 - 力扣（LeetCode）

287. 寻找重复数 - 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。   示例 1： 输入：nums = [1,3,4,2,2] 输出：2 示例 2： 输入：nums = [3,1,3,4,2] 输出：3 示例 3 : 输入：nums = [3,3,3,3,3] 输出：3     提示： * 1 <= n <= 105 * nums.length == n + 1 * 1 <= nums[i] <= n * nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次   进阶： * 如何证明 nums 中至少存在一个重复的数字? * 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

https://leetcode.cn/problems/find-the-duplicate-number/

667. 优美的排列 II（中等）

数学思维

• 这个题并没有考察算法，而是考的关于数学思维
• 其实关键就是如何翻（我刚开始想的是从第一个翻swap（1,2），swap（2,3）最后发现不对
• 之后找到了更好的方式，完全翻转，有一个较为清晰的图解
667. 优美的排列 II - 力扣（LeetCode）
667. 优美的排列 II - 给你两个整数 n 和 k ，请你构造一个答案列表 answer ，该列表应当包含从 1 到 n 的 n 个不同正整数，并同时满足下述条件： * 假设该列表是 answer = [a1, a2, a3, ... , an] ，那么列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数。 返回列表 answer 。如果存在多种答案，只需返回其中 任意一种 。   示例 1： 输入：n = 3, k = 1 输出：[1, 2, 3] 解释：[1, 2, 3] 包含 3 个范围在 1-3 的不同整数，并且 [1, 1] 中有且仅有 1 个不同整数：1 示例 2： 输入：n = 3, k = 2 输出：[1, 3, 2] 解释：[1, 3, 2] 包含 3 个范围在 1-3 的不同整数，并且 [2, 1] 中有且仅有 2 个不同整数：1 和 2   提示： * 1 <= k < n <= 104

https://leetcode.cn/problems/beautiful-arrangement-ii/solutions/1809575/you-by-capital-worker-rnwi/

697. 数组的度（简单）

哈希表

• 这个是我第一个想到的做法用unordered_map<int, vector<int>> mp

• 里面的vector第一个值是次数，第二个值是这个数在原数组中第一次出现的位置，第三个值这个数在原数组中最后一次出现的位置

565. 数组嵌套（中等）

图

• 这个题我第一个想法就是图，很明显要求的是连通图的最长的路径长度

• 我们学过的这种有向图，一定有一个或多个环
• 从 i 向 nums[i] 连边，我们可以得到一张有向图，有向图中每个点的出度和入度均为 1
• 所以我们vector<bool> vec(n)来标记访问过的节点 （这里不是很好想）

原地标记

769. 最多能完成排序的块（中等）

贪心

• 贪心算法本身我就觉得很玄学（有的时候根本想不到
• 这个题的思路：
• 由于 arr 是 [0,..,n−1] 的一个排列，若已遍历过的数中的最大值 mx 与当前遍历到的下标 i 相等，说明可以进行一次分割，累加答案。（局部最优）
• 但我还是没太搞明白这里（官方题解这里在说什么,放个链接
769. 最多能完成排序的块 - 力扣（LeetCode）
769. 最多能完成排序的块 - 给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。 我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。 返回数组能分成的最多块数量。   示例 1: 输入: arr = [4,3,2,1,0] 输出: 1 解释: 将数组分成2块或者更多块，都无法得到所需的结果。 例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。 示例 2: 输入: arr = [1,0,2,3,4] 输出: 4 解释: 我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。 然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。 对每个块单独排序后，结果为 [0, 1], [2], [3], [4]   提示: * n == arr.length * 1 <= n <= 10 * 0 <= arr[i] < n * arr 中每个元素都 不同

https://leetcode.cn/problems/max-chunks-to-make-sorted/solutions/1886333/zui-duo-neng-wan-cheng-pai-xu-de-kuai-by-gc4k/

• 这个链接如果实在看不懂建议跳过看数学思路

数学思路

• 这个想法我主要看到了一个评论区的答案（豁然开朗）

• 考虑到数组长度为n，而且数组元素位于区间[0, n-1]且不重复，那么数组排好序后，每个值和下标恰好是相等的；所以，从左到右遍历数组，并且分别对值和下标累加求和，只要两个和相等，就切出一个块。

单调栈

• 这个题我还真就没想到有单调栈这个做法（也挺厉害的

• 根据题目，我们可以发现，从左到右，每个分块都有一个最大值，并且这些分块的最大值呈单调递增。我们可以用一个栈来存储这些分块的最大值。最后得到的栈的大小，也就是题目所求的最多能完成排序的块。
769. 最多能完成排序的块 - 力扣（LeetCode）
769. 最多能完成排序的块 - 给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。 我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。 返回数组能分成的最多块数量。   示例 1: 输入: arr = [4,3,2,1,0] 输出: 1 解释: 将数组分成2块或者更多块，都无法得到所需的结果。 例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。 示例 2: 输入: arr = [1,0,2,3,4] 输出: 4 解释: 我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。 然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。 对每个块单独排序后，结果为 [0, 1], [2], [3], [4]   提示: * n == arr.length * 1 <= n <= 10 * 0 <= arr[i] < n * arr 中每个元素都 不同

https://leetcode.cn/problems/max-chunks-to-make-sorted/solutions/1888329/by-lcbin-jgrv/

• 画个图更好理解，如果当前元素大于栈顶，直接推进去，如果小于一直弹出再比较

系列专题介绍

每日刷题板块 | NotionNext BLOG

这是一个由NotionNext生成的站点

https://own.chailyncui.blog/daily