当前位置: 首页 > news >正文

力扣第五十四题——螺旋矩阵

内容介绍

给你一个 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] <= 100

完整代码

 int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {if (matrixSize == 0 || matrixColSize[0] == 0) {*returnSize = 0;return NULL;}int rows = matrixSize, columns = matrixColSize[0];int visited[rows][columns];memset(visited, 0, sizeof(visited));int total = rows * columns;int* order = malloc(sizeof(int) * total);*returnSize = total;int row = 0, column = 0;int directionIndex = 0;for (int i = 0; i < total; i++) {order[i] = matrix[row][column];visited[row][column] = true;int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {directionIndex = (directionIndex + 1) % 4;}row += directions[directionIndex][0];column += directions[directionIndex][1];}return order;
}

思路详解

一、问题背景

给定一个二维数组,要求按照螺旋顺序遍历数组,并返回一个一维数组,其中包含按螺旋顺序遍历得到的元素。

二、解题思路

  1. 边界处理

    • 首先检查数组是否为空,如果为空,则直接返回空数组。
  2. 初始化

    • 创建一个二维数组visited,用于标记数组中已经遍历过的元素。
    • 初始化数组的大小为行数乘以列数。
    • 创建一个一维数组order,用于存储按螺旋顺序遍历得到的元素。
  3. 遍历策略

    • 定义一个方向数组directions,包含四个方向:上、右、下、左。
    • 初始化起点rowcolumn,以及方向索引directionIndex
    • 遍历数组,按照螺旋顺序填充order数组。
    • 在遍历过程中,如果下一个位置越界或者已经遍历过,则改变方向。
  4. 结果返回

    • 遍历完成后,返回order数组。

三、代码详解

  1. 边界处理
    • 如果数组为空,直接返回空数组。
if (matrixSize == 0 || matrixColSize[0] == 0) {*returnSize = 0;return NULL;
}
  1. 初始化
    • 创建visited数组并初始化为0。
    • 创建order数组并分配内存。
    • 初始化rowscolumnstotaldirectionIndex
int rows = matrixSize, columns = matrixColSize[0];
int visited[rows][columns];
memset(visited, 0, sizeof(visited));
int total = rows * columns;
int* order = malloc(sizeof(int) * total);
*returnSize = total;
  1. 遍历策略
    • 初始化起点rowcolumn,以及方向索引directionIndex
    • 遍历数组,按照螺旋顺序填充order数组。
    • 在遍历过程中,如果下一个位置越界或者已经遍历过,则改变方向。
int row = 0, column = 0;
int directionIndex = 0;
for (int i = 0; i < total; i++) {order[i] = matrix[row][column];visited[row][column] = true;int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {directionIndex = (directionIndex + 1) % 4;}row += directions[directionIndex][0];column += directions[directionIndex][1];
}
  1. 结果返回
    • 遍历完成后,返回order数组。
return order;

四、总结

通过上述步骤,我们能够有效地遍历二维数组并按照螺旋顺序返回一维数组。关键在于正确地初始化数组、遍历策略和结果返回。这种方法的时间复杂度为O(n),其中n为数组的大小。空间复杂度为O(n),用于存储一维数组和二维数组。

知识点精炼

一、核心概念

  1. 边界条件检查:在开始遍历之前,检查输入的二维数组是否为空。
  2. 二维数组访问:使用两个索引变量来访问二维数组中的元素。
  3. 动态数组分配:在内存中动态分配一维数组来存储遍历结果。
  4. 方向数组:使用一个二维数组来表示遍历的方向。

二、知识点精炼

  1. 初始化

    • 创建一个二维数组visited来标记数组中已经遍历过的元素。
    • 创建一个一维数组order来存储按螺旋顺序遍历得到的元素。
  2. 遍历策略

    • 初始化起点rowcolumn,以及方向索引directionIndex
    • 遍历数组,按照螺旋顺序填充order数组。
    • 在遍历过程中,如果下一个位置越界或者已经遍历过,则改变方向。
  3. 结果返回

    • 遍历完成后,返回order数组。

三、性能分析

  • 时间复杂度:O(n),其中n为数组的大小。
  • 空间复杂度:O(n),用于存储一维数组和二维数组。

四、实际应用

  • 数据处理:在处理二维数据时,这种算法可以帮助我们按照特定顺序访问数据。
  • 算法竞赛:在算法竞赛中,掌握这种算法对于解决与二维数组遍历相关的问题非常有帮助。

五、代码实现要点

  • 边界条件检查:确保输入的二维数组不为空。
  • 动态数组分配:正确分配内存空间,避免内存泄漏。
  • 遍历策略:正确实现螺旋遍历策略,避免数组越界和重复访问。
  • 结果返回:正确返回遍历结果。

 减少空间复杂度的思路

