自学内容网 自学内容网

代码随想录移除元素二刷

代码随想录移除元素二刷

leetcode 27

在这里插入图片描述

这道题思路的话可以这样去理解,用两个指针,一个慢指针,一个快指针。先让快指针往前面去探路,也就是去遍历数组,遇到不为val的值再去把该值赋值给nums[slow],slow指针+1,遇到为val的值,nums[slow]不做任何操作,继续移动fast指针。具体代码如下:

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

因为还要返回元素的个数,所以返回slow即可。如何不理解为啥返回slow的话找个例子代入一下就可以看出来,

leetcode26

在这里插入图片描述
这道题初步分析也是移除元素,但与上道题不一样是移除数组中重复的元素,也就是跟上面一题的目标值是不一样的。但其实思路还是一样的:
仍旧是双指针。slow刚开始不动,fast往后遍历,遇到相同的值就直接pass掉。fast继续向后找。遇到跟slowB不同的。slow先加1,在把这个fast的值赋值给nums[slow],再根据新的这个nums[slow]去判断。
具体代码如下:

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

leetcode283

在这里插入图片描述
其实这个思路也是采用快慢指针,再来分析下这道题目,要把0都放到数组末尾。也就是把非0的挪到前面。所以判断条件就是快指针往前探路,slow指向数组中非0元素位置的索引,fast往前探路,遇到0忽略,然后将fast指向位置的值赋值给slow位置。同时原来fast指向的位置赋值为0.
如果数组不存在0的话,slow始终等于fast,此时也就不需要进一步处理数组。
只要数组存在0的话,fast就要比slow多走,多走的中间一定都是0。所以fast就一直遍历,遇到非0的就交换,直到遍历完数组。

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

leetcode844


这道题其实用堆栈的思想是更容易做出来的。遇到非#加入堆栈里面,遇到#就弹出,但是此时弹出一定要检查堆栈还有没有元素,否则就会报错。以这样的方式处理完这两个数组后。在比较两个数组是否相等即可。具体程序如下:

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        del_s = []
        del_t = []
        for i in range(len(s)): 
            if s[i]!= '#':
                del_s.append(s[i])
            elif del_s:
                del_s.pop()
        for i in range(len(t)):
            if t[i]!= '#':
                del_t.append(t[i])
            elif del_t:
                del_t.pop()
        if del_s == del_t:
            return True
        return False 

leetcode977

在这里插入图片描述
这道题如何用库函数的话就一句话就完事,直接整个数组平方后排序就行。但是一般面试还是最好不要用库函数把。双指针思路就是:比较left指向和right指向的值哪个大,就放入新的数组里面,但是要倒着放,这样最后就不用再反转一遍数组了。具体代码如下:

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

原文地址:https://blog.csdn.net/qq_44219883/article/details/140567614

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!