力扣难题解析

滑动窗口问题

76.最小覆盖子串

题目链接:76. 最小覆盖子串 - 力扣(LeetCode)

题目描述:

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。

输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

实现思路:

使用HashMap记录模板串t,中的字母分布数量。

在目标串s,中维护一个滑动窗口,并记录目标字符的数量,通过检测目标字符数与hashmap是否一致,判断当前窗口是否是有效窗口。

窗口的扩展:窗口向右扩展,收录一个字符。如果是目标字符,加入当前记录,并判断是否符合窗口收缩要求。不符合要求则继续扩展窗口。

窗口的收缩:1.当前窗口符合找到所有字符之后,并开始从左侧收缩,直到遇见了第一个不能舍去的有效字符。

代码实现:

class Solution {public String minWindow(String s, String t) {HashMap<Character, Integer> dict = new HashMap<>();HashMap<Character, Integer> map = new HashMap<>();char[] arrt = t.toCharArray();for (int i=0; i<arrt.length; i++) {dict.compute(arrt[i], (k,v) -> { return v == null ? 1 : v + 1;});map.compute(arrt[i], (k,v) -> {return 0;});}int left = 0, right = -1;int minLen = Integer.MAX_VALUE, ansl = -1, ansr = -1;       char[] arrs = s.toCharArray();while (right < arrs.length - 1) {// 向右拓展窗口right++;char ch = arrs[right];if (!dict.containsKey(ch)) continue; // 过滤掉非目标字符map.compute(ch, (k,v) -> { return v + 1;});// 从左侧收缩窗口if (check(map,dict)) {while (left <= right) {char c = arrs[left];// 收缩过程中跳过普通字符if (!dict.containsKey(c)) { left++;continue;}// 跳过数量过多的目标字符if (map.get(c) > dict.get(c)) { map.compute(c, (k,v) -> {return v-1;});left++;}// 遇到了不能跳过的目标字符else {// 更新结果if (right - left + 1 < minLen) {ansl = left;ansr = right;minLen = right - left + 1;}break;}}// System.out.println("收缩完毕 " + map + result);}}return ansl == -1 ? "" : s.substring(ansl, ansr+1);}// 检查当前字符合集是否符合要求public boolean check(HashMap<Character, Integer> map, HashMap<Character, Integer> dict) {for (Map.Entry<Character, Integer> entry : map.entrySet()) {if (entry.getValue() < dict.get(entry.getKey())) return false;   }return true;}
}

其他问题

54.螺旋矩阵

题目链接:54. 螺旋矩阵 - 力扣(LeetCode)

题目描述:

给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。

实现思路:

模拟每一圈的打印模式,规定上下左右层的打印顺序和打印的数据长度。

当剩余的元素不能够组成一圈的时候,补充核心元素。

重点在于控制元素数量:       

