LeetCode54. スパイラルマトリクスjava実装
4866 ワード
LeetCode54. スパイラルマトリクスjava実装
タイトル難易度中 は、m x n個の要素を含むマトリクス(m行、n列)を与え、マトリクス内のすべての要素を時計回りの螺旋順に返してください.
構想
各点の座標を探し出して、各点は毎回時計回りにそれぞれ右、下、左、上の4つの方向に1つの位置を歩いて、1つの方向の変数を維持して、異なる方向の時に相応の境界の判断をします.境界に遭遇するたびに、必ず方向を変えて、元の境界の大きさを短縮します.
解法
結果
2 msで99.74%勝った
タイトル
1:
:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
: [1,2,3,6,9,8,7,4,5]
2:
:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
: [1,2,3,4,8,12,11,10,9,5,6,7]
構想
各点の座標を探し出して、各点は毎回時計回りにそれぞれ右、下、左、上の4つの方向に1つの位置を歩いて、1つの方向の変数を維持して、異なる方向の時に相応の境界の判断をします.境界に遭遇するたびに、必ず方向を変えて、元の境界の大きさを短縮します.
解法
public List spiralOrder(int[][] matrix) {
ArrayList order = new ArrayList<>();
if (matrix.length == 0 || matrix[0].length == 0) {
return order;
}
int m = matrix.length;
int n = matrix[0].length;
int len = m * n;
int row = 0;
int col = 0;
int leftMin = 0;
// ,
// , (1,1) , row 1
int topMin = 1;
//
int k = 0;
int[][] dir = {
{1, 0, -1, 0},
{0, 1, 0, -1}
};
for (int i = 0; i < len; i++) {
order.add(matrix[row][col]);
col += dir[0][k % 4];
row += dir[1][k % 4];
switch (k % 4) {
case 0:
//
if (col > n - 1) {
col = n - 1;
row++;
k++;
n--;
}
break;
case 1:
//
if (row > m - 1) {
row = m - 1;
col--;
k++;
m--;
}
break;
case 2:
//
if (col < leftMin) {
col = leftMin;
leftMin++;
row--;
k++;
}
break;
case 3:
//
if (row < topMin) {
row = topMin;
topMin++;
col++;
k++;
}
break;
}
}
return order;
}
結果
2 msで99.74%勝った