力扣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…...

【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...

ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...

用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...

Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...

Python 实现 Web 静态服务器(HTTP 协议)
目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1)下载安装包2)配置环境变量3)安装镜像4)node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1)使用 http-server2)详解 …...
django blank 与 null的区别
1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是,要注意以下几点: Django的表单验证与null无关:null参数控制的是数据库层面字段是否可以为NULL,而blank参数控制的是Django表单验证时字…...