C++实现LeetCode(59.螺旋矩阵之二)

[LeetCode] 59. Spiral Matrix II 螺旋矩阵之二

Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

Example:

Input: 3
Output:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]

此题跟之前那道 Spiral Matrix 本质上没什么区别,就相当于个类似逆运算的过程,这道题是要按螺旋的顺序来填数,由于给定矩形是个正方形,我们计算环数时用 n / 2 来计算,若n为奇数时,此时最中间的那个点没有被算在环数里,所以最后需要单独赋值,还是下标转换问题是难点,参考之前 Spiral Matrix 的讲解来转换下标吧,参见代码如下:

解法一:

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n));
        int val = 1, p = n;
        for (int i = 0; i < n / 2; ++i, p -= 2) {
            for (int col = i; col < i + p; ++col)
                res[i][col] = val++;
            for (int row = i + 1; row < i + p; ++row)
                res[row][i + p - 1] = val++;
            for (int col = i + p - 2; col >= i; --col)
                res[i + p - 1][col] = val++;
            for (int row = i + p - 2; row > i; --row)
                res[row][i] = val++;
        }
        if (n % 2 != 0) res[n / 2][n / 2] = val;
        return res;
    }
};

当然我们也可以使用下面这种简化了坐标转换的方法,博主个人还是比较推崇下面这种解法,不容易出错,而且好理解,参见代码如下:

解法二:

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n));
        int up = 0, down = n - 1, left = 0, right = n - 1, val = 1;
        while (true) {
            for (int j = left; j <= right; ++j) res[up][j] = val++;
            if (++up > down) break;
            for (int i = up; i <= down; ++i) res[i][right] = val++;
            if (--right < left) break;
            for (int j = right; j >= left; --j) res[down][j] = val++;
            if (--down < up) break;
            for (int i = down; i >= up; --i) res[i][left] = val++;
            if (++left > right) break;
        }
        return res;
    }
};

