数据结构学习 jz29 顺时针打印矩阵

这篇具有很好参考价值的文章主要介绍了数据结构学习 jz29 顺时针打印矩阵。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

关键词:模拟

题目:螺旋遍历二维数组

简单题做了超过40分钟 调了很久 不好 

数据结构学习 jz29 顺时针打印矩阵,数据结构学习,数据结构,学习,矩阵

方法一:

我自己做的。

思路:

xy_t:

记录xy的方向,往右走,往下走,往左走,往上走

t控制方向

std::vector<std::vector<int>>xy_t{ {0,1},{1,0},{0,-1},{-1,0} };

isx:

        true:轮到x方向动

        false:轮到y方向动

bool isx = false;

n_res m_res:

        n_res:还没走过的行数(x方向)

        m_res:还没走过的列数(y方向)

int n_res = n, m_res = m;

res:

        现在走的方向剩余的行数/列数。

int res = isx ? n_res : m_res;

step:

        现在走的这一行/这一列已经走过的步数。

记录结果,步数加一:

result.push_back(array[x][y]);
step++;

如果step+1超过res,意味着这一行/这一列走到底了:

        1、如果isx==true(在x方向上走了一列),那么m_res-1 

        2、如果isx==false(在y方向上走了一行),那么n_res-1 

        3、isx方向反转

        4、改变t控制的方向

        5、step归零

            if (step + 1 > res)
            {
                n_res = isx ? n_res : n_res - 1;
                m_res = !isx ? m_res : m_res - 1;
                isx = !isx;
                t = (t + 1) % 4;
                step = 0;
            }

走下一步:

            x = x + xy_t[t][0];
            y = y + xy_t[t][1];

 比如:

先沿y方向走一行。

数据结构学习 jz29 顺时针打印矩阵,数据结构学习,数据结构,学习,矩阵

走完之后,n_res--

再沿x方向走一列。

数据结构学习 jz29 顺时针打印矩阵,数据结构学习,数据结构,学习,矩阵

走完之后,m_res--

循环这个过程直到所有数被走完。

复杂度计算:

时间复杂度O(nm)

空间复杂度O(1)文章来源地址https://www.toymoban.com/news/detail-796370.html

代码:

class Solution {
public:
    std::vector<int> spiralArray(std::vector<std::vector<int>>& array) {
        std::vector<int> result;
        if (array.empty() || array[0].empty()) return result;
        int n = array.size(), m = array[0].size();
        int x = 0, y = 0;
        std::vector<std::vector<int>>xy_t{ {0,1},{1,0},{0,-1},{-1,0} };
        bool isx = false;
        int n_res = n, m_res = m;
        int step = 0;
        int t = 0;
        for (int i = 0; i < n * m; i++)
        {
            int res = isx ? n_res : m_res;
            result.push_back(array[x][y]);
            step++;
            if (step + 1 > res)
            {
                n_res = isx ? n_res : n_res - 1;
                m_res = !isx ? m_res : m_res - 1;
                isx = !isx;
                t = (t + 1) % 4;
                step = 0;
            }
            x = x + xy_t[t][0];
            y = y + xy_t[t][1];
        }
        return result;
    }
};

方法二:

看了k神的提示,弄了四面会活动的墙。显然比我原本的好。

思路:

四面墙:

        l左墙

        r右墙

        t上墙

        b下墙

int l = 0, r = m - 1, t = 0, b = n - 1;

cut:

        统计已经走过的格子的个数。

从左往右走:

碰到右墙就停止。

走完之后上面第一行已经走完,上墙往下移动一行,t++。

            for (int i = l; i <= r; ++i)
            {
                cut++;
                result.push_back(array[t][i]);
            }
            if (cut >= m * n) break;
            t++;

从上往下走:

碰到下墙就停止。

走完之后右边第一列已经走完,右墙往左移动一列,r--。

            for (int i = t; i <= b; ++i)
            {
                cut++;
                result.push_back(array[i][r]);
            }
            if (cut >= m * n) break;
            r--;

从右往左走:

碰到左墙就停止。

走完之后下面第一行已经走完,下墙往上移动一行,b--。

            for (int i = r; i >= l; --i)
            {
                cut++;
                result.push_back(array[b][i]);
            }
            if (cut >= m * n) break;
            b--;

从下往上走:

碰到上墙就停止。

走完之后左边第一列已经走完,左墙往右移动一列,l++。

            for (int i = b; i >= t; --i)
            {
                cut++;
                result.push_back(array[i][l]);
            }
            if (cut >= m * n) break;
            l++;

复杂度计算:

时间复杂度O(nm)

空间复杂度O(1)

代码:

