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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!