26.删除有序数组的重复项
给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int slowidx = 0;
for(int fastidx = 0;fastidx < nums.size();fastidx++){
if(nums[fastidx]!=nums[slowidx]){
slowidx++;
nums[slowidx]=nums[fastidx];
}
}
return slowidx+1;
}
};
283.移除零
给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。
请注意 ,必须在不复制数组的情况下原地对数组进行操作。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int slow = 0;
for(int fast = 0;fast<nums.size();fast++){
if(nums[fast] != 0){
swap(nums[slow],nums[fast]);
slow++;
}
}
}
};
太好了是交换函数
844.比较含退格的字符串
给定 s 和 t 两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回 true 。# 代表退格字符。
注意:如果对空文本输入退格字符,文本继续为空。
示例 1:
输入:s = "ab#c", t = "ad#c"
输出:true
解释:s 和 t 都会变成 "ac"。
示例 2:
输入:s = "ab##", t = "c#d#"
输出:true
解释:s 和 t 都会变成 ""。
示例 3:
输入:s = "a#c", t = "b"
输出:false
解释:s 会变成 "c",但 t 仍然是 "b"。
提示:
1 <= s.length, t.length <= 200s和t只含有小写字母以及字符'#'
方法一:重构字符串(栈)
遍历原字符串,遇到非退格符则在新字符串末尾插入该字符,遇到退格符则删除新字符串末尾的元素(删除元素前需判空)
class Solution {
public:
bool backspaceCompare(string s, string t) {
return build(s) == build(t);
}
string build(string str){
string ret;
for(char ch : str){
if(ch != '#'){
ret.push_back(ch);
}
else if(ret.size() != 0){
ret.pop_back();
}
}
return ret;
}
};
时间复杂度:O(N+M),其中 N 和 M 分别为字符串 S 和 T 的长度。我们需要遍历两字符串各一次。
空间复杂度:O(N+M),其中 N 和 M 分别为字符串 S 和 T 的长度。主要为还原出的字符串的开销。 链接:https://leetcode.cn/problems/backspace-string-compare/solutions/451606/bi-jiao-han-tui-ge-de-zi-fu-chuan-by-leetcode-solu/
方法二:双指针法
一个字符是否会被删掉,只取决于该字符后面的退格符,而与该字符前面的退格符无关。因此当我们逆序地遍历字符串,就可以立即确定当前字符是否会被删掉。
具体地,我们定义 skip 表示当前待删除的字符的数量。每次我们遍历到一个字符:
若该字符为退格符,则我们需要多删除一个普通字符,我们让 skip 加 1,i–(删去退格符)
若该字符为普通字符:
若 skip 为 0,则说明当前字符不需要删去;
若 skip 不为 0,则说明当前字符需要删去,我们让 skip 减 1,i–(删去无效字符)
这样,我们定义两个指针,分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串,直到两字符串能够各自确定一个字符,然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等,或遍历完字符串为止。 链接:https://leetcode.cn/problems/backspace-string-compare/solutions/451606/bi-jiao-han-tui-ge-de-zi-fu-chuan-by-leetcode-solu/
- 外层
while循环的每一次迭代,就是从两个字符串中各找到一个有效字符,然后比较它们。 - 内层循环用于找到有效字符(i,j指向有效字符)
- 内层二个for循环后就找到了有效字符,然后进行比较判断
- 二个字符串都没遍历完:当有效字符不相等,说明整个有效字符串不相等,返回false。当有效字符相等,则进入下一次循环
- 一个字符串遍历完,另一个没有遍历完:说明有效字符串长度不等,无需再判断,直接返回false
- i–,j–,进入下一次外层循环
class Solution {
public:
bool backspaceCompare(string s, string t) {
int i = s.size()-1;
int j = t.size()-1;
int skips = 0;
int skipt = 0;
while(i >= 0 || j>= 0){
//下面二个for循环为了找到二个字符串各自的有效字符(从后往前)
while(i >= 0){
if(s[i] == '#'){
i--;
skips++;
}
else if(skips>0){
skips--;
i--;
}
else{
break;
}
}
while(j >= 0){
if(t[j] == '#'){
j--;
skipt++;
}
else if(skipt>0){
skipt--;
j--;
}
else{
break;
}
}
//如果都没遍历完,说明目前有效字符一样长,二个有效字符进行比较,不相同返回false
if(i >=0 &&j >= 0){
if(s[i] != t[j]){
return false;
}
}
//如果有一串字符串已经遍历完,另一串还没有,说明有效字符长度不一样,不可能相等,返回false
else{
if(i >= 0 || j >= 0){
return false;
}
}
//找到了一个有效字符后,接着找下一个有效字符(外层循环一次就相当于找到一个有效字符)
i--;
j--;
}
return true;
}
};
977.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
示例 1:
输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]
示例 2:
输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]
提示:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums已按 非递减顺序 排序
进阶:
- 请你设计时间复杂度为
O(n)的算法解决本问题
方法一:快速排序
先把各元素平方放到新数组,再用快排函数
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int>ans;
for(int num:nums){
ans.push_back(num * num);
}
sort(ans.begin(),ans.end());
return ans;
}
};
- 时间复杂度:O(nlogn),其中 n 是数组 nums 的长度。
- 空间复杂度:O(logn)。除了存储答案的数组以外,我们需要 O(logn) 的栈空间进行排序。
方法二:双指针
使用两个指针分别指向位置 0 和 n−1,每次比较两个指针对应的数,选择较大的那个逆序放入ans容器并移动指针。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
vector<int>ans(n);
int i = 0;
int j = n-1;
int pos = j;
while(i <= j){
if(nums[i]*nums[i] < nums[j]*nums[j]){
ans[pos] = nums[j]*nums[j];
j--;
}
else {
ans[pos] = nums[i]*nums[i];
i++;
}
pos--;
}
return ans;
}
};
- 时间复杂度:O(n),其中 n 是数组 nums 的长度。
- 空间复杂度:O(1)。除了存储答案的数组以外,我们只需要维护常量空间。