  • 打印当前宽度-1个元素
  • for (; i<colStart+rowWidth-1; i++)
  • for (; j<rowStart+colWidtg-1; j++)
  • 当某个维度剩余元素少于2个的时候,说明只剩下核心元素没有打印了

代码实现:

class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> result = new LinkedList<>();// 上下的圈数int m = matrix[0].length; // 剩余的列int n = matrix.length; // 剩余的行int rowWidth = m, colWith = n;int rowStart = 0, colStart = 0,i = 0,j = 0;// 左闭右开区间while(rowWidth > 1 && colWith > 1) {int loop1 = rowWidth;int loop2 = colWith;i = colStart;j = rowStart;// 打印上层for (; i<colStart+loop1-1; i++) result.add(matrix[j][i]);// 打印右侧for (; j<rowStart+loop2-1; j++)result.add(matrix[j][i]);// 打印下侧for (; i>colStart; i--) result.add(matrix[j][i]);// 打印左侧for (; j>rowStart;j--) result.add(matrix[j][i]);rowWidth -= 2;colWith -= 2;rowStart++;colStart++;}// 填充中间剩余部分i = colStart;j = rowStart;;if (rowWidth == 1) { // 只剩下一列for (int ct=0;ct<colWith; ct++,j++) result.add(matrix[j][i]);}else if (colWith == 1) { // 只剩下一行for (int ct=0;ct<rowWidth; ct++,i++) result.add(matrix[j][i]);            }return result;}
}

48.旋转图像

题目链接:48. 旋转图像 - 力扣(LeetCode)

题目描述:

给定一个 × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

实现思路:

翻转代理旋转,先水平反转,再对角反转。

对角线反转的代码其实很简单,但是我花了点时间才想明白。

代码实现:

class Solution {public void rotate(int[][] matrix) {int n = matrix.length;// 水平翻转for (int i = 0; i < n / 2; ++i) {for (int j = 0; j < n; ++j) {int temp = matrix[i][j];matrix[i][j] = matrix[n - i - 1][j];matrix[n - i - 1][j] = temp;}}// 主对角线翻转for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j) {int temp = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = temp;}}}
}

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

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

相关文章

一体化数据安全平台uDSP 入选【年度创新安全产品 TOP10】榜单

近日&#xff0c;由 FreeBuf 主办的 FCIS 2024 网络安全创新大会在上海隆重举行。大会现场揭晓了第十届 WitAwards 中国网络安全行业年度评选获奖名单&#xff0c;该评选自 2015 年举办以来一直饱受赞誉&#xff0c;备受关注&#xff0c;评选旨在以最专业的角度和最公正的态度&…

pycharm链接neo4j(导入文件)

1.新建csv文件 2.写入文件 3.运行代码 import csv from py2neo import Graph, Node, Relationship# 连接到Neo4j数据库&#xff0c;使用Bolt协议 graph Graph("bolt://localhost:7687", auth("neo4j", "password"))# 读取CSV文件 with open(…

vscode ctrl+/注释不了css

方式一.全部禁用插件排查问题. 方式二.打开首选项的json文件,注释掉setting.json,排查是哪一行配置有问题. 我的最终问题:需要将 "*.vue": "vue",改成"*.vue": "html", "files.associations": { // "*.vue": &qu…

TCP三次握手与四次挥手(TCP重传机制,2MSL)超详细!!!计算机网络

本篇是关于3次握手和四次挥手的详细解释~ 如果对你有帮助&#xff0c;请点个免费的赞吧&#xff0c;谢谢汪。&#xff08;点个关注也可以&#xff01;&#xff09; 如果以下内容需要补充和修改&#xff0c;请大家在评论区多多交流~。 目录 1. TCP头部&#xff1a; 2. 三次握手…

单片机学习笔记 15. 串口通信(理论)

更多单片机学习笔记&#xff1a;单片机学习笔记 1. 点亮一个LED灯单片机学习笔记 2. LED灯闪烁单片机学习笔记 3. LED灯流水灯单片机学习笔记 4. 蜂鸣器滴~滴~滴~单片机学习笔记 5. 数码管静态显示单片机学习笔记 6. 数码管动态显示单片机学习笔记 7. 独立键盘单片机学习笔记 8…

C#中switch语句使用

编写一个程序&#xff0c;使用switch语句将用户输入的分数转换成等级&#xff0c;如表 private static void Main(string[] args) { Console.WriteLine("请输入分数&#xff1a;"); int score int.Parse(Console.ReadLine()); switch (score) …

[网络安全]sqli-labs Less-5 解题详析

[网络安全]Less-5 GET - Double Injection - Single quotes - String:双注入GET单引号字符型注入 判断注入类型判断注入点个数查库名&#xff08;爆破&#xff09; left函数抓包查库名&#xff08;双查询注入&#xff09; 原理实例查库名&#xff08;extractvalue函数&#xff…

pyspark实现基于协同过滤的电影推荐系统

最近在学一门大数据的课&#xff0c;课程要求很开放&#xff0c;任意做一个大数据相关的项目即可&#xff0c;不知道为什么我就想到推荐算法&#xff0c;一直到着手要做之前还没有新的更好的来代替&#xff0c;那就这个吧。 推荐算法 推荐算法的发展由来已久&#xff0c;但和…

python股票数据分析(Pandas)练习

需求&#xff1a; 使用pandas读取一个CSV文件&#xff0c;文件内容包括股票名称、价格和交易量。完成以下任务&#xff1a; 找出价格最高的股票&#xff1b; 计算总交易量&#xff1b; 绘制价格折线图。 代码实现&#xff1a; import pandas as pd import matplotlib.pyplot …

利用Python爬虫精准获取淘宝商品详情的深度解析

在数字化时代&#xff0c;数据的价值日益凸显&#xff0c;尤其是在电子商务领域。淘宝作为中国最大的电商平台之一&#xff0c;拥有海量的商品数据&#xff0c;对于研究市场趋势、分析消费者行为等具有重要意义。本文将详细介绍如何使用Python编写爬虫程序&#xff0c;精准获取…

K8s调度器扩展(scheduler)

1.K8S调度器 筛选插件扩展 为了熟悉 K8S调度器扩展步骤&#xff0c;目前只修改 筛选 插件 准备环境&#xff08;到GitHub直接下载压缩包&#xff0c;然后解压&#xff0c;解压要在Linux系统下完成&#xff09; 2. 编写调度器插件代码 在 Kubernetes 源代码目录下编写调度插件…

领养我的宠物:SpringBoot开发指南

第2章 开发环境与技术 本章节对开发宠物领养系统需要搭建的开发环境&#xff0c;还有宠物领养系统开发中使用的编程技术等进行阐述。 2.1 Java语言 Java语言是当今为止依然在编程语言行业具有生命力的常青树之一。Java语言最原始的诞生&#xff0c;不仅仅是创造者感觉C语言在编…

Permute for Mac 媒体文件格式转换软件 安装教程【音视频图像文件转换,简单操作,轻松转换,提高效率】

Mac分享吧 文章目录 Permute for Mac 格式转换软件 效果图展示一、Permute 格式转换软件 Mac电脑版——v3.11.15⚠️注意事项&#xff1a;1️⃣&#xff1a;下载软件2️⃣&#xff1a;安装软件2.1 左侧安装包拖入右侧文件夹中&#xff0c;等待安装完成&#xff0c;运行软件2.2…

【Android】EventBus的使用及源码分析

文章目录 介绍优点基本用法线程模式POSTINGMAINMAIN_ORDEREDBACKGROUNDASYNC 黏性事件 源码注册getDefault()registerfindSubscriberMethods小结 postpostStickyunregister 介绍 优点 简化组件之间的通信 解耦事件发送者和接收者在 Activity、Fragment 和后台线程中表现良好避…

原子类、AtomicLong、AtomicReference、AtomicIntegerFieldUpdater、LongAdder

原子类 JDK提供的原子类&#xff0c;即Atomic*类有很多&#xff0c;大体可做如下分类&#xff1a; 形式类别举例Atomic*基本类型原子类AtomicInteger、AtomicLong、AtomicBooleanAtomic*Array数组类型原子类AtomicIntegerArray、AtomicLongArray、AtomicReferenceArrayAtomic…

【Electron学习笔记(三)】Electron的主进程和渲染进程

Electron的主进程和渲染进程 Electron的主进程和渲染进程前言正文1、主进程2、渲染进程3、Preload 脚本3.1 在项目目录下创建 preload.js 文件3.2 在 main.js 文件下创建路径变量并将 preload.js 定义为桥梁3.3 在 preload.js 文件下使用 electron 提供的contextBridge 模块3.4…

FFmpeg一些常用的命令

官网&#xff1a;https://ffmpeg.org/ 官网下载&#xff1a;https://ffmpeg.org/download.html 官网下载源码&#xff1a;https://www.ffmpeg.org/releases/ FFmpeg 实用命令 — FFmpeg 教程 文档 一、参数 1.1 FFmpeg 常用参数 参数说明备注-i filename指定输入文件&#…

JAVA篇08 —— String类

欢迎来到我的主页&#xff1a;【一只认真写代码的程序猿】 本篇文章收录于专栏【小小爪哇】 如果这篇文章对你有帮助&#xff0c;希望点赞收藏加关注啦~ 目录 1 String概述 1.1 String特性 1.2 String常用方法 2 StringBuffer类 2.1 String与StringBuffer互转 2.2 Stri…

Flink四大基石之Time (时间语义) 的使用详解

目录 一、引言 二、Time 的分类及 EventTime 的重要性 Time 分类详述 EventTime 重要性凸显 三、Watermark 机制详解 核心原理 Watermark能解决什么问题,如何解决的? Watermark图解原理 举例 总结 多并行度的水印触发 Watermark代码演示 需求 代码演示&#xff…

LabVIEW将TXT文本转换为CSV格式(多行多列)

在LabVIEW中&#xff0c;将TXT格式的文本文件内容转换为Excel格式&#xff08;即CSV文件&#xff09;是一项常见的数据处理任务&#xff0c;适用于将以制表符、空格或其他分隔符分隔的数据格式化为可用于电子表格分析的形式。以下是将TXT文件转换为Excel&#xff08;CSV&#x…