代码随想录一一一双指针法一一一移除元素

题目来源自leetcode与代码随想录

（1）27.移除元素

题目描述：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
解题思路：
双指针，一个确定要覆盖的位置，另一个确定谁去覆盖

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        l = len(nums)
        if l == 0:
            return 0
        
        fastIdx, slowIdx = 0, 0
        while fastIdx < l:
            if nums[fastIdx] != val:
                nums[slowIdx] = nums[fastIdx]
                slowIdx += 1
            else:
                pass
                
            fastIdx += 1

        return slowIdx
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

（2）26.删除排序数组中的重复项

题目描述：
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致
解题思路：
用快指针去过滤与慢指针相同的元素，慢指针确定覆盖位置

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        l = len(nums)
        if l <= 1:
            return l
        fastIdx, slowIdx = 1, 0

        while fastIdx < l:
            if nums[fastIdx] != nums[slowIdx]:
                slowIdx += 1
                nums[slowIdx] = nums[fastIdx]
            
            fastIdx += 1

        return slowIdx + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（3）283.移动零

题目描述：
把列表中的零全部按序移到队尾
解题思路：
慢指针确定覆盖位置，快指针确定移动谁(非0元素)

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        len_nums = len(nums)
        if len_nums <= 1:
            return
            
        fastIdx, slowIdx = 0, 0
        while fastIdx < len_nums:
            if nums[fastIdx] != 0:
                nums[slowIdx] = nums[fastIdx]
                slowIdx += 1
            fastIdx += 1

        while slowIdx < len_nums:
            nums[slowIdx] = 0
            slowIdx += 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

（4）844.比较含退格的字符串

题目描述：
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
解题思路：
按照#进行切片，有#退一个保存即可

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        s_list, t_list = [], []
        s, t = s.lstrip("#"), t.lstrip("#")
        
        for i in s:
            if i != "#":
                s_list.append(i)
            else:
                s_list = s_list[:-1]
        for i in t:
            if i != "#":
                t_list.append(i)
            else:
                t_list = t_list[:-1]

        return True if t_list == s_list else False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

（5）977.有序数组的平方

题目描述：
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
解题思路：
双指针，最大值肯定在两边，较大者相乘然后往里进一格即可

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        len_nums = len(nums)
        ans = [-1] * len_nums
        left, right, rear = 0, len_nums-1, len_nums-1

        while left <= right:
            leftNum = nums[left]**2
            rightNum = nums[right]**2

            if leftNum > rightNum:
                ans[rear] = leftNum
                left += 1
            else:
                ans[rear] = rightNum
                right -= 1
            
            rear -= 1
            
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20