数组-双指针-移除元素/删除有序数组中的重复项/有序数组的平方/比较含退格的字符串

27. 移除元素

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

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

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

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

示例 1：

输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2] 解释：函数应该返回新的长度 2, 并且nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。
例如，函数返回的新长度为 2 ，而 nums =[2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0,
4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        # 前部分是有效数组值不为val
        # idx是新数组的下标 如果nums[i] 不与val 相同，则将nums[i]移到nums[idx]处 idx++ 往前移动变成有效部分
        # 返回的idx 就是最后的新数组长度
        # nusm[idx]像一个新数组
        idx=0
        for x in nums:
            if(x!=val):
                nums[idx] = x
                idx +=1
        return idx

func removeElement(nums []int, val int) int {
    idx := 0
    for i := 0;i <len(nums);i++{
        // 不为val 就是有效元素 放入”新“数组
        if nums[i] != val{
            nums[idx] = nums[i]
            idx += 1
        }
    }
    return idx

}

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

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

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = […]; // 输入数组
int[] expectedNums = […]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过，那么您的题解将被通过。

示例 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 。不需要考虑数组中超出新长度后面的元素。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        idx=0
        # nums[idx]相当于新数组 如果x==nums[idx]跳过
        # idx最后指向nums的最后一个数 所以长度要idx+1
        for x in nums:
            if x==nums[idx]:
                continue
            
            # 默认idx=0的值先保存 
            # 直到x与nums[i]不同时 放入nums[idx]
            else:
                idx+=1
                nums[idx]=x
        return idx+1

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        idx = 0
        for x in nums:
            # 相当于是把不重复的值放到一个”新“数组 遍历旧数组 如果和新数组的值重复就跳过
            # 默认"新"数组放了第0个数
            if nums[idx]!=x:
                idx += 1
                nums[idx] = x
            else:
                continue
        # 如果nums没有重复数据，最后idx指向nums的最后一个元素 所以长度=idx+1
        return idx + 1

func removeDuplicates(nums []int) int {
    idx := 0 
    for i:=0;i<len(nums);i++{
        if nums[i] != nums[idx]{
            idx += 1
            nums[idx] = nums[i]
        }else{
            continue
        }
    }
    return idx + 1
}

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

给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素最多出现两次，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

示例 1：

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

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

思路：
对于后面的任意数字（x），能够保留的前提是：与当前写入的位置前面的第 k 个元素（idx - k）进行比较，不相同则保留，相同不保留（比如是1,1,1, K=2, idx=2时，nums[idx-k]=nums[0]=第一个1， x为第三个1，此时x和nums[idx-k]的值一样，所以不保留，下标差为k的两个元素不相同）

在这里插入图片描述

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        def removek(nums,k):
            idx=0
            for x in nums:
                # 前k个数直接放在数组中 
                # 看看此时idx处的前k和x 是不是一样 一样的话说明已经满了 不一样才放入x
                # 下标差为k的两个元素不相同
                if(idx<k or nums[idx-k]!=x):
                    nums[idx]=x
                    idx+=1
            return idx
        return removek(nums,2)

283. 移动零

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

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

示例 1:

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

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

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 把非0元素往前移动，相当于是有效数组，剩下的部分再用0填充
        idx =0
        for x in nums:
            if(x!=0):
                nums[idx]=x
                idx +=1
        while idx<len(nums):
            nums[idx]=0
            idx+=1

func moveZeroes(nums []int)  {
    idx := 0
    for i:=0;i<len(nums);i++{
        if nums[i] != 0{
            nums[idx] = nums[i]
            idx += 1
        }
    }
    for ; idx < len(nums);idx++{
        nums[idx] = 0
    }

}

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]

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        result=[]
        left=0
        right=len(nums)-1
        # 因为平方值最大一定就产生在最左边或最右边 所以每次将最大值添加子啊result的头部 类似快排
        while(left<=right):
            if(nums[left]*nums[left]>nums[right]*nums[right]):
                result.append(nums[left]*nums[left])
                left+=1
            else:
                result.append(nums[right]*nums[right])
                right-=1
        result.reverse()
        return result

func sortedSquares(nums []int) []int {
    l:=0
    r:=len(nums) - 1
    pos:= len(nums) - 1
    ans := make([]int,len(nums))
    for ;pos >=0;pos--{
        if nums[l]*nums[l] > nums[r]*nums[r]{
            ans[pos] = nums[l] * nums[l]
            l++
        }else{
            ans[pos] = nums[r] * nums[r]
            r--
        }
    }
    return ans
}

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”。

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def finalstring(ss):
            res=list()
            for x in ss:
                if x!='#':
                    res.append(x)
                # 如果是#  且res不空 t
                elif res:
                    res.pop()
            return ''.join(res)
            
        return finalstring(t)==finalstring(s)


func finalstring(s string)string {
    res:= []byte{}
    for i:= range s{
        if s[i]!='#'{
            res = append(res,s[i])
        }else if len(res)!=0 {
            res = res[:len(res)-1]
        }
    }
    return string(res)
}
func backspaceCompare(s string, t string) bool {
    return finalstring(s) == finalstring(t)
}

法二：模拟退格
https://leetcode.cn/problems/backspace-string-compare/solution/shuang-zhi-zhen-bi-jiao-han-tui-ge-de-zi-8fn8/

假设有两个数组，遍历所有旧数组的所有字符，把不是#的字母放入新数组，如果是#新数组的idx回退一个

class Solution(object):
    def backspaceCompare(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        def finastr(str):
            fast = 0
            slow = 0
            s = list(str)
            for fast in range(len(s)):
                #不是“#”放到新数组，新数组的idx往后移动
                if s[fast] !='#':
                    s[slow] = s[fast]
                    slow += 1
                # 当slow不是0的时候才可以回退
                elif slow >0:
                    slow -=1
            print(s)
            print(s[:slow])
            return s[:slow]

        return finastr(s) == finastr(t)