到此这篇关于C++实现LeetCode(59.螺旋矩阵之二)的文章就介绍到这了,更多相关C++实现螺旋矩阵之二内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++实现LeetCode(48.旋转图像)

    [LeetCode] 48. Rotate Image 旋转图像 You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Note: You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allo

  • C++实现LeetCode(57.插入区间)

    [LeetCode] 57. Insert Interval 插入区间 Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times. Example 1: Input: int

  • C++实现LeetCode(50.求x的n次方)

    [LeetCode] 50. Pow(x, n) 求x的n次方 Implement pow(x, n), which calculates x raised to the power n(xn). Example 1: Input: 2.00000, 10 Output: 1024.00000 Example 2: Input: 2.10000, 3 Output: 9.26100 Example 3: Input: 2.00000, -2 Output: 0.25000 Explanation

  • C++实现LeetCode(56.合并区间)

    [LeetCode] 56. Merge Intervals 合并区间 Given a collection of intervals, merge all overlapping intervals. Example 1: Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into

  • C++实现LeetCode(58.求末尾单词的长度)

    [LeetCode] 58. Length of Last Word 求末尾单词的长度 Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string. If the last word does not exist, return 0. Note: A word is defined as a

  • C++实现LeetCode(49.群组错位词)

    [LeetCode] 49. Group Anagrams 群组错位词 Given an array of strings, group anagrams together. Example: Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [ ["ate","eat",&quo

  • C++实现LeetCode(53.最大子数组)

    [LeetCode] 53. Maximum Subarray 最大子数组 Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. Example: Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1]

  • C++实现LeetCode(52.N皇后问题之二)

    [LeetCode] 52. N-Queens II N皇后问题之二 The n-queens puzzle is the problem of placing nqueens on an n×n chessboard such that no two queens attack each other. Given an integer n, return the number of distinct solutions to the n-queens puzzle. Example: Inpu

  • C++实现LeetCode(59.螺旋矩阵之二)

    [LeetCode] 59. Spiral Matrix II 螺旋矩阵之二 Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. Example: Input: 3 Output: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 此题跟之前那道 Spiral Matrix 本质上没什么区别,就相当于个类似逆

  • Java实现LeetCode(螺旋矩阵)

    LeetCode54. 螺旋矩阵 java实现 题目 难度 中 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素. 示例 1: 输入:  [   [ 1, 2, 3 ],   [ 4, 5, 6 ],   [ 7, 8, 9 ]  ]  输出: [1,2,3,6,9,8,7,4,5] 示例 2: 输入:  [    [1, 2, 3, 4],    [5, 6, 7, 8],    [9,10,11,12]  ] 输出: [1,2,3,4,8

  • Python使用迭代器打印螺旋矩阵的思路及代码示例

    思路 螺旋矩阵是指一个呈螺旋状的矩阵,它的数字由第一行开始到右边不断变大,向下变大, 向左变大,向上变大,如此循环. 螺旋矩阵用二维数组表示,坐标(x,y),即(x轴坐标,y轴坐标). 顺时针螺旋的方向是->右,下,左,上,用数值表示即是x加1格(1,0),y加1格(0,1),x减1格(-1,0),y减1格(0,-1). 坐标从(0,0)开始行走,当超出范围或遇到障碍时切换方向. 螺旋矩阵的打印首先要对n*n的数组进行赋值,根据规律可以看出,每一层都是按照右->下->左->上的顺序

  • Python实现打印螺旋矩阵功能的方法

    本文实例讲述了Python实现打印螺旋矩阵功能的方法.分享给大家供大家参考,具体如下: 一.问题描述 输入N, 打印 N*N 螺旋矩阵 比如 N = 3,打印: 1 2 3 8 9 4 7 6 5 N = 4,打印: 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 二.思路 常规法是不断的对数据边界进行判断会很复杂,不妨考虑通过递归的解决每一层的数字. 三.代码 #coding:utf-8 n = int(raw_input('>')) #初始化数组 arr = [

  • JavaScript定义及输出螺旋矩阵的方法详解

    本文实例讲述了JavaScript定义及输出螺旋矩阵的方法.分享给大家供大家参考,具体如下: 昨晚无意看到这样一个算法题目,然后就想着用js来实现. 昨晚草草写完后感觉代码很丑,很臭,于是今晚又花点时间重构了一下,感觉变得优雅了. 什么是螺旋矩阵 螺旋矩阵是指一个呈螺旋状的矩阵,它的数字由第一行开始到右边不断变大,向下变大,向左变大,向上变大,如此循环. 如图: 实现效果 实现代码 (function() { var map = (function() { function map(n) { t

  • Python实现螺旋矩阵的填充算法示例

    本文实例讲述了Python实现螺旋矩阵的填充算法.分享给大家供大家参考,具体如下: afanty的分析: 关于矩阵(二维数组)填充问题自己动手推推,分析下两个下表的移动规律就很容易咯. 对于螺旋矩阵,不管它是什么鬼,反正就是依次向右.向下.向右.向上移动. 向右移动:横坐标不变,纵坐标加1 向下移动:纵坐标不变,横坐标加1 向右移动:横坐标不变,纵坐标减1 向上移动:纵坐标不变,横坐标减1 代码实现: #coding=utf-8 import numpy ''''' Author: afanty

  • Java实现的打印螺旋矩阵算法示例

    本文实例讲述了Java实现的打印螺旋矩阵算法.分享给大家供大家参考,具体如下: 一个N阶矩阵顺时针呈螺旋状,形如下面的矩阵: 思路:使用一个二维数组存放数据,数组初始化为0,数组共有n平方个元素,因为是从1开始,所以元素的值是从1到n×n.按照上面的路线从1开始遍历一遍填入数据,每填入一个数据时后,判断边界和方向(说明,任意长度和宽度都可以使用这个思路,本例使用N*N的矩阵说明).直接上代码了: package study.haishen.com; /** * @author Administr

  • PHP实现蛇形矩阵,回环矩阵及数字螺旋矩阵的方法分析

    本文实例讲述了PHP实现蛇形矩阵,回环矩阵及数字螺旋矩阵的方法.分享给大家供大家参考,具体如下: 回环矩阵指的是一个从一开始,不断按照上.右.下.左顺序依次增大的矩阵序列,例: 1 2 3 8 9 4 7 6 5 现在要求: 输入: m.n,分别代表行数和列数 输出: m * n 的回环矩阵 例: 输入: 7 8 输出: 1 2 3 4 5 6 7 8 26 27 28 29 30 31 32 9 25 44 45 46 47 48 33 10 24 43 54 57 56 49 34 11 2

  • C语言 经典题目螺旋矩阵 实例详解

    C语言 经典题目螺旋矩阵 //N阶螺旋矩阵 #include <stdio.h> #include <stdlib.h> int main() { int N,i,j,n,num=1; int a[10][10]={0}; printf("输入你要输出的几阶中断:"); scanf("%d",&N); for(n=0;n<=N/2;n++) { for(j=n;j<=N-n-1;j++) a[n][j]=num++; fo

  • C++实现:螺旋矩阵的实例代码

    通过观察发现矩阵的下标有这样一个规律:a行递增后b列递增然后c行递减再d列递减,但是对应值却是逐渐增加的.因此可用4个循环实现,需要注意的是在赋值时不要把之前的值覆盖了.所以在这里选择相同顔色部分赋值,代码如下: 复制代码 代码如下: #include <iostream>#include <iomanip> using namespace std; // 输出螺旋矩阵void Matrix(){    const int size = 10; // 矩阵大小    int mat

随机推荐