LeetCode刷题的一天（1）
前言
因为某些已知原因，我又开始在LeetCode上 真·刷题 了。
简单题·移除元素
确实是很简单啊，但是我还是写了一个小时，因为有些细节把控的不到位，写的过程中也发生了不少有趣的思考。
题目
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) { print(nums[i]);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
- 1
- 2
- 3
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
- 1
- 2
- 3
提示：
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
- 1
- 2
- 3
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
思路其实很直接，我不知道我是不是有讲过这道题，很亲切的感觉。
就是从前往后遍历，遇到相同的就和“末尾”互换一下位置，使用双指针的方式。
优化嘛，那就要交换的时候，把尾部的“target”消除掉（尾指针前移）。
很直接的思路。
代码实现
class Solution {
public: void change(int& a, int& b) { int c = a; a = b; b = c; } int removeElement(vector<int>& nums, int val) { int sz = nums.size(); for (int i = 0; i <= (sz-1); i++) { if (nums[i] == val) { while (sz-1 >= 0 && nums[sz-1] == val) { sz--; } if (sz - 1 > i) { change(nums[i], nums[sz - 1]); sz--; } } } return sz; }
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
思考
在写这题的时候，想了很多。为什么C++不支持[-1]检索？为什么C++不能执行切片？为什么C++ STL没有foreach的快速遍历，而是非要去用迭代器？
在网上一波搜索无果后，我想了想，也是，这些操作，还有什么很高效的算法去实现？那如果没有，自己写不就好了嘛。
果然，这些抱怨的源头都是因为读书少。
简单题·搜索插入位置
这题我都不想说我做过了。
这不就是二分法，难不成还要我祭出“加权二分法”？
题目
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
代码实现
class Solution {
public: int searchInsert(vector<int>& nums, int target) { for(int i=0;i<nums.size();i++) { if(nums[i]>=target) { return i; } } return nums.size(); }
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
中等题·四数之和
这个啊，之前讲N数和的时候讲过了，但是写起来居然这么麻烦。
代码还可以再优化，比如说抽象成N数和的通用解法，但是写的太累了，就没去抽象了。
class Solution {
public: void TwoSum(vector<int>& nums, vector<vector<int>>& ret, int target, int add1, int add2, int begin) {
for (vector<int>::iterator it = nums.begin() + begin; it != --nums.end(); it++) { //指针一号
// if (*it == *(++it)) //如果和下一位重复，就跳过（那如果 3 3 6呢？）
if(it!=nums.begin() + begin && *it==*(it-1)) //如果和上一位重复，就跳过 continue; int temp_target = target - *it;
for (vector<int>::iterator it2 = (it+1); it2 != nums.end(); it2++) { //这里就是不要和下一位重复咯 if ((it2+1) != nums.end() && *it2 == *(it2+1)) continue; //如果刚好碰上了，那就写入 if (temp_target == *it2) { ret.push_back({add1, add2, *it, temp_target}); } //如果下一位明显大于结果值 if ((it2+1) != nums.end() && *(it2+1) > temp_target) break;
}
}
}
void ThreeSum(vector<int>& nums, vector<vector<int>>& ret, int target, int add, int begin) {
int i = 0;
for (vector<int>::iterator it = nums.begin() + begin; it != (nums.end() - 2); it++) {
i++;
if (it != nums.begin() + begin && *it == *(it - 1)) //如果和上一位重复，就跳过 continue;
TwoSum(nums, ret, target - *it, add, *it, (begin + i));
}
}
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ret;
if (nums.size()<4)
return ret;
sort(nums.begin(), nums.end());
int i = 0;
for (vector<int>::iterator it = nums.begin(); it != (nums.end() - 3); it++){
i++;
if (it != nums.begin() && *it == *(it - 1)) //如果和上一位重复，就跳过 continue; ThreeSum(nums, ret, target - *it, *it, i);
}
return ret;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
困难题·跳跃游戏II
说困难呐，其实也不是很困难嘛。好吧，还是挺困难的。
贪心算法，都讲过的啦。
代码实现
class Solution {
public:
int jump(vector<int>& nums) { int maxPos = 0, n = nums.size(), end = 0, step = 0; /* maxPos:最远到达距离；end:边界*/ for (int i = 0; i < n - 1; ++i) { if (maxPos >= i) { //如果可以到达 i maxPos = max(maxPos, i + nums[i]); //不断调整当前可到达边界 if (i == end) { //到达边界 end = maxPos; //更新边界 ++step; //计算步数 } } } return step;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
累死啦，休息休息，刚刚报名了LeetCode的双周赛，十点半准备参加了。
一觉醒来，明早还有单周赛等着我。
文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。
原文链接：lion-wu.blog.csdn.net/article/details/114458135
- 点赞
- 收藏
- 关注作者
评论（0）