Thought
For the rotation question, we could get an easy approach by observing the rotation result.
For the Spiral question, we should set the four dimension ranges and keep updating them.
Example
48. Rotate Image (https://leetcode.com/problems/rotate-image/)
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Example 2:
Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
For this problem, an easy approach is we transpose the elements in matrix along the diagonal first, then reverse row by row.
My Solution
class Solution {
public void rotate(int[][] matrix) {
// transpose
for(int i = 0; i < matrix.length; i++){
for(int j = i; j < matrix.length; j++){
// [i, j] <-> [j, i]
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
// reverse
for(int i = 0; i < matrix.length; i++){
int left = 0, right = matrix[i].length - 1;
while(left < right){
int tmp = matrix[i][left];
matrix[i][left] = matrix[i][right];
matrix[i][right] = tmp;
left++;
right--;
}
}
}
}54. Spiral Matrix (https://leetcode.com/problems/spiral-matrix/)
Given an m x n matrix, return all elements of the matrix in spiral order.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
Keep track of top, right, bottom and left restriction, and update them after each iteration
My Solution
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List ans = new ArrayList();
if (matrix.length == 0) return ans;
int m = matrix.length;
int n = matrix[0].length;
int i, k = 0, l = 0;
/* k - starting row index
m - ending row index
l - starting column index
n - ending column index
i - iterator
*/
while (k < m && l < n) {
// Print the first row from the remaining rows
for (i = l; i < n; ++i) {
ans.add(matrix[k][i]);
}
k++;
// Print the last column from the remaining columns
for (i = k; i < m; ++i) {
ans.add(matrix[i][n - 1]);
}
n--;
// Print the last row from the remaining rows */
if (k < m) {
for (i = n - 1; i >= l; --i) {
ans.add(matrix[m - 1][i]);
}
m--;
}
// Print the first column from the remaining columns */
if (l < n) {
for (i = m - 1; i >= k; --i) {
ans.add(matrix[i][l]);
}
l++;
}
}
return ans;
}
}59. Spiral Matrix II (https://leetcode.com/problems/spiral-matrix-ii/)
Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.
Example 1:
Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]
Example 2:
Input: n = 1
Output: [[1]]
Totally same as previous one.
My Solution
int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
int upper_bound = 0, lower_bound = n - 1;
int left_bound = 0, right_bound = n - 1;
// 需要填入矩阵的数字
int num = 1;
while (num <= n * n) {
if (upper_bound <= lower_bound) {
// 在顶部从左向右遍历
for (int j = left_bound; j <= right_bound; j++) {
matrix[upper_bound][j] = num++;
}
// 上边界下移
upper_bound++;
}
if (left_bound <= right_bound) {
// 在右侧从上向下遍历
for (int i = upper_bound; i <= lower_bound; i++) {
matrix[i][right_bound] = num++;
}
// 右边界左移
right_bound--;
}
if (upper_bound <= lower_bound) {
// 在底部从右向左遍历
for (int j = right_bound; j >= left_bound; j--) {
matrix[lower_bound][j] = num++;
}
// 下边界上移
lower_bound--;
}
if (left_bound <= right_bound) {
// 在左侧从下向上遍历
for (int i = lower_bound; i >= upper_bound; i--) {
matrix[i][left_bound] = num++;
}
// 左边界右移
left_bound++;
}
}
return matrix;
}