leetcode-hot100双指针专题

发布时间:2024年01月23日

第一题:移动零

题目链接

283. 移动零 - 力扣(LeetCode)

解题思路

我们创建两个指针i,j,第一次遍历的时候指针j用来记录当前面有多少非0元素。即遍历的时候每遇到一个非0元素就将其往数组左边挪,第一次遍历完后,j指针的下标就指向了最后一个非0元素下边。
第二次遍历,起始位置就从j开始到结束,将剩下的这段区域内的元素全部置为0。

解题代码

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

第二题 盛最多水容器

题目链接

11. 盛最多水的容器 - 力扣(LeetCode)

暴力破解-解题代码

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0 
        right = len(height) - 1
        result = 0 
        for left in range(len(height)-1):
            for right in range(left+1,len(height)):
                temp = min(height[right],height[left]) * (right - left)
                result = max(temp,result)
        return result

时间复杂度太高

改进

1、初始化:双指针i,j分别列水槽左右两端
2、循环收窄:直至双指针相遇时跳出;首先更新面积最大值res;其次选定两板高度中的短板,向中间收窄一格。
3、返回值:返回面积的最大值res即可

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0 
        right = len(height) - 1
        result = 0 
        while right > left:
            temp = min(height[right],height[left]) * (right - left)
            result = max(temp,result)
            if height[right] > height[left]:
                left += 1
            else:
                right -= 1
        return result

文章来源:https://blog.csdn.net/weixin_53908842/article/details/135772507
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。