首页 > 其他分享 >6.5数组--模拟、偏移量-螺旋矩阵

6.5数组--模拟、偏移量-螺旋矩阵

时间:2024-06-05 19:00:25浏览次数:27  
标签:-- res 矩阵 偏移量 int 6.5 vector array dr

M:59.螺旋矩阵II

题意描述

给你一个正整数 n ,生成一个包含 1n^2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix

示例 1:

img

输入:n = 3
输出:[[1,2,3],[8,9,4],[7,6,5]]

示例 2:

输入:n = 1
输出:[[1]]

提示:

  • 1 <= n <= 20

思路

这道题目可以说在面试中出现频率较高的题目,本题并不涉及到什么算法,就是模拟过程,但却十分考察对代码的掌控能力。

要如何画出这个螺旋排列的正方形矩阵呢?

求解本题依然是要坚持循环不变量原则。

模拟顺时针画矩阵的过程:

  • 填充上行从左到右
  • 填充右列从上到下
  • 填充下行从右到左
  • 填充左列从下到上

由外向内一圈一圈这么画下去。

这里一圈下来,我们要画每四条边,这四条边怎么画,每画一条边都要坚持一致的左闭右开,或者左开右闭的原则,这样这一圈才能按照统一的规则画下来。

那么我按照左闭右开的原则,来画一圈,大家看一下:

img

这里每一种颜色,代表一条边,我们遍历的长度,可以看出每一个拐角处的处理规则,拐角处让给新的一条边来继续画。

这也是坚持了每条边左闭右开的原则。

AC代码:

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组
        int startx = 0, starty = 0; // 定义每循环一个圈的起始位置
        int loop = n / 2; // 每个圈循环几次,例如n为奇数3,那么loop = 1 只是循环一圈,矩阵中间的值需要单独处理
        int mid = n / 2; // 矩阵中间的位置,例如:n为3, 中间的位置就是(1,1),n为5,中间位置为(2, 2)
        int count = 1; // 用来给矩阵中每一个空格赋值
        int offset = 1; // 需要控制每一条边遍历的长度,每次循环右边界收缩一位
        int i,j;
        while (loop --) {
            i = startx;
            j = starty;

            // 下面开始的四个for就是模拟转了一圈
            // 模拟填充上行从左到右(左闭右开)
            for (j; j < n - offset; j++) {
                res[i][j] = count++;
            }
            // 模拟填充右列从上到下(左闭右开)
            for (i; i < n - offset; i++) {
                res[i][j] = count++;
            }
            // 模拟填充下行从右到左(左闭右开)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模拟填充左列从下到上(左闭右开)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // 第二圈开始的时候,起始位置要各自加1, 例如:第一圈起始位置是(0, 0),第二圈起始位置是(1, 1)
            startx++;
            starty++;

            // offset 控制每一圈里每一条边遍历的长度
            offset += 1;
        }

        // 如果n为奇数的话,需要单独给矩阵最中间的位置赋值
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};

法二:偏移量法

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n , vector<int>(n , 0));
     
        //顺序依次为左上右下,一开始向右,因此d=1, 列+1
        int dx[4] = {-1 , 0 , 1 , 0}, dy[4] = {0 , 1 , 0 , -1};
      //注意这里循环是以填的数cnt:1~n*n来循环n^2次
        for(int cnt = 1 , x = 0 , y = 0 , d = 1 ;cnt <= n * n ; cnt++){
          res[x][y] = cnt;
          int a = x + dx[d] , b = y + dy[d];
          if(a < 0 || a >= n || b < 0 || b >= n || res[a][b]){
            d = (d + 1) % 4;
            a = x + dx[d] , b = y + dy[d];
          }
          x = a , y = b;
        }

        return res;
    }
};

ACwing756.蛇形矩阵

题目描述:

输入两个整数

标签:--,res,矩阵,偏移量,int,6.5,vector,array,dr
From: https://www.cnblogs.com/7dragonpig/p/18233605

