185.矩阵的之字形遍历

题目

给你一个包含 m x n 个元素的矩阵 (m 行, n 列), 求该矩阵的之字型遍历。http://www.lintcode.com/zh-cn/problem/matrix-zigzag-traversal/

分析

之字型遍历的模式可以通过状态机来描述,它的变化过程如下:

  1. 起点在左上角
  2. 向右移动1位
  3. 向左下方移动,直至行或者列触底
    • 如果是移动到最左侧,那么下一步向下移动
    • 如果移动到最底侧,那么下一步向右移动
  4. 向右上方移动,直至行触顶或者列触边
    • 行触顶时,以当前点位起点,重新执行第1步
    • 列触边时,此时应当向下移动

只要已知当前的位置信息和移动方向,以及矩阵的信息,就可以推断出下一步的状态。因此,不妨使用Position类来表示当前的位置信息,移动方向只有四种值,可以用枚举来表示


 enum Direction {
    right, downleft, down, upright
}

class Position{
    int row, col;
    Direction direction;  // 0: right; 1: downleft; 2: down; 3: upright;

    Position(){
        this.row = 0;
        this.col = 0;
        this.direction = Direction.right;
    }
}

假设计算下一步状态的函数为zwalk,那么printZMatrix就可以实现为


 public int[] printZMatrix(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int total = rows * cols;
        Position position = new Position();
        int[] result = new int[total];
        int index = 0;
        while( position.col < cols && position.row < rows){
            result[index++] = matrix[position.row][position.col];
            position = zwalk(matrix, position);
        }
        result[rows * cols - 1] = matrix[rows-1][cols-1];

        return result;
    }

关键就是zwalk函数的实现了,它最重要的就是分析可能的状态变化情况,主要是触底、触边时的不同处理。


    Position zwalk(int[][] matrix, Position current){
        int rows = matrix.length;
        int cols = matrix[0].length;

        switch(current.direction){
            case right:
                if(current.col+1 < cols){
                    current.col++;
                    current.direction = Direction.downleft;
                }else{
                    current.direction = Direction.down;
                    return zwalk(matrix, current);
                }
                break;
            case downleft:
                if(current.col > 0 && current.row < rows - 1){
                    current.col--;
                    current.row++;
                }else{
                    if(current.row == rows - 1){
                        current.col++;
                        current.direction = Direction.upright;
                    }else if(current.col == 0){
                        current.direction = Direction.down;
                        return zwalk(matrix, current);
                    }else{
                        current.col = -1;
                        current.row = -1;
                    }
                }
                break;
            case down:
                if(current.col != cols -1){
                    if(current.row+1 < rows){
                        current.row++;
                        current.direction = Direction.upright;
                    }else{
                        current.col++;
                        current.direction = Direction.upright;
                    }
                }else{
                    current.row++;
                    current.direction = Direction.downleft;
                }

                break;
            case upright:
                if(current.row > 0 && current.col < cols - 1){
                    current.col++;
                    current.row--;
                }else{
                    if(current.col == cols - 1){
                        current.direction = Direction.down;
                        return zwalk(matrix, current);
                    }else if(current.row == 0){
                        current.direction = Direction.right;
                        return zwalk(matrix, current);
                    }else{
                        current.col = -1;
                        current.row = -1;
                    }
                }
                break;
            default:
                break;
        }
        return current;
    }

不涉及算法,主要就是理清楚状态变迁的几种情况。

代码

完整代码如下:



enum Direction {
    right, downleft, down, upright, start
}

class Position{
    int row, col;
    Direction direction;  // 0: right; 1: downleft; 2: down; 3: upright;
    
    Position(){
        this.row = 0;
        this.col = 0;
        this.direction = Direction.right;
    }
}

public class Solution {
    
    
    
    Position zwalk(int[][] matrix, Position current){
        int rows = matrix.length;
        int cols = matrix[0].length;

        switch(current.direction){
            case right:
                if(current.col+1 < cols){
                    current.col++;
                    current.direction = Direction.downleft;
                }else{
                    current.direction = Direction.down;
                    return zwalk(matrix, current);
                }
                break;
            case downleft:
                if(current.col > 0 && current.row < rows - 1){
                    current.col--;
                    current.row++;
                }else{
                    if(current.row == rows - 1){
                        current.col++;
                        current.direction = Direction.upright;
                    }else if(current.col == 0){
                        current.direction = Direction.down;
                        return zwalk(matrix, current);
                    }else{
                        current.col = -1;
                        current.row = -1;
                    }
                }
                break;
            case down:
                if(current.col != cols -1){
                    if(current.row+1 < rows){
                        current.row++;
                        current.direction = Direction.upright;
                    }else{
                        current.col++;
                        current.direction = Direction.upright;
                    }
                }else{
                    current.row++;
                    current.direction = Direction.downleft;
                }

                break;
            case upright:
                if(current.row > 0 && current.col < cols - 1){
                    current.col++;
                    current.row--;
                }else{
                    if(current.col == cols - 1){
                        current.direction = Direction.down;
                        return zwalk(matrix, current);
                    }else if(current.row == 0){
                        current.direction = Direction.right;
                        return zwalk(matrix, current);
                    }else{
                        current.col = -1;
                        current.row = -1;
                    }
                }
                break;
            default:
                break;
        }
        return current;
    }


    public int[] printZMatrix(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int total = rows * cols;
        Position position = new Position();
        int[] result = new int[total];
        int index = 0;
        while( position.col < cols && position.row < rows){
            result[index++] = matrix[position.row][position.col];
            position = zwalk(matrix, position);
        }
        result[rows * cols - 1] = matrix[rows-1][cols-1];

        return result;
    }
}
Show Comments

Get the latest posts delivered right to your inbox.