首页 > 其他分享 >力扣最热一百题——螺旋矩阵

力扣最热一百题——螺旋矩阵

时间:2024-09-15 15:48:52浏览次数:11  
标签:遍历 matrix bottom top 矩阵 最热 力扣 left 边界

目录

题目链接:54. 螺旋矩阵 - 力扣(LeetCode)

题目描述

示例

提示:

解法一:模拟

1. 边界初始化

2. 循环遍历矩阵

3. 从左到右遍历上边界

4. 从上到下遍历右边界

5. 从右到左遍历下边界

6. 从下到上遍历左边界

7. 结束条件

代码执行流程总结

Java写法:

运行时间以及内存消耗

C++写法:

运行时间以及内存消耗

总结


题目链接:54. 螺旋矩阵 - 力扣(LeetCode)

注:下述题目描述和示例均来自力扣

题目描述

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


解法一:模拟

按照顺时针方向从外圈到内圈依次读取矩阵中的元素。具体实现思路可以分为以下几个步骤:

1. 边界初始化

  • 定义四个边界:top, bottom, left, right,分别表示矩阵的上边界、下边界、左边界和右边界。
  • 初始时,top 为 0(最上方),bottom 为矩阵的最后一行索引,left 为 0(最左边),right 为矩阵的最后一列索引。

2. 循环遍历矩阵

  • 进入 while 循环,条件是:top <= bottom && left <= right。这意味着当矩阵还未完全遍历时,继续循环。
  • 在每次循环中,按照四个方向依次遍历:从左到右、从上到下、从右到左、从下到上。每次遍历完一条边界后,收缩该边界(即移动内圈的边界)。

3. 从左到右遍历上边界

  • 首先,遍历当前 top 行,从 leftright,将该行的所有元素依次添加到结果数组中。
  • 遍历完成后,将 top 变量加 1,表示上边界下移一行,进入内层。

4. 从上到下遍历右边界

  • 然后,遍历当前 right 列,从 topbottom,将该列的所有元素依次添加到结果数组中。
  • 遍历完成后,将 right 变量减 1,表示右边界左移一列。

5. 从右到左遍历下边界

  • 如果 top <= bottom 仍然成立(即还有未遍历的行),开始遍历 bottom 行,从 rightleft,将该行的所有元素依次添加到结果数组中。
  • 遍历完成后,将 bottom 变量减 1,表示下边界上移一行。

6. 从下到上遍历左边界

  • 如果 left <= right 仍然成立(即还有未遍历的列),开始遍历 left 列,从 bottomtop,将该列的所有元素依次添加到结果数组中。
  • 遍历完成后,将 left 变量加 1,表示左边界右移一列。

7. 结束条件

  • 循环不断缩小边界,直到 top > bottomleft > right,表示已经遍历完所有的元素,此时退出循环。
  • 返回保存螺旋顺序的 res 数组。

代码执行流程总结

  1. 每次从四个方向依次遍历矩阵的当前边界。
  2. 每遍历完一条边界,收缩该边界,进入下一层的螺旋圈。
  3. 重复上述步骤,直到所有元素都被遍历完。

Java写法:

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0) {
            return res;
        }

        int top = 0; // 上边界
        int bottom = matrix.length - 1; // 下边界
        int left = 0; // 左边界
        int right = matrix[0].length - 1; // 右边界

        while (top <= bottom && left <= right) {
            // 从左到右遍历当前的上边界
            for (int i = left; i <= right; i++) {
                res.add(matrix[top][i]);
            }
            top++; // 上边界收缩

            // 从上到下遍历当前的右边界
            for (int i = top; i <= bottom; i++) {
                res.add(matrix[i][right]);
            }
            right--; // 右边界收缩

            // 判断是否还需要遍历
            if (top <= bottom) {
                // 从右到左遍历当前的下边界
                for (int i = right; i >= left; i--) {
                    res.add(matrix[bottom][i]);
                }
                bottom--; // 下边界收缩
            }

            // 判断是否还需要遍历
            if (left <= right) {
                // 从下到上遍历当前的左边界
                for (int i = bottom; i >= top; i--) {
                    res.add(matrix[i][left]);
                }
                left++; // 左边界收缩
            }
        }

        return res;
    }
}

 

运行时间以及内存消耗

C++写法:

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        if (matrix.empty() || matrix[0].empty()) {
            return res;
        }

        int top = 0; // 上边界
        int bottom = matrix.size() - 1; // 下边界
        int left = 0; // 左边界
        int right = matrix[0].size() - 1; // 右边界

        while (top <= bottom && left <= right) {
            // 从左到右遍历当前的上边界
            for (int i = left; i <= right; i++) {
                res.push_back(matrix[top][i]);
            }
            top++; // 上边界收缩

            // 从上到下遍历当前的右边界
            for (int i = top; i <= bottom; i++) {
                res.push_back(matrix[i][right]);
            }
            right--; // 右边界收缩

            // 判断是否还需要遍历
            if (top <= bottom) {
                // 从右到左遍历当前的下边界
                for (int i = right; i >= left; i--) {
                    res.push_back(matrix[bottom][i]);
                }
                bottom--; // 下边界收缩
            }

            // 判断是否还需要遍历
            if (left <= right) {
                // 从下到上遍历当前的左边界
                for (int i = bottom; i >= top; i--) {
                    res.push_back(matrix[i][left]);
                }
                left++; // 左边界收缩
            }
        }

        return res;
    }
};
运行时间以及内存消耗


