用Rust🦀写算法-数组篇-螺旋矩阵

59. 螺旋矩阵 II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

• 1 <= n <= 20

💡 思路：模拟，将填入的过程用代码模拟出来

代码（思路一）：

impl Solution {
    pub fn generate_matrix(n: i32) -> Vec<Vec<i32>> {
        let mut ans = vec![vec![0; n as usize]; n as usize]; // 存储结果
        let mut x = 0;
        let mut y = 0;
        let mut fx = 0;

        for v in 1..=n * n {
            ans[x as usize][y as usize] = v;
            let mut i = x; //引入 i, j 作为中间量 判断是否变化方向
            let mut j = y;
            match fx {
                0 => j += 1,
                1 => i += 1,
                2 => j -= 1,
                3 => i -= 1,
                _ => (),
            }
            
            if i < 0 || i >= n || j < 0 || j >= n || ans[i as usize][j as usize] != 0 {
                fx = (fx + 1) % 4;
            }

            match fx { // 判断变化方向后再移动
                0 => y += 1,
                1 => x += 1,
                2 => y -= 1,
                3 => x -= 1,
                _ => (),
            }
        }

        ans
    }
}

优化一下代码：

const DIRECTIONS: [(i32, i32); 4] = [(0, 1), (1, 0), (0, -1), (-1, 0)]; // 右、下、左、上

impl Solution {
    pub fn generate_matrix(n: i32) -> Vec<Vec<i32>> {
        let mut matrix = vec![vec![0; n as usize]; n as usize];
        let (mut row, mut col) = (0, 0);
        let mut dir = 0;
        
        for num in 1..=n * n {
            matrix[row as usize][col as usize] = num;
            
            // 计算下一步位置
            let next_row = row + DIRECTIONS[dir].0;
            let next_col = col + DIRECTIONS[dir].1;
            
            // 检查是否需要转向
            if next_row < 0 || next_row >= n || next_col < 0 || next_col >= n 
            || matrix[next_row as usize][next_col as usize] != 0 {
                dir = (dir + 1) % 4;
            }
            
            // 更新位置
            row = row + DIRECTIONS[dir].0;
            col = col + DIRECTIONS[dir].1;
        }
        
        matrix
    }
}

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• 100 <= matrix[i][j] <= 100

💡 思路：模拟

代码（思路一）：

impl Solution {
    pub fn spiral_order(matrix: Vec<Vec<i32>>) -> Vec<i32> {
        let n = matrix.len();
        let m = matrix[0].len();
        let mut visited = vec![vec![false; m]; n];
        let mut result = Vec::with_capacity(n * m);
        let (mut i, mut j) = (0, 0);
        let dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)];
        let mut dir = 0;

        for _ in 0..n * m {
            result.push(matrix[i][j]);
            visited[i][j] = true;

            // 计算下一步位置
            let next_i = i as i32 + dirs[dir].0;
            let next_j = j as i32 + dirs[dir].1;

            // 检查是否需要转向
            if next_i < 0 || next_i >= n as i32 || next_j < 0 || next_j >= m as i32 
                || visited[next_i as usize][next_j as usize] {
                dir = (dir + 1) % 4;
            }

            // 更新位置
            i = (i as i32 + dirs[dir].0) as usize;
            j = (j as i32 + dirs[dir].1) as usize;
        }

        result
    }
}