轻松搞定螺旋矩阵面试题

心已赠人 2022-03-17 15:18 249阅读 0赞

#### 1. leetCode 59 ####

Given a positive integer n, generate a square matrix filled with elements 
    from 1 to n2 in spiral order.
    
    Example:
    
    Input: 3
    Output:
    [
     [ 1, 2, 3 ],
     [ 8, 9, 4 ],
     [ 7, 6, 5 ]
    ]

参考：  
[面试题-螺旋矩阵][-]

完整 Java 代码:

public class SpiralMatrix { 
    
        public static void main(String[] args) { 
            int n = 5;
            int[][] dataArray = new int[n][n];
    
            solution(dataArray, n);
            // 行数
            for (int i = 0; i < dataArray.length; i++) { 
                // 列
                for (int j = 0; j < dataArray[0].length; j++) { 
                    System.out.print(dataArray[i][j] + " ");
                }
                System.out.println();
            }
    
        }
    
        public static void solution(int[][] dataArray, int n) { 
            spiralMatrix(dataArray, n, 1, 0, 0);
    
            // 处理奇数的情况
            if (n % 2 != 0) { 
                dataArray[n / 2][n / 2] = n * n;
            }
        }
    
    
        public static void spiralMatrix(int[][] dataArray, int n, int number, int x, int y) { 
    
            int startX = x;
            int startY = y;
    
            // up
            while (y < n - 1) { 
                dataArray[startX][y] = number;
                number++;
                y++;
            }
    
            // right
            while (x < n - 1) { 
                dataArray[x][y] = number;
                x++;
                number++;
            }
    
            // down
            while (y > startY) { 
                dataArray[x][y] = number;
                number++;
                y--;
            }
    
            // left
            while (x > startX) { 
                dataArray[x][y] = number;
                number++;
                x--;
            }
            
            n--;
            if (n > 2) { 
                // 递归打印
                spiralMatrix(dataArray, n, number, ++startX, ++startY);
            }
    
        }
    }

#### 2. leetCode 54 ####

参考：[Leetcode 54：螺旋矩阵（最详细的解法！！！）][Leetcode 54]

Given a matrix of m x n elements (m rows, n columns),
     return all elements of the matrix in spiral order.
    
    Example 1:
    
    Input:
    [
     [ 1, 2, 3 ],
     [ 4, 5, 6 ],
     [ 7, 8, 9 ]
    ]
    Output: [1,2,3,6,9,8,7,4,5]
    Example 2:
    
    Input:
    [
      [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]

完整 Java 代码：

public class SpiralMatrix1 { 
    
        public static void main(String[] args) { 
            int row = 3;
            int col = 4;
            int[][] dataArr = new int[row][col];
            int number = 1;
            for (int i = 0; i < row; i++) { 
                for (int j = 0; j < col; j++) { 
                    dataArr[i][j] = number;
                    number++;
                }
            }
    
            System.out.println(solution(dataArr));
        }
    
        public static List<Integer> solution(int[][] dataArr) { 
            List<Integer> results = new ArrayList<>();
            if (dataArr.length == 0) { 
                return results;
            }
    
            // 行边界
            int r1 = 0, r2 = dataArr.length - 1;
            // 列边界
            int c1 = 0, c2 = dataArr[0].length - 1;
            while (r1 <= r2 && c1 <= c2) { 
                for (int i = c1; i <= c2; i++) { 
                    results.add(dataArr[r1][i]);
                }
                for (int j = r1 + 1; j <= r2; j++) { 
                    results.add(dataArr[j][c2]);
                }
                if (r1 < r2 && c1 < c2) { 
                    for (int i = c2 - 1; i > c1; i--) { 
                        results.add(dataArr[r2][i]);
                    }
                    for (int j = r2; j > r1; j--) { 
                        results.add(dataArr[j][c1]);
                    }
                }
                // 往内部进一层
                r1++;
                r2--;
                c1++;
                c2--;
            }
    
            return results;
        }
    }

leetCode 59 也可以用这种方法求解。

#### 3. 从内至外的螺旋矩阵 ####

形如：
      7   8   9  10 
      6   1   2  11 
      5   4   3  12 
     16  15  14  13 
     这样的一个矩阵，有下面两个问题：
     1. 编程实现输出这个矩阵 
     2. 设1点的坐标是(0,0)，x 方向向右为正，y 方向向上为正，
        例如：7 的坐标为 (-1，1) ，2 的坐标为 (0，1)，3 的坐标为 (-1，-1)。
        编程实现输入任意一点坐标 (x，y)，输出螺旋矩阵所对应的数字。

参考：[面试题-螺旋矩阵(模拟)][- 1]

##### 问题 1 #####

从这个矩阵可以看出从 1 开始的方向是先向右 -> 向下 -> 向左 -> 向上，每一个方向上所走的长度为 1 -> 1 -> 2 -> 2 -> 3 -> 3 -> 4 -> 4…

1 的位置在 (n - 1) / 2, (n - 1) / 2。

方向用几个数字来表示，0：向右，1：向下，2：向左，3：向上，  
方向的变化则是对 4 进行取模。

每过 2 轮循环（count = 2）,len 就加 1。

完整 Java 代码：

public class SpiralMatrix2 { 
        public static void main(String[] args) { 
            int n = 4;
            int[][] dataArray = new int[n][n];
            solution(dataArray);
            // 行数
            for (int i = 0; i < dataArray.length; i++) { 
                // 列
                for (int j = 0; j < dataArray[0].length; j++) { 
                    System.out.print(dataArray[i][j] + " ");
                }
                System.out.println();
            }
        }
    
        public static void solution(int[][] dataArray) { 
            int n = dataArray.length;
            int x, y;
            // 1 的位置
            x = y = (n - 1) / 2;
            dataArray[x][y] = 1;
    
            int len = 1;
            int count = 0;
            int num = 2;
    
            int dir = 0;
            while (num <= n * n) { 
                for (int i = 0; i < len; i++) { 
                    switch (dir) { 
                        case 0:
                            // 向右
                            ++y;
                            break;
                        case 1:
                            // 向下
                            ++x;
                            break;
                        case 2:
                            // 向左
                            --y;
                            break;
                        case 3:
                            // 向上
                            --x;
                            break;
    
                        default:
                            break;
                    }
                    // 避免溢出，dataArray 只能存到 n * n
                    if (num > n * n) { 
                        return;
                    }
                    dataArray[x][y] = num++;
                }
                count++;
                if (count == 2) { 
                    count = 0;
                    len++;
                }
                dir = (dir + 1) % 4;
            }
        }
    }

##### 问题 2 #####

问题 2 找规律实在太绕了（放弃了），求大佬们更加简洁的实现。

[-]: https://www.cnblogs.com/minesky/p/3362575.html
[Leetcode 54]: https://blog.csdn.net/qq_17550379/article/details/83148050
[- 1]: https://www.cnblogs.com/drizzlecrj/archive/2007/04/10/706784.html