Leetcode(滑动窗口习题思路总结,持续更新。。。)

讲解题目:长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target ,找出该数组中满足其和 ≥ target 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。示例: 输入: target = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

这类型题类似于规划问题,有约束(和 >= targrt),有目标函数(长度最小)

暴力解题思路

就是首先遍历窗口从1到len(nums),然后再遍历该窗口长度下的所有数组,计算和,因为窗口长度从小遍历,所以只要出现和 >= target 就结束计算,时间复杂度是N2

def minSubArrayLen(target, nums):for win in range(1, len(nums) + 1):# print(f'win:{win}')for left in range(len(nums) - win + 1):left = max(0, left)right = min(left + win, len(nums))val = nums[left:right]if sum(val) >= target:return winelse:passreturn 0
改进解题思路
  1. 初始化 left = right = 0,把区间 [left, right] 称为一个「窗口」。
  2. 不断地增加 right 指针扩大窗口 [left, right],直到窗口中的字符串符合要求。
  3. 停止增加 right,转而不断增加 left 指针缩小窗口 [left, right],直到窗口中的字符串不再符合要求。
  4. 重复第 2 和第 3 步,直到 right 到达字符串 S 的尽头。
def minSubArrayLen(s, nums):start = 0end = 0min_length = len(nums) + 1sum_nums = 0while end < len(nums):sum_nums += nums[end]while sum_nums >= s:min_length = min(min_length, end - start + 1)sum_nums -= nums[start]start += 1end += 1return 0 if min_length == len(nums) + 1 else min_length

习题1

给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字母的最小子串示例输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

思路:

  1. 滑动窗口:我们维护一个可变的窗口,这个窗口的左右边界分别用指针 start 和 end 表示。我们通过移动  end 指针来扩大窗口,直到窗口包含 T 中所有的字母。然后,我们尝试通过移动 start 指针来缩小窗口,以得到最小的满足条件的子串。

  2. 字符频率:我们需要记录 T 中字符的频率,并在窗口中保持一个字典来统计窗口内的字符频率。每当窗口内的字符完全满足 T 中所有字符时,我们就更新最小子串的长度。

def minSubArrayLen(S, T):if not S or not T:return ''t_dic = Counter(T)start = 0flag = 0min_len = float('inf')min_substr = ''s_dic = Counter()for end in range(len(S)):char = S[end]s_dic[char] += 1# print(f'sub_str:{sub_str}')# print(f's_dic:{s_dic}')if char in t_dic.keys() and t_dic[char] == s_dic[char]:flag += 1# print(f'flag:{flag}')while flag == len(t_dic) and start <= end:if end - start + 1 <= min_len:min_len = end - start + 1min_substr = S[start:end + 1]else:pass# print(f'min_substr:{min_substr}')s_dic[S[start]] -= 1if S[start] in t_dic.keys() and t_dic[S[start]] > s_dic[S[start]]:flag -= 1start += 1# print(f's_dic:{s_dic}')# print(f'flag:{flag}')# print(f'res_final:{res_final}')return min_substr

习题2

给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和:子数组的长度是 k,且
子数组中的所有元素 各不相同 。
返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件,返回 0 。子数组 是数组中一段连续非空的元素序列。示例 输入:nums = [1,5,4,2,9,9,9], k = 3
输出:15
解释:nums 中长度为 3 的子数组是:
- [1,5,4] 满足全部条件,和为 10 。
- [5,4,2] 满足全部条件,和为 11 。
- [4,2,9] 满足全部条件,和为 15 。
- [2,9,9] 不满足全部条件,因为元素 9 出现重复。
- [9,9,9] 不满足全部条件,因为元素 9 出现重复。
因为 15 是满足全部条件的所有子数组中的最大子数组和,所以返回 15 。

思路:

  1. 用字典 nums_dic 维护窗口内元素的个数,用 max_sum 维护窗口内的数之和
  2. 遍历数组,窗口进入进出一个元素(需要维护 nums_dic 和 max_sum),若满足条件(len(nums_dic)== k)则更新 max_val