总结

这里的边界条件实在是非常的难把握,所实话,一但掉入了边界条件的陷阱之后就会让你一直缝缝补补,很难有几率能缝缝补补出来。

正如那句话所说:一如入循环深似海,从此offer是路人

 

标签:遍历,matrix,bottom,top,矩阵,最热,力扣,left,边界
From: https://blog.csdn.net/DDDDWJDDDD/article/details/142283998

相关文章

  • 2024-06-02 矩阵重塑2
    include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e4+1;intmar[maxn];voidtmar(intmar[],constintn,constintm){intmat[n+1][m+1],mat1[m+1][n+1];inti,j;for(i=1;i<=n;i++){for(j=1;j<=m;j++){mat[i][j]=mar[(i-1)*m+j];}}for(......
  • 算法工程师重生之第二天(长度最小的子数组 螺旋矩阵II 区间和 开发商购买土地 总结 )
    参考文献代码随想录一、长度最小的子数组给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl,numsl+1,...,numsr-1,numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。示......
  • 矩阵乘法、矩阵快速幂
    一定要看好乘的顺序!!!!!横的在前,竖的在后!矩阵乘法和矩阵快速幂本身简单,但是构造出矩阵递推式的过程比较考验智慧。1矩阵乘法1.定义若矩阵A的大小为\(n\timesm\),矩阵B的大小为\(m\timesp\),则两个矩阵可以做乘法,得到的矩阵C的大小为\(n\timesp\)。\(A=\begin{bmatrix}a_{......
  • 【随想录day2】LeetCode209长度最小的子数组 | LeetCode59螺旋矩阵
    LeetCode209长度最小的子数组1、题目:给定一个含有n个正整数的数组和一个正整数s,找出该数组中满足其和≥s的长度最小的连续子数组,并返回其长度。如果不存在符合条件的子数组,返回0示例:输入:s=7,nums=[2,3,1,2,4,3]输出:2解释:子数组[4,3]是该条件下的长度最小......
  • 力扣494-目标和(Java详细题解)
    题目链接:494.目标和-力扣(LeetCode)前情提要:因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。最近刚学完01背包,所以现在的题解都是以01背包问题为基础再来写的。如果大家不懂01背包的话,建议可以去学一学,01背包问题可以说是背包问题的基础。如果大家感兴趣,......
  • Day2|209.长度最小的子数组|59.螺旋矩阵II|区间和|开发商购买土地
    209.长度最小的子数组59.螺旋矩阵II 209.长度最小的子数组classSolution{publicintminSubArrayLen(inttarget,int[]nums){intfastIndex=0;intslowIndex=0;intsums=0;intresult=Integer.MA......
  • 力扣刷题——2398. 预算内的最多机器人数目
    由题目中求“最多可以连续运行的机器人数目”可知,求的是数组子数组的长度,那么就可以直接使用滑动窗口求解。配合前缀和,可以快速的求得滑动窗口内的运行时间和。那么编写代码如下:intmaximumRobots(vector<int>&chargeTimes,vector<int>&runningCosts,longlongbudget){......
  • [NOIP 2024 模拟2]矩阵学说
    [NOIP2024模拟2]矩阵学说题意给出\(n\)行\(m\)列的矩阵,第\(i\)行第\(j\)列的元素为\(a_{i,j}\),找出满足以下条件的三元组\((i,j,x)\)的数量:\(1≤i≤n\),\(1≤j\lem\),\(1≤x≤\min(n−i+1,m−j+1)\)矩阵的左上角\((i,j)\)到右下角......
  • 题解 力扣 LeetCode 105 从前序与中序遍历序列构造二叉树 C/C++
    题目传送门:105.从前序与中序遍历序列构造二叉树-力扣(LeetCode)https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/每次在中序遍历序列片段中找到前序遍历序列队首,这是该层的根节点该位置左侧是左子树,右侧是右子树再......
  • 【力扣16】最接近的三数之和
    16.最接近的三数之和-力扣(LeetCode)接近target:大于或小于两种情况。但是实际操作中只需考虑大于的情况,找到之后结果的前一个数也有可能是结果,进行比较(更新结果res)。第二种情况的实现依靠右指针的移动思路类似15对于每个j,找到一个最小的k,使得满足条件(j变大,k一定减小即k--)......