【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. …...
【设计模式】【创建型模式】建造者模式(Builder)
👋hi,我不是一名外包公司的员工,也不会偷吃茶水间的零食,我的梦想是能写高端CRUD 🔥 2025本人正在沉淀中… 博客更新速度 👍 欢迎点赞、收藏、关注,跟上我的更新节奏 🎵 当你的天空突…...
如何利用国内镜像从huggingface上下载项目
1、利用镜像快速下载项目 在huggingface上下载模型时速度太慢,可以用下面的方法 pip install -U huggingface_hub pip install huggingface-cliexport HF_ENDPOINThttps://hf-mirror.comhuggingface-cli download --resume-download shenzhi-wang/Llama3-8B-Chine…...
pandas常用操作
pandas是Python中用于数据操作和分析的强大库。以下是一些常用的操作: ### 1. 读取数据 - **从CSV文件读取**: python import pandas as pd df pd.read_csv(path/to/file.csv) - **从Excel文件读取**: python df pd.read_exc…...
linux使用
文章目录 前言操作系统的作用组成二、安装linux系统安装VMware Workstation安装ubuntu图形化,命令行finalshell快照目录理解命令执行命令格式常用命令lscdmkdir 前言 本文讲解认识与使用linux操作系统 操作系统的作用 操作系统是用户和计算机的桥梁。比如我们输入…...
基于豆瓣2025电影数据可视化分析系统的设计与实现
✔️本项目旨在通过对豆瓣电影数据进行综合分析与可视化展示,构建一个基于Python的大数据可视化系统。通过数据爬取收集、清洗、分析豆瓣电影数据,我们提供了一个全面的电影信息平台,为用户提供深入了解电影产业趋势、影片评价与演员表现的工…...
基于Python的深度学习音乐推荐系统(有配套论文)
音乐推荐系统 提供实时音乐推荐功能,根据用户行为和偏好动态调整推荐内容 Python、Django、深度学习、卷积神经网络 、算法 数据库:MySQL 系统包含角色:管理员、用户 管理员功能:用户管理、系统设置、音乐管理、音乐推荐管理、系…...
远程计算机无conda情况下配置python虚拟环境
1. 按照正常流程,根据远程计算机的IP地址/用户名/密码,通过pycharm进行部署 部署流程为: pycharm主菜单--> 工具-->部署 -->配置 **注意,pycharm的远程部署必须是专业版 2. 配置远程python解释器 上图是配置SSH解释器的截图&…...
强化学习-价值学习算法
Sarsa 理论解释 Sarsa是基于时序差分算法的,它的公式非常简单且易理解,不像策略梯度算法那样需要复杂的推导过程。 Sarsa的核心函数是 Q ( s , a ) Q(s, a) Q(s,a),它的含义是在状态 s s s下执行 a a a,在后续轨迹中获取的期望…...
Golang深度学习
前言 在2009年,Google公司发布了一种新的编程语言,名为Go(或称为Golang),旨在提高编程效率、简化并发编程,并提供强大的标准库支持。Go语言的设计者们希望通过Go语言能够解决软件开发中的一些长期存在的问…...
基于推荐算法的在线课程推荐系统设计与实现
开发语言:Java框架:springbootJDK版本:JDK1.8服务器:tomcat7数据库:mysql 5.7(一定要5.7版本)数据库工具:Navicat11开发软件:eclipse/myeclipse/ideaMaven包:…...
es和kibana安装
es安装 安装 wget https://artifacts.elastic.co/downloads/elasticsearch/elasticsearch-8.17.1-linux-x86_64.tar.gz 参考: https://www.cnblogs.com/shamo89/p/18504053 https://blog.csdn.net/u012899618/article/details/130383429 解压 tar -zxvf elastic…...
本地部署Anything LLM+Ollama+DeepSeek R1打造AI智能知识库教程
文章目录 前言1. 本地部署OllamaDeepSeek2. 本地安装Anything LLM3. 配置与使用演示4. 远程调用大模型5. 安装内网穿透6. 配置固定公网地址 前言 本文主要介绍如何在Windows电脑上本地部署Ollama并接入DeepSeek R1大模型,然后使用强大的开源AI工具Anything LLM结合…...
zyNo.25
SSRF漏洞 在了解ssrf漏洞前先了解curl命令的使用 1.curl命令的使用 基本格式:curl<参数值>请求地址 get请求:curl http://127.0.0.1 post请求:curl -X POST -d "a1&b2" http://127.0.0.1/(其中,使用-X参…...
Spring框架基本使用(Maven详解)
前言: 当我们创建项目的时候,第一步少不了搭建环境的相关准备工作。 那么如果想让我们的项目做起来方便快捷,应该引入更多的管理工具,帮我们管理。 Maven的出现帮我们大大解决了管理的难题!! Maven…...
关于前后端分离跨域问题——使用DeepSeek分析查错
我前端使用ant design vue pro框架,后端使用kratos框架开发。因为之前也解决过跨域问题,正常是在后端的http请求中加入中间件,设置跨域需要通过的字段即可,代码如下所示: func NewHTTPServer(c *conf.Server, s *conf…...
三层渗透测试-DMZ区域 二三层设备区域
DMZ区域渗透 信息收集 首先先进行信息收集,这里我们可以选择多种的信息收集方式,例如nmap如此之类的,我的建议是,可以通过自己现有的手里小工具,例如无影,密探这种工具,进行一个信息收集。以免…...
领航Linux UDP:构建高效网络新纪元
欢迎来到 破晓的历程的 博客 ⛺️不负时光,不负己✈️ 文章目录 引言Udp和Tcp的异同相同点不同点总结 1.1、socket1.2、bind1.3、recvfrom1.4、sendto2.1、代码2.1、说明3.1、代码3.2、说明 引言 在前几篇博客中,我们学习了Linux网络编程中的一些概念。…...
基于MATLAB的均匀面阵MUSIC算法DOA估计仿真
基于MATLAB的均匀面阵MUSIC算法DOA估计仿真 文章目录 前言一、二维MUSIC算法原理二、二维MUSIC算法MATLAB仿真三、MATLAB源代码总结 前言 \;\;\;\;\; 在波达角估计算法中,MUSIC 算法与ESPRIT算法属于特征结构子空间算法,是波达角估计算法中的基石。在前面…...
HTML/CSS中后代选择器
1.作用:选中指定元素中,符合要求的后代元素. 2.语法:选择器1 选择器2 选择器3 ...... 选择器n(使用空格隔开) 3.举例: /* 选中ul中的所有li */ul li{color: red;}/* 选中类名为subject元素中的所有li */.subject li{color: blue;}/* 选中类名为subject元素中的所有类名为f…...
网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分: 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...