def maximumSubarraySum(nums, k):if len(nums) == 0 or k == 0:return 0if k == 1:return max(nums)max_val = float('-inf')nums_dic = Counter(nums[:k-1])max_sum = sum(nums[:k-1])for i in range(k - 1, len(nums)):nums_dic[nums[i]] += 1max_sum = max_sum + nums[i]# print(f'nums_dic:{nums_dic}')# print(f'max_sum:{max_sum}')if len(nums_dic) == k:max_val = max(max_sum, max_val)nums_dic[nums[i - k + 1]] -= 1if nums_dic[nums[i - k + 1]] == 0:del nums_dic[nums[i - k + 1]]max_sum -= nums[i - k + 1]return 0 if max_val == float('-inf') else max_val

        

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/474964.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

DAO模式

前言 DAO&#xff08;Data Access Object&#xff09;模式 是一种常用的设计模式&#xff0c;主要用于将数据访问逻辑与业务逻辑分离。它提供了一种抽象层&#xff0c;使得应用程序可以与不同的数据源&#xff08;如数据库、文件系统等&#xff09;进行交互&#xff0c;而无需…

mysql日志写满出现The table ‘xxxx_amazon_order’ is full

数仓发现写数据出现 SQL 错误 [1114] [HY000]: The table ‘xxxx_amazon_order’ is full 1.第一时间查看系统磁盘, 发现空间写满了 df -h因为mysql是使用docker部署的, Docker 的默认存储位置在 /var/lib/docker /var 目录默认是在根分区 (/dev/mapper/centos-root) 下的 …

【读书笔记-《网络是怎样连接的》- 7】Chapter3_2 路由器

本篇继续介绍路由器及其转发过程。 1 路由器内部结构 路由器内部结构图如图所示。 即主要包含左侧的包转发模块和右侧的端口模块。转发模块负责查找包的发送目的地&#xff0c;端口模块完成包的发送。通过安装不同的硬件&#xff0c;转发模块不仅可以支持以太网&#xff0c;也…

P5099 [USACO04OPEN] Cave Cows 4

P5099 [USACO04OPEN] Cave Cows 4https://www.luogu.com.cn/problem/P5099 思路&#xff1a; 这里的垫蹄石之间很明显是有后效性的 所以不能用dp来做 考虑宽搜 我们每次都枚举和这个垫蹄石之间x方向和z方向的距离均不超过2的垫脚石 因为都很大 我们可以使用 代码&#xf…

高阶C语言之六:程序环境和预处理

本文介绍程序的环境&#xff0c;在Linux下对编译链接理解&#xff0c;较为简短&#xff0c;着重在于编译的步骤。 C的环境 在ANSI C&#xff08;标准C语言&#xff09;的任何一种实现中&#xff0c;存在两个不同的环境。 翻译环境&#xff1a;在这个环境中&#xff0c;源代码…

【Python数据可视化分析实战】数据爬取—京东手机品牌信息数据爬取和数据分析与可视化

大数据分析设计方案 1.数据集来源&#xff1a;https://search.jd.com 2.实现思路&#xff1a; &#xff08;1&#xff09;数据爬取 首先&#xff0c;我们需要从京东平台上采集手机品牌的相关数据。可以通过网络爬虫或API接口等方式获取数据。为了保证数据的完整性和准确性&…

【MySQL-4】表的基本查询

目录 1. 整体学习的思维导图 2. 表的创建 2.1 Create(创建) 2.1.1 插入规则 2.1.2 更新插入 2.2 Retrieve(读取) 2.2.1 创建一个实例表 2.3 select使用 2.3.1 全表查询 2.3.2 指定序列查询 2.3.3 查询表达式 2.3.3.1 为查询表达式改名字 2.3.4 查询去重 2.…

无人机航测技术算法概述!

一、核心技术 传感器技术&#xff1a; GPS/GLONASS&#xff1a;无人机通过卫星定位系统实现高精度的飞行控制和数据采集。 高清相机&#xff1a;用于拍摄地面图像&#xff0c;通过后续图像处理生成三维模型。 激光雷达&#xff08;LiDAR&#xff09;&#xff1a;通过激光扫…

uniapp 自定义加载组件,全屏加载,局部加载 (微信小程序)

效果图 全屏加载 页面加载使用 局部加载 列表加载里面使用 使用gif html <template><view><view class"" v-if"typeFullScreen"><view class"loading" v-if"show"><view class""><i…

【D3.js in Action 3 精译_040】4.4 D3 弧形图的绘制方法

当前内容所在位置&#xff1a; 第四章 直线、曲线与弧线的绘制 ✔️ 4.1 坐标轴的创建&#xff08;上篇&#xff09; 4.1.1 D3 中的边距约定&#xff08;中篇&#xff09;4.1.2 坐标轴的生成&#xff08;中篇&#xff09; 4.1.2.1 比例尺的声明&#xff08;中篇&#xff09;4.1…

