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

本文主要是介绍2数组-双指针-移除元素/删除有序数组中的重复项/有序数组的平方/比较含退格的字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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=0for x in nums:if(x!=val):nums[idx] = xidx +=1return idx

func removeElement(nums []int, val int) int {idx := 0for 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+1for x in nums:if x==nums[idx]:continue# 默认idx=0的值先保存 # 直到x与nums[i]不同时 放入nums[idx]else:idx+=1nums[idx]=xreturn idx+1

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

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

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

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

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

说明：

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

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

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

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

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

示例 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=0for x in nums:# 前k个数直接放在数组中 # 看看此时idx处的前k和x 是不是一样 一样的话说明已经满了 不一样才放入x# 下标差为k的两个元素不相同,idx是要放入新的元素的位置，所以idx和idx-k位置的值不能一样if(idx<k or nums[idx-k]!=x):nums[idx]=xidx+=1return idxreturn 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 =0for x in nums:if(x!=0):nums[idx]=xidx +=1while idx<len(nums):nums[idx]=0idx+=1

func moveZeroes(nums []int)  {idx := 0for 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=0right=len(nums)-1# 因为平方值最大一定就产生在最左边或最右边 所以每次将最大值添加子啊result的头部 类似快排while(left<=right):if(nums[left]*nums[left]>nums[right]*nums[right]):result.append(nums[left]*nums[left])left+=1else:result.append(nums[right]*nums[right])right-=1result.reverse()return result

func sortedSquares(nums []int) []int {l:=0r:=len(nums) - 1pos:= len(nums) - 1ans := 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不空 telif 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 = 0slow = 0s = list(str)for fast in range(len(s)):#不是“#”放到新数组，新数组的idx往后移动if s[fast] !='#':s[slow] = s[fast]slow += 1# 当slow不是0的时候才可以回退elif slow >0:slow -=1print(s)print(s[:slow])return s[:slow]return finastr(s) == finastr(t)            

这篇关于2数组-双指针-移除元素/删除有序数组中的重复项/有序数组的平方/比较含退格的字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---