面试题29:顺时针打印矩阵

顺时针打印矩阵

题目描述leetcode 螺旋矩阵leetcode 螺旋矩阵2leetcode 螺旋矩阵3

题目描述

输入一个矩阵，从外到里以顺时针顺序依次打印

思路：将其看作一圈一圈打印

开始：(start, start)坐标，(0, 0), (1, 1),(2,2)…终止打印一圈的条件：cols>startx2, rows>starty2如何打印一圈？ 从左到右：总需要从上到下：起始行号>终止行号从右到左：圈内至少两行两列从下到上：至少三行两列 void PrintMatrixClockwisely(int **numbers, int columns, int rows) { if(numbers == nullptr || columns<0 ||rows<0) return; int start = 0; while(start *2 < rows && start *2 < columns) { PrintMatixInCircle(numbers, colunmns, rows, start); start++; } } void PrintMatixInCircle(int **numbers,int columns, int rows, int start) { int endX = columns - 1 - start; int endY = rows - 1 - start; //从左到右 for(int i=start; i<=endX; ++i) { int number = numbers[start][i] printNumber(number); } //从上到下 if(start < endY) { for(int i=start + 1; i<=endY; i++) { int number = numbers[i][endX]; printNumber(number); } } //从右到左 if(endX - start >=1 && endY-start >=1) { for(int i=endX-1; i>=start; i--) { int number = numbers[endY][i]; printNumber(number); } } //从下到上 if(start<endX && start<endY-1) { for(int i=endY-1; i>=start; i--) { int number = numbers[i][start]; printNumber(number); } } }

leetcode 螺旋矩阵

螺旋矩阵 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。 vector<int> spiralOrder(vector<vector<int>>& matrix) { vector<int>res; int rows = matrix.size(); if(rows<=0) return res; int cols = matrix[0].size(); if(cols<=0) return res; int start=0; while(start * 2 <rows && start*2<cols) { int endX = cols - 1 - start; int endY = rows - 1 - start; for(int i=start; i<=endX; i++) { res.push_back(matrix[start][i]); } if(start<endY) { for(int i=start+1; i<=endY;i++) { res.push_back(matrix[i][endX]); } } if(start<endX && start<endY) { for(int i=endX-1; i>=start; i--) { res.push_back(matrix[endY][i]); } } if(start<endX && start<endY - 1) { for(int i=endY - 1; i>start; i--) { res.push_back(matrix[i][start]); } } start ++; } return res; }

执行用时 : 4 ms, 在Spiral Matrix的C++提交中击败了97.17% 的用户 内存消耗 : 8.8 MB, 在Spiral Matrix的C++提交中击败了17.53% 的用户

leetcode 螺旋矩阵2

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

思路同上

vector<vector<int>> generateMatrix(int n) { vector<vector<int >>res(n, vector<int>(n, 0)); if(n==0) return res; int rows = n, cols = n; int num=1; int start =0; while(num<=n*n) { int endX = cols - start -1; int endY = rows - start -1; for(int i=start; i<=endX; i++) { res[start][i] = num; num++; } if(start < endY) { for(int i=start+1; i<=endY; i++) { res[i][endX] = num; num++; } } if(start<endX && start<endY) { for(int i=endX-1; i>=start; i--) { res[endY][i] = num; num++; } } if(start<endX && start<endY - 1) { for(int i=endY - 1; i>start; i--) { res[i][start]=num; num++; } } start ++; } return res; }

执行用时 : 8 ms, 在Spiral Matrix II的C++提交中击败了95.63% 的用户 内存消耗 : 9 MB, 在Spiral Matrix II的C++提交中击败了50.19% 的用户

leetcode 螺旋矩阵3

螺旋矩阵 III 在 R 行 C 列的矩阵上，我们从 (r0, c0) 面朝东面开始 这里，网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。 现在，我们以顺时针按螺旋状行走，访问此网格中的每个位置。 每当我们移动到网格的边界之外时，我们会继续在网格之外行走（但稍后可能会返回到网格边界）。 最终，我们到过网格的所有 R * C 个空间。 按照访问顺序返回表示网格位置的坐标列表。

思路同上，但是加入了左边界判断

bool legPosition(int R, int C, int r0, int c0) { if(r0 < R && c0 < C && r0>=0 && c0>=0) return true; return false; } vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) { vector<vector<int> >res(R, vector<int>(C, 0)); if(R<=0 || C<=0) return res; int num = 1; int count = 1; int circle = 1; int startX = c0, startY = r0; while(num<=R*C) { int leftX = startX - 1 ; int leftY = startY - 1; int rightX = startX + circle*2 - 1; int rightY = startY + circle*2 - 1; for(int i=startX; i<=rightX; i++) { if(legPosition(R, C, startY, i)) { res[startY][i] = num; num++; } } if(startY<rightY) { for(int i=startY+1; i<=rightY; i++) { if(legPosition(R, C, i, rightX)) { res[i][rightX] = num; num++; } } } if(leftY < rightY && leftX <rightX) { for(int i=rightX-1; i>=leftX ;i--) { if(legPosition(R, C, rightY, i)) { res[rightY][i] = num; num++; } } } if(leftX<rightX && leftY<rightY - 1) { for(int i=rightY - 1; i>leftY; i--) { if(legPosition(R, C, i, leftX)) { res[i][leftX] = num; num++; } } } circle ++; startX --; startY --; } return res; }

执行用时 : 84 ms, 在Spiral Matrix III的C++提交中击败了98.51% 的用户 内存消耗 : 13.8 MB, 在Spiral Matrix III的C++提交中击败了71.88% 的用户