《剑指Offer》 面试题29 顺时针打印矩阵

2020-04-28  本文已影响0人  萨缪

最近一直在刷《剑指Offer》 认真看的话这本书对👨‍💻‍代码的构造,优化能力提升还是很大的,尤其是对特殊情况的考虑,作者几乎在每道题都会强调。很好的一本书,会继续看下去。
题目描述

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下4 X 4矩阵:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
思路

这道题乍一看很像初学C语言时做的蛇形数组问题,但比那个难度还是有所提高的,主要思路就是先考虑数组的形态,特殊边界的判定,特殊矩阵的考虑等。书上写的思路我觉得比较复杂,所以没有采纳。

自己想到的思路是:先判断特殊情况:数组只有一行或者一列,那么直接打印数组即可。
有多行多列,那么至少第一次循环肯定是先从左到右打印,打印完后开始行startRow+1 再从最右边的下方一个数组单元起始从上到下打印,打印完后最后一列endCol-1 再从最后一行最右边数组单元左边一个单元开始,从右往左打印,打印完后最后一行endRow-1 最后从打印到的最终位置也就是左下角的上方一个单元开始从下到上进行打印,打印完后起始列startCol+1 这样最外圈的数组单元就依次顺时针打印完毕了,并对行列进行加减操作相当于删除了最外围的各个数组单元。

那么如何判断是否该数字内部还有需要打印的单元?如果内圈还有可以继续打印的单元 那么 startRow必然会等于endRow starCol必定会小于endCol
试想一下如果每次都能完整的进行两行两列打印那么startRow++ endRow-- startCol++ endCol-- 把数组想象成一个圈 每次的加减操作相当于对数组进行缩圈,当为奇数行时必定最后还要打印最中间的那一行(至于中间的那一行有几个元素我们不用管),当为奇数列时最后肯定是打印中间的一列(同样几个元素我们不用考虑) 还有其他情况都会归类到下面源代码中while循环中的else 中 会帮我们处理一切。
源代码

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        int row = matrix.size();
        int col = matrix[0].size();
        int startRow = 0;
        int endRow = row - 1;
        int startCol = 0;
        int endCol = col - 1;
     
        vector <int> printVector;
        if (row <= 1 || col <= 1) {
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    printVector.push_back(matrix[i][j]);
                }
            }
            return printVector;
        }
        while (startRow <= endRow && startCol <= endCol) {
            if (startRow == endRow) {
                for (int i = startCol; i <= endCol; i++) {
                    printVector.push_back(matrix[startRow][i]);
                }
                break;
            } else {
            for (int i = startCol; i <= endCol; i++) {
                printVector.push_back(matrix[startRow][i]);
            }
            startRow++;
            for (int i = startRow; i <= endRow; i++) {
                printVector.push_back(matrix[i][endCol]);
            }
            endCol--;
            for (int i = endCol; i >= startCol; i--) {
                printVector.push_back(matrix[endRow][i]);
            }
            endRow--;
            for (int i = endRow; i >= startRow; i--) {
                printVector.push_back(matrix[i][startCol]);
            }
            startCol++;
            }
        }
        return printVector;

    }
};
上一篇下一篇

猜你喜欢

热点阅读