Today I found an interesting OA question related to printing matrix in spiral order, and had a shot at it. Simply googling it I find another question related to checking Toeplitz Matrix. I will keep updating this post once I found more interesting questions related to matrix operations.
Spiral Matrix
Problem Statement
Here goes the problem description related to Spiral Matrix[1]:
Given a matrix of $m times n$ elements ($m$ rows, $n$ columns), return all elements of the matrix in spiral order. For example:
Input: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
Solutions
Solutions to this question should be trival. The key idea is to manipulate the matrix element index in spiral order. Observing the moving direction for the spiral order, there should be four cases:
-
Moving left:
Previously the direction should be up, until it reaches the visited element, then tunning left. -
Moving down:
Previously the direction should be left, until it reaches the visited element, then tunning down. -
Moving right:
Previously the direction should be down, until it reaches the visited element, then tunning right. -
Moving up:
Previously the direction should be right, until it reaches the visited element, then tunning up.
Also, if we say going through above mentioned fource cases as $1$ loop, then after each loop we will reduce the number of elements to be visited by $2$ for each case. More Specifically, the number of elements to be printed in each loop for each case should be:
-
Moving left:
$n, n-2, n-4, …, $ -
Moving down:
$m-1, m-3, …, $ -
Moving right:
$n-1, n-3, …, $ -
Moving up:
$m-2, m-4, …, $
We can enumerate the number of total loops as well. One of the four cases will first end up with $0$ for no doubt, which indicates the ending of the loop. So we get:
$$LOOPS = min{lceil frac{n-1}{2} rceil, lceil frac{m-2}{2} rceil}$$
Now I firstly show the most trival java version code below:
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<Integer>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return result;
}
int m = matrix.length;
int n = matrix[0].length;
int printednum = 0;
int loopnum = (int) (Math.ceil(((float)m-2)/2) < Math.ceil(((float)n-1)/2) ? Math.ceil(((float)m-2)/2) : Math.ceil(((float)n-1)/2));
int tovisitnum = 0;
for (int i = 0; i < loopnum; i++) {
/** moving left**/
tovisitnum = 0;
while (tovisitnum != n - 2 * i) {
result.add(matrix[i][tovisitnum+i]);
tovisitnum ++;
printednum ++;
}
/** moving down **/
tovisitnum = 0;
while (tovisitnum != m-1-2*i) {
result.add(matrix[tovisitnum + i+1][n-1-i]);
tovisitnum ++;
printednum ++;
}
/** Moving right **/
tovisitnum = 0;
while (tovisitnum != n-1-2*i) {
result.add(matrix[m-1-i][n-2-i-tovisitnum]);
tovisitnum ++;
printednum ++;
}
/** Moving up **/
tovisitnum = 0;
while (tovisitnum != m-2-2*i) {
result.add(matrix[m-2-i-tovisitnum][i]);
tovisitnum ++;
printednum ++;
}
}
//finish spiral order printing
if (printednum == m * n)
return result;
else {
// moving right
tovisitnum = 0;
while (tovisitnum != n - 2 * loopnum) {
result.add(matrix[loopnum][tovisitnum+loopnum]);
tovisitnum ++;
printednum ++;
}
//moving down
if (printednum < m * n) {
tovisitnum = 0;
while (tovisitnum != m-1-2*loopnum) {
result.add(matrix[tovisitnum + loopnum+1][n-1-loopnum]);
tovisitnum ++;
printednum ++;
}
}
//moving left
if (printednum < m * n) {
tovisitnum = 0;
while (tovisitnum != n-1-2*loopnum) {
result.add(matrix[m-1-loopnum][n-2-loopnum-tovisitnum]);
tovisitnum ++;
printednum ++;
}
}
}
return result;
}
}
This solution simply enumerates all possible cases and consider each corresponding operations. It’s trival but the code is a bit verbose. We can simply the code by considering the printing layer by layer. We can just consider printing the elemnts in each layer and iterate it layer by layer. An very good picture in leetcode solution illustrates the basic idea. I directly cite that picture here:
Based on this idea, the simplified python code is below:
class Solution(object):
def spiralOrder(self, matrix):
def spiral_coords(r1, c1, r2, c2):
for c in range(c1, c2 + 1):
yield r1, c
for r in range(r1 + 1, r2 + 1):
yield r, c2
if r1 < r2 and c1 < c2:
for c in range(c2 - 1, c1, -1):
yield r2, c
for r in range(r2, r1, -1):
yield r, c1
if not matrix: return []
ans = []
r1, r2 = 0, len(matrix) - 1
c1, c2 = 0, len(matrix[0]) - 1
while r1 <= r2 and c1 <= c2:
for r, c in spiral_coords(r1, c1, r2, c2):
ans.append(matrix[r][c])
r1 += 1; r2 -= 1
c1 += 1; c2 -= 1
return ans
Spiral Matrix II
Problem Statement
Here goes the problem description of another version problem about Spiral Matrix in leetcode[2]:
Given an integer $n$, generate a square matrix filled with elements from $1$ to $n^2$ in spiral order.
For example, given $n = 3$,
You should return the following matrix:
[ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
Solution
This is exactly the same with the 1st version of Spiral Matrix. By traversing the result matrix exactly the same way when we traverse the input matrix in 1st question, we can generate the matrix filling with elements in spiral order. Here goes the java solution:
class Solution {
public int[][] generateMatrix(int n) {
int[][] result = new int[n][n];
if (n <= 0)
return result;
int colbegin = 0, colend = n-1;
int rowbegin = 0, rowend = n-1;
int curval = 1;
while (colbegin <= colend && rowbegin <= rowend) {
for (int i = colbegin; i <= colend; i++) {
result[rowbegin][i] = curval++;
}
rowbegin++;
for (int i = rowbegin; i <= rowend; i++) {
result[i][colend] = curval++;
}
colend --;
if (colbegin < colend && rowbegin < rowend) {
for (int i = colend; i >= colbegin; i--) {
result[rowend][i] = curval++;
}
rowend --;
for (int i = rowend; i >= rowbegin; i--) {
result[i][colbegin] = curval++;
}
colbegin++;
}
}
return result;
}
}
Toeplitz Matrix
Problem Statement
The checking whether a given matrix is Toeplitz or not can be found in GeeksforGeeks[3]:
Given a square matrix, find if it’s a Toeplitz matrix or not. A Toeplitz (or diagonal-constant) matrix is a matrix in which each descending diagonal from left to right is constant, i.e., all elements in a diagonal are same.
In general, any $ntimes n$ matrix $mat[][]$ is a Toeplitz matrix if every cell $mat[i][j]$ is same as $mat[i-1][j-1]$, $mat[i+1][j+1]$, $mat[i-2][j-2]$, $mat[i+2][j+2]$, .. for every cell $mat[i][j]$ and all the valid cells $mat[i+k][j+k]$ or $mat[i-k][j-k]$.
For example:
Input: mat[N][N] = {{ 6, 7, 8}, { 4, 6, 7}, { 1, 4, 6}}, Output : True; Values in all diagonals are same. Input: mat[N][N] = {{ 6, 7, 8, 9 }, { 4, 6, 7, 8 }, { 1, 4, 6, 7 }, { 0, 1, 4, 6 }, { 2, 0, 1, 4 }}; Output : True; Input: mat[N][N] = {{ 6, 3, 8}, { 4, 9, 7}, { 1, 4, 6}}, Output : False;
Solutions
// Java program to check whether given matrix
// is a Toeplitz matrix or not
import java.io.*;
class GFG
{
public static int N = 5;
public static int M = 4;
// Function to check if all elements present in
// descending diagonal starting from position
// (i, j) in the matrix are all same or not
static boolean checkDiagonal(int mat[][], int i, int j)
{
int res = mat[i][j];
while (++i < N && ++j < M)
{
// mismatch found
if (mat[i][j] != res)
return false;
}
// we only reach here when all elements
// in given diagonal are same
return true;
}
// Function to check whether given matrix is a
// Toeplitz matrix or not
static boolean isToepliz(int mat[][])
{
// do for each element in first row
for (int i = 0; i < M; i++)
{
// check descending diagonal starting from
// position (0, j) in the matrix
if (!checkDiagonal(mat, 0, i))
return false;
}
// do for each element in first column
for (int i = 1; i < N; i++)
{
// check descending diagonal starting from
// position (i, 0) in the matrix
if (!checkDiagonal(mat, i, 0))
return false;
}
// we only reach here when each descending
// diagonal from left to right is same
return true;
}
近期评论