『减而治之』题解 | #螺旋矩阵#
螺旋矩阵
http://www.nowcoder.com/practice/7edf70f2d29c4b599693dc3aaeea1d31
01.分治法和减治法区分
- 参考自『维基百科 』
- 分治法这个名称有时亦会用于将问题简化为只有一个细问题的算法,例如用于在已排序的列中查找其中一项的折半搜索算法(或是在数值分析中类似的勘根算法)。这些算法比一般的分治算法更能有效地运行。其中,假如算法使用尾部递归的话,便能转换成简单的循环。但在这广义之下,所有使用递归或循环的算法均被视作“分治算法”。
- 因此,有些作者考虑“分治法”这个名称应只用于每个有最少两个子问题的算法。而只有一个子问题的曾被建议使用减治法这个名称。
02.减治法思路的代码
class Solution { public: vector<int> spiralOrder(vector<vector<int> > &matrix) { vector<int> res; if( 0==matrix.size() ) { return res; } //左上和右下2个点确定一个矩形 int LeftUpRow=0,LeftUpCol=0; int RightDownRow=matrix.size()-1,RightDownCol=matrix[0].size()-1; //开始『减而治之』的遍历 while( LeftUpRow<=RightDownRow && LeftUpCol<=RightDownCol ) { for(int loop=LeftUpCol; loop<=RightDownCol; ++loop) { res.push_back( matrix[LeftUpRow][loop] ); } ++LeftUpRow;//遍历完一行之后,将左上角的点移动位置『减而治之』 //易错,比如[ [2,3] ]这样的样例 if( LeftUpRow>RightDownRow || LeftUpCol>RightDownCol ) break; for(int loop=LeftUpRow; loop<=RightDownRow; ++loop) { res.push_back( matrix[loop][RightDownCol] ); } --RightDownCol; if( LeftUpRow>RightDownRow || LeftUpCol>RightDownCol ) break; for(int loop=RightDownCol; loop>=LeftUpCol; --loop) { res.push_back( matrix[RightDownRow][loop] ); } --RightDownRow; if( LeftUpRow>RightDownRow || LeftUpCol>RightDownCol ) break; for(int loop=RightDownRow; loop>=LeftUpRow; --loop) { res.push_back( matrix[loop][LeftUpCol] ); } ++LeftUpCol; } return res; } };