当前位置: 首页 > 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…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

基于Java+MySQL实现(GUI)客户管理系统

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

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

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 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...

绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化

iOS 应用的发布流程一直是开发链路中最“苹果味”的环节&#xff1a;强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说&#xff0c;这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发&#xff08;例如 Flutter、React Na…...

怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)

+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...