LeetCode 算法:螺旋矩阵c++
原题链接🔗:螺旋矩阵
难度:中等⭐️⭐️
题目
给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。
示例 1:

输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]
示例 2:

输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]
提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 1
题解
四指针遍历法
- 题解:
这个算法不需要修改原始矩阵。以下是实现这个算法的步骤:
- 初始化四个边界:
top表示矩阵的顶部边界,bottom表示底部边界,left表示左侧边界,right表示右侧边界。- 创建一个空列表
result用于存储按螺旋顺序排列的元素。- 使用一个循环,直到
top大于bottom或left大于right:
- 从
left到right遍历top行,将这些元素添加到result。- 增加
top的值,缩小顶部边界。- 从
top到bottom遍历right列,将这些元素添加到result。- 减少
right的值,缩小右侧边界。- 如果
top小于等于bottom,从right到left遍历bottom行,将这些元素添加到result。- 减少
bottom的值,缩小底部边界。- 如果
left小于等于right,从bottom到top遍历left列,将这些元素添加到result。- 增加
left的值,缩小左侧边界。- 返回
result列表,它包含了矩阵中所有元素的顺时针螺旋顺序。
- 复杂度:时间复杂度O(m×n),因为每个单元格都被填充一次;空间复杂度O(m×n),用于存储最终的矩阵。
- 过程:
螺旋矩阵是一种特殊的矩阵,其元素按照螺旋的方式填充,从外圈向内圈逐渐填充,每个元素的值依次递增。
实现过程如下:
首先,函数检查输入矩阵是否为空或其子数组是否为空。如果是,则直接返回一个空的一维数组。
定义四个变量
top,bottom,left,right来分别表示矩阵的上边界、下边界、左边界和右边界。使用一个
while循环,当top不大于bottom且left不大于right时,循环继续。这确保了矩阵中至少还有一行或一列可以遍历。在循环内部,首先从
left到right遍历矩阵的顶部行,将这些元素添加到结果数组中,然后top加1。接着,从
top到bottom遍历矩阵的最右列,将这些元素添加到结果数组中,然后right减1。确保在继续之前,当前的遍历行与上一次的遍历行不同(如果
top小于等于bottom),从right到left遍历矩阵的底部行,然后bottom减1。同样,确保在继续之前,当前的遍历列与上一次的遍历列不同(如果
left小于等于right),从bottom到top遍历矩阵的最左列,然后left加1。函数最后返回包含矩阵所有元素的一维数组,这些元素按照螺旋顺序排列。
main函数中创建了3x3、3x4的两个矩阵,并调用spiralOrder函数来获取螺旋顺序的元素,然后打印这些元素。
- c++ demo:
#include <iostream>
#include <vector>std::vector<int> spiralOrder(const std::vector<std::vector<int>>& matrix) {if (matrix.empty() || matrix[0].empty()) return {};std::vector<int> result;int top = 0, bottom = matrix.size() - 1;int left = 0, right = matrix[0].size() - 1;while (top <= bottom && left <= right) {// Traverse from left to right.for (int i = left; i <= right; ++i) {result.push_back(matrix[top][i]);}++top;// Traverse downwards.for (int i = top; i <= bottom; ++i) {result.push_back(matrix[i][right]);}--right;// Make sure we are now on a different row.if (top <= bottom) {for (int i = right; i >= left; --i) {result.push_back(matrix[bottom][i]);}--bottom;}// Make sure we are now on a different column.if (left <= right) {for (int i = bottom; i >= top; --i) {result.push_back(matrix[i][left]);}++left;}}return result;
}int main() {std::vector<std::vector<int>> matrix = {{1, 2, 3},{4, 5, 6},{7, 8, 9}};std::vector<int> spiral = spiralOrder(matrix);for (int num : spiral) {std::cout << num << " ";}std::cout << std::endl;std::vector<std::vector<int>> matrix2 = {{1, 2, 3, 4 },{5, 6, 7, 8 },{9, 10, 11, 12}};std::vector<int> spiral2 = spiralOrder(matrix2);for (int num : spiral2) {std::cout << num << " ";}std::cout << std::endl;return 0;
}
- 输出结果:
1 2 3 6 9 8 7 4 5
1 2 3 4 8 12 11 10 9 5 6 7
相关文章:
LeetCode 算法:螺旋矩阵c++
原题链接🔗:螺旋矩阵 难度:中等⭐️⭐️ 题目 给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。 示例 1: 输入:matrix [[1,2,3],[4,5,6],[7,8,9]] 输出&…...
【全开源】医护上门系统小程序APP公众号h5源码
医护上门系统:健康守护,就在您身边 🚪引言:开启全新的医护模式 在快节奏的现代生活中,健康问题往往成为我们关注的焦点。而“医护上门系统”正是为了满足这一需求,将专业的医疗服务送到您的家中。这一创新…...
结构体<C语言>
导言 结构体是C语言中的一种自定义类型,它的值(成员变量)可以是多个,且这些值可以为不同类型,这也是和数组的主要区别,下面将介绍它的一些基本用法,包括:结构体的创建、结构体变量的…...
点云分割报告整理(未完成版-每天写一点)
体积占用网格表示对点进行体素化,然后使用3d卷积神经网络来学习体素级语义。由于点云的稀疏性,体素化效率低,为避免较高的计算成本而忽略了细节。此外,由于同一体素内的所有点都被赋予了相同的语义标签,因此精度受到限…...
python基础 002 - 1 基础语法
1 标识符(identifier),识别码,表明身份 身份证,ID 定义:在编程语言中标识符就是程序员自己规定的具有特定含义的词,比如类名称、属性名称、变量名等, 在Python 中,pyt…...
浅谈Web开发的三大主流框架:Angular、React和Vue.js
在现代Web开发领域,Angular、React和Vue.js作为三大主流前端框架,各自拥有独特的特点和优势,为开发者提供丰富的选择。让我们更深入地了解这三大框架,并通过一些小型样例来展示它们的特性。 Angular Angular是一个完整的前端框架…...
使用net.sf.mpxj读取project的.mpp文件
1、导入.mpp文件 public void importMppFile(String updateType, MultipartFile multipartFile) {try (InputStream inputStream multipartFile.getInputStream()) {// 读取文件的组件MPPReader mppReader new MPPReader();// 注意,如果在这一步出现了读取异常&a…...
ubuntu 22.04 升级到24.04
step1. sudo apt update sudo apt upgrade sudo apt dist-upgrade step2. sudo apt autoremove step3. sudo apt install update-manager-core step4. sudo vim /etc/update-manager/release-upgrades 将 Prompt 设置为 lts: Promptlts 保存并退出 step5. sudo do-r…...
FreeRTOS学习笔记-基于stm32(14)内存管理
一、FreeRTOS 内存管理简介 FreeRTOS有两种方法来创建任务,队列,信号量等,一种动态一种静态。静态方法需要手动定义任务堆栈。使用动态内存管理的时候 FreeRTOS 内核在创建任务、队列、信号量的时候会动态的申请 RAM。 我们在移植FreeRTOS时可…...
关于Lambert W函数
来源:R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth, “On Lambert’s W function,” Adv. Comput. Math., vol. 5, pp. 329–359, May 1996, doi: 10.1007/BF02124750. 摘要 Lambert W函数被定义为函数 w ↦ w e w w \mapsto we^…...
【免杀】C2远控-APC注入-进程镂空
目录 进程镂空&傀儡进程(主要过内存扫描)代码 傀儡进程演示如何上线上线演示 APC注入&进程欺骗(主要过内存扫描)同步调用与异步调用代码演示 进程镂空&傀儡进程(主要过内存扫描) 进程镂空(Pro…...
20240611 讯飞JAVA工程师(研发经理岗)面试
1.线程安全的集合类 在Java中,一些线程安全的集合类有Stack、Vector、Properties、Hashtable等 2.线程池中execute和submit的区别 1)参数及返回值不同 excute只能提交Runnable,无返回值 submit既可以提交Runnable,返回值为null&am…...
【研发日记】Matlab/Simulink软件优化(三)——利用NaNFlag为数据处理算法降阶
文章目录 前言 背景介绍 初始算法 优化算法 分析和应用 总结 前言 见《【研发日记】Matlab/Simulink软件优化(一)——动态内存负荷压缩》 见《【研发日记】Matlab/Simulink软件优化(二)——通信负载柔性均衡算法》 背景介绍 在一个嵌入式软件开发项目中,需要开…...
go语言接口之http.Handler接口
package httptype Handler interface {ServeHTTP(w ResponseWriter, r *Request) }func ListenAndServe(address string, h Handler) error ListenAndServe函数需要一个例如“localhost:8000”的服务器地址,和一个所有请求都可以分 派的Handler接口实例。它会一直运…...
R语言 | 使用最简单方法添加显著性ggpubr包
本期教程原文:使用最简单方法添加显著性ggsignif包 本期教程 获得本期教程代码和数据,在后台回复关键词:20240605 小杜的生信笔记,自2021年11月开始做的知识分享,主要内容是R语言绘图教程、转录组上游分析、转录组下游…...
【Linux】shell脚本变量——系统变量、环境变量和用户自定义变量
系统变量 系统变量是由系统预设的,它们通常在系统启动时被加载,并对所有用户和所有shell实例都有效。这些变量通常控制着系统的行为和配置,例如PATH(命令搜索路径)、HOME(用户主目录)等。系统变…...
QWidget 属性——windowTitle·windowIcon·qrc
🐌博主主页:🐌倔强的大蜗牛🐌 📚专栏分类:QT ❤️感谢大家点赞👍收藏⭐评论✍️ 文章目录 一、windowTitle二、windowIcon三、qrc 一、windowTitle windowTitle 是一个通常用于表示窗口标题…...
深入理解rtmp(一)之开发环境搭建
深入理解rtmp(一)之开发环境搭建 手机直播在15年的时候突然火起来,随着花椒,映客等出现,直播一下就出现在了风口,各个公司针对直播的战斗迅速打响,战斗过程比较短暂,随着许多公司的退出和死去,手机直播行业趋于稳定,直播服务时长也被传统的CDN厂商牢牢占据,后面大家又把精力投…...
java常用面试基础题
&与&&区别? &和&&都是逻辑运算符,都是判断两边同时真则为真,否则为假;但是&&当第一个条件不成之后,后面的条件都不执行了,而&则还是继续执行,直到整个条件…...
互联网摸鱼日报(2024-06-11)
互联网摸鱼日报(2024-06-11) 36氪新闻 雅诗兰黛,胆子也太大了 苹果WWDC终极前瞻:5大看点20大AI新功能,库克不能输的一战 瑞士清洁科技公司Enerdrape开发预制地热板,回收城市地下空间的浅层地热能和废热用于建筑物制热或制冷 | …...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
日常一水C
多态 言简意赅:就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过,当子类和父类的函数名相同时,会隐藏父类的同名函数转而调用子类的同名函数,如果要调用父类的同名函数,那么就需要对父类进行引用&#…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...