在原始代码中,我们使用了一个二维数组visited来标记已经遍历过的元素,这导致了较高的空间复杂度。为了减少空间复杂度,我们可以使用一个一维数组来替代二维数组,这样可以将空间复杂度从O(n)降低到O(1)。

以下是优化后的代码:

int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {if (matrixSize == 0 || matrixColSize[0] == 0) {*returnSize = 0;return NULL;}int rows = matrixSize, columns = matrixColSize[0];int* order = malloc(sizeof(int) * (rows * columns));*returnSize = rows * columns;int top = 0, bottom = rows - 1, left = 0, right = columns - 1;int index = 0;while (top <= bottom && left <= right) {// Traverse the top rowfor (int i = left; i <= right; i++) {order[index++] = matrix[top][i];}top++;// Traverse the rightmost columnfor (int i = top; i <= bottom; i++) {order[index++] = matrix[i][right];}right--;// If there is still a row leftif (top <= bottom) {// Traverse the bottom rowfor (int i = right; i >= left; i--) {order[index++] = matrix[bottom][i];}bottom--;}// If there is still a column leftif (left <= right) {// Traverse the leftmost columnfor (int i = bottom; i >= top; i--) {order[index++] = matrix[i][left];}left++;}}return order;
}

在这个优化版本中,我们使用了一个一维数组order来存储遍历结果,而不是使用一个二维数组visited来标记已经遍历过的元素。我们通过维护四个边界变量(topbottomleftright)来控制遍历的方向,并在每次迭代中只遍历尚未访问的部分。这种方法避免了使用额外的空间来存储已访问的元素,从而将空间复杂度降低到O(1)。

 

相关文章:

力扣第五十四题——螺旋矩阵

内容介绍 给你一个 m 行 n 列的矩阵 matrix &#xff0c;请按照 顺时针螺旋顺序 &#xff0c;返回矩阵中的所有元素。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,2,3],[4,5,6],[7,8,9]] 输出&#xff1a;[1,2,3,6,9,8,7,4,5]示例 2&#xff1a; 输入&#xff1a;matrix …...

中创算力:以知识产权转化运用促进高质量发展

创新是引领发展的第一动力&#xff0c;保护知识产权就是保护创新。为深入实施知识产权公共服务普惠工程&#xff0c;促进知识产权公共服务更好服务高水平科技&#xff0c;国家知识产权局发布关于全面提升知识产权公共服务效能的指导意见。 在政策落地过程中&#xff0c;如何精…...

C语言9~10 DAY(合集)

数组的概念 什么是数组 数组是相同类型&#xff0c;有序数据的集合。 数组的特征 数组中的数据被称为数组的元素&#xff0c;是同构的 数组中的元素存放在内存空间里 (char player_name[6]&#xff1a;申请在内存中开辟6块连续的基于char类型的变量空间) 衍生概念&#x…...

【Kubernetes】应用的部署(一):金丝雀部署

应用的部署&#xff08;一&#xff09;&#xff1a;金丝雀部署 在项目迭代开发过程中&#xff0c;经常需要对应用进行上线部署。上线部署策略主要有 3 种&#xff1a;金丝雀部署、蓝绿部署 和 滚动部署。 金丝雀部署 也被叫作 灰度部署。金丝雀部署过程&#xff1a;先让一部分…...

1.面试准备篇

筛选简历 找实习用处不大 简历注意事项 注意职业技能和项目经历 职业技能 黄金位置 针对性 引导面试官提问 只写会的 不会的不能写 项目描述 主要设计… 展示指标 找练手项目 来源&#xff1a;Gitee 或者github 主要关注点:功能实现、常见问题、系统设计 面试过程 一面…...

Spring: try-catch 是否还会回滚

问题出现&#xff1a; try-catch 语句 依旧会抛出如下错误 org.springframework.transaction.TransactionSystemException: Could not commit JPA transaction; nested exception is javax.persistence.RollbackException: Transaction marked as rollbackOnlyat org.springf…...

spdlog日志库--基础介绍

文章目录 1. 简介1.1. spdlog代码特点1.2. 说明1.3. spdlog架构 2. spdlog的安装2.1. 使用包管理器安装2.2. 使用源码安装2.3. 仅使用头文件 3. 相关概念3.0 常用的头文件3.1. level_enum3.2. sink3.3. logger3.4 格式输出3.5 对齐方式3.6 截断3.7 字符串格式化fmt 4. 特性4.1.…...

【网络】网络编程套接字(二)

网络编程套接字&#xff08;二&#xff09; 文章目录 1.单执行流的TCP网络程序1.1服务端创建套接字1.2服务端绑定1.3服务端监听1.4服务端获取链接1.5服务端处理请求1.6客户端创建套接字1.7客户端连接服务器1.8客户端发起请求 2.多进程版的TCP网络程序2.1单执行流的弊端2.2多进…...

1.1、centos stream 9安装Kubernetes v1.30集群 环境说明

最近正在学习kubernetes&#xff0c;买了一套《Kubernetes权威指南 从Docker到Kubernetes实践全接触(第六版)》这本书讲得很好&#xff0c;上下两册&#xff0c;书中k8s的版本是V1.29&#xff0c;目前官网最新版本是v1.30。强烈建议大家买一套看看。 Kubernetes官网地址&#x…...

Redis3

目录 什么是缓存穿透&#xff1f;怎么解决&#xff1f; 什么是缓存雪崩&#xff1f;怎么解决&#xff1f; 如何保证数据库和缓存的数据一致性&#xff1f; 如何保证Redis服务高可用&#xff1f; 哨兵的作用 Redis虚拟槽分区有什么优点&#xff1f; 为什么Redis集群最大槽…...

Oracle数据巡检 - 设计巡检模板

设计巡检模板 明确巡检数据库等信息 包括数据库种类、版本、架构、数量等&#xff0c;例如 Oracle DG和Oracle RAC数据库巡检项肯定会有差异&#xff0c;Oracle 11g和12c版本巡检内容也会有所不同。 明确巡检项 这一块需要结合自身的运维经验&#xff0c;列出详尽的巡检项&…...

优盘未格式化数据恢复实战指南

在数字时代&#xff0c;优盘&#xff08;USB闪存驱动器&#xff09;作为便携存储媒介&#xff0c;承载着无数重要的文件与数据。然而&#xff0c;当您插入优盘准备访问资料时&#xff0c;却遭遇了“驱动器未被格式化”的提示&#xff0c;这无疑是一场突如其来的数据危机。本文将…...

【python基础】python基础习题练习(一)

文章目录 一. python语言简介二. python基本语法与常用函数三. python基本数据类型一.选择题二.编程题四. python组合数据类型一.选择题二.简答题三.编程题一. python语言简介 查看python是否安装成功的命令是:python -vPython IDE有:pyCharm、Spyder、Jupter NotebookPython…...

GESP 4级样题 ---> 绝对素数

这题需要判断一个数和它的反转后的数是否都为素数。 可以转成 string 后 reverse 一下。 AC CODE&#xff1a; #include <bits/stdc.h> using namespace std; typedef long long LL; bool isPrime(int x){if(x<2) return false;for(int i2;i*i<x;i){if(x%i0) re…...

大语言模型系列 - Transformer

1. 简介 1.1. 概述 大语言模型Transformer是一种由谷歌公司提出的基于注意力机制的神经网络模型,它在自然语言处理(NLP)领域取得了显著成就,并逐渐被应用于其他领域如语音识别、计算机视觉和强化学习等。 1.2. 学习资源 以下是一些学习大语言模型Transformer的资源地址…...

Java面试之操作系统

1、冯诺依曼模型 运算器、控制器、存储器、输入设备、输出设备 32位和64位CPU最主要区别是一次性能计算多少字节数据&#xff0c;如果计算的数额不超过 32 位数字的情况下&#xff0c;32 位和 64 位 CPU 之间没什么区别的&#xff0c;只有当计算超过 32 位数字的情况下&#…...

springboot船舶维保管理系统--论文源码调试讲解

第二章 相关技术 本次开发船舶维保管理系统使用的是Vue进行程序开发&#xff0c;船舶维保管理系统的数据信息选择MySQL数据库进行存放。 2.1 VUE介绍 Vue (读音 /vjuː/&#xff0c;类似于 view) 是一套用于构建用户界面的渐进式框架。与其它大型框架不同的是&#xff0c;Vue…...

【机器学习西瓜书学习笔记——神经网络】

机器学习西瓜书学习笔记【第五章】 第五章 神经网络5.1神经元模型5.2 感知机与多层网络学习感知机学习率成本/损失函数梯度下降 5.3 BP神经网络&#xff08;误差逆传播&#xff09;5.4 全局最小与局部极小5.5 其他常见神经网络RBF网络RBF 与 BP 最重要的区别 ART网络 第五章 神…...

安装 electron 报错解决

1. 报错 大概率由镜像问题导致 2. 解决 2.1 打开 npm 配置 npm config edit 2.2 添加配置 registryhttps://registry.npmmirror.comelectron_mirrorhttps://cdn.npmmirror.com/binaries/electron/electron_builder_binaries_mirrorhttps://npmmirror.com/mirrors/electron…...

【Material-UI】Icon Button 组件详解

文章目录 一、基础用法1. 禁用状态 二、大小&#xff08;Sizes&#xff09;1. 小尺寸&#xff08;Small&#xff09;2. 大尺寸&#xff08;Large&#xff09; 三、颜色&#xff08;Colors&#xff09;1. 主题颜色2. 自定义颜色 四、高级用法和最佳实践1. 无障碍性&#xff08;A…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...