Java教程

数据结构与算法--螺旋矩阵

本文主要是介绍数据结构与算法--螺旋矩阵,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目:给你一个正整数 n ,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。(来源:https://leetcode-cn.com/problems/spiral-matrix-ii/)
在这里插入图片描述
代码:

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int num = 1;   //添加的数
        int round = 0; //轮次
        int a,b,c,d;   //四个方向
        //以轮次,即圈数作为循环的条件
        while(round < (n + 1)/2){
            //n为奇数时,最后一个值无法赋予(因为就剩一个值无法形成圈圈)
            if (n - 2*round == 1)
            {
                res[round][round] = num;
                break;
            }
            //上左-->上右
            for(a = round; a < n - round - 1; a++){
                res[round][a] = num;
                num++;
            }
            //上右-->下右
            for(b = round; b < n - round - 1; b++){
                res[b][n - round - 1] = num;
                num++;
            }
            //下右-->下左
            for(c = n - round- 1; c > round; c--){
                res[n - round - 1][c] = num;
                num++;
            }
            //下左-->上左
            for(d = n - round - 1; d > round; d--){
                res[d][round] = num;
                num++;
            }
            //圈数加一,进入下一圈
            round++;
        }
        return res;
    }
}

思路:(主要参照代码随想录的解题思路:https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html#%E6%80%9D%E8%B7%AF)
正如书中所说要遵循循环不变量原则,确定好循环的区间,我选择了以矩阵的端点作为起始,遍历的末尾并不到达另一个端点,即左闭右开。示意如图:
在这里插入图片描述
在这里插入图片描述
可以看出,这样模拟了螺旋的遍历顺序,将其看成一个个套着的圈,唯一不同的只是n为奇数时剩下的最后一个数无法成圈。对此,我们只要圈用循环来赋值(确定好边界区间),并判断奇偶来决定最后一个数的赋值。很多小伙伴也采用这样的模拟螺旋的思路,但是我觉得有价值的是像上面这样写循环的区间,更清晰。通过圈数来设定端点和边界以得到区间,这样起始的端点就简单的分为了两类:round和n-round-1,末尾的边界也便是:sth < n-round-1和 sth >round,这也使得四个循环看起来更具有衔接性。比较容易理解这段代码的方法就是,将round=0,n=3的情况带入……(得自己想象了,当初自己就是这么想出来的)

最后,提交结果,速度挺快就是内存消耗有点大。
在这里插入图片描述

P.S. 这是我发的第一篇文章,一时兴起,也是为了记录和分享今天学习的点滴。CSDN让我受益良多,但自己没有以这种形式进行过分享和记录,一方面,觉得写出精品的帖子更有意义;另一方面,觉得自己一直在学习,似乎值得分享不多。基础的学习解答贴已经很多了,这里面有部分是重复甚至拷贝,我觉得这样总是不大好的。当然,这不排除他人只是为了记录学习 痕迹,无论是在本子、word、博客上,勤做笔记都是极好的,最重要的是加深了印象!现在想来,作为分享,在学习中有自己的思考,有些许不一样的产出也是好的,至少对自己是有意义的。今天的分享基于leetcode的各项帖子、评论以及《代码随想录》的学习,当然有了自己的思考和产出。希望日后更能勤于思考,多做分享,多做有意义的分享。

这篇关于数据结构与算法--螺旋矩阵的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!