27. 移除元素

题目链接 link

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

注意：需要改动原来的数组，虽然没有直接返回改动后的数组

暴力解法

两个循环，分别用于查找 val 和移动后续元素。注意第一个循环要用 while，因为移动后续元素时减少了一位，for 循环无法控制变量 i。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        size = len(nums)
        i = 0
        while i < size:
            if nums[i] == val:
                for j in range(i+1, size):
                    nums[j-1] = nums[j]
                size -= 1
                i -= 1
            i += 1
        return size

双指针法

双指针法（快慢指针法）：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。本题中，两个指针分别代表：

快指针：查找的索引

慢指针：更改后的数组的索引
此外，每一步都需要把快指针的值赋值给慢指针（无论是否遇到等于）

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        size = len(nums)
        fast, slow = 0, 0
        while fast < size:
            nums[slow] = nums[fast]
            if nums[fast] == val:
                slow -= 1
            fast += 1
            slow += 1
        
        return slow

26. 删除有序数组中的重复项

题目链接 link

给你一个非严格递增排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ，并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

思路

仍然是快慢指针法，只是没有给定 val，需要在循环中动态更新 val。更新 val 的规则为，如果当前 fast 对应的值不等于 val，则将其赋值给 val。因为数组升序排列，相同的数字在一起，如果 fast 对应的值和 val（上一个数字）不相等，说明上一个数字已经不重复了。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        slow, fast = 0, 0
        size = len(nums)
        val = None
       
        while fast < size:
            nums[slow] = nums[fast]
            if val == nums[fast]:
                slow -= 1
            else:
                val = nums[fast]
            slow += 1
            fast += 1
        return slow

283. 移动零

题目链接 link

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

思路

相当于是 val 为 0 的删除元素，同样使用快慢指针法，只是最后需要将 [slow, fast) 区间内的元素赋值为 0。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        slow, fast, size = 0, 0, len(nums)
        while fast < size:
            nums[slow] = nums[fast]
            if nums[fast] == 0:
                slow -= 1
            slow += 1
            fast += 1
        
        if fast != slow:
            for i in range(slow, fast):
                nums[i] = 0

844. 比较含退格的字符串

题目链接 link

给定 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

双指针法，相当于是查找 “#” 字符，查找到之后删除 # 以及其之前的字符。注意要考虑 # 之前没有字符的情况。

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:

        def dele(nums: list):
            slow, fast, size = 0, 0, len(nums)
            while fast < size:
                nums[slow] = nums[fast]
                if nums[fast] == "#":
                    if slow == 0:
                        slow -= 1
                    else:
                        slow -= 2
                
                slow += 1
                fast += 1
            if slow < 0:
                return []
            else:
                return nums[0: slow]
        
        s1 = dele(list(s))
        t1 = dele(list(t))

        s = "".join(s1)
        t = "".join(t1)

        if s == t:
            return True
        else:
            return False

思路2

使用栈的思想，遍历到 # 字符，则当前栈顶的字符 pop。注意 list 的 pop 方法需要 list 不为空，所以需要进行判断。

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:

        def dele(nums: list):
            ret = list()
            for i in nums:
                
                if i != "#":
                    
                    ret.append(i)
                elif len(ret) != 0:
                    ret.pop()
            
            return "".join(ret)

        s = dele(list(s))
        t = dele(list(t))
        
        if s == t:
            return True
        else:
            return False

977. 有序数组的平方

题目链接 link
给你一个按非递减顺序排序的整数数组 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]

思路

双指针法，左右分别两个指针，依次比较大小，直到左指针大于右指针。注意，这里需要返回新的数组，和上面的题目不一样，所以可以新建数组，不需要在原有数组上操作。

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        left, right = 0, len(nums) - 1
        new_nums = [0] * len(nums)
        i = len(nums) - 1
        while left <= right:
            if nums[left] * nums[left] < nums[right] * nums[right]:
                new_nums[i] = nums[right] * nums[right]
                right -= 1
            else:
                new_nums[i] = nums[left] * nums[left]
                left += 1
            i -= 1
        return new_nums