汉扬编程 C语言入门 leetcode C++题解系列-053 螺旋矩阵

leetcode C++题解系列-053 螺旋矩阵

leetcode C++题解系列-053 螺旋矩阵

题目给定一个包含 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,12,11,10,9,5,6,7]解题代码与测试//// Created by tannzh on 2020/7/13.///* 螺旋矩阵 *给定一个包含 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,12,11,10,9,5,6,7] */#include <iostream>#include <vector>using std::vector;class Solution {public: vector<int> spiralOrder(vector<vector<int>>& matrix) { vector<int> ret; if (matrix.empty()) return ret; int mMax = matrix.size(); int nMax = matrix[0].size(); int mMin = 0, nMin = 0; ret.reserve(mMax*nMax); for (; nMin<mMax && nMin<nMax; –mMax, –nMax, ++mMin, ++nMin) { for (int i=nMin; i<nMax; ++i) ret.push_back(matrix[mMin][i]); for (int i=mMin+1; i<mMax; ++i) ret.push_back(matrix[i][nMax-1]); if (mMax-1 == mMin) break; for (int i=nMax-2; i>=nMin; –i) ret.push_back(matrix[mMax-1][i]); if (nMax-1 == nMin) break; for (int i=mMax-2; i>mMin; –i) ret.push_back(matrix[i][nMin]); } return ret; }};int main(int argc, char **argv){ std::vector<std::vector<int>> matrix = { {1,2,3}, {4,5,6}, {7,8,9} }; Solution s; auto result = s.spiralOrder(matrix); for(auto item : result) { std::cout << item << ", "; } std::cout << std::endl; return 0;}解题思路分析m * n 的矩阵按螺旋顺序转为数组:

1 2 34 5 6 –> 1 2 3 6 9 8 7 4 57 8 9我想到的是,直接用下标作为限制。m 行,n 列,即范围:

row: 0 ~ mcol: 0 ~ n首先是列递增,(0,0), (0,1), (0,2). 然后行递增,(1,2), (2,2). 再后是列递减,(2,1), (2,0). 和行递减,(1,0). 最后进入下一螺旋:(1,1). 到此为止,全部数组都迭代出来。

可以发现的规律是,每一次螺旋,都按照以下顺序:

列递增 (row 降到最低)行递增 (col 增到最高)列递减 (row 增到最高)行递减 (col 降到最低)写成 for 循环的形式,则为:

for (; nMin<mMax && nMin<nMax; –mMax, –nMax, ++mMin, ++nMin) { for (int i=nMin; i<nMax; ++i) ret.push_back(matrix[mMin][i]); for (int i=mMin+1; i<mMax; ++i) ret.push_back(matrix[i][nMax-1]); for (int i=nMax-2; i>=nMin; –i) ret.push_back(matrix[mMax-1][i]); for (int i=mMax-2; i>mMin; –i) ret.push_back(matrix[i][nMin]);}除此之外,需要增加一些边界条件判断:

n = matrix[0].size(); // 要提前判断 matrix.empty()第三个 for 循环要避免重复,如仅有一行的情况,列递增之后,没有行递增,直接就列递减了,那必然重复。判断 mMax-1 != mMin.第四个 for 循环同理,避免行重复,判断 nMax-1 != nMin.

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/cjia/6835.html

(一定要懂你的点)为什么建议你一定要学懂C++

为什么建议你一定要学懂C++

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部