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, 0for right in range(n):if nums[right] not in s:s.add(nums[right])nums[left] = nums[right]left += 1return 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 0slow = 1for fast in range(1, n):if nums[fast] != nums[fast - 1]:nums[slow] = nums[fast]slow += 1return slow

12. 283. 移動零(簡單,雙指針)

283. 移動零 - 力扣（LeetCode）

思想

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 = 0for fast in range(n):if nums[fast] != 0:nums[slow], nums[fast] = nums[fast], nums[slow]slow += 1

13. 844. 比較含退格的字符串(簡單,學習，棧，雙指針)

844. 比較含退格的字符串 - 力扣（LeetCode）

思想

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 Truereturn Falsedef build(self, s: str) -> str:res = ""for ch in s:if ch != "#":res += chelif 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) - 1while i >= 0 or j >= 0:skipS, skipT = 0, 0while i >= 0:if s[i] == "#":skipS += 1i -= 1elif skipS > 0:skipS -= 1i -= 1else:breakwhile j >= 0:if t[j] == "#":skipT += 1j -= 1elif skipT > 0:skipT -= 1j -= 1else:breakif i >= 0 and j >= 0:if s[i] != t[j]:return Falseelse:if i >= 0 or j >= 0:return Falsei -= 1j -= 1return True