相关文章

  • Docker 启蒙教程 (1)
    Docker启蒙教程(1)本教程致力于以通俗易懂的方式使读者上手Docker。本文使用CentOS7系统演示。第一章什么是DockerDocker是一个开源的应用容器引擎,让开发者可以打包他们的应用以及依赖包到一个可移植的镜像中,然后发布到任何流行的Linux或Windows操作系统的机器......
  • 【调试笔记-20240601-Linux-在 OpenWRT-23.05 上配置 frpc 实现内网穿透】
    调试笔记-系列文章目录调试笔记-20240601-Linux-在OpenWRT-23.05上配置frpc实现内网穿透文章目录调试笔记-系列文章目录调试笔记-20240601-Linux-在OpenWRT-23.05上配置frpc实现内网穿透前言一、调试环境操作系统:OpenWrt23.05.3调试环境调试目标二、调试步......
  • 【教程】使用 Tailchat 搭建团队内部聊天平台,Slack 的下一个替代品!
    前言多人协作,私有聊天一直是团队协作的关键点,现在有很多专注于团队协作的应用和平台,比如飞书、企业微信和Slack等。这期教程将带你手把手的搭建一个在线的团队协作向聊天室,希望对你有所帮助!本期聊天室使用TailChat作为服务端,TailChat是下一代nolM(不仅仅是IM)应用程序,适......
  • 最新版手把手升级GPT-4o、GPT-4 Turbo详细步骤教程!! 【2024年6月】
    01GPT-4介绍ChatGPT3.5自从发布以来,便受到了广泛的关注和火热追求。而作为3.5升级版的GPT4.0,比3.5会更加稳定、没有字数限制、回答更准确以及支持AI绘图等,为用户带来了更多的创意与想象空间。如何免费使用GPT-4o?如何升级GPT4.0Turbo?(内附详细步骤教程)我个人体验来说,日常科......
  • 力扣刷题--2553. 分割数组中数字的数位【简单】
    题目描述给你一个正整数数组nums,请你返回一个数组answer,你需要将nums中每个整数进行数位分割后,按照nums中出现的相同顺序放入答案数组中。对一个整数进行数位分割,指的是将整数各个数位按原本出现的顺序排列成数组。比方说,整数10921,分割它的各个数位得到[1,0......
  • C语言排序
    一、排序的运用生活中排序随处可见,比如我们高考时的排名,大学学校水平的排名等,打开京东,可以发现每样商品按照不同的方式排序,比如综合,销量,价格。其内部需要排序代码来完成。二、常见的排序算法一、交换排序一、冒泡排序冒泡排序是一种最容易想到的排序,但是其效率不高,没有实......
  • 进程间的通信(信号通信)
    进程间的通信(信号通信)进程的信号通信是操作系统中进程间通信(IPC)的一种方式,它允许一个进程向另一个进程发送一个信号,从而改变另一个进程的状态或执行某个操作。信号是异步的,意味着信号的发送和接收并不依赖于接收进程的执行状态。信号通信的基本概念信号类型:操作系统定义了一系......
  • 「C++」论高精度
    大家好,我是Charzie。在编程领域,高精度计算是一个常见的问题。当标准的整型或浮点型无法满足我们的计算需求时,高精度计算就显得尤为重要。在C++中,虽然标准库没有直接提供高精度数据类型,但我们可以通过一些技巧和工具类来实现高精度计算。为什么需要高精度?在编程中,我们经常会遇到......
  • 代码随想录算法训练营 第一天 704 二分查找 27 移除元素
    leetcode704 二分查找704二分查找思想:二分法简单二分问题注意二分问题有很多模式,二分问题查找核心是区间问题注意所学两种写法:区间左闭右开  区间左闭右闭二分查找问题 classSolution{publicintsearch(int[]nums,inttarget){if(target>nu......
  • 【Java】JVM字节码分析
    一、功能1、工作原理2、解释和运行jvm本质上是运行在计算机上的程序,负责运行java字节码文件对字节码文件中的指令,实时的解释成机器码,供计算机执行3、内存管理自动为对象、方法等分配内存自动垃圾回收机制,回收不再使用的对象4、即时编译在java中每次执行都需要实时解释......