leetcode之hot100---54螺旋矩阵(C++)

思路一:模拟

模拟螺旋矩阵的路径,路径超出界限,顺时针旋转,使用一个数组记录当前数字是否被访问到,直到所有的数字全部被访问

class Solution {
    //一个静态的常量数组,用于标记螺旋矩阵的移动方向(行列变化)
    //{0, 1}:表示向右移动一格(x 不变,y+1)。
    //{1, 0}:表示向下移动一格(x+1,y 不变)。
    //{0, -1}:表示向左移动一格(x 不变,y-1)。
    //{-1, 0}:表示向上移动一格(x-1,y 不变)
    static constexpr int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        //判断矩阵行列是否为空,如果为空则返回空值
        if(matrix.size() == 0 || matrix[0].size() == 0){
            return {};
        }
        vector<int> ans;
        int m = matrix.size();//行最大
        int n = matrix[0].size();//列最大
        
        
        //数字是否已经被访问的标签数组
        vector<vector<bool>> visited(m, vector<bool>(n,false));
        //记录存入答案数组中的个数
        int col = 0, row = 0;//螺旋矩阵的起始路径
        //当前方向的索引,可以取0-3,分别对应directions数组中的四个方位
        int direction_index = 0;
        for(int count = 0; count < m * n; count++){
            ans.push_back(matrix[row][col]);//将矩阵中的数字存入结果中
            visited[row][col] = true;//标记已访问的数字
            //计算下一位置
            //行变化列不动,取directions数组中的x坐标
            //列变化行不动,取directions数组中的y坐标
            int next_row = row + directions[direction_index][0];
            int next_col = col + directions[direction_index][1];
            // 判断是否需要改变移动方向(越界或已访问)
            if(next_row < 0 || next_row >= m || next_col < 0 || next_col >= n || visited[next_row][next_col]){
                direction_index = (direction_index + 1) % 4;
            }
            //根据判断的方向进行移动
            row += directions[direction_index][0];
            col += directions[direction_index][1];
        }
        return ans;
    }
};

constexpr的使用是告诉大家该数组为一个常量表达式,在编译的过程中其值不会改变

这个方法的关键在于写出这个方向数组,我们平时做的题目中如果涉及到处理二维网格上的移动问题,例如:遍历上下左右四个方向执行 BFS/DFS 等搜索算法模拟迷宫、棋盘等问题中的移动逻辑,都可以使用这个方向数组

  • 时间复杂度:O(mn)

  • 空间复杂度:O(mn)

思路二:按层模拟

与上述方法不同的是,这个方法更像是分治的思路,将顺时针矩阵分解成不同层的矩阵,然后又把不同层分解成从左至右、从上至下、从右至左、从下至上四个方向,详解如图所示:

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        //矩阵行或者列为空,说明矩阵为空,则返回空值
        if(matrix.size() == 0 || matrix[0].size() == 0){
            return {};
        }
        vector<int> ans;
        int m = matrix.size();//行最大
        int n = matrix[0].size();//列最大
                
        int top = 0, bottom = m - 1;
        int left = 0, right = n - 1;
        while(left <= right && top <= bottom){
            //把每一层的数从左至右放入结果数组中
            for(int col = left; col <= right; col++){
                ans.push_back(matrix[top][col]);//将矩阵中的数字存入结果中
            }
            
            //把每一层的数从上至下放入结果数组中
            for(int row = top + 1; row <= bottom; row++){
                ans.push_back(matrix[row][right]);//将矩阵中的数字存入结果中
            }
            
            if(left < right && top < bottom){
                //把每一层的数从右至左放入结果数组中
                for(int col = right - 1; col > left; col--){
                    ans.push_back(matrix[bottom][col]);//将矩阵中的数字存入结果中
                }
                
                //把每一层的数从下至上放入结果数组中
                for(int row = bottom; row > top; row--){
                    ans.push_back(matrix[row][left]);//将矩阵中的数字存入结果中
                }
                
            }
            top++;
            right--;
            bottom--;
            left++;
        }
       
        return ans;
    }
};

基于上述思想,可以自行选择每一层四个方向的截止位置(也就是每一方向存入数组的最后一个数)和起始位置(也就是每一方向存入数组的第一个数),比如从左至右的截止点可以是[top, right],也可以是[top,right - 1],同时,从上至下的起始点也可以是[top + 1, right],也可以是[top, right]只要每一方向的起始点和上一方向的截止点保证连续即可

  • 时间复杂度:O(mn)

  • 空间复杂度:O(1)。该方法与上述方法比,只是使用了四个表示方位的变量,因此空间复杂度为常量级别

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

