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

题解

四指针遍历法

  1. 题解

这个算法不需要修改原始矩阵。以下是实现这个算法的步骤:

  1. 初始化四个边界:top 表示矩阵的顶部边界,bottom 表示底部边界,left 表示左侧边界,right 表示右侧边界。
  2. 创建一个空列表 result 用于存储按螺旋顺序排列的元素。
  3. 使用一个循环,直到 top 大于 bottomleft 大于 right
    • leftright 遍历 top 行,将这些元素添加到 result
    • 增加 top 的值,缩小顶部边界。
    • topbottom 遍历 right 列,将这些元素添加到 result
    • 减少 right 的值,缩小右侧边界。
    • 如果 top 小于等于 bottom,从 rightleft 遍历 bottom 行,将这些元素添加到 result
    • 减少 bottom 的值,缩小底部边界。
    • 如果 left 小于等于 right,从 bottomtop 遍历 left 列,将这些元素添加到 result
    • 增加 left 的值,缩小左侧边界。
  4. 返回 result 列表,它包含了矩阵中所有元素的顺时针螺旋顺序。
  1. 复杂度:时间复杂度O(m×n),因为每个单元格都被填充一次;空间复杂度O(m×n),用于存储最终的矩阵。
  2. 过程

螺旋矩阵是一种特殊的矩阵,其元素按照螺旋的方式填充,从外圈向内圈逐渐填充,每个元素的值依次递增。

实现过程如下:

  1. 首先,函数检查输入矩阵是否为空或其子数组是否为空。如果是,则直接返回一个空的一维数组。

  2. 定义四个变量top, bottom, left, right来分别表示矩阵的上边界、下边界、左边界和右边界。

  3. 使用一个while循环,当top不大于bottomleft不大于right时,循环继续。这确保了矩阵中至少还有一行或一列可以遍历。

  4. 在循环内部,首先从leftright遍历矩阵的顶部行,将这些元素添加到结果数组中,然后top加1。

  5. 接着,从topbottom遍历矩阵的最右列,将这些元素添加到结果数组中,然后right减1。

  6. 确保在继续之前,当前的遍历行与上一次的遍历行不同(如果top小于等于bottom),从rightleft遍历矩阵的底部行,然后bottom减1。

  7. 同样,确保在继续之前,当前的遍历列与上一次的遍历列不同(如果left小于等于right),从bottomtop遍历矩阵的最左列,然后left加1。

  8. 函数最后返回包含矩阵所有元素的一维数组,这些元素按照螺旋顺序排列。

main函数中创建了3x3、3x4的两个矩阵,并调用spiralOrder函数来获取螺旋顺序的元素,然后打印这些元素。

  1. 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
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/347209.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

调用华为API实现语音合成

目录 1.作者介绍2.华为云语音合成2.1 语音合成介绍2.2 华为语音合成服务2.3 应用场景 3. 实验过程以及结果3.1 获取API密钥3.2 调用语音合成算法API3.3 实验代码3.4 运行结果 1.作者介绍 袁斌&#xff0c;男&#xff0c;西安工程大学电子信息学院&#xff0c;2023级研究生 研究…

怎么解决常见的泄密途径问题,源代码防泄密的方法

在当今发展潮流中&#xff0c;网络信息安全隐患变得越来越突出&#xff0c;信息泄漏事件时有发生。我们都知道&#xff0c;电子文件非常容易复制&#xff0c;可以通过各种途径如邮件、光盘、U盘、网络存储等进行传播。企事业单位的机密文件、研发源代码、图纸等核心技术机密资料…

【数据结构初阶】 --- 单链表

关于链表你应该先了解这些 下图描述了物理模型和逻辑模型&#xff0c;大多数常见的其实是逻辑模型&#xff0c;但这对初学者或者掌握不扎实的同学不太友好&#xff0c;所以这里我重点讲解物理模型&#xff0c;当了解了这些细节&#xff0c;以后做题或是什么就直接画逻辑模型就…

经典文献阅读之--FlashOcc(快速且内存高效的占用预测模块)

Tip: 如果你在进行深度学习、自动驾驶、模型推理、微调或AI绘画出图等任务&#xff0c;并且需要GPU资源&#xff0c;可以考虑使用UCloud云计算旗下的Compshare的GPU算力云平台。他们提供高性价比的4090 GPU&#xff0c;按时收费每卡2.6元&#xff0c;月卡只需要1.7元每小时&…

基础IO(下)

基础IO 1. 磁盘1.1 磁盘的物理结构1.2 磁盘的逻辑抽象结构 2. 理解文件系统2.1 前言2.2 文件系统2.3 文件的新建和删除2.4 文件的查找2.5 理解软硬链接 3. 动态库和静态库3.1 生成静态库3.2 生成动态库3.3 动态库加载 实际上&#xff0c;大部分文件都不是被打开的&#xff08;当…

Catia装配体零件复制

先选中要复制的零件 然后选中复制到的父节点才可以。 否则 另外一种方法是多实例化

Jmeter07:函数

1 Jmeter组件&#xff1a;函数 1.1 是什么&#xff1f; 是程序中的封装单元&#xff08;最小的&#xff09;&#xff0c;封装一些功能实现 1.2 为什么&#xff1f; 优点1&#xff1a;易读 易维护 优点2&#xff1a;实现功能复用 1.3 怎么用&#xff1f; 流程&#xff1a; 1&…

