『减而治之』题解 | #螺旋矩阵#

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;
    }
};