力扣hot100题解(python版7-9题)
7、接雨水
给定 n
个非负整数表示每个宽度为 1
的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 1:
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
示例 2:
输入:height = [4,2,0,3,2,5]
输出:9
提示:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
思路解答:
- 使用左右双指针分别指向数组的两端,同时维护左右两端的最大高度。
- 在移动指针的过程中,根据当前的左右最大高度来计算当前位置能接的雨水量,并移动指针。
- 不断更新左右两端的最大高度,直到两个指针相遇。
def trap(self, height: list[int]) -> int:if not height:return 0n = len(height)left, right = 0, n - 1left_max, right_max = height[left], height[right]water = 0while left < right:left_max = max(left_max, height[left])right_max = max(right_max, height[right])if left_max < right_max:water += left_max - height[left]left += 1else:water += right_max - height[right]right -= 1return water
8、无重复字符的最长子串
给定一个字符串 s
,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
提示:
-
0 <= s.length <= 5 * 104
-
s
由英文字母、数字、符号和空格组成
思路解答:
补充:
滑动窗口是一种经典的算法技巧,通常用于解决数组或字符串的子数组或子串问题。它通过维护一个窗口(通常是一个子数组或子串),在遍历过程中动态调整窗口的起始位置和结束位置,以便在满足特定条件的情况下找到所需的结果。
对于此题:
- 定义一个窗口,初始时起始位置和结束位置都指向字符串的开头,同时定义一个哈希表
char_index_map
用于记录每个字符最近出现的位置。 - 遍历字符串,不断移动结束位置
end
,并根据当前字符是否在窗口内已经出现过来更新起始位置start
。 - 如果当前字符已经在窗口内出现过,需要更新
start
指针的位置为重复字符的下一个位置。 - 在每次遍历时,更新字符的最新位置,并计算当前窗口的长度(即
end - start + 1
),并更新最大长度。 - 最终返回最长不含重复字符的子串长度。
通过滑动窗口算法,我们可以在一次遍历过程中找到最长的不含重复字符的子串长度,并且时间复杂度为 O(n),其中 n 是字符串的长度。这种方法在处理子串问题时非常高效,适用于需要动态调整窗口范围的场景。
def lengthOfLongestSubstring(self, s: str) -> int:n = len(s)if n == 0:return 0char_index_map = {} # 用于记录字符的索引位置max_length = 0start = 0for end,num in enumerate(s):if num in char_index_map:# 如果当前字符在窗口内已经出现过,更新起始位置start = max(start, char_index_map[num] + 1)# 更新当前字符的最新位置char_index_map[num] = endmax_length = max(max_length, end - start + 1)return max_length
9、找到字符串中所有字母异位词
给定两个字符串 s
和 p
,找到 s
中所有 p
的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
提示:
-
1 <= s.length, p.length <= 3 * 104
-
s
和p
仅包含小写字母
思路解答:
- 创建两个字典
p_count
和window
,分别用于记录 p 中字符的计数和当前窗口中字符的计数。 - 初始化指针
left
和right
,分别表示窗口的左右边界,初始时两者都指向字符串 s 的起始位置。 - 不断移动右指针
right
,直到窗口包含了 p 中所有字符,此时开始移动左指针left
来缩小窗口。 - 在移动窗口的过程中,根据窗口内字符的计数情况来更新结果。
- 最终返回所有符合条件的子串的起始索引。
def findAnagrams(self, s: str, p: str) -> list[int]:result = []#统计p中的字符个数p_count = collections.defaultdict(int)#记录窗口中的字符个数window = collections.defaultdict(int)required = len(p)left, right = 0, 0for char in p:p_count[char] += 1#移动窗口右边界while right < len(s):char = s[right]if char in p_count:window[char] += 1if window[char] <= p_count[char]:required -= 1while required == 0:if right - left + 1 == len(p):result.append(left)left_char = s[left]if left_char in p_count:window[left_char] -= 1if window[left_char] < p_count[left_char]:required += 1left += 1right += 1return result
相关文章:

力扣hot100题解(python版7-9题)
7、接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,…...
ECMAScript 6+ 新特性 ( 四 ) 迭代器 与 生成器
2.14.迭代器 2.14.1.for…of for...of 是 JavaScript ES6 引入的一种新的循环结构,,用于遍历可迭代对象(Iterable objects)的每个元素。 它可以自动调用目标对象的迭代器接口,并按顺序逐个访问集合中的每个值。 它…...
【MySQL】事务的一致性究竟怎么理解?
众所周知,事务有四大特性:原子性、一致性、隔离性、持久性,除了一致性,其他三类特性都很好理解。而关于一致性的解释有点让人头疼,我查了很多文章,大多类似:事务的执行必须使数据库处于一致状态…...

证件照(兼容H5,APP,小程序)
证件照由uniappuyui开发完成,并同时兼容H5、App、微信小程序、支付宝小程序,其他端暂未测试。 先看部分效果图吧具体可以下方复制链接体验demo 首页代码 <template><view class""><view class"uy-m-x-30 uy-m-b-20"…...
pytorch-textregression,中文文本回归实践,支持多值输出
pytorch-textregression,中文文本回归实践,支持多值输出 pytorch-textregression是一个以pytorch和transformers为基础,专注于中文文本回归的轻量级自然语言处理工具,支持多值回归等。 目录 数据使用方式paper参考 项目地址 py…...
go语言学而思【持续更新】
问题:在Go语言中nil是什么意思? 答:在Go语言中,nil是一个预声明的标识符,用于表示某些类型的零值。它可以被用作以下类型的零值: 指针(Pointer)切片(Slice)…...

