Massive Algorithms: LeetCode 54

LeetCode 54 - Spiral Matrix

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].


1. m和n可以不同，所以对于第i层来说，最后一行为lastRow = m-1-i，而最后一列为lastCol = n-1-i。所以层数由min(m,n)决定。

2. 当min(m,n)为奇数时，最后一层为一行或一列，需要特殊处理。

https://leetcode.com/problems/spiral-matrix/discuss/20599/Super-Simple-and-Easy-to-Understand-Solution

This is a very simple and easy to understand solution. I traverse right and increment rowBegin, then traverse down and decrement colEnd, then I traverse left and decrement rowEnd, and finally I traverse up and increment colBegin.

The only tricky part is that when I traverse left or up I have to check whether the row or col still exists to prevent duplicates. If anyone can do the same thing without that check,

    public List<Integer> spiralOrder(int[][] matrix) {
        
        List<Integer> res = new ArrayList<Integer>();
        
        if (matrix.length == 0) {
            return res;
        }
        
        int rowBegin = 0;
        int rowEnd = matrix.length-1;
        int colBegin = 0;
        int colEnd = matrix[0].length - 1;
        
        while (rowBegin <= rowEnd && colBegin <= colEnd) {
            // Traverse Right
            for (int j = colBegin; j <= colEnd; j ++) {
                res.add(matrix[rowBegin][j]);
            }
            rowBegin++;
            
            // Traverse Down
            for (int j = rowBegin; j <= rowEnd; j ++) {
                res.add(matrix[j][colEnd]);
            }
            colEnd--;
            
            if (rowBegin <= rowEnd) {
                // Traverse Left
                for (int j = colEnd; j >= colBegin; j --) {
                    res.add(matrix[rowEnd][j]);
                }
            }
            rowEnd--;
            
            if (colBegin <= colEnd) {
                // Traver Up
                for (int j = rowEnd; j >= rowBegin; j --) {
                    res.add(matrix[j][colBegin]);
                }
            }
            colBegin ++;
        }
        
        return res;
    }

https://leetcode.com/articles/spiral-matrix/

public List<Integer> spiralOrder(int[][] matrix) {

List ans = new ArrayList();

if (matrix.length == 0)

return ans;

int r1 = 0, r2 = matrix.length - 1;

int c1 = 0, c2 = matrix[0].length - 1;

while (r1 <= r2 && c1 <= c2) {

for (int c = c1; c <= c2; c++)

ans.add(matrix[r1][c]);

for (int r = r1 + 1; r <= r2; r++)

ans.add(matrix[r][c2]);

if (r1 < r2 && c1 < c2) {

for (int c = c2 - 1; c > c1; c--)

ans.add(matrix[r2][c]);

for (int r = r2; r > r1; r--)

ans.add(matrix[r][c1]);

}

r1++;

r2--;

c1++;

c2--;

}

return ans;

}

http://www.cnblogs.com/yuzhangcmu/p/4046543.html

http://www.gaoshenghan.me/2014/12/leetcode-59-spiral-matrix.html

The solution is easy to understand, just iterate upper left -> upper right -> lower right -> lower -> left -> upper left. So we need four variable top, button, left, right to shrink to center step by step. The only tricky part is when we move from right to left and button to top, we should check if there are still space for this two operations.


vector<int> spiralOrder(vector<vector<int> > &matrix) {

    vector<int> result;

    if (matrix.size() < 1) 

        return result;

    int top = 0;

    int button = matrix.size() - 1;

    int left = 0;

    int right = matrix[0].size() - 1;

    while (top <= button && left <= right) {

        for (int x = left; x <= right; x++) { //left to right

            result.push_back(matrix[top][x]);

        }

        top++;



        for (int y = top; y <= button; y++) { //top to button

            result.push_back(matrix[y][right]);

        }

        right--;

        if (button >= top) { // check if the button line haven't been pushed

            for (int x = right; x >= left; x--) {

                result.push_back(matrix[button][x]);

            }

            button--;

        }



        if (right >= left) { //check if the left line haven't been pushed

            for (int y = button; y >= top; y--) {

                result.push_back(matrix[y][left]);

            }

            left++;

        }



    }

    return result;

}

