11. 26. 删除有序数组中的重复项(简单，双指针)
26. 删除有序数组中的重复项 - 力扣（LeetCode）
思想:
1.我的思想:
双指针遍历+集合储存已有元素
2.官方思想：
题目条件有序数组删除重复元素，所以重复元素都是连续存在的
同向快慢指针，慢指针指向下一个赋值位置，快指针遍历寻找不重复元素，即fast[i]!=fast[i-1]时，找到不重复元素，赋值给slow位置，slow++
最终[0,slow)为不重复元素区域，长度为slow
初始条件判断：数组元素为0直接返回0，让fast[i-1]有意义
代码
我的:
c++:
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
set<int> s;
int n = nums.size();
int left = 0;
for (int right = 0; right < n; ++right) {
if (s.find(nums[right]) == s.end()) {
nums[left] = nums[right];
left++;
s.insert(nums[right]);
}
}
return left;
}
};
python:
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
s = set()
n = len(nums)
left, right = 0, 0
for right in range(n):
if nums[right] not in s:
s.add(nums[right])
nums[left] = nums[right]
left += 1
return left
官方:
c++:
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n = nums.size();
if (n == 0)
return 0;
int slow = 1;
for (int fast = 1; fast < n; ++fast) {
if (nums[fast] != nums[fast - 1]) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
};
python:
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
slow = 1
for fast in range(1, n):
if nums[fast] != nums[fast - 1]:
nums[slow] = nums[fast]
slow += 1
return slow
12. 283. 移动零(简单,双指针)
思想
1.快慢双指针，10 27.移除元素 val=0时的特殊情况，且不再是赋值，而是交换
代码
c++:
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size();
int slow = 0;
for (int fast = 0; fast < n; ++fast) {
if (nums[fast] != 0) {
swap(nums[slow], nums[fast]);
slow++;
}
}
}
};
python:
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
slow = 0
for fast in range(n):
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
13. 844. 比较含退格的字符串(简单,学习，栈，双指针)
思想
1.法一（栈）：
最直观想到遇到’#'号回退，来模拟这一过程，就是栈,因为是字符串处理，可以直接用字符串当栈
注意:栈要弹出元素时立刻想到判断栈不为空
2.法二（双指针）：
（1）一个字符是否会被删掉取决于后面的字符，与前面的字符无关，所以逆序遍历可以先遇到#号字符从而确定前面的字符是否要被删掉
（2）目标是比较不会被删掉的字符，所以用两个同向逆序指针，i表示当前要比较的不会被删掉的字符，skip记录当前遇到的#号字符数量，即要删除的字符数量，从而确定i的位置，逻辑如下：
- 遇到#号字符，skip++，i–
- 未遇到#号字符
- skip>0,删除当前字符,i–
- skip=0,退出寻找i的位置循环
而总体的遍历指针是i，遍历范围[0,n),寻找i的位置后要判断是否在范围内
代码
法一：
c++：
class Solution {
public:
bool backspaceCompare(string s, string t) {
if (build(s) == build(t))
return true;
return false;
}
string build(string str) {
string res;
for (char ch : str) {
if (ch != '#')
res.push_back(ch);
else if (!res.empty())
res.pop_back();
}
return res;
}
};
python:
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
if self.build(s) == self.build(t):
return True
return False
def build(self, s: str) -> str:
res = ""
for ch in s:
if ch != "#":
res += ch
elif s:
res = res[:-1]
return res
1.调用函数要用self.
2.字符串是不可变对象，要用+=
3.删除最后一个字符为[:-1],因为最后一个end取不到
法二:
c++:
class Solution {
public:
bool backspaceCompare(string s, string t) {
int i = s.size() - 1, j = t.size() - 1;
while (i >= 0 ||
j >= 0) { // 一个为空串时，另一个可能前面还有#号可能变成空串
int skipS = 0, skipT = 0;
while (i >= 0) {
if (s[i] == '#') {
skipS++;
i--;
} else if (skipS > 0) {
skipS--;
i--;
} else {
break;
}
}
while (j >= 0) {
if (t[j] == '#') {
skipT++;
j--;
} else if (skipT > 0) {
skipT--;
j--;
} else {
break;
}
}
if (i >= 0 && j >= 0) {
if (s[i] != t[j]) {
return false;
}
} else {
if (i >= 0 || j >= 0) {
return false;
}
}
i--;
j--;
}
return true;
}
};
python:
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
i, j = len(s) - 1, len(t) - 1
while i >= 0 or j >= 0:
skipS, skipT = 0, 0
while i >= 0:
if s[i] == "#":
skipS += 1
i -= 1
elif skipS > 0:
skipS -= 1
i -= 1
else:
break
while j >= 0:
if t[j] == "#":
skipT += 1
j -= 1
elif skipT > 0:
skipT -= 1
j -= 1
else:
break
if i >= 0 and j >= 0:
if s[i] != t[j]:
return False
else:
if i >= 0 or j >= 0:
return False
i -= 1
j -= 1
return True