element ui 走马灯一页展示多个数据实现

element ui 走马灯一页展示多个数据实现 element ui 走马灯一页展示多个数据实现 element ui 走马灯一页展示多个数据实现 主要是对走马灯的数据的操作&#xff0c;先看js处理 let list [{ i: 1, name: 1 },{ i: 2, name: 2 },{ i: 3, name: 3 },{ i: 4, name: 4 },]let newL…

使用MaxKB搭建知识库问答系统并接入个人网站(halo)

首发地址&#xff08;欢迎大家访问&#xff09;&#xff1a;使用MaxKB搭建知识库问答系统并接入个人网站 前言 从OpenAI推出ChatGPT到现在&#xff0c;大模型已经渗透到各行各业&#xff0c;大模型也逐渐趋于平民化&#xff1b;从最开始对其理解、生成、强大的知识积累的惊叹&…

Linux进阶:软件安装、网络操作、端口、进程等

软件安装 yum 和 apt 均需要root权限 CentOS系统使用&#xff1a; yum [install remove search] [-y] 软件名称 install 安装remove 卸载search 搜索-y&#xff0c;自动确认 Ubuntu系统使用 apt [install remove search] [-y] 软件名称 install 安装remove 卸载search 搜索-y&…

如何解决飞书网页文字无法复制的问题

如何解决网页文字无法复制的问题&#xff1f;特别推荐提词宝防复制文案功能&#xff01; 在日常工作和学习中&#xff0c;我们经常遇到一些网页文字无法复制的情况&#xff0c;无论是因为权限限制还是其他原因&#xff0c;手动输入内容不仅耗时费力&#xff0c;还容易出错。那…

STM32电源管理—实现低功耗

注&#xff1a; 本文是学习野火的指南针开发板过程的学习笔记&#xff0c;可能有误&#xff0c;详细请看B站野火官方配套视频教程&#xff08;这个教程真的讲的很详细&#xff0c;请给官方三连吧&#xff09; 在响应绿色发展的同时&#xff0c;在很多应用场合中都对电子设备的功…

Linux网络:守护进程

Linux网络&#xff1a;守护进程 会话进程组会话终端 守护进程setsiddaemon 在创建一个网络服务后&#xff0c;往往这个服务进程是一直运行的。但是对于大部分进程来说&#xff0c;如果退出终端&#xff0c;这个终端上创建的所有进程都会退出&#xff0c;这就导致进程的生命周期…

基于深度学习的文本信息提取方法研究(pytorch python textcnn框架)

&#x1f497;博主介绍&#x1f497;&#xff1a;✌在职Java研发工程师、专注于程序设计、源码分享、技术交流、专注于Java技术领域和毕业设计✌ 温馨提示&#xff1a;文末有 CSDN 平台官方提供的老师 Wechat / QQ 名片 :) Java精品实战案例《700套》 2025最新毕业设计选题推荐…

Seatunnel解决Excel中无法将数字类型转换成字符串类型以及源码打包

需求 需要实现将Excel中的数字类型的单元格像数据库中字符串类型的字段中推送 问题原因 Seatunnel在读取字段类型的时候都是使用强转的形式去获取数据的 假如说数据类型不一样的话直接强转就会报错 修改位置 org/apache/seatunnel/api/table/type/SeaTunnelRow.java org…

AntFlow 0.11.0版发布,增加springboot starter模块,一款设计上借鉴钉钉工作流的免费企业级审批流平台

AntFlow 0.11.0版发布,增加springboot starter模块,一款设计上借鉴钉钉工作流的免费企业级审批流平台 传统老牌工作流引擎比如activiti,flowable或者camunda等虽然功能强大&#xff0c;也被企业广泛采用&#xff0c;然后也存着在诸如学习曲线陡峭&#xff0c;上手难度大&#x…

UniAPP快速入门教程(一)

一、下载HBuilder 首先需要下载HBuilder开发工具&#xff0c;下载地址:https://www.dcloud.io/hbuilderx.htmlhttps://www.dcloud.io/hbuilder.html 选择Windows正式版.zip文件下载。下载解压后直接运行解压目录里的HBuilderX.exe就可以启动HBuilder。 UniApp的插件市场网址…