http://bangbingsyb.blogspot.com/2014/11/leetcode-spiral-matrix-i-ii.html

Iterative Version:

    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(matrix == null || matrix.length == 0) return result;
        int m = matrix.length;
        int n = matrix[0].length;
        int x=0; 
        int y=0;
        while(m>0 && n>0){
 
            //if one row/column left, no circle can be formed
            if(m==1){
                for(int i=0; i<n; i++){
                    result.add(matrix[x][y++]);
                }
                break;
            }else if(n==1){
                for(int i=0; i<m; i++){
                    result.add(matrix[x++][y]);
                }
                break;
            }
            //below, process a circle
            //top - move right
            for(int i=0;i<n-1;i++){
                result.add(matrix[x][y++]);
            }
            //right - move down
            for(int i=0;i<m-1;i++){
                result.add(matrix[x++][y]);
            }
            //bottom - move left
            for(int i=0;i<n-1;i++){
                result.add(matrix[x][y--]);
            }
            //left - move up
            for(int i=0;i<m-1;i++){
                result.add(matrix[x--][y]);
            }
            x++;
            y++;
            m=m-2;
            n=n-2;
        }
 
        return result;
    }

Recursive Version

public ArrayList<Integer> spiralOrder(int[][] matrix) {
        if(matrix==null || matrix.length==0) 
            return new ArrayList<Integer>();
        return spiralOrder(matrix,0,0,matrix.length,matrix[0].length);
    }
    public ArrayList<Integer> spiralOrder(int [][] matrix, int x, int y, int m, int n){
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(m<=0||n<=0) 
            return result;
        //only one element left
        if(m==1&&n==1) {
            result.add(matrix[x][y]);
            return result;
        }
        //top - move right
        for(int i=0;i<n-1;i++){
            result.add(matrix[x][y++]);
        }
        //right - move down
        for(int i=0;i<m-1;i++){
            result.add(matrix[x++][y]);
        }
        //bottom - move left
        if(m>1){    
            for(int i=0;i<n-1;i++){
                result.add(matrix[x][y--]);
            }
        }
        //left - move up
        if(n>1){
            for(int i=0;i<m-1;i++){
                result.add(matrix[x--][y]);
            }
        }
        if(m==1||n==1)
            result.addAll(spiralOrder(matrix, x, y, 1, 1));
        else    
            result.addAll(spiralOrder(matrix, x+1, y+1, m-2, n-2));
        return result;
    }

http://javabypatel.blogspot.com/2016/11/print-matrix-in-spiral-order-recursion.html

 private void printMatrixInSpiralWayUsingRecursion(int[][] matrix, int rowStart, int colStart, int colLength,  int rowLength){

  for (int i = rowStart; i <= colLength; i++) {

   System.out.print(matrix[rowStart][i] + " ");

}

  for (int i = rowStart+1; i <= rowLength; i++) {

   System.out.print(matrix[i][colLength] + " ");

}

  if(rowStart+1 <= rowLength){

   for (int i = colLength-1; i >= colStart; i--) {

    System.out.print(matrix[rowLength][i] + " ");

}

}

  if(colStart+1 <= colLength){

   for (int i = rowLength-1; i > rowStart; i--) {

    System.out.print(matrix[i][colStart] + " ");

}

}

  if(rowStart+1 <= rowLength-1 && colStart+1 <= colLength-1){

   printMatrixInSpiralWayUsingRecursion(matrix, rowStart+1, colStart+1, colLength-1, rowLength-1);

}

}

