1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 29 题] “顺时针打印矩阵”做题记录

[剑指 Offer 第 2 版第 29 题] “顺时针打印矩阵”做题记录

第 29 题:顺时针打印矩阵

传送门:顺时针打印矩阵牛客网 online judge 地址

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。

样例:

输入: [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ]

输出:[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

分析: + 这道题,书本上的解法我个人觉得还不够直观、简洁,要考虑到一些边界情况。 + 借用之前做题中,使用状态以及状态转移的策略,不难画出图形如下。

下面是对这张图的解释,我们只解释了一个状态执行的代码,其它状态可以同样分析得出。

  • 在初始状态下,应该向右边走,因此状态为“RIGHT”(或许,这里定义成“方向”会更贴切一些)。
  • 遍历完第 1 行,其实以后,我们都不会再遍历到横坐标为 0 的点,因此 row_min 加 1。
  • 遍历完成以后,其实点的坐标越界了,我们要把它挪到下一次状态的起点。
  • 如果遍历到中心的时候,很可能遇到只更改了状态,不执行循环体的情况,这就避免了对一些边界情况的考虑。

Java 代码:

  import java.util.ArrayList;

    // 29 顺时针打印矩阵
    // 参考资料:https://www.nowcoder.com/questionTerminal/9b4c81a02cd34f76be2659fa0d54342a
    public class Solution {

        private enum State {
            RIGHT, DOWN, LEFT, UP
        }

        public ArrayList<Integer> printMatrix(int[][] matrix) {
            ArrayList<Integer> res = new ArrayList<>();
            int row_max = matrix.length;
            if (row_max == 0) {
                return res;
            }
            int col_max = matrix[0].length;
            row_max--;
            col_max--;
            int row_min = 0;
            int col_min = 0;
            // 上面的代码虽然看起来行数比较多,但是其实只是做了极端情况的考虑和一些变量的初始化工作

            // 下面的代码虽然看起来比较长,但是也只是做了当前状态的判断以及状态转移,代码框架是一模一样的
            // 仔细体会这个过程,其实就是:每次接收一个状态,根据这个状态做出相应的操作,然后变更状态
            State state = State.RIGHT;
            int i = 0;
            int j = 0;
            while (row_min <= row_max && col_min <= col_max) {
                if (state == State.RIGHT) {
                    while (j <= col_max) {
                        res.add(matrix[i][j]);
                        j++;
                    }
                    j--;
                    i++;
                    state = State.DOWN;
                    row_min++;
                } else if (state == State.DOWN) {
                    while (i <= row_max) {
                        res.add(matrix[i][j]);
                        i++;
                    }
                    i--;
                    j--;
                    state = State.LEFT;
                    col_max--;
                } else if (state == State.LEFT) {
                    while (j >= col_min) {
                        res.add(matrix[i][j]);
                        j--;
                    }
                    j++;
                    i--;
                    state = State.UP;
                    row_max--;
                } else {
                    assert state == State.UP;
                    while (i >= row_min) {
                        res.add(matrix[i][j]);
                        i--;
                    }
                    i++;
                    j++;
                    state = State.RIGHT;
                    col_min++;
                }
            }
            return res;
        }

        public static void main(String[] args) {
            int[][] matrix1 = {{1, 2, 3, 4},
                    {5, 6, 7, 8},
                    {9, 10, 11, 12},
                    {13, 14, 15, 16}};
            int[][] matrix = new int[5][6];
            int count = 1;
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    System.out.print(count + "\t");
                    matrix[i][j] = count;
                    count++;
                }
                System.out.println();
            }
            Solution solution = new Solution();
            ArrayList<Integer> printMatrix = solution.printMatrix(matrix);
            System.out.println(printMatrix);
        }
    }

Python 代码:

  class Solution:
        # matrix类型为二维列表,需要返回列表
        def printMatrix(self, matrix):
            rows = len(matrix)
            cols = len(matrix[0])
            result = []
            if rows == 0 and cols == 0:
                return result
            left, right, top, buttom = 0, cols - 1, 0, rows - 1
            while left <= right and top <= buttom:
                for i in range(left, right + 1):
                    result.append(matrix[top][i])
                for i in range(top + 1, buttom + 1):
                    result.append(matrix[i][right])
                if top != buttom:
                    for i in range(left, right)[::-1]:
                        result.append(matrix[buttom][i])
                if left != right:
                    for i in range(top + 1, buttom)[::-1]:
                        result.append(matrix[i][left])
                left += 1
                top += 1
                right -= 1
                buttom -= 1
            return result

“大雪菜”的写法:我们顺时针定义四个方向:上右下左。从左上角开始遍历,先往右走,走到不能走为止,然后更改到下个方向,再走到不能走为止,依次类推,遍历 n^2 个格子后停止。

时间复杂度:矩阵中每个格子遍历一次,所以总时间复杂度是 O(n^2)

C++ 代码:

  class Solution {
    public:
        vector<int> printMatrix(vector<vector<int>>& matrix) {
            vector<int> res;
            if (matrix.empty()) return res;
            int n = matrix.size(), m = matrix[0].size();
            vector<vector<bool>> st(n, vector<bool>(m, false));
            int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
            int x = 0, y = 0, d = 1;
            for (int k = 0; k < n * m; k ++ )
            {
                res.push_back(matrix[x][y]);
                st[x][y] = true;

                int a = x + dx[d], b = y + dy[d];
                if (a < 0 || a >= n || b < 0 || b >= m || st[a][b])
                {
                    d = (d + 1) % 4;
                    a = x + dx[d], b = y + dy[d];
                }
                x = a, y = b;
            }
            return res;
        }
    };


作者:yxc 链接:https://www.acwing.com/solution/AcWing/content/748/ 来源:AcWing 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 29 题] “顺时针打印矩阵”做题记录

链接:https://www.javajike.com/article/3277.html

« [剑指 Offer 第 2 版第 28 题] “对称的二叉树”做题记录
[剑指 Offer 第 2 版第 30 题] “包含min函数的栈”做题记录»

相关推荐

QR code