class Solution {
public:
    std::vector<int> spiralArray(std::vector<std::vector<int>>& array) {
        std::vector<int> result;
        if (array.empty() || array[0].empty()) return result;
        int n = array.size(), m = array[0].size();
        int l = 0, r = m - 1, t = 0, b = n - 1;
        int cut = 0;//统计已经放进result的个数
        while (true)
        {
            for (int i = l; i <= r; ++i)
            {
                cut++;
                result.push_back(array[t][i]);
            }
            if (cut >= m * n) break;
            t++;
            for (int i = t; i <= b; ++i)
            {
                cut++;
                result.push_back(array[i][r]);
            }
            if (cut >= m * n) break;
            r--;
            for (int i = r; i >= l; --i)
            {
                cut++;
                result.push_back(array[b][i]);
            }
            if (cut >= m * n) break;
            b--;
            for (int i = b; i >= t; --i)
            {
                cut++;
                result.push_back(array[i][l]);
            }
            if (cut >= m * n) break;
            l++;

        }

        return result;
    }
};

到了这里,关于数据结构学习 jz29 顺时针打印矩阵的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode-简单】剑指 Offer 29. 顺时针打印矩阵(详解)

    输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。 示例 1: 示例 2: 剑指 Offer 29. 顺时针打印矩阵 - 力扣(LeetCode) 与 力扣54题相同 54. 螺旋矩阵 二维数组顺时针从外往里走 可以想象成:按照 右-》下-》左 -》上 的顺序一直走,走过的地方不要走即可。

    2024年02月09日
    浏览(51)
  • 【LeetCode-中等】剑指 Offer 29. 顺时针打印矩阵(详解)

    输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。 示例 1: 示例 2: 剑指 Offer 29. 顺时针打印矩阵 - 力扣(LeetCode) 与 力扣54题相同 54. 螺旋矩阵 二维数组顺时针从外往里走 可以想象成:按照 右-》下-》左 -》上 的顺序一直走,走过的地方不要走即可。

    2024年02月13日
    浏览(43)
  • Leetcode-每日一题【剑指 Offer 29. 顺时针打印矩阵】

    输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。 示例 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] 限制: 0 = matrix.length = 100 0 = matrix[i].length = 100 1.题目要求

    2024年02月13日
    浏览(57)
  • 剑指29.顺时针打印矩阵 31 栈的压入,弹出序列 03 数组中的重复数字 53缺失的数字 04二维数组中的查找

    回字形 思路:pushed数组里遍历进栈,遍历时候,先进栈,再判断栈顶是否和poped序列的当前指向的是否一样,一样就pop,直到不一样为止,然后继续遍历进栈。然后再判断栈里面剩余的和poped序列指向的一不一样,一样,就把栈里面的pop,直到栈为空,只要有一个不一样,就

    2024年02月16日
    浏览(39)
  • 【数据结构】数组和字符串(八):稀疏矩阵的链接存储:十字链表的创建、插入元素、遍历打印(按行、按列、打印矩阵)、销毁

    【数据结构】数组和字符串(一):矩阵的数组表示   矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵,如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储,会出现大量存储空间存放重复信息或零元素的情况,这样会造

    2024年02月06日
    浏览(53)
  • 【算法】顺时针打印矩阵(图文详解,代码详细注释

    目录 题目 代码如下: 输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。例如:如果输入如下矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则打印出数字:1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 这一道题乍一看,没有包含任何复杂的数据结构和高级算法,似乎蛮简单的。但

    2024年04月26日
    浏览(33)
  • 【算法 | 模拟No.4】AcWing 756. 蛇形矩阵 & AcWing 40. 顺时针打印矩阵

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【AcWing算法提高学习专栏】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成

    2024年01月16日
    浏览(54)
  • 数据结构学习笔记——多维数组、矩阵

    数组是由n(n≥1)个 相同数据类型 的数据元素组成的有限序列,在定义数组时,会为数组分配一个固定大小的内存空间,用来存储元素,数组在被定义后,其维度不可以被改变。 数组在确定其维度和维界后,元素的个数是固定的,所以不能进行插入和删除运算。数组中最常

    2024年02月03日
    浏览(48)
  • 数据结构与算法基础-学习-23-图之邻接矩阵与邻接表

    目录 一、定义和术语 二、存储结构 1、邻接矩阵 1.1、邻接矩阵优点 1.2、邻接矩阵缺点 2、邻接表 3、邻接矩阵和邻接表的区别和用途 3.1、区别 3.2、用途 三、宏定义 四、结构体定义 1、邻接矩阵 2、邻接表 3、网数据类型(造测试数据) 五、函数定义 1、使用邻接矩阵创建无

    2024年02月14日
    浏览(33)
  • 数据结构学习记录——如何建立图(邻接矩阵、邻接表-图节点的结构、创建并初始化、插入变、完整图的建立)

    目录 邻接矩阵 图节点的结构 创建并初始化 插入边 完整的图的建立  邻接表 图节点的结构 创建并初始化 插入边  完整的图的建立  定义结构体GNode,其中包含以下成员变量: Nv:表示图中的顶点数。 Ne:表示图中的边数。 二维数组表示图的邻接矩阵。它的大小是MaxVertexN

    2024年02月06日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包