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

力扣难题解析

滑动窗口问题

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;}}}
}

相关文章:

力扣难题解析

滑动窗口问题 76.最小覆盖子串 题目链接&#xff1a;76. 最小覆盖子串 - 力扣&#xff08;LeetCode&#xff09; 题目描述&#xff1a; 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串&#xff0c;则返回空…...

4.5-Channel 和 Flow:SharedFlow 和 StateFlow

文章目录 SharedFlow数据流的收集和事件订阅的区别launchIn() 和 shareIn() 的区别SharedFlow 与 Flow、Channel 的区别shareIn() 适用场景 shareIn() 的具体参数说明shareIn() 的 replay 参数shareIn() 的 started 参数WhileSubscribed() 的参数及适用场景 MutableSharedFlow、…...

Qt | TCP服务器实现QTcpServer,使用线程管理客户端套接字

点击上方"蓝字"关注我们 01、QTcpServer >>> QTcpServer 是 Qt 网络模块中的一个类,用于实现TCP服务器。它允许创建一个服务器,可以接受来自客户端的连接。QTcpServer 是事件驱动的,这意味着它将通过信号和槽机制处理网络事件。 常用函数 构造函数: QT…...

【提高篇】3.6 GPIO(六,寄存器介绍,下)

目录 2.3 输出速度寄存器OSPEEDR(GPIOx_OSPEEDR) (x = A..I) 2.4 上拉/下拉寄存器 (GPIOx_PUPDR) (x = A..I) 2.5 输入数据寄存器(IDR) 2.6 输出数据寄存器(ODR) 2.7 置位/复位寄存器(BSRR) 2.8 BSRR与ODR寄存器的区别 2.3 输出速度寄存器OSPEEDR(GPIOx_OSPEEDR) (…...

【AI】数据,算力,算法和应用(3)

三、算法 算法这个词&#xff0c;我们都不陌生。 从接触计算机&#xff0c;就知道有“算法”这样一个神秘的名词存在。象征着专业、权威、神秘、高难等等。 算法是一组有序的解决问题的规则和指令&#xff0c;用于解决特定问题的一系列步骤。算法可以被看作是解决问题的方法…...

深度学习笔记——生成对抗网络GAN

本文详细介绍早期生成式AI的代表性模型&#xff1a;生成对抗网络GAN。 文章目录 一、基本结构生成器判别器 二、损失函数判别器生成器交替优化目标函数 三、GAN 的训练过程训练流程概述训练流程步骤1. 初始化参数和超参数2. 定义损失函数3. 训练过程的迭代判别器训练步骤生成器…...

网络安全开源组件

本文只是针对开源项目进行收集&#xff0c;如果后期在工作中碰到其他开源项目将进行更新。欢迎大家在评论区留言&#xff0c;您在工作碰到的开源项目。 祝您工作顺利&#xff0c;鹏程万里&#xff01; 一、FW&#xff08;防火墙&#xff09; 1.1 pfSense pfSense项目是一个免费…...

Python毕业设计选题:基于django+vue的智慧社区可视化平台的设计与实现+spider

开发语言&#xff1a;Python框架&#xff1a;djangoPython版本&#xff1a;python3.7.7数据库&#xff1a;mysql 5.7数据库工具&#xff1a;Navicat11开发软件&#xff1a;PyCharm 系统展示 管理员登录 管理员功能界面 养老机构管理 业主管理 社区安防管理 社区设施管理 车位…...

Oracle LinuxR7安装Oracle 12.2 RAC集群实施(DNS解析)

oracleLinuxR7-U6系统Oracle 12.2 RAC集群实施&#xff08;DNS服务器&#xff09; 环境 RAC1RAC2DNS服务器操作系统Oracle LinuxR7Oracle LinuxR7windows server 2008R2IP地址172.30.21.101172.30.21.102172.30.21.112主机名称hefei1hefei2hefei数据库名hefeidbhefeidb实例名…...

M2芯片安装es的步骤

背景&#xff1a;因为最近经常用到es&#xff0c;但是测试环境没有es&#xff0c;自己本地也没安装&#xff0c;为了方便测试&#xff0c;然后安装一下&#xff0c;但是刚开始安装就报错&#xff0c;记录一下&#xff0c;安装的版本为8.16.1 第一步&#xff1a;去官网下载maco…...

macos下brew安装redis

首先确保已安装brew&#xff0c;接下来搜索资源&#xff0c;在终端输入如下命令&#xff1a; brew search redis 演示如下&#xff1a; 如上看到有redis资源&#xff0c;下面进行安装&#xff0c;执行下面的命令&#xff1a; brew install redis 演示效果如下&#xff1a; …...

第六届金盾信安杯-SSRF

操作内容&#xff1a; 进入环境 可以查询网站信息 查询环境url https://114.55.67.167:52263/flag.php 返回 flag 就在这 https://114.55.67.167:52263/flag.php 把这个转换成短连接&#xff0c;然后再提交 得出 flag...

【论文投稿】国产游戏技术:迈向全球引领者的征途

【IEEE出版南方科技大学】第十一届电气工程与自动化国际会议&#xff08;IFEEA 2024)_艾思科蓝_学术一站式服务平台 更多学术会议论文投稿请看&#xff1a;https://ais.cn/u/nuyAF3 目录 国产游戏技术能否引领全球&#xff1f; 一、国产游戏技术的崛起之路 1.1 初期探索与积…...

腾讯微众银行大数据面试题(包含数据分析/挖掘方向)面试题及参考答案

为什么喜欢使用 XGBoost,XGBoost 的主要优势有哪些? XGBoost 是一个优化的分布式梯度增强库,在数据科学和机器学习领域应用广泛,深受喜爱,原因主要在于其众多突出优势。 首先,它的精度高,在许多机器学习竞赛和实际应用中,XGBoost 都展现出卓越的预测准确性。其基于决策…...

【Linux】死锁、读写锁、自旋锁

文章目录 1. 死锁1.1 概念1.2 死锁形成的四个必要条件1.3 避免死锁 2. 读者写者问题与读写锁2.1 读者写者问题2.2 读写锁的使用2.3 读写策略 3. 自旋锁3.1 概念3.2 原理3.3 自旋锁的使用3.4 优点与缺点 1. 死锁 1.1 概念 死锁是指在⼀组进程中的各个进程均占有不会释放的资源…...

Spring Web开发(请求)获取JOSN对象| 获取数据(Header)

大家好&#xff0c;我叫小帅今天我们来继续Spring Boot的内容。 文章目录 1. 获取JSON对象2. 获取URL中参数PathVariable3.上传⽂件RequestPart3. 获取Cookie/Session3.1 获取和设置Cookie3.1.1传统获取Cookie3.1.2简洁获取Cookie 3. 2 获取和存储Session3.2.1获取Session&…...

用c语言完成俄罗斯方块小游戏

用c语言完成俄罗斯方块小游戏 这估计是你在编程学习过程中的第一个小游戏开发&#xff0c;怎么说呢&#xff0c;在这里只针对刚学程序设计的学生&#xff0c;就是说刚接触C语言没多久&#xff0c;有一点功底的学生看看&#xff0c;简陋的代码&#xff0c;简陋的实现&#xff0…...

SpringBoot整合Retry详细教程

问题背景 在现代的分布式系统中&#xff0c;服务间的调用往往需要处理各种网络异常、超时等问题。重试机制是一种常见的解决策略&#xff0c;它允许应用程序在网络故障或临时性错误后自动重新尝试失败的操作。Spring Boot 提供了灵活的方式来集成重试机制&#xff0c;这可以通过…...

JS API事件监听(绑定)

事件监听 语法 元素对象.addEventListener(事件监听,要执行的函数) 事件监听三要素 事件源&#xff1a;那个dom元素被事件触发了&#xff0c;要获取dom元素 事件类型&#xff1a;用说明方式触发&#xff0c;比如鼠标单击click、鼠标经过mouseover等 事件调用的函数&#x…...

ceph手动部署

ceph手动部署 一、 节点规划 主机名IP地址角色ceph01.example.com172.18.0.10/24mon、mgr、osd、mds、rgwceph02.example.com172.18.0.20/24mon、mgr、osd、mds、rgwceph03.example.com172.18.0.30/24mon、mgr、osd、mds、rgw 操作系统版本&#xff1a; Rocky Linux release …...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

LOOI机器人的技术实现解析:从手势识别到边缘检测

LOOI机器人作为一款创新的AI硬件产品&#xff0c;通过将智能手机转变为具有情感交互能力的桌面机器人&#xff0c;展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家&#xff0c;我将全面解析LOOI的技术实现架构&#xff0c;特别是其手势识别、物体识别和环境…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

Linux中《基础IO》详细介绍

目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改&#xff0c;实现简单cat命令 输出信息到显示器&#xff0c;你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...