Linux RS232

一、确认硬件信息 RS232&#xff1a; 引脚信息&#xff1a; 二、软件配置 1、pinctrl信息&#xff1a; 2、设备树节点&#xff1a; 3、修改串口支持的模式 三、驱动 bsp/drivers/uart/sunxi-uart.c 四、烧录测试 查看串口参数&#xff1a; stty -F /dev/ttyAS3 -a stty -F…

解锁ChatGPT:从原理探索到GPT-2的中文实践及性能优化

⭐️我叫忆_恒心&#xff0c;一名喜欢书写博客的研究生&#x1f468;‍&#x1f393;。 如果觉得本文能帮到您&#xff0c;麻烦点个赞&#x1f44d;呗&#xff01; 近期会不断在专栏里进行更新讲解博客~~~ 有什么问题的小伙伴 欢迎留言提问欧&#xff0c;喜欢的小伙伴给个三连支…

面向对象设计原则概述

面向对象设计原则概述 面向对象设计原则概述 面向对象设计原则概述单一职责原则开闭原则里氏代换原则依赖倒转原则接口隔离原则合成复用原则迪米特法则 内容来自《设计模式与艺术》一文。后续会陆续分享书中值得深思观点。 面向对象设计的目标之一在于支持可维护性复用&#xf…

Nginx配置详细解释:(5)rewrite重写功能

rewrite重写功能&#xff0c;在编译安装时需要有相应的模块&#xff0c;ngx_http_rewritte_module模块指令中&#xff0c;有if指令&#xff0c;return,set,break等指令。 1.ngx_http_rewrite_module模块指令 1.if指令 if指令在nginx配置中&#xff0c;用于条件判断&#xff…

Huggingface-cli 登录最新版(2024)

安装Huggingface-cli pip install -U "huggingface_hub[cli]"设置好git的邮箱和用户名和huggingface的github账号一致 git config --global user.mail xxx git config --global user.name xxx登录 复制token&#xff0c;划红线的地方&#xff0c;在命令行中点击右…

迷宫最短路径求解--c++

【代码】 #include<iostream> #include<queue> #include<stack> using namespace std; #define ROW 8 #define COL 8 //测试迷宫数据 int maze[ROW][COL] {{0,0,0,1,0,0,0,0},{0,1,0,1,0,1,0,1},{0,1,0,0,0,1,0,1},{0,1,0,1,1,1,0,1},{0,1,0,1,1,0,0,0},{0…

Fiddler抓包工具详细使用教程

各位做测试的同学想必对抓包工具fiddler并不陌生&#xff0c;但是很多同学可能没有总结过它的用法&#xff0c;下面我总结了fiddler一些常用的用法。 Web端抓包配置 打开Fiddler&#xff0c;Tools -> Fiddler Options -> HTTPS 配置完后记得要重启Fiddler 选中Decrpt …

34.打印K型

上海市计算机学会竞赛平台 | YACSYACS 是由上海市计算机学会于2019年发起的活动,旨在激发青少年对学习人工智能与算法设计的热情与兴趣,提升青少年科学素养,引导青少年投身创新发现和科研实践活动。https://www.iai.sh.cn/problem/76 题目描述 小爱想用 * 打出一个大写的 K。…

6.11 作业

以下是一个简单的比喻&#xff0c;将多态概念与生活中的实际情况相联系&#xff1a; 比喻&#xff1a;动物园的讲解员和动物表演 想象一下你去了一家动物园&#xff0c;看到了许多不同种类的动物&#xff0c;如狮子、大象、猴子等。现在&#xff0c;动物园里有一位讲解员&…

使用fvm切换flutter版本

切换flutter版本 下载fvm 1、dart pub global activate fvm dart下载fvm 2、warning中获取下载本地的地址 3、添加用户变量path&#xff1a; 下载地址 终端查看fvm版本 fvm --version 4、指定fvm文件缓存地址 fvm config --cache-path C:\src\fvm&#xff08;自定义地址&…

《精通ChatGPT:从入门到大师的Prompt指南》附录A:常用Prompt示例

附录A&#xff1a;常用Prompt示例 在《精通ChatGPT&#xff1a;从入门到大师的Prompt指南》的附录A中&#xff0c;我们将展示一系列常用的Prompt示例&#xff0c;帮助读者更好地理解和应用Prompt技术。每个示例将包含Prompt的描述、使用场景、预期结果以及实际输出。希望这些示…

调试环境搭建(Redis 6.X 版本)

今儿&#xff0c;我们来搭建一个 Redis 调试环境&#xff0c;目标是&#xff1a; 启动 Redis Server &#xff0c;成功断点调试 Server 的启动过程。使用 redis-cli 启动一个 Client 连接上 Server&#xff0c;并使用 get key 指令&#xff0c;发起一次 key 的读取。 视频可见…

公司面试题总结(二)

7. 说说 JavaScript 中的数据类型&#xff1f;存储上的差别&#xff1f; • 基本类型&#xff1a; o Number o String o Boolean o Undefined o null o symbol • 引用类型 o Object o Array o Function • 声明变量时不同的内存地址分配&#xff1a; o 简单类型的…