leetcode Spiral Matrix

题目：螺旋输出数组（听师兄说是今年google电话面试题）

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

定义四个变量，上下左右，别人记录螺旋到的界限。到每一个边界，都需要判断是否遍历完。我用的是每个边界条件的判断。详见代码。leetcode的时间估计是不怎么准的，加了注释之后，说只运行了4ms。

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) 
    {
        vector<int> ans;
        if (matrix.size() == 0)
            return ans;
        int i = 0, j = 0, prei = -1, prej = -1, left = 0, up = 0, right = matrix[0].size() - 1, down = matrix.size() - 1;
        while(left <= right && up <= down)
        {
            prei += 1; prej += 1;
            i = prei; j = prej; // 绕一圈回来，如果还能继续走，那么下一个起点肯定是在之前起点右下方
            while(j <= right)
            {
                ans.push_back(matrix[i][j]); j++; // 把这一行输出
            }
            j--; i++;
            if (down == up) return ans; // 如果up和down属于同于一排了，说明无需再向下了
            while(i <= down)
            {
                ans.push_back(matrix[i][j]); i++;// 把最后一列输出（不包括和刚才输出行的最后一个）
            }
            i--; j--;
            if (left == right) return ans;// 如果左右相等了，说明无需再向左了
            while(j >= left)
            {
                ans.push_back(matrix[i][j]); j--;// 把左后一行向左输出
            }
            if (down == up + 1) return ans; // 满足这个时，已经不能再向上了
            j++; i--;
            while(i > up)
            {
                ans.push_back(matrix[i][j]); i--; // 把最左边一列输出
            }
            if (left == right - 1) return ans;//满足这个说明已经不能再向右了
            left++; right--; up++; down--;//更新各个值
        }
        return ans;
    }
};

其实也可以用一个cnt变量记录，如果cnt等于总的元素个数就结束。基本代码和上述一样，如下折叠代码。

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) 
    {
        vector<int> ans;
        if (matrix.size() == 0)
            return ans;
        int cnt = 0, i = 0, j = 0, prei = -1, prej = -1, left = 0, up = 0, right = matrix[0].size() - 1, down = matrix.size() - 1;
        int total = (matrix.size())*(matrix[0].size());
        while(left <= right && up <= down)
        {
            prei += 1; prej += 1;
            i = prei; j = prej; // 绕一圈回来，如果还能继续走，那么下一个起点肯定是在之前起点右下方
            while(j <= right)
            {
                ans.push_back(matrix[i][j]);cnt++;j++; // 把这一行输出
            }
            j--; i++;
            if (cnt == total) return ans;// 
            while(i <= down)
            {
                ans.push_back(matrix[i][j]);cnt++; i++;// 把最后一列输出（不包括和刚才输出行的最后一个）
            }
            i--; j--;
            if (cnt == total) return ans;// 
            while(j >= left)
            {
                ans.push_back(matrix[i][j]); cnt++;j--;// 把左后一行向左输出
            }
            if (cnt == total)  return ans; // 
            j++; i--;
            while(i > up)
            {
                ans.push_back(matrix[i][j]); cnt++; i--;// 把最左边一列输出
            }
            if (cnt == total) return ans;//
            left++; right--; up++; down--;//更新各个值
        }
        return ans;
    }
};