Hot100之子串
560和为K的子数组
题目
给你一个整数数组 nums
和一个整数 k
,请你统计并返回 该数组中和为 k
的子数组的个数 。
子数组是数组中元素的连续非空序列
思路解析
ps:我们的presum【0】就是0,如果没有这个0的话我们的第一个元素就无法减去上一个元素,为了让我们的第一个元素也能参与前缀和减法,所以我们的presum【0】就是0
我们首先收集前缀和
然后我们两个for循环,里面前缀和作差
然后count++收集答案
代码
class Solution {public int subarraySum(int[] nums, int k) {//前缀和数组int[] presum = new int[nums.length+1];for (int i = 0; i < nums.length; i++) {//这里需要注意,我们的前缀和是presum[1]开始填充的presum[i+1] = nums[i] + presum[i];}//统计个数int count = 0;for (int i = 0; i < nums.length; ++i) {for (int j = i; j < nums.length; ++j) {//注意偏移,因为我们的nums[2]到nums[4]等于presum[5]-presum[2]//所以这样就可以得到nums[i,j]区间内的和if (presum[j+1] - presum[i] == k) {count++;}}}return count;}
}
239滑动窗口的最大值
题目
给你一个整数数组 nums
,有一个大小为 k
的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k
个数字。滑动窗口每次只向右移动一位
思路解析
简单的单调栈+滑动窗口思想
我们维护栈内单调递减就行
当里面元素个数大于K的时候,我们就弹出第一个元素就好了
代码
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {Deque<Integer> deque = new ArrayDeque<>();int n = nums.length;// 初始化收集结果的数组int result[] = new int[n - k + 1];for (int i = 0; i < n; i++) {// 入while (!deque.isEmpty() && nums[deque.getLast()] <= nums[i]) {deque.removeLast(); // 维护q的单调性}deque.addLast(i); // 入队,这是把我们的下标给存进去if (i - deque.getFirst() >= k) {// 这个是我们的队首已经离开窗口了deque.removeFirst();}// 收集我们的答案if (i >= k - 1) {result[i - k + 1] = nums[deque.getFirst()];}}return result;}
}
前置知识--209长度最小的子数组
题目
思路解析
不断缩小左端点
代码
class Solution {public int minSubArrayLen(int target, int[] nums) {int left = 0, right = 0, n = nums.length;int min = Integer.MAX_VALUE;int sum = 0;while (right < n) {sum += nums[right];while (sum >= target) {min = Math.min(min, right - left + 1);sum -= nums[left];left++;}right++;}return min == Integer.MAX_VALUE ? 0 : min;}
}
76最小覆盖子串
题目
去看上一节的前置知识先
思路解析
字符数组的含义
我们把子串变成字符数组,父串变成字符数组
数组的逻辑是,我们遍历字符串,对特定的字符进行计数,也就是++
char[] SChar = s.toCharArray();//子串的数组int m=s.length();//子串的长度int ansLeft=-1;int ansRight=m;int[] cntS=new int[128];//s子串的字母出现次数,s是子串int[] cntT=new int[128];//t字符串中字母出现的次数,t是父串//对父串中的字符的值进行初始化for(char c:t.toCharArray()){cntT[c]++;}
涵盖函数
然后我们弄个涵盖函数,判断当前字符串是否涵盖
如果父串里面的字符比子串多,我们返回false,说明这个子串没有涵盖父串的所有字符
如果子串里的字符数量都比子串多,那么说明这个子串没问题,这个子串涵盖了父串中的所有字符
//如果父串里面的字符比子串多,我们返回false,说明这个子串并没有涵盖父串的所有字符//如果子串里的字符数量都比子串多,那么说明这个子串没问题,这个子串涵盖了父串中的所有字符private boolean isCovered(int[] cntS,int[] cntT){for(int i='A';i<='Z';i++){if(cntS[i]<cntT[i]){return false;}}for(int i='a';i<='z';i++){if(cntS[i]<cntT[i]){return false;}}return true;}
滑动窗口思想
我们遍历子串,操作子串
子串进入数组,然后根据我们的涵盖函数
如果涵盖+找到了更短的子串,那我们就计算最短长度然后记住left和right
然后弹出最左侧元素,也就是left++进行我们的滑动窗口的收缩
int left=0;for(int right=0;right<m;right++){//移动子串右端点cntS[SChar[right]]++;//右端点字母进入子串while(isCovered(cntS,cntT)){//涵盖if(right-left<ansRight-ansLeft){//找到了更短的子串ansLeft=left;ansRight=right;}cntS[SChar[left]]--;//左端点字母移出子串left++;}}return ansLeft<0?"":s.substring(ansLeft,ansRight+1);
为什么ansLeft要初始化成-1?
因为我们要是初始化成0的话,我们并不能判断是否找到了满足条件的子串,因为我们的最终的return函数是根据0来判断,我们是否移动了指针(即是否找到了一个满足条件的子串)
看看我们的return
return ansLeft<0?"":s.substring(ansLeft,ansRight+1);
代码
class Solution {public String minWindow(String s, String t) {char[] SChar = s.toCharArray();//子串的数组int m=s.length();//子串的长度int ansLeft=-1;int ansRight=m;int[] cntS=new int[128];//s子串的字母出现次数,s是子串int[] cntT=new int[128];//t字符串中字母出现的次数,t是父串//对父串中的字符的值进行初始化for(char c:t.toCharArray()){cntT[c]++;}int left=0;for(int right=0;right<m;right++){//移动子串右端点cntS[SChar[right]]++;//右端点字母进入子串while(isCovered(cntS,cntT)){//涵盖if(right-left<ansRight-ansLeft){//找到了更短的子串ansLeft=left;ansRight=right;}cntS[SChar[left]]--;//左端点字母移出子串left++;}}return ansLeft<0?"":s.substring(ansLeft,ansRight+1);}//如果父串里面的字符比子串多,我们返回false,说明这个子串并没有涵盖父串的所有字符//如果子串里的字符数量都比子串多,那么说明这个子串没问题,这个子串涵盖了父串中的所有字符private boolean isCovered(int[] cntS,int[] cntT){for(int i='A';i<='Z';i++){if(cntS[i]<cntT[i]){return false;}}for(int i='a';i<='z';i++){if(cntS[i]<cntT[i]){return false;}}return true;}
}
相关文章:
Hot100之子串
560和为K的子数组 题目 给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续非空序列 思路解析 ps:我们的presum【0】就是0,如果没有这个0的话我们的第一个元素就无法减去上…...
SpringBoot笔记
1.创建 使用idea提供的脚手架创建springboot项目,选上需要的模块,会自动进行导包 打成jar包,之前直接用原生的maven打包的是一个瘦jar,不能直接跑,把服务器上部署的jar排除在外了,但是现在加上打包查件&am…...
一、TensorFlow的建模流程
1. 数据准备与预处理: 加载数据:使用内置数据集或自定义数据。 预处理:归一化、调整维度、数据增强。 划分数据集:训练集、验证集、测试集。 转换为Dataset对象:利用tf.data优化数据流水线。 import tensorflow a…...
4 Hadoop 面试真题
4 Hadoop 面试真题 1. Apache Hadoop 3.0.02. HDFS 3.x 数据存储新特性-纠删码Hadoop面试真题 1. Apache Hadoop 3.0.0 Apache Hadoop 3.0.0在以前的主要发行版本(hadoop-2.x)上进行了许多重大改进。 最低要求的Java版本从Java 7增加到Java 8 现在&…...
信息学奥赛一本通 ybt 1608:【 例 3】任务安排 3 | 洛谷 P5785 [SDOI2012] 任务安排
【题目链接】 ybt 1608:【 例 3】任务安排 3 洛谷 P5785 [SDOI2012] 任务安排 【题目考点】 1. 动态规划:斜率优化动规 2. 单调队列 3. 二分答案 【解题思路】 与本题题面相同但问题规模不同的题目: 信息学奥赛一本通 1607:…...
实验六 项目二 简易信号发生器的设计与实现 (HEU)
声明:代码部分使用了AI工具 实验六 综合考核 Quartus 18.0 FPGA 5CSXFC6D6F31C6N 1. 实验项目 要求利用硬件描述语言Verilog(或VHDL)、图形描述方式、IP核,结合数字系统设计方法,在Quartus开发环境下ÿ…...
基于最近邻数据进行分类
人工智能例子汇总:AI常见的算法和例子-CSDN博客 完整代码: import torch import numpy as np from sklearn.neighbors import KNeighborsClassifier from sklearn.metrics import accuracy_score import matplotlib.pyplot as plt# 生成一个简单的数据…...
SpringSecurity:There is no PasswordEncoder mapped for the id “null“
文章目录 一、情景说明二、分析三、解决 一、情景说明 在整合SpringSecurity功能的时候 我先是去实现认证功能 也就是,去数据库比对用户名和密码 相关的类: UserDetailsServiceImpl implements UserDetailsService 用于SpringSecurity查询数据库 Logi…...
redex快速体验
第一步: 2.回调函数在每次state发生变化时候自动执行...
Flask框架基础入门教程_ezflaskapp
pip install flaskFlask 快速入门小应用 学东西,得先知道我们用这个东西,能做出来一个什么东西。 一个最小的基于flask 的应用可能看上去像下面这个样子: from flask import Flask app Flask(__name__)app.route(/) def hello_world():ret…...
Anaconda 全面解析:从入门到精通的操作教程
大家好,我是滔滔,欢迎来到我的空间。先简单介绍下anconda 一、环境管理 轻松创建独立的 Python 环境:可以为不同的项目创建不同的环境,每个环境可以有不同的 Python 版本和安装不同的包,避免了包冲突问题。例如&…...
3D图形学与可视化大屏:什么是材质属性,有什么作用?
一、颜色属性 漫反射颜色 漫反射颜色决定了物体表面对入射光进行漫反射后的颜色。当光线照射到物体表面时,一部分光被均匀地向各个方向散射,形成漫反射。漫反射颜色的选择会直接影响物体在光照下的外观。例如,一个红色的漫反射颜色会使物体在…...
HTML-新浪新闻-实现标题-排版
标题排版 图片标签:<img> src:指定图片的url(绝对路径/相对路径) width:图片的宽度(像素/相对于父元素的百分比) heigth:图片的高度(像素/相对于父元素的百分比&a…...
.Net / C# 分析文件编码 并将 各种编码格式 转为 另一个编码格式 ( 比如: GB2312→UTF-8, UTF-8→GB2312)
相关库 .Net 8 编码识别: github.com/CharsetDetector/UTF-unknown <PackageReference Include"UTF.Unknown" Version"2.5.1" />代码 using UtfUnknown;var dir_path "D:\\Desktop\\新建文件夹2\\新建文件夹"; var dir_new_path &quo…...
本地部署 DeepSeek-R1 大模型
本地部署 DeepSeek-R1 大模型指南 1. 引言 1.1 DeepSeek-R1 模型简介 在人工智能的世界里,大型语言模型(LLM)正如一座巨大的宝库,里面储存着丰富的信息和无限的潜力。而DeepSeek-R1,就像那扇打开智慧之门的钥匙。它…...
canvas的基本用法
canvas canvas元素简介 1.是个container元素<canvas width100 height100></canvas>,有开闭标签 2.有且只有width和height两个attribute,不需要写单位 canvas的基本使用 const canvasEl document.getElementById(canvas01) const ctx …...
力扣【416. 分割等和子集】详细Java题解(背包问题)
首先我们可以求出数组和,当我们找到一个子集中元素的和为数组和的一半时,该就说明可以分割等和子集。 对于该问题我们可以转换成背包问题,求 数组里的元素 装入 数组和的一半大小的背包 能取得的最大值。 然后注意可以剪枝的地方。 代码&…...
UE学习日志#17 C++笔记#3 基础复习3
19.2 [[maybe_unused]] 禁止编译器在未使用某些内容时发出警告 19.3 [[noreturn]] 永远不会把控制权返回给调用点 19.4 [[deprecated]] 标记为已弃用,仍然可以使用但是不鼓励使用 可以加参数表示弃用的原因[[deprecated("")]] 19.5 [[likely]]和[[un…...
c++:vector
1.使用 1.1构造函数 常见的三种构造方式:空构造,拷贝构造,指定元素构造 1.2iterator begin和end也分为正向和反向。 注意:反向迭代器可以反向遍历是因为在定义rbegin和rend函数的时候把尾地址给到了rbegin,而不是说改…...
37. RGBLCD实验
一、RGBLCD显示原理简介 1、像素点 于一个“小灯“,不管是液晶屏,还是手机,平板,RGBLCD屏幕他都是有由一个个的彩色小灯构成的。彩色点阵屏每个像素点有三个小灯,红色、绿色和蓝色,也叫做RGB。RGB就是光的…...
反馈驱动、上下文学习、多语言检索增强等 | Big Model Weekly 第55期
点击蓝字 关注我们 AI TIME欢迎每一位AI爱好者的加入! 01 A Bayesian Approach to Harnessing the Power of LLMs in Authorship Attribution 传统方法严重依赖手动特征,无法捕捉长距离相关性,限制了其有效性。最近的研究利用预训练语言模型的…...
【深度分析】微软全球裁员计划不影响印度地区,将继续增加当地就业机会
当微软的裁员刀锋掠过全球办公室时,班加罗尔的键盘声却愈发密集——这场资本迁徙背后,藏着数字殖民时代最锋利的生存法则。 表面是跨国公司的区域战略调整,实则是全球人才市场的地壳运动。微软一边在硅谷裁撤年薪20万美金的高级工程师&#x…...
H. Mad City
题目链接:Problem - H - Codeforces 题目大意:给定一个带环的图, 以及a, b两点 判断再图上不断的移动, b想不与a相遇, a想捉到b, 并且二者只能移动一步。 若b跑不掉 NO 否则YES. 具体题目看链接 输入: …...
【C++】类与对象(下)
🦄 个人主页: 小米里的大麦-CSDN博客 🎏 所属专栏: 小米里的大麦——C专栏_CSDN博客 🎁 代码托管: 小米里的大麦的Gitee仓库 ⚙️ 操作环境: Visual Studio 2022 文章目录 1. 再谈构造函数1.1 构造函数体赋值1.2 初始化列表1.3 explicit 关键…...
AJAX案例——图片上传个人信息操作
黑马程序员视频地址: AJAX-Day02-11.图片上传https://www.bilibili.com/video/BV1MN411y7pw?vd_source0a2d366696f87e241adc64419bf12cab&spm_id_from333.788.videopod.episodes&p26 图片上传 <!-- 文件选择元素 --><input type"file"…...
Redis-布隆过滤器
文章目录 布隆过滤器的特点:实践布隆过滤器应用 布隆过滤器的特点: 就可以把布隆过滤器理解为一个set集合,我们可以通过add往里面添加元素,通过contains来判断是否包含某个元素。 布隆过滤器是一个很长的二进制向量和一系列随机映射函数。 可以用来检索…...
OpenCV 图像旋转
在学习 OpenCV 和 Matplotlib 处理图像时,遇到了一些关于 cv2.imread()、cv2.getRotationMatrix2D()、plt.imshow() 的问题: import cv2 import numpy as np import matplotlib.pyplot as pltimg cv2.imread(img2.png, 1) # 读取彩色图像(…...
联想Y7000+RTX4060+i7+Ubuntu22.04运行DeepSeek开源多模态大模型Janus-Pro-1B+本地部署
直接上手搓了: conda create -n myenv python3.10 -ygit clone https://github.com/deepseek-ai/Janus.gitcd Januspip install -e .pip install webencodings beautifulsoup4 tinycss2pip install -e .[gradio]pip install pexpect>4.3python demo/app_januspr…...
在线知识库创建与维护提升企业效率与知识共享能力
内容概要 在当今数字化快速发展的背景下,在线知识库逐渐成为企业管理信息的重要工具。其核心在于将知识进行系统化、结构化的整理和存储,便于员工获取和分享。这不仅提高了信息的访问效率,还促进了团队之间的协作。在线知识库的建立可以有效…...
C语言指针专题二 -- 字符指针与字符串
目录 1. 字符指针与字符串的核心原理 字符串的本质 字符串的存储 字符指针的特性 字符指针的操作 2. 编程实例 3. 常见陷阱与注意事项 4. 总结 1. 字符指针与字符串的核心原理 字符串的本质 C语言中没有独立的字符串类型,字符串本质是 以\0(空…...
玄武计划--干中学,知行合一
作为开发者转型安全领域有一定优势,但需要系统学习网络安全知识。以下是针对你的情况(Java背景 + 快速入门)的实战导向学习路径,分为基础、工具、漏洞利用和进阶四个阶段: 一、基础准备(1-2周) 网络协议与渗透基础 重点协议:深入理解 TCP/IP、HTTP/HTTPS、DNS、SMTP,用…...
处理 .gitignore 未忽略文件夹问题
本地删除缓存 例如 .idea 文件夹被其他同事误提交,那么他本地执行以下代码 git rm -r --cached .idea对应本地再提交即可...
实验七 JSP内置对象II
实验七 JSP内置对象II 目的: 1、掌握JSP内置对象的使用。 2、理解JSP的作用域 3、掌握session,application对象的使用 实验要求: 1、完成实验题目 2、要求提交实验报告,将代码和实验结果页面截图放入报告中 实验过程:…...
【Leetcode 每日一题 - 补卡】219. 存在重复元素 II
问题背景 给你一个整数数组 n u m s nums nums 和一个整数 k k k,判断数组中是否存在两个 不同的索引 i i i 和 j j j,满足 n u m s [ i ] n u m s [ j ] nums[i] nums[j] nums[i]nums[j] 且 ∣ i − j ∣ < k |i - j| < k ∣i−j∣<…...
Flask数据的增删改查(CRUD)_flask删除数据自动更新
查询年龄小于17的学生信息 Student.query.filter(Student.s_age < 17) students Student.query.filter(Student.s_age.__lt__(17))模糊查询,使用like,查询姓名中第二位为花的学生信息 like ‘_花%’,_代表必须有一个数据,%任何数据 st…...
web自动化——前端知识
<iframe> 是 HTML 中的一个元素,用于在当前网页中嵌入另一个网页或文档。它就像一个“窗口”,可以在页面中显示其他内容。 主要特点: 嵌入外部内容:可以在网页中嵌入其他网页、视频、地图等。独立上下文:嵌入的…...
计算机网络一点事(22)
地址解析协议ARP ARP:查询Mac地址 ARP表(ARP缓存):记录映射关系,一个数据结构,定期更新ARP表 过程:请求分组,响应分组 动态主机配置协议DHCP 分配IP地址,配置默认网关…...
SG算法解析
Savitzky-Golay 滤波器的核心代码主要集中在计算投影矩阵B并使用这个矩阵对输入信号进行滤波。这部分核心代码包括计算B矩阵、处理边界效应和进行实际滤波操作。以下是对核心代码的一点解释: ① 计算 Savitzky-Golay 投影矩阵B B sgolay(order, framelen, weight…...
Ubuntu Server连接wifi
背景 家里服务器放在客厅太吵了, 准备挪到阳台, 所以买了TP wifi接收器, 因此需要配置wifi连接. 刚开始买了Tenda Ax300, 结果不支持服务器系统, 买前还是得和客服交流交流. 准备 驱动安装 对于windows系统来说, 这款接收器是免驱的, 但在linux上需要安装相应型号驱动 安装…...
Linux 4.19内核中的内存管理:x86_64架构下的实现与源码解析
在现代操作系统中,内存管理是核心功能之一,它直接影响系统的性能、稳定性和多任务处理能力。Linux 内核在 x86_64 架构下,通过复杂的机制实现了高效的内存管理,涵盖了虚拟内存、分页机制、内存分配、内存映射、内存保护、缓存管理等多个方面。本文将深入探讨这些机制,并结…...
L30.【LeetCode笔记】设计链表
1.题目 707. 设计链表 - 力扣(LeetCode) 你可以选择使用单链表或者双链表,设计并实现自己的链表。 单链表中的节点应该具备两个属性:val 和 next 。val 是当前节点的值,next 是指向下一个节点的指针/引用。 如果是双向…...
使用Pygame制作“Flappy Bird”游戏
1. 前言 Flappy Bird 是一款“点击上浮、松手下落”的横向卷轴游戏: 场景中持续出现上下成对的管道,玩家需要让小鸟在管道之间穿行;每穿过一对管道记 1 分;若小鸟碰到管道或掉到地面,则游戏结束;一旦上手…...
PHP中配置 variables_order详解
variables_order 是 PHP 配置文件 php.ini 中的一项配置指令,决定了 PHP 在处理请求时,哪些类型的变量将被注册到全局变量空间(如 $GLOBALS)中,以及这些变量的顺序。理解和正确配置 variables_order 对于开发和维护安全…...
Go学习:运算符总结
在 Go语言中,一元运算符拥有最高的优先级,二元运算符的运算方向均是从左至右。 下表列出了所有运算符以及它们的优先级,由上至下代表优先级由高到低:...
JS面相对象小案例:自定义安全数组
在JS中,数组不像其他语言(java、python)中那样安全,它具有动态性和弱类型性,切越界访问没有具体的报错,而是返回空,为提升数组的安全性,我们可以自行定义一个安全数组。 一、增加报…...
将markdown文件转为word文件
通义千问等大模型生成的回答多数是markdown类型的,需要将他们转为Word文件 一 pypandoc 介绍 1. 项目介绍 pypandoc 是一个用于 pandoc 的轻量级 Python 包装器。pandoc 是一个通用的文档转换工具,支持多种格式的文档转换,如 Markdown、HTM…...
Unet 改进:在encoder和decoder间加入TransformerBlock
目录 1. TransformerBlock 2. Unet 改进 3. 完整代码 Tips:融入模块后的网络经过测试,可以直接使用,设置好输入和输出的图片维度即可 1. TransformerBlock TransformerBlock是Transformer模型架构的基本组件,广泛应用于机器翻译、文本摘要和情感分析等自然语言处理任务…...
LeetCode题练习与总结:两个列表的最小索引总和--599
一、题目描述 假设 Andy 和 Doris 想在晚餐时选择一家餐厅,并且他们都有一个表示最喜爱餐厅的列表,每个餐厅的名字用字符串表示。 你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个,则输出所有答案并且不考虑顺序。…...
IBM数据与人工智能系列 安装 IBM 编程助手
登录CPD环境 ${CPDM_OC_LOGIN} 安装编程助手 cpd-cli manage apply-olm \ --release${VERSION} \ --cpd_operator_ns${PROJECT_CPD_INST_OPERATORS} \ --componentswca cpd-cli manage apply-cr \ --componentswca \ --release${VERSION} \ --cpd_instance_ns${PROJECT_CPD…...
细说机器学习算法之ROC曲线用于模型评估
系列文章目录 第一章:Pyhton机器学习算法之KNN 第二章:Pyhton机器学习算法之K—Means 第三章:Pyhton机器学习算法之随机森林 第四章:Pyhton机器学习算法之线性回归 第五章:Pyhton机器学习算法之有监督学习与无监督…...