http://www.programcreek.com/2013/01/leetcode-spiral-matrix-java/

    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> result = new ArrayList<Integer>();
 
        if(matrix == null || matrix.length == 0) return result;
 
        int m = matrix.length;
        int n = matrix[0].length;
 
        int x=0; 
        int y=0;
 
        while(m>0 && n>0){
 
            //if one row/column left, no circle can be formed
            if(m==1){
                for(int i=0; i<n; i++){
                    result.add(matrix[x][y++]);
                }
                break;
            }else if(n==1){
                for(int i=0; i<m; i++){
                    result.add(matrix[x++][y]);
                }
                break;
            }
 
            //below, process a circle
 
            //top - move right
            for(int i=0;i<n-1;i++){
                result.add(matrix[x][y++]);
            }
 
            //right - move down
            for(int i=0;i<m-1;i++){
                result.add(matrix[x++][y]);
            }
 
            //bottom - move left
            for(int i=0;i<n-1;i++){
                result.add(matrix[x][y--]);
            }
 
            //left - move up
            for(int i=0;i<m-1;i++){
                result.add(matrix[x--][y]);
            }
 
            x++;
            y++;
            m=m-2;
            n=n-2;
        }
 
        return result;
    }

    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        if(matrix==null || matrix.length==0) 
            return new ArrayList<Integer>();
 
        return spiralOrder(matrix,0,0,matrix.length,matrix[0].length);
    }
 
 
    public ArrayList<Integer> spiralOrder(int [][] matrix, int x, int y, int m, int n){
        ArrayList<Integer> result = new ArrayList<Integer>();
 
        if(m<=0||n<=0) 
            return result;
 
        //only one element left
        if(m==1&&n==1) {
            result.add(matrix[x][y]);
            return result;
        }
 
        //top - move right
        for(int i=0;i<n-1;i++){
            result.add(matrix[x][y++]);
        }
 
        //right - move down
        for(int i=0;i<m-1;i++){
            result.add(matrix[x++][y]);
        }
 
        //bottom - move left
        if(m>1){    
            for(int i=0;i<n-1;i++){
                result.add(matrix[x][y--]);
            }
        }
 
        //left - move up
        if(n>1){
            for(int i=0;i<m-1;i++){
                result.add(matrix[x--][y]);
            }
        }
 
        if(m==1||n==1)
            result.addAll(spiralOrder(matrix, x, y, 1, 1));
        else    
            result.addAll(spiralOrder(matrix, x+1, y+1, m-2, n-2));
 
        return result;
    }

X. http://www.cnblogs.com/grandyang/p/4362675.html

这道题让我们将一个矩阵按照螺旋顺序打印出来，我们只能一条边一条边的打印，首先我们要从给定的mxn的矩阵中算出按螺旋顺序有几个环，注意最终间的环可以是一个数字，也可以是一行或者一列。环数的计算公式是 min(m, n) / 2，知道了环数，我们可以对每个环的边按顺序打印，比如对于题目中给的那个例子，个边生成的顺序是(用颜色标记了数字) Red -> Green -> Blue -> Yellow -> Black

1　2　3

4　5　6

7　8　9

我们定义p，q为当前环的高度和宽度，当p或者q为1时，表示最后一个环只有一行或者一列，可以跳出循环。此题的难点在于下标的转换，如何正确的转换下标是解此题的关键，我们可以对照着上面的3x3的例子来完成下标的填写，代码如下：

    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        int m = matrix.size(), n = matrix[0].size();
        vector<int> res;
        int c = m > n ? (n + 1) / 2 : (m + 1) / 2;
        int p = m, q = n;
        for (int i = 0; i < c; ++i, p -= 2, q -= 2) {
            for (int col = i; col < i + q; ++col) 
                res.push_back(matrix[i][col]);
            for (int row = i + 1; row < i + p; ++row)
                res.push_back(matrix[row][i + q - 1]);
            if (p == 1 || q == 1) break;
            for (int col = i + q - 2; col >= i; --col)
                res.push_back(matrix[i + p - 1][col]);
            for (int row = i + p - 2; row > i; --row) 
                res.push_back(matrix[row][i]);
        }
        return res;
    }

http://www.cnblogs.com/graphics/archive/2010/06/05/1739658.html
与从外向内填充不同的是，边界判断中不会再出现下标越界的情况，只需判断当前位置是否填充过即可
方向转换
从内向外填充时，能转向时优先转向，不能转向时才继续向前填充，而从外向内填充则恰恰相反，无法继续向前填充时才转向。

