54. 螺旋矩阵---算法题。思路

2023-12-26 19:33:58

给你一个?m?行?n?列的矩阵?matrix?,请按照?顺时针螺旋顺序?,返回矩阵中的所有元素

本题的leetcode,官方题解一中没有给出关键代码的思路

如下的代码中:

????????通过 directions 数组来定义四个方向的移动。

  • directions 数组是一个二维数组,每个元素代表一个方向。例如,{0, 1} 表示向右移动,{1, 0} 表示向下移动,{0, -1} 表示向左移动,{-1, 0} 表示向上移动。

  • directionIndex 是一个指示当前方向的索引,初始值为 0。

  • 在遍历的过程中,首先访问当前位置,并标记为已访问,然后计算下一个位置。如果下一个位置超出矩阵边界或者已经访问过,就改变方向,确保顺时针旋转移动。最后,更新当前位置。

如果你觉得这个写法比较复杂,你可以使用一个更简洁的方式,不再使用 directions 数组,而是直接计算下一个位置。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> order = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }
        int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;

        while (top <= bottom && left <= right) {
            for (int i = left; i <= right; i++) {
                order.add(matrix[top][i]);
            }
            top++;

            for (int i = top; i <= bottom; i++) {
                order.add(matrix[i][right]);
            }
            right--;

            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    order.add(matrix[bottom][i]);
                }
                bottom--;
            }

            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    order.add(matrix[i][left]);
                }
                left++;
            }
        }

        return order;
    }
}

解二:一层一层解决。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> order = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }
        int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;

        while (top <= bottom && left <= right) {
            for (int i = left; i <= right; i++) {
                order.add(matrix[top][i]);
            }
            top++;

            for (int i = top; i <= bottom; i++) {
                order.add(matrix[i][right]);
            }
            right--;

            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    order.add(matrix[bottom][i]);
                }
                bottom--;
            }

            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    order.add(matrix[i][left]);
                }
                left++;
            }
        }

        return order;
    }
}

从左到右遍历上边界。

从上到下遍历右边界。

检查是否还有未遍历的行,从右到左遍历下边界。

检查是否还有未遍历的列,从下到上遍历左边界。

文章来源:https://blog.csdn.net/qq_28909387/article/details/135228552
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。