当前位置: 首页 > news >正文

力扣hot100题解(python版7-9题)

7、接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

示例 1:

img

输入: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

思路解答:

  1. 使用左右双指针分别指向数组的两端,同时维护左右两端的最大高度。
  2. 在移动指针的过程中,根据当前的左右最大高度来计算当前位置能接的雨水量,并移动指针。
  3. 不断更新左右两端的最大高度,直到两个指针相遇。
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 由英文字母、数字、符号和空格组成

思路解答:

补充:

滑动窗口是一种经典的算法技巧,通常用于解决数组或字符串的子数组或子串问题。它通过维护一个窗口(通常是一个子数组或子串),在遍历过程中动态调整窗口的起始位置和结束位置,以便在满足特定条件的情况下找到所需的结果。

对于此题:

  1. 定义一个窗口,初始时起始位置和结束位置都指向字符串的开头,同时定义一个哈希表 char_index_map 用于记录每个字符最近出现的位置。
  2. 遍历字符串,不断移动结束位置 end,并根据当前字符是否在窗口内已经出现过来更新起始位置 start
  3. 如果当前字符已经在窗口内出现过,需要更新 start 指针的位置为重复字符的下一个位置。
  4. 在每次遍历时,更新字符的最新位置,并计算当前窗口的长度(即 end - start + 1),并更新最大长度。
  5. 最终返回最长不含重复字符的子串长度。

通过滑动窗口算法,我们可以在一次遍历过程中找到最长的不含重复字符的子串长度,并且时间复杂度为 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、找到字符串中所有字母异位词

给定两个字符串 sp,找到 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

  • sp 仅包含小写字母

思路解答:

  1. 创建两个字典 p_countwindow,分别用于记录 p 中字符的计数和当前窗口中字符的计数。
  2. 初始化指针 leftright,分别表示窗口的左右边界,初始时两者都指向字符串 s 的起始位置。
  3. 不断移动右指针 right,直到窗口包含了 p 中所有字符,此时开始移动左指针 left 来缩小窗口。
  4. 在移动窗口的过程中,根据窗口内字符的计数情况来更新结果。
  5. 最终返回所有符合条件的子串的起始索引。
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 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;6 解释&#xff1a;上面是由数组 [0,1,0,2,1,0,1,…...

ECMAScript 6+ 新特性 ( 四 ) 迭代器 与 生成器

2.14.迭代器 2.14.1.for…of for...of 是 JavaScript ES6 引入的一种新的循环结构&#xff0c;&#xff0c;用于遍历可迭代对象&#xff08;Iterable objects&#xff09;的每个元素。 它可以自动调用目标对象的迭代器接口&#xff0c;并按顺序逐个访问集合中的每个值。 它…...

【MySQL】事务的一致性究竟怎么理解?

众所周知&#xff0c;事务有四大特性&#xff1a;原子性、一致性、隔离性、持久性&#xff0c;除了一致性&#xff0c;其他三类特性都很好理解。而关于一致性的解释有点让人头疼&#xff0c;我查了很多文章&#xff0c;大多类似&#xff1a;事务的执行必须使数据库处于一致状态…...

证件照(兼容H5,APP,小程序)

证件照由uniappuyui开发完成&#xff0c;并同时兼容H5、App、微信小程序、支付宝小程序&#xff0c;其他端暂未测试。 先看部分效果图吧具体可以下方复制链接体验demo 首页代码 <template><view class""><view class"uy-m-x-30 uy-m-b-20"…...

pytorch-textregression,中文文本回归实践,支持多值输出

pytorch-textregression&#xff0c;中文文本回归实践&#xff0c;支持多值输出 pytorch-textregression是一个以pytorch和transformers为基础&#xff0c;专注于中文文本回归的轻量级自然语言处理工具&#xff0c;支持多值回归等。 目录 数据使用方式paper参考 项目地址 py…...

go语言学而思【持续更新】

问题&#xff1a;在Go语言中nil是什么意思&#xff1f; 答&#xff1a;在Go语言中&#xff0c;nil是一个预声明的标识符&#xff0c;用于表示某些类型的零值。它可以被用作以下类型的零值&#xff1a; 指针&#xff08;Pointer&#xff09;切片&#xff08;Slice&#xff09;…...

LVS-NAT之VMNET环境搭建

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

[TCP] TCP/IP 基础知识词典(2)

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

【牛牛送书 | 第四期】《高效使用Redis:一书学透数据存储与高可用集群》带你快速学习使用Redis

前言&#xff1a; 当今互联网技术日新月异&#xff0c;随着数据量的爆炸式增长&#xff0c;如何高效地存储和管理数据成为了每个公司都必须面对的挑战。与此同时&#xff0c;用户对于应用程序的响应速度和稳定性要求也越来越高。在这个背景下&#xff0c;Redis 作为一个…...

Threejs 实现3D影像地图,Json地图,地图下钻

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

根据Excel创建管道系统及材质

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

第八篇【传奇开心果系列】python的文本和语音相互转换库技术点案例示例:Google Text-to-Speech虚拟现实(VR)沉浸式体验经典案例

传奇开心果博文系列 系列博文目录python的文本和语音相互转换库技术点案例示例系列 博文目录前言一、雏形示例代码二、扩展思路介绍三、虚拟导游示例代码四、交互式学习示例代码五、虚拟角色对话示例代码六、辅助用户界面示例代码七、实时语音交互示例代码八、多语言支持示例代…...

ubuntu使用LLVM官方发布的tar.xz来安装Clang编译器

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

Windows 远程控制 Mac 电脑怎么操作

要从 Windows 远程控制 Mac 电脑&#xff0c;您可以使用内置 macOS 功能或第三方软件解决方案。以下是一些方法&#xff1a; 一、使用内置 macOS 功能&#xff08;屏幕共享&#xff09; 1、在 macOS 上启用屏幕共享 转至系统偏好设置 > 共享&#xff1b;选中“屏幕共享”…...

c# HttpCookie操作,建立cookie工具类

HttpCookie 是一个在.NET Framework中用于管理和操作HTTP Cookie的类。它提供了一种方便的方式来创建、设置、读取和删除Cookie。 Cookie是一种在客户端和服务器之间传递数据的机制&#xff0c;用于跟踪用户的会话状态和存储用户相关的信息。它通常由服务器发送给客户端&#…...

【这个词(Sequence-to-Sequence)在深度学习中怎么解释,有什么作用?】

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;深度学习笔记 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac; Sequence-to-Sequence&#xff08;Seq2Seq&#xff09; Sequence-to-Sequence&#xff08;Seq2Seq…...

挑战30天学完Python:Day16 日期时间

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

Web3之光:揭秘数字创新的未来

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

Stable Diffusio——采样方法使用与原理详解

简介 当使用稳定扩散&#xff08;Stable Diffusion&#xff09;技术生成图像时&#xff0c;首先会生成一张带有噪声的图像。然后&#xff0c;通过一系列步骤逐渐去除图像中的噪声&#xff0c;这个过程类似于从一块毛坯的白色大理石开始&#xff0c;经过多日的精细雕刻&#xf…...

小米14 ULTRA:重新定义手机摄影的新篇章

引言 随着科技的飞速发展&#xff0c;智能手机已经不仅仅是一个通讯工具&#xff0c;它更是我们生活中的一位全能伙伴。作为科技领域的佼佼者&#xff0c;小米公司再次引领潮流&#xff0c;推出了全新旗舰手机——小米14 ULTRA。这款手机不仅在性能上进行了全面升级&am…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

ESP32读取DHT11温湿度数据

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

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

用docker来安装部署freeswitch记录

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

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

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是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...