新能源汽车锂离子电池各参数的时间序列关系

Hi&#xff0c;大家好&#xff0c;我是半亩花海。为了进一步开展新能源汽车锂离子电池的相关研究&#xff0c;本文主要汇总并介绍了电动汽车的锂离子电池的各项参数&#xff0c;通过 MATLAB 软件对 Oxford Dataset 的相关数据集进行数据处理与分析&#xff0c;进一步研究各项参…

FastStone 10.x 注册码

简介 FastStone Capture是一款经典好用的屏幕截图软件&#xff0c;在屏幕截图领域具有广泛的应用和众多优势。 软件基本信息 FastStone Capture体积小巧&#xff0c;占用内存少&#xff0c;这使得它在运行时不会给计算机系统带来过多的负担&#xff0c;即使在配置较低的电脑…

AI合成图片是什么意思?有什么用?

随着人工智能的发展&#xff0c;现在市面上出现了很多对企业帮助很大的AI工具&#xff0c;比如说AI合成图片、AI换模特、AI穿衣、AI图片设计等等&#xff0c;下面小编就以AI合成图片为例&#xff0c;为大家详细介绍下。 一、AI合成图片是什么意思? AI合成图片主要就是指利用人…

【示例】Vue AntV G6 base64自定义img 动画效果,自适应宽高屏

需求&#xff1a;拓扑图中需要用动画的线条连接node&#xff0c;在此之前将HTML页面改成了vue页面。需要使用到G6的registerEdge 自定义边&#xff0c;小车的图片需要转成base64格式&#xff08;并翻转&#xff09;&#xff0c;可以通过base64转image查看原来的样子。 另外&am…

MySQL的分析查询语句

【图书推荐】《MySQL 9从入门到性能优化&#xff08;视频教学版&#xff09;》-CSDN博客 《MySQL 9从入门到性能优化&#xff08;视频教学版&#xff09;&#xff08;数据库技术丛书&#xff09;》(王英英)【摘要 书评 试读】- 京东图书 (jd.com) MySQL9数据库技术_夏天又到了…

【递归,搜索与回溯算法 综合练习】深入理解暴搜决策树:递归,搜索与回溯算法综合小专题(二)

优美的排列 题目解析 算法原理 解法 &#xff1a;暴搜 决策树 红色剪枝&#xff1a;用于剪去该节点的值在对应分支中&#xff0c;已经被使用的情况&#xff0c;可以定义一个 check[ ] 紫色剪枝&#xff1a;perm[i] 不能够被 i 整除&#xff0c;i 不能够被 per…

观察者模式(sigslot in C++)

大家&#xff0c;我是东风&#xff0c;今天抽点时间整理一下我很久前关注的一个不错的库&#xff0c;可以支持我们在使用标准C的时候使用信号槽机制进行观察者模式设计&#xff0c;sigslot 官网&#xff1a; http://sigslot.sourceforge.net/ 本文较为详尽探讨了一种观察者模…

GitCode 光引计划投稿|智能制造一体化低代码平台 Skyeye云

随着智能制造行业的快速发展&#xff0c;企业对全面、高效的管理解决方案的需求日益迫切。然而&#xff0c;传统的开发模式往往依赖于特定的硬件平台&#xff0c;且开发过程繁琐、成本高。为了打破这一瓶颈&#xff0c;Skyeye云应运而生&#xff0c;它采用先进的低代码开发模式…

高校就业管理:系统设计与实现的全流程分析

3.1可行性分析 在项目进行开发之前&#xff0c;必须要有可行性分析报告&#xff0c;分别从技术角度&#xff0c;经济角度&#xff0c;操作角度上面进行分析&#xff0c;经过可行性分析是实现科学开发的必要步骤。 3.1.1技术可行性 从技术的角度出发&#xff0c;目前采用开发的技…

超级AI图像放大工具Upscayl:让你的照片细节更清晰,色彩更鲜艳!

前言 Hello大家好&#xff0c;我又来推荐非常好用的AI图片无损放大器,模糊图片秒变高清&#xff0c;Upscayl是一个免费开源的AI图像超分辨率工具。它使用AI模型来通过猜测细节的方式增强图像并提高其分辨率。该工具适用于Linux、macOS和Windows操作系统 安装环境 [名称]&…

