【LeetCode Hot100 矩阵】矩阵置零、螺旋矩阵、旋转图像、搜索二维矩阵II
矩阵
- 1. 矩阵置零(Set Matrix Zeroes)
- 解题思路
- 步骤:
- 代码实现
- 2. 螺旋矩阵(Spiral Matrix)
- 解题思路
- 具体步骤:
- 代码实现
- 3. 旋转矩阵 90 度
- 解决思路
- 代码实现
- 5. 搜索二维矩阵中的目标值
- 解决思路
- 代码实现
1. 矩阵置零(Set Matrix Zeroes)
给定一个 m x n
的矩阵 matrix
,如果一个元素是 0,则将其所在的整行和整列都设置为 0。你需要 原地 修改输入矩阵,不能 使用额外的矩阵。
解题思路
要实现原地修改矩阵,可以借助矩阵的第一行和第一列作为辅助存储,记录哪些行和列需要被置零。
步骤:
-
检查第一行和第一列是否包含零:
- 由于我们使用第一行和第一列来标记其他行列是否需要置零,所以需要先检查第一行和第一列是否包含零。如果包含零,我们分别用
rowFlag
和colFlag
进行标记。
- 由于我们使用第一行和第一列来标记其他行列是否需要置零,所以需要先检查第一行和第一列是否包含零。如果包含零,我们分别用
-
遍历矩阵:
- 从第二行第二列开始遍历整个矩阵。如果某个元素是零,则将其所在的第一行和第一列对应的元素设为零,表示该行和该列后续需要置零。
-
根据标记置零:
- 再次遍历矩阵,根据第一行和第一列的标记,将需要置零的位置修改为零。
-
处理第一行和第一列:
- 最后,根据
rowFlag
和colFlag
的值,单独处理第一行和第一列的置零问题。
- 最后,根据
代码实现
class Solution {public void setZeroes(int[][] matrix) {int n = matrix[0].length; // 列数int m = matrix.length; // 行数boolean colFlag = false, rowFlag = false;// 检查第一列是否包含零for (int i = 0; i < m; i++) {if (matrix[i][0] == 0) {colFlag = true;break;}}// 检查第一行是否包含零for (int j = 0; j < n; j++) {if (matrix[0][j] == 0) {rowFlag = true;break;}}// 遍历矩阵,使用第一行和第一列标记零的位置for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (matrix[i][j] == 0) {matrix[0][j] = 0; // 标记该列matrix[i][0] = 0; // 标记该行}}}// 根据第一行和第一列的标记进行置零for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (matrix[0][j] == 0 || matrix[i][0] == 0) {matrix[i][j] = 0;}}}// 处理第一列置零if (colFlag) {for (int i = 0; i < m; i++) {matrix[i][0] = 0;}}// 处理第一行置零if (rowFlag) {for (int j = 0; j < n; j++) {matrix[0][j] = 0;}}}
}
2. 螺旋矩阵(Spiral Matrix)
给定一个 m x n
的矩阵,按螺旋顺序返回矩阵中的所有元素。
解题思路
我们可以模拟螺旋遍历的过程,使用四个边界来控制当前遍历的范围。随着遍历的进行,逐步缩小这些边界,直到遍历完成整个矩阵。
具体步骤:
-
定义边界:
l
表示左边界,初始为 0。r
表示右边界,初始为m-1
。t
表示上边界,初始为 0。b
表示下边界,初始为n-1
。
-
遍历顺序:
- 按照螺旋顺序:从左到右遍历上边界,向下遍历右边界,从右到左遍历下边界,向上遍历左边界。
- 每次遍历完一条边后,更新相应的边界。
-
终止条件:
- 当结果列表的大小等于
m * n
时,遍历结束。
- 当结果列表的大小等于
代码实现
class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> list = new ArrayList<>();int m = matrix[0].length, n = matrix.length;int l = 0, r = m - 1, t = 0, b = n - 1;// 继续遍历直到所有元素都被加入列表while (list.size() < m * n) {// 从左到右遍历上边界for (int i = l; i <= r; i++) {if (list.size() == m * n) break;list.add(matrix[t][i]);}t++; // 缩小上边界的范围// 从上到下遍历右边界for (int i = t; i <= b; i++) {if (list.size() == m * n) break;list.add(matrix[i][r]);}r--; // 缩小右边界的范围// 从右到左遍历下边界for (int i = r; i >= l; i--) {if (list.size() == m * n) break;list.add(matrix[b][i]);}b--; // 缩小下边界的范围// 从下到上遍历左边界for (int i = b; i >= t; i--) {if (list.size() == m * n) break;list.add(matrix[i][l]);}l++; // 缩小左边界的范围}return list;}
}
3. 旋转矩阵 90 度
给定一个 n x n
的二维矩阵,编写一个函数将该矩阵顺时针旋转 90 度。你必须在原地(即不使用额外的二维数组)完成旋转。
解决思路
该问题可以通过两步操作实现:
- 水平翻转:将矩阵上下翻转。
- 对角线翻转:再将矩阵沿主对角线进行翻转。
通过这两步操作,我们可以原地完成矩阵的 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;}}}
}
5. 搜索二维矩阵中的目标值
给定一个 m x n
的矩阵 matrix
和一个目标值 target
,编写一个函数判断目标值是否在矩阵中。矩阵中的元素按照以下规则排序:
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
你需要在 O(m + n)
时间复杂度内完成这个搜索。
解决思路
由于矩阵的元素是按行升序、按列升序排列的,我们可以使用一种特殊的搜索方法:
-
从矩阵的右上角开始搜索:
- 如果当前元素等于目标值,直接返回
true
。 - 如果当前元素大于目标值,说明目标值可能在该元素的左边(向左移动一列)。
- 如果当前元素小于目标值,说明目标值可能在该元素的下方(向下移动一行)。
- 如果当前元素等于目标值,直接返回
-
这样,每次搜索都可以排除一行或一列,因此我们可以在
O(m + n)
时间复杂度内完成搜索。
代码实现
class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length, n = matrix[0].length;int x = 0, y = n - 1; // 从右上角开始搜索while (x < m && y >= 0) { // 当索引仍在矩阵范围内if (matrix[x][y] == target) {return true; // 找到目标值} else if (matrix[x][y] > target) {y--; // 当前值大于目标值,向左移动} else {x++; // 当前值小于目标值,向下移动}}return false; // 未找到目标值}
}
相关文章:
【LeetCode Hot100 矩阵】矩阵置零、螺旋矩阵、旋转图像、搜索二维矩阵II
矩阵 1. 矩阵置零(Set Matrix Zeroes)解题思路步骤: 代码实现 2. 螺旋矩阵(Spiral Matrix)解题思路具体步骤: 代码实现 3. 旋转矩阵 90 度解决思路代码实现 5. 搜索二维矩阵中的目标值解决思路代码实现 1. …...
最新版IDEA下载安装教程
一、下载IDEA 点击前往官网下载 或者去网盘下载 点击前往百度网盘下载 点击前往夸克网盘下载 进去后点击IDEA 然后点击Download 选择自己电脑对应的系统 点击下载 等待下载即可 二、安装IDEA 下载好后双击应用程序 点击下一步 选择好安装目录后点击下一步 勾选这两项后点击…...
Embedding模型
检索的方式有那些 关键字搜索:通过用户输入的关键字来查找文本数据。 语义搜索:它的目标是理解用户查询的真实意图,不仅考虑关键词的匹配,还考虑词汇之间的语义 (文字,语音,语调...࿰…...
WSL进阶使用指南
WSL2通过 Hyper-V 技术创建了一个轻量级的虚拟机(VM),在这个虚拟机之上可以运行一个真正的 Linux 内核,这给希望同时使用 Windows 和 Linux 的开发人员提供了无缝高效的体验。本文会介绍一些使用WSL的知识,帮助你更好地…...
JavaScript函数-函数的参数
在JavaScript编程语言中,函数是组织代码和实现复杂逻辑的基本单元。而函数参数则是这些功能的重要组成部分,它们允许我们将数据传递给函数,从而使得函数更加通用和灵活。本文将深入探讨JavaScript函数参数的各种特性及其最佳实践。 参数基础…...
【C语言】第五期——函数
目录 0 前言 1 定义函数 2 调用函数 3 函数的实参和形参 4 函数声明 5 作用域 5.1 局部变量和全局变量 5.2 static关键字 5.2.1 修饰局部变量 5.2.2 修饰全局变量 5.2.3 修饰函数 6 函数的返回值 6.1 return语句 6.2 函数返回值的类型 7 函数的其他形式 7.1 函…...
线结构光三维重建
利用线结构光和单目进行三维重构(测距)_线结构光三维重建-CSDN博客...
Spring Boot 应用(官网文档解读)
Spring Boot 启动方式 SpringApplication.run(MyApplication.class, args); Spring Boot 故障分析器 在Spring Boot 项目启动发生错误的时候,我们通常可以看到上面的内容,即 APPLICATION FAILED TO START,以及后面的错误描述。这个功能是通过…...
基于ffmpeg+openGL ES实现的视频编辑工具-添加转场(九)
在视频编辑的广阔领域中,转场效果无疑是提升视频流畅性与观赏性的关键要素。巧妙运用转场,能够让不同视频片段之间的衔接更为自然,同时赋予视频独特的创意魅力。本文将深入探讨如何借助 ffmpeg 和 openGL ES 技术,在视频编辑工具中实现丰富多样的转场效果。 一、转场技术原…...
库的制作与原理(一)
1.库的概念 库是写好的,现成的可以复用的代码。本质上库是一种可执行的二进制形式,可以被操作系统载入内存执行。库有俩种:静态库 .a[Linux] .lib[windows] 动态库 .so[Linux] .dll[windows] 就是把.c文件变成.o文件,把…...
Java List 自定义对象排序 Java 8 及以上版本使用 Stream API
从 Java 8 开始,你可以使用 Stream API 对 List 进行排序,这种方式更加简洁和灵活。 以下是一个示例代码: import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.stream.Collectors;// 自定…...
单元测试的策略有哪些,主要包括什么?
单元测试的策略及主要内容 单元测试(Unit Testing)是指对软件系统中的最小可测试单元(通常是一个函数、方法或类)进行验证,以确保其行为符合预期。常见的单元测试策略可以分为基于代码的策略和基于数据的策略…...
《深度剖析:AI与姿态估计技术在元宇宙VR交互中的应用困境》
在元宇宙的宏大版图里,虚拟现实(VR)交互是构建沉浸式体验的关键支柱,而人工智能(AI)与姿态估计技术的融合,本应成为提升交互体验的强大引擎。但在实际应用中,它们面临着诸多复杂且棘…...
基于YOLO11深度学习的糖尿病视网膜病变检测与诊断系统【python源码+Pyqt5界面+数据集+训练代码】
《------往期经典推荐------》 一、AI应用软件开发实战专栏【链接】 项目名称项目名称1.【人脸识别与管理系统开发】2.【车牌识别与自动收费管理系统开发】3.【手势识别系统开发】4.【人脸面部活体检测系统开发】5.【图片风格快速迁移软件开发】6.【人脸表表情识别系统】7.【…...
【QT 网络编程】HTTP协议(二)
文章目录 🌟1.概述🌟2.代码结构概览🌟3.代码解析🌸Http_Api_Manager - API管理类🌸Http_Request_Manager- HTTP请求管理类🌸ThreadPool - 线程池🌸TestWindow- 测试类 🌟4.运行效果&…...
mysql之规则优化器RBO
文章目录 MySQL 基于规则的优化 (RBO):RBO 的核心思想:模式匹配与规则应用RBO 的主要优化规则查询重写 (Query Rewrite) / 查询转换 (Query Transformation)子查询优化 (Subquery Optimization) - RBO 的重中之重非相关子查询 (Non-Correlated Subquery)…...
Python天梯赛10分题-念数字、求整数段和、比较大小、计算阶乘和
007-念数字 输入一个整数,输出每个数字对应的拼音。当整数为负数时,先输出fu字。十个数字对应的拼音如下: 0: ling 1: yi 2: er 3: san 4: si 5: wu 6: liu 7: qi 8: ba 9: jiu输入格式: 输入在一行中给出一个整数,如&…...
如何进行文档类图像的校正?
可以使用OpenCV实现的图像校正算法,包含透视校正和旋转校正的步骤,并附有详细注释。 具体如下: import cv2 import numpy as npdef order_points(pts):"""将四个点按左上、右上、右下、左下顺序排列"""rect …...
GPIO外设
一、GPIO简介 GPIO,general-purpos IO port,通用输入输出引脚,所有的GPIO引脚都有基本的输入输出功能。 最基本的输出功能:STM32控制引脚输出高、低电平,实现开关控制;最基本的输入功能:检测外部输入电平&…...
DeepSeek-R1之二_基于Open-WebUI的AI托管平台之Pyenv-win安装与配置搭建本地AI知识库
DeepSeek-R1之二_基于Open-WebUI的AI托管平台之Pyenv-win安装与配置搭建本地AI知识库 文章目录 DeepSeek-R1之二_基于Open-WebUI的AI托管平台之Pyenv-win安装与配置搭建本地AI知识库1. 官网及前提条件1. 官网2. 前提条件1. 安装了Ollama2. 通过Ollama下载与管理了DeepSeek-R1模…...
My Metronome for Mac v1.4.2 我的节拍器 支持M、Intel芯片
应用介绍 My Metronome 是一款适用于 macOS 的专业节拍器应用程序,旨在帮助音乐家、作曲家、学生和任何需要精确节奏控制的人进行练习。无论是进行乐器练习、音乐创作还是演出排练,My Metronome 都能为用户提供精准的节拍支持和灵活的功能,确…...
Windows系统本地部署DeepSeek-R1+本地知识库+联网搜索+Agent功能
本文记录了Windows11 Ollama AnythingLLM,3步快速本地部署DeepSeek-R1模型,支持联网搜索、应用本地知识库和创建Agent功能。 前言 DeepSeek-R1 知识库相关 更新时间:截至 2025年2月,当前版本的 R1 基于 2024年7月之前的数据训…...
RT-Thread+STM32L475VET6——TF 卡文件系统
文章目录 前言一、板载资源二、具体步骤1.打开CubeMX进行USB配置1.1 使用外部高速时钟,并修改时钟树1.2 打开SPI1,参数默认即可(SPI根据自己需求调整)1.3 打开串口,参数默认1.4 生成工程 2.配置SPI2.1 打开SPI驱动2.2 声明使用SPI…...
Jmeter进阶篇(34)如何解决jmeter.save.saveservice.timestamp_format=ms报错?
问题描述 今天使用Jmeter完成压测执行,然后使用命令将jtl文件转换成html报告时,遇到了报错! 大致就是说jmeter里定义了一个jmeter.save.saveservice.timestamp_format=ms的时间格式,但是jtl文件中的时间格式不是标准的这个ms格式,导致无法正常解析。对于这个问题,有如下…...
Javascript使用Sodium库实现 aead_xchacha20poly1305_ietf加密解密,以及与后端的密文交互
Node.js环境安装 sodium-native (其他库可能会出现加密解密失败,如果要使用不一样的库,请自行验证) npm install sodium-native 示例代码,使用的是 sodium-native v4.3.2 (其他版本可能会有变化,如果要使用,请自行验…...
机器学习实战(8):降维技术——主成分分析(PCA)
第8集:降维技术——主成分分析(PCA) 在机器学习中,降维(Dimensionality Reduction) 是一种重要的数据处理技术,用于减少特征维度、去除噪声并提高模型效率。主成分分析(Principal C…...
0099__Visual Studio 引入外部静态库与动态库
Visual Studio 引入外部静态库与动态库_visual studio 添加库-CSDN博客...
eclips 快捷键
eclips 快捷键 类别快捷键功能描述通用Ctrl S保存当前文件Ctrl Shift S保存所有文件Ctrl Z撤销操作Ctrl Y重做操作Ctrl X剪切Ctrl C复制Ctrl V粘贴Ctrl A全选Ctrl F查找Ctrl H打开搜索对话框Ctrl /注释/取消注释当前行或选中的代码块Ctrl Shift /添加块注释Ctrl …...
VSCode ssh远程连接内网服务器(不能上网的内网环境的Linux服务器)的终极解决方案
VSCode ssh远程连接内网服务器(不能上网的内网环境的Linux服务器) 离线下载vscode-server并安装: 如果远程端不能联网可以下载包离线安装,下载 vscode-server 的 url 需要和 vscode 客户端版本的 commit-id 对应.通过 vscode 面板的帮助->关于可以获…...
【Gin-Web】Bluebell社区项目梳理3:社区相关接口开发
本文目录 一、接口详情1. 获取分类社区列表接口2. 根据id查询社区 二、值类型与引用类型 一、接口详情 跟社区有关的接口详情如下。 1. 获取分类社区列表接口 首先是Controller层,然后跳转到Logic层业务逻辑的开发。 这是Logic层,再做一次跳转&#…...
鸟语林-论坛系统自动化测试
文章目录 一、自动化实施步骤1.1编写Web测试用例1.2 编写自动化代码1.2.1 LoginPageTest1) 能否正确打开登录页面2) 点击去注册能否跳转注册页面3) 模拟用户登录,输入多组登录测试用例 1.2.2 RegisterPageTest1) 能否成功打开注册页面2) 注册测试用例3) 点击去登录按…...
图解循环神经网络(RNN)
目录 1.循环神经网络介绍 2.网络结构 3.结构分类 4.模型工作原理 5.模型工作示例 6.总结 1.循环神经网络介绍 RNN(Recurrent Neural Network,循环神经网络)是一种专门用于处理序列数据的神经网络结构。与传统的神经网络不同,…...
c语言左值和右值的区别
在C语言中,左值(lvalue)和右值(rvalue)是互斥的概念,左值不能是右值。以下是详细的解释和总结: 1. 左值(lvalue) 定义:左值是一个表达式,表示一个…...
Scrapy:Downloader下载器设计详解
Scrapy下载器设计详解 1. 整体架构 Scrapy的下载器(Downloader)是整个爬虫框架的核心组件之一,负责处理所有网络请求的下载工作。它的主要职责是: 管理并发请求实现请求调度处理下载延迟维护下载槽(Slot) 官方文档:Settings中的Downloader配…...
细说STM32F407单片机2个ADC使用DMA同步采集各自的1个输入通道的方法
目录 一、示例说明 二、工程配置 1、RCC、DEBUG、CodeGenerator 2、USART6 3、TIM3 (1)Mode (2)参数设置 (3) TRGO (4)ADC1_IN0 1)ADCs_Common_Settings 2&a…...
【分治法】线性时间选择问题
问题描述 给定线性序列中n个元素和一个整数k,1≤k≤n,要求在线性时间中找出这n个元素中第k小的元素 常规思路 常规思路是对序列先排序,落在第k个位置的元素就是第k小的元素。 这种方法的时间复杂度不是线性的,是O(nlogn)的时间…...
redis中的Lua脚本,redis的事务机制
lua脚本的特点 lua脚本可以操作redis数据库,并且脚本中的代码满足原子性,要么全部被执行,要么全部不执行 lua脚本的语法 脚本示例 lua脚本的草稿: 最终的lua脚本 lua脚本在java里调用的方法 RedisTemplete类里有一个方法&…...
ASUS/华硕 ROG Strix GL503VM 原厂Win10系统 工厂文件 带ASUS Recovery恢复
华硕工厂文件恢复系统 ,安装结束后带隐藏分区,带一键恢复,以及机器所有的驱动和软件。 支持型号:GL503VM 系统版本:Windows 10 文件下载:点击下载 文件格式:工厂文件 安装教程:…...
Oracle 深入理解Lock和Latch ,解析访问数据块全流程
Oracle 锁机制介绍 根据保护对象的不同,单实例Oracle数据库锁可以分为以下几大类: DML lock(data locks,数据锁):用于保护数据的完整性; DDL lock(dictionary locks,字典…...
Django Admin: 动态合并数据库和预定义选项的高级过滤器实现
在 Django 管理界面中,我们经常需要为某些字段提供过滤选项。通常情况下,这些选项要么是预定义的,要么是从数据库中动态获取的。但是,有时我们需要更灵活的解决方案:当数据库为空时使用预定义选项,而当数据库有数据时,则合并预定义选项和数据库中的值。本文将详细介绍如…...
Linux文件系统
理解硬件 磁盘、服务器、机柜、机房 机械磁盘是计算机中唯一的一个机械设备 磁盘--- 外设,慢,容量大,价格便宜 磁盘物理结构 扇区是从磁盘读出和写入信息的最小单位,通常大小为 512 字节。磁头(head)数&a…...
C++标准库——时间
文章目录 chrono库durationtime_pointclocks C 风格日期和时间库参考 C 支持两种类型的时间操作: Chrono库,在chrono头文件中提供C 风格日期和时间库,std::time这种,在ctime头文件中提供 chrono库 在<chrono>中࿰…...
AutoGen 技术博客系列 八:深入剖析 Swarm—— 智能体协作的新范式
本系列博文在掘金同步发布, 更多优质文章,请关注本人掘金账号: 人肉推土机的掘金账号 AutoGen系列一:基础介绍与入门教程 AutoGen系列二:深入自定义智能体 AutoGen系列三:内置智能体的应用与实战 AutoGen系列四&am…...
【系统架构设计师】操作系统的分类
目录 1. 说明2. 批处理操作系统3. 分时操作系统4. 实时操作系统5. 网络操作系统6. 分布式操作系统7. 微型计算机操作系统8.嵌入式操作系统9.例题9.1 例题1 1. 说明 1.通常,操作系统可分为批处理操作系统、分时操作系统、实时操作系统、网络操作系统、分布式操作系统…...
25林业研究生复试面试问题汇总 林业专业知识问题很全! 林业复试全流程攻略 林业考研复试真题汇总
25 林业考研复试,专业面试咋准备?学姐来支招! 宝子们,一提到林业考研复试面试,是不是就慌得不行,感觉老师会扔出一堆超难的问题?别怕别怕,其实林业考研复试就那么些套路,…...
基于SSM的《计算机网络》题库管理系统(源码+lw+部署文档+讲解),源码可白嫖!
摘 要 《计算机网络》题库管理系统是一种新颖的考试管理模式,因为系统是用Java技术进行开发。系统分为三个用户进行登录并操作,分别是管理员、教师和学生。教师在系统后台新增试题和试卷,学生进行在线考试,还能对考生记录、错题…...
常用高压缩率的视频容器格式,并进行大比例压缩
常用的高压缩率视频容器格式,包括*.mp4 、*.mkv、*.webM等。 容器格式本身并不直接决定压缩率,而是取决于容器中所使用的视频编码格式等因素。不过,在常见的视频容器格式中,一些容器在搭配特定编码格式时,通常能表现出较高的压缩效率,以下是相关介绍: 1 MKV格式 …...
请说明C#中的List是如何扩容的?
在 C# 中,List<T>是一个动态数组,它会根据需要自动调整其容量以容纳更多的元素。 目录 1 扩容条件与扩容算法规则 2 总结 1 扩容条件与扩容算法规则 当你创建一个新的List<T>实例时,如果没有指定初始容量,它会使…...
《微软量子芯片:开启量子计算新纪元》:此文为AI自动生成
量子计算的神秘面纱 在科技飞速发展的今天,量子计算作为前沿领域,正逐渐走进大众的视野。它宛如一把神秘的钥匙,有望开启未来科技变革的大门,而微软量子芯片则是这把钥匙上一颗璀璨的明珠。 量子计算,简单来说,是一种遵循量子力学规律调控量子信息单元进行计算的新型计算…...
使用AI创建流程图和图表的 3 种简单方法
你可能已经尝试过使用 LLMs 生成图像,但你有没有想过用它们来创建 流程图和图表?这些可视化工具对于展示流程、工作流和系统架构至关重要。 通常,在在线工具上手动绘制图表可能会耗费大量时间。但你知道吗?你可以使用 LLMs 通过简…...