http://comproguide.blogspot.com/2013/11/printing-matrix-in-spiral-order.html
No need to use direction, just loop first row/column, last row/column in one loop.
Also refer to http://leetcode.com/2010/05/printing-matrix-in-spiral-order.html
http://www.geeksforgeeks.org/print-a-given-matrix-in-spiral-form/

https://www.cnblogs.com/lightwindy/p/8564387.html

解法：用变量left, right, top, bottom记录左，右，顶，底。然后按照左到右，顶到底，右到左，底到顶的顺序循环，把遍历的元素加入到结果。

    public List<Integer> spiralOrder(int[][] matrix) {

        List<Integer> res = new ArrayList<>();

        if(matrix == null || matrix.length == 0)

            return res;

        int rowNum = matrix.length, colNum = matrix[0].length;

        int left = 0, right = colNum - 1, top = 0, bot = rowNum - 1;

        while(res.size() < rowNum * colNum) {

            for(int col = left; col <= right; col++)

                res.add(matrix[top][col]);

            top++;

            if(res.size() < rowNum * colNum) {

                for(int row = top; row <= bot; row++)

                    res.add(matrix[row][right]);

                right--;   

            }

            if(res.size() < rowNum * colNum) {

                for(int col = right; col >= left; col--)

                    res.add(matrix[bot][col]);

                bot--;

            }

            if(res.size() < rowNum * colNum) {

                for(int row = bot; row >= top; row--)

                    res.add(matrix[row][left]);

                left++;

            }

        }

        return res;

    }

X.

https://www.jianshu.com/p/6ae7cb8f8532
最关键的还是理解终止条件与边界条件的判断

一般走path的题，都可以用dir变量表示上下左右的方向。除此之外，本题的关键是理解终止条件：

行或列均没有格子可以走了！！！

那到底每行与每列可以走多少格子呢？

以row为例：

假设有0~m-1一共m行，已经走了r行，

那么还可以走m-r个格子。

从遍历一开始，有m个格子可以走，到最后只剩0个的时候跳出循环！
思路二：

和之前的一样，但可以略去dir变量，因为本题遍历方向的变化是存在规律的，即行向右，列向下，行向左，列向上，因此用一个循环模拟这四个步骤即可。关键还是判断什么时候终止，且每次走几步。要明白每完成一次行扫描或列扫描，对应的需要扫描的行数与列数都减1！！！

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> path = new ArrayList<>();
        if (matrix.length == 0) return path;
        
        int rowStart = 0, rowEnd = matrix.length-1, colStart = 0, colEnd = matrix[0].length-1;
             
        // Until it reach the spiral center that is rowStart > rowEnd or colStart > colEnd
        while (true) {
            // Right
            for (int j = colStart; j <= colEnd; j++) {
                path.add(matrix[rowStart][j]);
            }
            rowStart++;
            if (rowStart > rowEnd) break;
            
            // Down
            for (int i = rowStart; i <= rowEnd; i++) {
                path.add(matrix[i][colEnd]);
            }
            colEnd--;
            if (colStart > colEnd) break;
            
            // Left
            for (int j = colEnd; j >= colStart; j--) {
                path.add(matrix[rowEnd][j]);
            }
            rowEnd--;
            if (rowStart > rowEnd) break;
            
            // Up
            for (int i = rowEnd; i >= rowStart; i--) {
                path.add(matrix[i][colStart]);
            }
            colStart++;
            if (colStart > colEnd) break;
        }
        
        return path;
    }

https://leetcode.com/articles/spiral-matrix/
Approach 1: Simulation

Draw the path that the spiral makes. We know that the path should turn clockwise whenever it would go out of bounds or into a cell that was previously visited.

Let the array have

\text{R}

rows and

\text{C}

columns.

\text{seen[r][c]}

denotes that the cell on the

\text{r}

-th row and

\text{c}

-th column was previously visited. Our current position is

\text{(r, c)}

, facing direction

\text{di}