LVS-NAT之VMNET环境搭建
目录 搭建拓扑图 搭建规划 VMNET0 搭建 VMNET2 搭建 LVS端增加网卡 搭建拓扑图: 搭建规划: CLIENT(servera): VMNET0 LVS(serverb): VMNET0 VMNET2 WEB1(serverd): VMNET2 WEB2(servere): VMNET2 VMNE…...

[TCP] TCP/IP 基础知识词典(2)
我想统计一下,TCP/IP 尤其是TCP协议,能搜到的常见的问题,整理起来,关键词添加在目录中,便于以后查阅。 目前预计整理共3篇: [TCP] TCP/IP 基础知识问答 :基础知识 [TCP] TCP/IP 基础知识问答&…...

【牛牛送书 | 第四期】《高效使用Redis:一书学透数据存储与高可用集群》带你快速学习使用Redis
前言: 当今互联网技术日新月异,随着数据量的爆炸式增长,如何高效地存储和管理数据成为了每个公司都必须面对的挑战。与此同时,用户对于应用程序的响应速度和稳定性要求也越来越高。在这个背景下,Redis 作为一个…...

Threejs 实现3D影像地图,Json地图,地图下钻
1.使用threejs实现3D影像地图效果,整体效果看起来还可以,底层抽象了基类,实现了通用,对任意省份,城市都可以只替换数据,即可轻松实现效果。 效果如下: 链接https://www.bilibili.com/video/BV1…...

根据Excel创建管道系统及材质
之前看过程鑫老师的文章,介绍过根据Excel数据创建管道系统,但是有小伙伴问过我,照着他这个做,没成功,于是呢,我就想试下,结果发现也没成功。 然后我逐个节点过了一遍,发现可能是因为…...

第八篇【传奇开心果系列】python的文本和语音相互转换库技术点案例示例:Google Text-to-Speech虚拟现实(VR)沉浸式体验经典案例
传奇开心果博文系列 系列博文目录python的文本和语音相互转换库技术点案例示例系列 博文目录前言一、雏形示例代码二、扩展思路介绍三、虚拟导游示例代码四、交互式学习示例代码五、虚拟角色对话示例代码六、辅助用户界面示例代码七、实时语音交互示例代码八、多语言支持示例代…...

ubuntu使用LLVM官方发布的tar.xz来安装Clang编译器
ubuntu系统上的软件相比CentOS更新还是比较快的,但是还是难免有一些软件更新得不那么快,比如LLVM Clang编译器,目前ubuntu 22.04版本最高还只能安装LLVM 15,而LLVM 18 rc版本都出来了。参见https://github.com/llvm/llvm-project/…...

Windows 远程控制 Mac 电脑怎么操作
要从 Windows 远程控制 Mac 电脑,您可以使用内置 macOS 功能或第三方软件解决方案。以下是一些方法: 一、使用内置 macOS 功能(屏幕共享) 1、在 macOS 上启用屏幕共享 转至系统偏好设置 > 共享;选中“屏幕共享”…...
c# HttpCookie操作,建立cookie工具类
HttpCookie 是一个在.NET Framework中用于管理和操作HTTP Cookie的类。它提供了一种方便的方式来创建、设置、读取和删除Cookie。 Cookie是一种在客户端和服务器之间传递数据的机制,用于跟踪用户的会话状态和存储用户相关的信息。它通常由服务器发送给客户端&#…...

【这个词(Sequence-to-Sequence)在深度学习中怎么解释,有什么作用?】
🚀 作者 :“码上有前” 🚀 文章简介 :深度学习笔记 🚀 欢迎小伙伴们 点赞👍、收藏⭐、留言💬 Sequence-to-Sequence(Seq2Seq) Sequence-to-Sequence(Seq2Seq…...

挑战30天学完Python:Day16 日期时间
📘 Day 16 🎉 本系列为Python基础学习,原稿来源于 30-Days-Of-Python 英文项目,大奇主要是对其本地化翻译、逐条验证和补充,想通过30天完成正儿八经的系统化实践。此系列适合零基础同学,或仅了解Python一点…...

Web3之光:揭秘数字创新的未来
随着数字化时代的深入发展,Web3正以其独特的技术和理念,为我们打开数字创新的崭新视角。作为数字化时代的新兴力量,Web3将深刻影响着我们的生活、工作和社会。本文将揭秘Web3的奥秘,探讨其在数字创新领域的前景和潜力。 1. 重新定…...

Stable Diffusio——采样方法使用与原理详解
简介 当使用稳定扩散(Stable Diffusion)技术生成图像时,首先会生成一张带有噪声的图像。然后,通过一系列步骤逐渐去除图像中的噪声,这个过程类似于从一块毛坯的白色大理石开始,经过多日的精细雕刻…...

小米14 ULTRA:重新定义手机摄影的新篇章
引言 随着科技的飞速发展,智能手机已经不仅仅是一个通讯工具,它更是我们生活中的一位全能伙伴。作为科技领域的佼佼者,小米公司再次引领潮流,推出了全新旗舰手机——小米14 ULTRA。这款手机不仅在性能上进行了全面升级&am…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...

dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...

基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...

【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化
iOS 应用的发布流程一直是开发链路中最“苹果味”的环节:强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说,这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发(例如 Flutter、React Na…...
怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)
+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...