
Two-pointers
双指针算法(移除元素类型)
leetcode.27
- 链接https://leetcode.cn/problems/...
- 解题方法:用len指针指向新数组下标
i指针从前往后遍历原数组
如果nums[i] == val
那么len指针不动,i指针继续向后遍历
如果nums[i] != val
那么len向后移动一位,并将原数组的值赋给新数组
返回新数组的下标即可 leetcode解题代码
class Solution { public: int removeElement(vector<int>& nums, int val) { int len = 0; for (int i = 0; i < nums.size(); i ++){ if (nums[i] == val) continue; else nums[len ++] = nums[i]; } return len; } };
- ACM模式调试
输入
第一行输入两个数n,val
n表示数组中有n个数,val表示目标值
第二行表示数组
4 3
3 2 2 3
输出
第一行表示移除目标值之后新数组的长度
第二行表示新数组
2
2 2
调试代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, val;
vector<int> nums(4);
cin >> n >> val;
for (int i = 0; i < n; i ++) cin >> nums[i];
vector<int> res;
for (int i = 0; i < n; i ++){
if (nums[i] == val) continue;
else{
res.push_back(nums[i]);
}
}
cout << res.size() << endl;
for (auto c: res){
cout << c << ' ';
}
return 0;
}
leetcode.26
- 链接https://leetcode.cn/problems/...
- 解题方法:与上一题类似,注意特判第一位
leetcode解题代码
class Solution { public: int removeDuplicates(vector<int>& nums) { int len = 0; for (int i = 0; i < nums.size(); i ++){ if (i == 0 || nums[i] != nums[i - 1]) nums[len ++] = nums[i]; } return len; } };
- ACM模式调试 和上题类似
leetcode.283
- 链接https://leetcode.cn/problems/...
- 解题方法:将题目转换为
移除目标值为0的元素(与第一题类似)
并保证新数组与原数组的元素个数相同(差多少个元素就补多少个0) leetcode解题代码
class Solution { public: void moveZeroes(vector<int>& nums) { int k = 0; for (int i = 0; i < nums.size(); i ++){ if (nums[i] != 0) nums[k ++] = nums[i]; } while (k < nums.size()) nums[k ++] = 0; } };
- ACM模式调试
输入
第一行输入一个数n
n表示数组中有n个数
第二行表示数组
5
0 1 0 3 12
输出
新数组
1 3 12 0 0
调试代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n;
vector<int> nums(5);
cin >> n;
for (int i = 0; i < n; i ++) cin >> nums[i];
vector<int> res;
for (int i = 0; i < n; i ++){
if (nums[i] != 0)
res.push_back(nums[i]);
}
while (res.size() < n) res.push_back(0);
for (auto c: res){
cout << c << ' ';
}
return 0;
}
leetcode.844
- 链接https://leetcode.cn/problems/...
- 解题方法:定义一个函数,函数的功能是返回编辑结束后的字符串
遍历字符串
如果当前字符串不是'#'则将其加入答案
如果当前字符串是'#'则将上一个字符串删除
调用函数,判断两个字符串是否相等 leetcode解题代码
class Solution { public: string edit(string& s){ string res; for (auto c: s){ if (c != '#') res += c; else if (res.size()) res.pop_back(); } return res; } bool backspaceCompare(string s, string t) { return edit(s) == edit(t); } };
- ACM模式调试
输入
第一行输入字符串s
第二行输入字符串t
ab#c
ad#c
输出
true
调试代码
#include <iostream>
#include <string>
using namespace std;
string edit(string& s){
string res;
for (auto c: s){
if (c != '#') res += c;
else
if (res.size())
res.pop_back();
}
return res;
}
bool compare(string& s, string& t){
if (edit(s) == edit(t)) cout << "true" << endl;
else cout << "false" << endl;
return true;
}
int main(){
string s, t;
getline(cin, s);
getline(cin, t);
compare(s, t);
return 0;
}
解题参考:https://www.acwing.com/
刷题顺序:https://www.programmercarl.com/