, and we want to visit

\text{R}

\text{C}

total cells.

As we move through the matrix, our candidate next position is

\text{(cr, cc)}

. If the candidate is in the bounds of the matrix and unseen, then it becomes our next position; otherwise, our next position is the one after performing a clockwise turn.

public List<Integer> spiralOrder(int[][] matrix) {

List ans = new ArrayList();

if (matrix.length == 0)

return ans;

int R = matrix.length, C = matrix[0].length;

boolean[][] seen = new boolean[R][C];

int[] dr = { 0, 1, 0, -1 };

int[] dc = { 1, 0, -1, 0 };

int r = 0, c = 0, di = 0;

for (int i = 0; i < R * C; i++) {

ans.add(matrix[r][c]);

seen[r][c] = true;

int cr = r + dr[di];

int cc = c + dc[di];

if (0 <= cr && cr < R && 0 <= cc && cc < C && !seen[cr][cc]) {

r = cr;

c = cc;

} else {

di = (di + 1) % 4;

r += dr[di];

c += dc[di];

}

return ans;

}

X. http://noahsnail.com/2018/12/12/2018-12-12-Leetcode-54--Spiral-Matrix/


vector<int> spiralOrder(vector<vector<int>>& matrix) {

vector<int> result;

int rows = matrix.size();

if(rows == 0) {

return result;

}

int columns = matrix[0].size();

int total = rows * columns;

for(int i = 0, j = 0; result.size() < total; i++, j++) {

if(result.size() < total) {

// top

for(int k = j; k < columns - j; k++) {

result.push_back(matrix[i][k]);

}

}

if(result.size() < total) {

// right

for(int k = i + 1; k < rows - i; k++) {

result.push_back(matrix[k][columns - 1 - j]);

}

}

if(result.size() < total) {

// bottom

for(int k = columns - 2 - j; k >= j; k--) {

result.push_back(matrix[rows - 1 - i][k]);

}

}

if(result.size() < total) {

// left

for(int k = rows - 2 - i; k > i; k--) {

result.push_back(matrix[k][j]);

}

}

}

return result;

}

https://leetcode.com/problems/spiral-matrix/discuss/20573/A-concise-C%2B%2B-implementation-based-on-Directions

When traversing the matrix in the spiral order, at any time we follow one out of the following four directions: RIGHT DOWN LEFT UP. Suppose we are working on a 5 x 3 matrix as such:

0 1 2 3 4 5
6 7 8 9 10
11 12 13 14 15

Imagine a cursor starts off at (0, -1), i.e. the position at '0', then we can achieve the spiral order by doing the following:

Go right 5 times
Go down 2 times
Go left 4 times
Go up 1 times.
Go right 3 times
Go down 0 times -> quit

Notice that the directions we choose always follow the order 'right->down->left->up', and for horizontal movements, the number of shifts follows:{5, 4, 3}, and vertical movements follows {2, 1, 0}.

Thus, we can make use of a direction matrix that records the offset for all directions, then an array of two elements that stores the number of shifts for horizontal and vertical movements, respectively. This way, we really just need one for loop instead of four.

Another good thing about this implementation is that: If later we decided to do spiral traversal on a different direction (e.g. Counterclockwise), then we only need to change the Direction matrix; the main loop does not need to be touched.

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<vector<int> > dirs{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    vector<int> res;
    int nr = matrix.size();     if (nr == 0) return res;
    int nc = matrix[0].size();  if (nc == 0) return res;
    
    vector<int> nSteps{nc, nr-1};
    
    int iDir = 0;   // index of direction.
    int ir = 0, ic = -1;    // initial position
    while (nSteps[iDir%2]) {
        for (int i = 0; i < nSteps[iDir%2]; ++i) {
            ir += dirs[iDir][0]; ic += dirs[iDir][1];
            res.push_back(matrix[ir][ic]);
        }
        nSteps[iDir%2]--;
        iDir = (iDir + 1) % 4;
    }
    return res;
}

LeetCode 54 - Spiral Matrix

Labels

Popular Posts