【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和

简介: 【经典LeetCode算法题目专栏分类】【第1期】左右双指针系列:盛最多水的容器、接雨水、回文子串、三数之和

1. 盛最多水的容器

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # 左右双指针
        left = 0
        right = len(height) - 1
        res = 0
        while left < right:
            if height[left] > height[right]:
                area = (right - left) * height[right]
                right -= 1
            else:
                area = (right - left) * height[left]
                left += 1
            res = max(res, area)
        return res

2.接雨水

# 左右双指针
class Solution:
    def trap(self, height: List[int]) -> int:
        # 左右双指针,一般通过while left<right循环作为终止条件
        # 某一点处的雨水与左右最大柱子的高度有关
        # left_max与right_max用于动态存储左右从左向右,及从右向左的最大高度
        # 如果left_max < right_max ,则只用考虑left点处左侧的高度即可,
        # 因为右侧的最大高度肯定比左侧高,相当于在left点处取到了左侧最大值与右侧最大值中的较小者
        n = len(height)
        left = 0
        right = n - 1
        left_max = 0
        right_max = 0
        ans = 0
        while left < right:
            if height[left] < height[right]:
                left_max = max(left_max,height[left])
                ans += left_max - height[left]
                left += 1
            else:
                right_max = max(right_max,height[right])
                ans += right_max - height[right]
                right -= 1
        return ans
#单调递减栈
class Solution:
    def trap(self, height: List[int]) -> int:
        #单调递减栈
        res = 0
        st = []
        for i in range(len(height)):
            while st and height[st[-1]] < height[i]:
                cur = st.pop()
                if not st:
                    break
                l = st[-1]
                r = i
                h = min(height[r],height[l]) - height[cur]
                res += (r-l-1) * h
            st.append(i)
        return res

3.回文子串

class Solution:
    def countSubstrings(self, s: str) -> int:
        num = 0
        n = len(s)
        for i in range(n): # 遍历回文中心点
            for j in [0,1]: # j=0,中心是一个点,j=1,中心是两个点
                l = i
                r = i + j
                while l >= 0 and r < n and s[l] == s[r]:
                    num += 1
                    l -= 1
                    r += 1
        return num

4.三数之和

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 通过排序 + 双指针实现
        nums.sort()
        res = []
        k = 0
        n = len(nums)
        for k in range(n - 2):
            if nums[k] > 0: 
                break # 1. because of j > i > k.
            if k > 0 and nums[k] == nums[k - 1]: 
                continue # 2. skip the same `nums[k]`.
            i, j = k + 1, n - 1
            while i < j: # 3. double pointer
                s = nums[k] + nums[i] + nums[j]
                if s < 0:
                    i += 1
                elif s > 0:
                    j -= 1
                else:
                    res.append([nums[k], nums[i], nums[j]])
                    i += 1
                    j -= 1
                    while i < j and nums[i] == nums[i - 1]: i += 1 # 跳过相同元素
                    while i < j and nums[j] == nums[j + 1]: j -= 1 # 跳过相同元素
        return res


目录
打赏
0
0
0
0
115
分享
相关文章
【算法】——双指针算法合集(力扣)
移动零,复写零,快乐数,盛最多水的容器,有效三角形的个数,和为s的两个数(查找总价格为目标值的两个商品 ),三数之和,四数之和
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
|
4月前
|
Leetcode第十一题(盛最多水的容器)
LeetCode第十一题要求找出两条线,使得它们与x轴构成的容器能盛最多的水,通常使用双指针法来解决,通过移动较短的一边来尝试增加容量。
26 0
Leetcode第十一题(盛最多水的容器)
CASE WHEN 语句的语法及示例,LeetCode 题目 “确认率” 练习
本文介绍了SQL中CASE语句的两种形式和语法,并通过LeetCode题目“确认率”的SQL查询示例展示了CASE语句在实际问题中的应用,解释了如何使用CASE语句计算特定条件的比率。
ubuntu22 编译安装docker,和docker容器方式安装 deepseek
本脚本适用于Ubuntu 22.04,主要功能包括编译安装Docker和安装DeepSeek模型。首先通过Apt源配置安装Docker,确保网络稳定(建议使用VPN)。接着下载并配置Docker二进制文件,创建Docker用户组并设置守护进程。随后拉取Debian 12镜像,安装系统必备工具,配置Ollama模型管理器,并最终部署和运行DeepSeek模型,提供API接口进行交互测试。
161 15
《docker基础篇:3.Docker常用命令》包括帮助启动类命令、镜像命令、有镜像才能创建容器,这是根本前提(下载一个CentOS或者ubuntu镜像演示)、容器命令、小总结
《docker基础篇:3.Docker常用命令》包括帮助启动类命令、镜像命令、有镜像才能创建容器,这是根本前提(下载一个CentOS或者ubuntu镜像演示)、容器命令、小总结
169 6
《docker基础篇:3.Docker常用命令》包括帮助启动类命令、镜像命令、有镜像才能创建容器,这是根本前提(下载一个CentOS或者ubuntu镜像演示)、容器命令、小总结
入门级容器技术解析:Docker和K8s的区别与关系
本文介绍了容器技术的发展历程及其重要组成部分Docker和Kubernetes。从传统物理机到虚拟机,再到容器化,每一步都旨在更高效地利用服务器资源并简化应用部署。容器技术通过隔离环境、减少依赖冲突和提高可移植性,解决了传统部署方式中的诸多问题。Docker作为容器化平台,专注于创建和管理容器;而Kubernetes则是一个强大的容器编排系统,用于自动化部署、扩展和管理容器化应用。两者相辅相成,共同推动了现代云原生应用的快速发展。
224 11
docker 是什么?docker初认识之如何部署docker-优雅草后续将会把产品发布部署至docker容器中-因此会出相关系列文章-优雅草央千澈
Docker 是一个开源的容器化平台,允许开发者将应用程序及其依赖项打包成标准化单元(容器),确保在任何支持 Docker 的操作系统上一致运行。容器共享主机内核,提供轻量级、高效的执行环境。本文介绍如何在 Ubuntu 上安装 Docker,并通过简单步骤验证安装成功。后续文章将探讨使用 Docker 部署开源项目。优雅草央千澈 源、安装 Docker 包、验证安装 - 适用场景:开发、测试、生产环境 通过以上步骤,您可以在 Ubuntu 系统上成功安装并运行 Docker,为后续的应用部署打下基础。
97 8
docker 是什么?docker初认识之如何部署docker-优雅草后续将会把产品发布部署至docker容器中-因此会出相关系列文章-优雅草央千澈
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等