Leetcode 0814周总结

本周刷题：

88, 108, 121, 219, 228, 268, 283, 303, 349, 350, 414, 448

88 合并两个有序数组

nums1={1, 2, 3 ,0, 0, 0}

nums2={2, 5, 6}

合成效果：nums1={1, 2, 2, 3, 5, 6}

思路：【双指针】对两个数组设置双指针，依次比较哪个小就放入新数组。遍历完之后再把新数组复制给 nums1。

108 将有序数组转换为二叉搜索树

未做。

121 买卖股票的最佳时机

【动态规划】

217. 存在重复元素

数组 nums1={1, 2, 3, 1}，任一值在数组中出现至少两次，就返回 true，否则返回 false。

思路：先排序，然后依次遍历。判断当前元素 与 之前元素是否相同，发现相同就返回 true，如果到最后都没相同，则返回 false。

219. 存在重复元素 II

滑动窗口，但是忘记怎么做了，好了仔细回想了一下想起来了 = =

题目：数组nums={1, 2, 3, 1}，整数k，判断数组中是否存在两个不同的索引 i 和 j。满足 nums[i] == nums[j]，且 abs(i-j) <= k。存在返回true，否则返回false。

思路：【滑动窗口】，使用set设置一个数组，遍历nums数组，先判断是否在st中有，如果没有就将该值加入st（这里使用set不使用vector是可以去重，且可以使用find函数，vector遍历查找会超时）。判断如果st中元素大于k个，就删掉最开始加入的元素（这里set自动排序，要按num指定下标那个数字，或者这里可以使用 unordered_set）。

228. 汇总区间

题目：数组nums={0, 1, 2, 4, 5, 7} 输出效果：["0->2","4->5","7"]

思路：【双指针】【滑动窗口】

设置一个map数组存放区间，先low，再fast++，如果发现 nums[fast] != nums[fast-1] 就把low，fast插入到map中，更新low。

输出再把map集合转到 vector<string> 中int转字符串可以用 to_string() 方法

268. 丢失的数字

题目：给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

思路：超简单。普通遍历。先排序，遍历，如果哪个和下标不同，就返回该有的那个数字。

283. 移动零

题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例：输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]

思路1：从前往后遍历，遇0删除并计数k，最后在后面插入k个0

思路2：【双指针】left指向零元素，right往后跑，遇到非零元素则交换。交换之后left也要更新。right更新。

303 区域和检索-数组不可变

没看懂题目==

349.两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例：输入：nums1 = [1, 2, 2, 1], nums2 = [2, 2] 输出：[2]

思路：【哈希表】遍历nums1并设置哈希表，再遍历nums2，如果哈希表有值，就说明有。其中有几个细节需要注意（比如不可二次哈希赋值，不可二次插入结果数组）

350. 两个数组的交集 II

题目：请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）

示例：输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2]

思路：【双指针，分别指向两个数组】，比较两个数组对应值，然后相同则入栈，不同则自增。

414.第三大的数

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

示例：输入：[3, 2, 1] 输出：1 解释：第三大的数是 1 。

思路：设置一个set，遍历时往里面插值，如果大于3，就删除首元素（最小）。

448. 找到所有数组中消失的数字

题目：给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例：输入：nums = [4,3,2,7,8,2,3,1] 输出：[5,6]

思路：【哈希表】，且自身实现哈希表。