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

螺旋矩阵

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;
    }
};
全部评论

相关推荐

找不到工作死了算了:没事的,雨英,hr肯主动告知结果已经超越大部分hr了
点赞 评论 收藏
分享
不想再科研:如果是假的,希望是真的,如果是真的,希望是假的
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务