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

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

comfyui 工作流中 图生视频 如何增加视频的长度到5秒

comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗&#xff1f; 在ComfyUI中实现图生视频并延长到5秒&#xff0c;需要结合多个扩展和技巧。以下是完整解决方案&#xff1a; 核心工作流配置&#xff08;24fps下5秒120帧&#xff09; #mermaid-svg-yP…...