1.gitlab 服务器搭建流程

前提条件&#xff1a; 一、服务器硬件水平 搭建gitlab服务器最低配置要求2核4G,低于这个配置的服务器运行效果很差。 gitlab官网&#xff1a;https://about.gitlab.com/ 下载地址&#xff1a;gitlab/gitlab-ce - Packages packages.gitlab.com 本机ubuntu 二、安装依赖 su…

Ai编程从零开始全栈开发一个后台管理系统之用户登录、权限控制、用户管理-前端部分(十二)

云风网 云风笔记 云风知识库 一、创建前端部分 1、vite初始化项目 npm create vitelatest admin-frontend – --template vue-ts 2、安装必要的依赖 npm install vue-router pinia axios element-plus element-plus/icons-vue安装完成后package.json如下&#xff1a; {&qu…

CVE-2024-34351 漏洞复现

CVE-2024-34351&#xff0c;由Next.js异步函数createRedirectRenderResult导致的SSRF。 影响版本&#xff1a;13.4.0< Next.js < 14.1.1 参考文章&#xff1a; Next.js Server-Side Request Forgery in Server Actions CVE-2024-34351 GitHub Advisory Database Gi…

怎么理解GKE Role-Based Access Control (RBAC) 和 Pod Security Policies (PSP)

怎么理解GKE Role-Based Access Control (RBAC) 和 Pod Security Policies (PSP) 理解 Google Kubernetes Engine (GKE) 中的角色基于访问控制&#xff08;RBAC&#xff09;和 Pod 安全策略&#xff08;PSP&#xff09;对于确保集群安全性至关重要。以下是对这两个概念的详细解…

什么是 DevOps 自动化?

DevOps 自动化是一种现代软件开发方法&#xff0c;它使用工具和流程来自动化任务并简化工作流程。它将开发人员、IT 运营和安全团队聚集在一起&#xff0c;帮助他们有效协作并交付可靠的软件。借助 DevOps 自动化&#xff0c;组织能够处理重复性任务、优化流程并更快地将应用程…

帝国CMS:如何去掉帝国CMS登录界面的认证码登录

如果在安装的时候&#xff0c;不小心选中了认证码选项&#xff0c;那么后面登录帝国后台都会要求输入认证码才能登录&#xff0c;如何去除这个设置呢&#xff0c;笔者以古诗词网 www.gushichi.com为例&#xff0c;为大家举例说明&#xff01; 去除步骤如下&#xff1a; 1.前往…

4.2V单节锂电池充电电路(TP4056)、USB与锂电池切换电路分享

一、充电原理图 1、连接说明 BAT_VCC和BAT_GND连接电池 VUSB和GND连接USB电源 2、芯片介绍 a、DW01 DW01芯片是一种电池管理保护芯片&#xff0c;主要用于锂离子电池的保护和管理。DW01芯片具有以下特点&#xff1a; 电池电压保护&#xff1a;DW01芯片可以监测和保护电池的…

ChatGPT生成接口文档实践案例(二)

不难发现&#xff0c;两个方案都出色地完成了接口文档的生成&#xff0c;但笔者更喜欢Response 2的表达&#xff0c;因为其描述更加全面。 还可以让ChatGPT生成符合OpenAPI 3.0规范的接口文档&#xff0c;以便于项目相关成员阅读&#xff0c;如图5-13所示。 为什么要生成OpenAP…

MFC用List Control 和Picture控件实现界面切换效果

添加List Control 和Picture控件 添加 3个子窗体 把子窗体边框设置为None, 样式设为Child 声明 CListCtrl m_listPageForm;void ShowForm(int nIndex);void CreatFormList();void CMFCApplication3Dlg::DoDataExchange(CDataExchange* pDX) {CDialogEx::DoDataExchange(pDX);DD…

JavaWeb Servlet的反射优化、Dispatcher优化、视图(重定向)优化、方法参数值获取优化

目录 1. 背景2. 实现2.1 pom.xml2.2 FruitController.java2.3 DispatcherServlet.java2.4 applicationContext.xml 3. 测试 1. 背景 前面我们做了Servlet的一个案例。但是存在很多问题&#xff0c;现在我们要做优化&#xff0c;优化的步骤如下&#xff1a; 每个Fruit请求都需…