阿里菜鸟网络一面最新笔试题

程序员小熊

发布于 2021-10-20 17:03:01

9300

发布于 2021-10-20 17:03:01

文章被收录于专栏：程序员小熊带你学算法程序员小熊带你学算法

前言

大家好，我是来自于华为的程序员小熊。最近熊哥的一位朋友，参加阿里菜鸟网络的面试，一轮面完后，面试官要求考察代码，于是昨天要求朋友参加菜鸟的机考。

今天熊哥分享一下这道题，该题是一道面试高频题，半年内被腾讯、字节、微软和 B 站等大厂考过，即力扣上的剑指 Offer 29. 顺时针打印矩阵。

顺时针打印矩阵

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

示例及提示

分析

从外向里顺时针打印矩阵，以矩阵 nums = [[1,2,3],[4,5,6],[7,8,9]]为例，如下图示：

打印前的矩阵

打印后的矩阵

解题思路

要顺时针打印矩阵，则必须顺时针遍历矩阵中的每个元素。对 M x N 的矩阵，遍历时，一般通过固定行或列，改变列或行的方式进行遍历。

举例

还是以上面的矩阵 nums = [[1,2,3],[4,5,6],[7,8,9]]为例，记第一行为 up，第一列为 left，最后一行为 down，最后一列为 right，如下图示。

设置行和列

在遍历第一行 [1, 2, 3] 时，固定行不变，改变列。

固定行，改变列

举栗

在遍历最后一列 [3, 6, 9]时，移动行(up)，固定列（right）。

遍历列

顺时针遍历的整个过程，如下动图所示。

顺时针打印矩阵整个过程

Show me the Code

int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
    if (matrixSize == 0 || matrix == NULL) {
        *returnSize = 0;
        return NULL;
    }

    *returnSize = matrixSize * (*matrixColSize);
    int *res = (int*)malloc(*returnSize * sizeof(int));
    if (res == NULL) {
        *returnSize = 0;
        return NULL;        
    }
    memset(res, 0, *returnSize * sizeof(int));

    int up = 0, down = matrixSize - 1;
    int left = 0, right = *matrixColSize - 1;
    int index = 0;
    while (index < *returnSize) {
        for (int i = left; index < *returnSize && i <= right; i++) {
            res[index++] = matrix[up][i];
        }
        up++;
        
        for (int i = up; index < *returnSize && i <= down; i++) {
            res[index++] = matrix[i][right];
        }
        right--;

        for (int i = right; index < *returnSize && i >= left; i--) {
            res[index++] = matrix[down][i];
        }
        down--;

        for (int i = down; index < *returnSize && i >= up; i--) {
            res[index++] = matrix[i][left];
        }
        left++;
    }
    
    return res;
}

C++

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    if (matrix.empty()) {
        return {};
    }

    vector<int> res;
    int up = 0, down = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;
    int total = matrix.size() * matrix[0].size();
    while (right >=left && up <= down) {
        for (int i = left; res.size() < total && i <= right; i++) {
            res.push_back(matrix[up][i]);
        }
        up++;
        
        for (int i = up; res.size() < total && i <= down; i++) {
            res.push_back(matrix[i][right]);
        }
        right--;

        for (int i = right; res.size() < total && i >= left; i--) {
            res.push_back(matrix[down][i]);
        }
        down--;

        for (int i = down; res.size() < total && i >= up; i--) {
            res.push_back(matrix[i][left]);
        }
        left++;
    }
    
    return res;
}

Java

int[] spiralOrder(int[][] matrix) {
    if(matrix == null ||matrix.length == 0){
        return new int[0];
    }

    int left = 0, up = 0;
    int right = matrix[0].length - 1;
    int down = matrix.length - 1;
    int[] res = new int[(right + 1) * (down + 1)];
    int index = 0;
    
    while(up <= down && left <= right) {
        for(int i = left; i <= right; i++) { 
            res[index++] = matrix[up][i];
        }
        up++;

        for(int i = up; i <= down; i++) { 
            res[index++] = matrix[i][right];
        }
        right--;

        for(int i = right; i >= left && up <= down; i--) {   
            res[index++] = matrix[down][i];
        }
        down--;

        for(int i = down; i >= up && left <= right; i--){    
            res[index++] = matrix[i][left];
        }
        left++;
    }
    
    return res;
}

Python3

def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
    if not matrix: 
        return []
    left, right, up, down, res = 0, len(matrix[0]) - 1, 0, len(matrix) - 1, []
    while True:
        for i in range(left, right + 1): 
            res.append(matrix[up][i])
        up += 1
        if up > down: 
            break

        for i in range(up, down + 1): 
            res.append(matrix[i][right]) 
        right -= 1
        if left > right: 
            break

        for i in range(right, left - 1, -1): 
            res.append(matrix[down][i]) 
        down -= 1
        if up > down: 
            break

        for i in range(down, up - 1, -1): 
            res.append(matrix[i][left]) 
        left += 1
        if left > right: 
            break

    return res

Golang

func spiralOrder(matrix [][]int) []int {
    if len(matrix) == 0 {
        return []int{}
    }
    var res []int 
    left := 0 
    right := len(matrix[0]) - 1
    up := 0
    down := len(matrix) - 1
    for {
        for i := left; i <= right; i++ {
            res = append(res, matrix[up][i])
        }
        up++ 
        if up > down {
            break
        }

        for i := up; i <= down; i++ {
            res = append(res, matrix[i][right])
        }
        right-- 
        if left > right {
            break
        }

        for i := right; i >= left; i-- {
            res = append(res, matrix[down][i])
        }
        down--
        if up > down {
            break
        }

        for i := down; i >= up; i-- {
            res = append(res, matrix[i][left])
        }
        left++ 
        if left > right {
            break
        }
    }
    
    return res 
}

复杂度分析

时间复杂度：O(m * n)，其中 m 和 n 分别是矩阵的行数和列数。

空间复杂度：O(m * n)。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2021-10-17，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自程序员小熊微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度