Leetcode 54: 螺旋矩阵
Leetcode 54: 螺旋矩阵 是一道经典的矩阵遍历模拟题目,要求我们以螺旋顺序遍历一个二维数组。这个问题在面试中非常经典,考察模拟、数组操作以及逻辑清晰度。掌握本题的高效解法可以迅速给面试官留下好印象。
适合面试的解法:边界法(层级遍历)
解法描述
- 核心思想:一次遍历一圈,按四个边界移动指针
- 定义四个边界:
top,bottom,left,right,分别表示当前未遍历层的上边界、下边界、左边界和右边界。 - 遍历一圈后,逐步缩小边界范围,直到所有元素都被处理。
- 定义四个边界:
- 边界调整规则:
- 从左到右遍历上侧(
top行),然后top++; - 从上到下遍历右侧(
right列),然后right--; - 如果还有未遍历的行,则 从右到左遍历底侧(
bottom行),然后bottom--; - 如果还有未遍历的列,则 从下到上遍历左侧(
left列),然后left++。 - 每次遍历完一圈,都缩小边界范围。
- 从左到右遍历上侧(
- 终止条件:
- 当
top > bottom或left > right时,说明所有元素都已访问。
- 当
代码模板
import java.util.*;class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> result = new ArrayList<>();if (matrix == null || matrix.length == 0) return result;int top = 0, bottom = matrix.length - 1; // 上下边界int left = 0, right = matrix[0].length - 1; // 左右边界while (top <= bottom && left <= right) {// 从左到右遍历上边界for (int i = left; i <= right; i++) {result.add(matrix[top][i]);}top++; // 上边界缩小// 从上到下遍历右边界for (int i = top; i <= bottom; i++) {result.add(matrix[i][right]);}right--; // 右边界缩小// 检查是否还有未遍历的行if (top <= bottom) {// 从右到左遍历下边界for (int i = right; i >= left; i--) {result.add(matrix[bottom][i]);}bottom--; // 下边界缩小}// 检查是否还有未遍历的列if (left <= right) {// 从下到上遍历左边界for (int i = bottom; i >= top; i--) {result.add(matrix[i][left]);}left++; // 左边界缩小}}return result;}
}
复杂度分析
- 时间复杂度:O(m * n)
- 访问每个元素一次,m 为行数,n 为列数。
- 空间复杂度:O(1)(不计算结果集)
- 原地遍历,无需额外空间。
适用场景
- 面试首选解法:
- 模拟问题逻辑清晰,层次分明,行为可解释。
- 高效,简单易实现,能快速写出来。
- 面试中可以结合剪枝优化、边界调整等细节,展示代码能力。
其他解法及分析
解法 2:模拟法
该解法直接按照螺旋的变化顺序(右 -> 下 -> 左 -> 上)模拟移动,通过控制方向实现遍历。
思路
- 定义方向和边界:
- 使用方向数组
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]表示右、下、左、上的顺序; - 通过一个
dirIndex控制当前的方向(如dirIndex = 0表示向右,dirIndex = 1表示向下)。 - 定义已经访问过的区域,并使用二维
visited数组记录已经访问的元素。
- 使用方向数组
- 遍历矩阵:
- 从
(0, 0)点开始,模拟按照当前方向移动; - 如果即将移动超出边界或者已经访问过,切换到下一个方向;
- 直到所有元素遍历完为止。
- 从
代码模板
class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> result = new ArrayList<>();if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return result;int m = matrix.length, n = matrix[0].length;boolean[][] visited = new boolean[m][n]; // 记录访问情况// 定义方向数组(右、下、左、上)int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};int dirIndex = 0; // 当前方向int row = 0, col = 0; // 当前坐标for (int i = 0; i < m * n; i++) {result.add(matrix[row][col]);visited[row][col] = true;// 计算下一个位置int nextRow = row + dirs[dirIndex][0];int nextCol = col + dirs[dirIndex][1];// 如果越界或已经访问过,改变方向if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n || visited[nextRow][nextCol]) {dirIndex = (dirIndex + 1) % 4; // 顺时针切换方向nextRow = row + dirs[dirIndex][0];nextCol = col + dirs[dirIndex][1];}row = nextRow;col = nextCol;}return result;}
}
复杂度分析
- 时间复杂度:O(m * n)
- 每个元素遍历一次。
- 空间复杂度:O(m * n)
- 使用了
visited二维数组记录访问情况。
- 使用了
适用场景
- 如果面试官要求实现更灵活的模拟法,则此解法是合适的替代。
- 不过,由于需要额外的
visited数组,其空间复杂度较高,不是首选。
快速AC总结
推荐解决方案
- 优先使用:边界法(解法 1)
- 模拟螺旋顺序,根据边界进行缩小调整;
- 代码简洁高效,容易直接实现,完全满足面试需求。
- 备选模拟法(解法 2)
- 如果需要通过灵活控制方向和遍历行为进行实现,此解法较为通用,但需要额外空间。
在面试中如何快速AC
- 清晰描述解法:
- 解释如何依次遍历每一圈,使用上下左右边界标记矩阵;
- 让面试官了解整个遍历顺序和边界调整的逻辑。
- 快速实现代码:
- 边界法(解法 1) 适合作为首选;
- 模拟移动的代码少且简洁,更容易写。
- 关注边界条件:
- 注意矩阵为空的情况;
- 单行单列、非方阵等特殊情况要覆盖。
通过掌握这两种解法,能够灵活应对问题,并快速在面试中实现清晰的解答,获得面试官肯定!
相关文章:
Leetcode 54: 螺旋矩阵
Leetcode 54: 螺旋矩阵 是一道经典的矩阵遍历模拟题目,要求我们以螺旋顺序遍历一个二维数组。这个问题在面试中非常经典,考察模拟、数组操作以及逻辑清晰度。掌握本题的高效解法可以迅速给面试官留下好印象。 适合面试的解法:边界法ÿ…...
abseil-cpp:环境搭建
参考: https://abseil.io/docs/cpp/quickstart-cmake abseil-cpp.git/dd4c89b abseil-cpp.git/20240722.1 1. clone代码仓库、编译 git clone https://github.com/abseil/abseil-cpp.git /app/abseil-cpp/ #/app/abseil-cpp/.git/config git checkout 20240722.1git rev-pa…...
Centos7部署k8s(单master节点安装)
单master节点部署k8s集群(Centos) 一、安装前准备 1、修改主机名 按照资源准备修改即可 # master01 hostnamectl set-hostname master01 ; bash # node1 hostnamectl set-hostname node1 ; bash # node2 hostnamectl set-hostname node2 ; bash2、修改hosts文件 以下命令所…...
RPA 职业前景:个人职场发展的 “新机遇”
1. RPA职业定义与范畴 1.1 RPA核心概念 机器人流程自动化(RPA)是一种通过软件机器人模拟人类操作,自动执行重复性、规则性任务的技术。RPA的核心在于其能够高效、准确地处理大量数据和流程,减少人工干预,从而提高工作…...
详解DeepSeek模型底层原理及和ChatGPT区别点
一、DeepSeek大模型原理 架构基础 DeepSeek基于Transformer架构,Transformer架构主要由编码器和解码器组成,在自然语言处理任务中,通常使用的是Transformer的解码器部分。它的核心是自注意力机制(Self - Attention),这个机制允许模型在处理输入序列时,关注序列中不同位…...
《2025年软件测试工程师面试》JAVA基础面试题
基础题 == 和 equals 的区别是什么? ==比较的是引用是否相同,比较的是对象的引用地址,如果比较的两个对象地址位不同,值相同也会返回falseequals()比较的是...
【算法学习之路】5.贪心算法
贪心算法 前言一.什么是贪心算法二.例题1.合并果子2.跳跳!3. 老鼠和奶酪 前言 我会将一些常用的算法以及对应的题单给写完,形成一套完整的算法体系,以及大量的各个难度的题目,目前算法也写了几篇,题单正在更新…...
如何打造一个安全稳定的海外社媒账号?
您好!随着TikTok、Instagram、Facebook等海外社媒平台的迅猛发展,越来越多的个人和企业希望借助这些平台实现全球化传播。然而,注册和运营海外社媒账号的过程中,许多人频繁遭遇到封禁、限制和账号关联等问题,常常导致严…...
【Python 数据结构 5.栈】
目录 一、栈的基本概念 1.栈的概念 2.入栈 入栈的步骤 3.出栈 出栈的步骤 4.获取栈顶元素 获取栈顶元素的步骤 二、 Python中的栈 顺序表实现 链表实现 三、栈的实战 1.LCR 123. 图书整理 I 思路与算法 2.LCR 027. 回文链表 思路与算法 3.1614. 括号的最大嵌套深度 思路与算法 …...
Qt开发⑪Qt网络+Qt音视频_使用实操
目录 1. Qt 网络 1.1 UDP Socket 1.2 TCP Socket 1.3 HTTP Client 2. Qt 音视频 2.1 Qt 音频 2.2 Qt 视频 本篇完。 1. Qt 网络 和多线程类似,Qt 为了支持跨平台, 对网络编程的 API 也进行了重新封装。 实际 Qt 开发中进行网络编程,也不一定使用…...
JavaEE--计算机是如何工作的
一、一台计算机的组成部分 1.CPU(中央处理器) 2.主板(一个大插座) 3.内存(存储数据的主要模板) 4.硬盘(存储数据的主要模板) 内存和硬盘对比: 内存硬盘读写速度快慢存…...
API接口:企业名称、注册号、统一社会信用代码、企业类型、成立日期和法定代表人等数据 API 接口使用指南
API接口:企业名称、注册号、统一社会信用代码、企业类型、成立日期和法定代表人等数据 API 接口使用指南 本文详细介绍一种基于 Web 搜索方式实现的企业信息查询接口,适用于数据补全、企业资质验证、信息查询等场景。文章内容涵盖接口功能、请求参数、返…...
微信小程序text组件decode属性的小问题
今天学习微信小程序的text组件,这个组件类似于网页制作中的span标签,内联文本只能用 text 组件,不能用 view,如 foo bar </text。 text组件常用属性如下表: 属性说明user-select文本是否可选,该属性会使…...
【计算机网络入门】初学计算机网络(九)
目录 1.令牌传递协议 2. 局域网&IEEE802 2.1 局域网基本概念和体系结构 3. 以太网&IEEE802.3 3.1 MAC层标准 3.1.1 以太网V2标准 编辑 3.2 单播广播 3.3 冲突域广播域 4. 虚拟局域网VLAN 1.令牌传递协议 先回顾一下令牌环网技术,多个主机形成…...
LeetCode 974:和可被 K 整除的子数组
974. 和可被 K 整除的子数组 - 力扣(LeetCode) 给定一个整数数组 nums 和一个整数 k ,返回其中元素之和可被 k 整除的非空 子数组 的数目。 子数组 是数组中 连续 的部分。 示例 1: 输入:nums [4,5,0,-2,-3,1], k …...
vector习题
完数和盈数 题目 完数VS盈数_牛客题霸_牛客网 一个数如果恰好等于它的各因子(该数本身除外)之和,如:6321。则称其为“完数”;若因子之和大于该数,则称其为“盈数”。 求出2到60之间所有“完数”和“盈数”。 输入描述ÿ…...
001-码云操作
码云操作 一、配置公钥1.官网地址1.进入 git bash2.查看生成的公钥3.设置到 Gitee4.测试 二、初始化一个项目1.新建仓库 一、配置公钥 方便后续提交代码不用填写密码 1.官网地址 官网地址:https://gitee.com/Git码云教程:https://gitee.com/help/arti…...
数据结构:二叉搜索树(排序树)
1.二叉搜索树的定义 二叉搜索树要么是空树,要么是满足以下特性的树 (1)左子树不为空,那么左子树左右节点的值都小于根节点的值 (2)右子树不为空,那么右子树左右节点的值都大于根节点的值 &#…...
【愚公系列】《Python网络爬虫从入门到精通》036-DataFrame日期数据处理
标题详情作者简介愚公搬代码头衔华为云特约编辑,华为云云享专家,华为开发者专家,华为产品云测专家,CSDN博客专家,CSDN商业化专家,阿里云专家博主,阿里云签约作者,腾讯云优秀博主,腾讯云内容共创官,掘金优秀博主,亚马逊技领云博主,51CTO博客专家等。近期荣誉2022年度…...
C++(蓝桥杯常考点)
前言:这个是针对于蓝桥杯竞赛常考的C内容,容器这些等下棋期再讲 C 在DEVC中注释和取消注释的方法:ctrl/ ASCII值(常用的): A-Z:65-90 a-z:97-122 0-9:48-57 换行/n:10科学计数法:eg:…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...
