二维数组的花式遍历技巧

48. 旋转图像

54. 螺旋矩阵

59. 螺旋矩阵 II

这篇文章介绍几种花式遍历二维数组的技巧，废话少说，直接上题目！！

旋转图像

详情可见题目 旋转图像

今天 (2022-04-08 20:36:26) 看到这个题目的时候，突然想起来了自己在很久很久前写了一丢丢小小的技巧总结，贴出链接 link

哈哈哈哈哈哈，居然还看到有一个外国人评论我了，今日份开心！！！！

看了上面贴出来的总结，相信就很明了了。就是一种很常规的思路。唯一的弊端就是，需要分析清楚移动元素的「下标关系」，绕来绕去的，很容易搞错！

今天学习了一种全新的思路，好家伙，直接 OMG，惊呆了！！

这里先上一个引例

对于字符串I am a good boy，如何原地反转所有单词的顺序，反转后的结果应该为boy good a am I

相信很多人的惯性思维就是，先根据「空格」切分字符串，然后把「首尾元素」交换

这里提供一种新的思路

• 先将字符串反转，反转后结果应该为yob doog a ma I
• 然后将每个单词反转，其结果应该为boy good a ma I

好了，针对今天的题目，我们的思路「先沿 左上-右下 的对角线翻转，然后对每一行进行反转」,如下图所示：

这个题目是顺时针，如果是逆时针，也只需要稍作变化即可，如下图所示：

是不是有种发现新大陆的感觉，哈哈哈哈哈

下面是题目的详细代码 (顺时针)

public void rotate(int[][] matrix) {
    int n = matrix.length;
    // 沿对角线翻转
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    }
    // 对每行反转
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n / 2; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[i][n - j - 1];
            matrix[i][n - j - 1] = tmp;
        }
    }
}

螺旋矩阵

详情可见题目 螺旋矩阵

这个题目其实没有什么技巧可言，就是模拟螺旋移动的过程

需要注意的是，边界的控制，以及下标的变化。请详细看代码中的注释，写的很清楚了，同时结合下面的图

​x
public List<Integer> spiralOrder(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    int upper_bound = 0, lower_bound = m - 1;
    int left_bound = 0, right_bound = n - 1;
    List<Integer> res = new ArrayList<>();
    while (res.size() < m * n) {
        // 从左到右
        // 「上边界」要在「下边界」上面
        if (upper_bound <= lower_bound) {
            // 从「左边界」开始，到「右边界」截止
            for (int j = left_bound; j <= right_bound; j++) {
                res.add(matrix[upper_bound][j]);
            }
            // 「上边界」下移
            upper_bound++;
        }

        // 从上到下
        // 「右边界」要在「左边界」右边
        if (right_bound >= left_bound) {
            // 从「上边界」开始，到「下边界」截止
            for (int i = upper_bound; i <= lower_bound; i++) {
                res.add(matrix[i][right_bound]);
            }
            // 「右边界」左移
            right_bound--;
        }

        // 从右到左
        // 「下边界」要在「上边界」下面
        if (lower_bound >= upper_bound) {
            // 从「右边界」开始，到「左边界」截止
            for (int j = right_bound; j >= left_bound; j--) {
                res.add(matrix[lower_bound][j]);
            }
            // 「下边界」上移
            lower_bound--;
        }

        // 从下到上
        // 「左边界」要在「右边界」左边
        if (left_bound <= right_bound) {
            // 从「下边界」开始，到「上边界」截止
            for (int i = lower_bound; i >= upper_bound; i--) {
                res.add(matrix[i][left_bound]);
            }
            // 「左边界」右移
            left_bound++;
        }
    }
    return res;
}

螺旋矩阵 II

详情可见题目 螺旋矩阵 II

这个题目就是上面题目的逆过程，把代码稍微修改一下即可

xxxxxxxxxx
public int[][] generateMatrix(int n) {
    int upper_bound = 0, lower_bound = n - 1;
    int left_bound = 0, right_bound = n - 1;
    int[][] matrix = new int[n][n];
    int count = 0;
    while (count < n * n) {
        // 从左到右
        // 「上边界」要在「下边界」上面
        if (upper_bound <= lower_bound) {
            // 从「左边界」开始，到「右边界」截止
            for (int j = left_bound; j <= right_bound; j++) {
                matrix[upper_bound][j] = ++count;
            }
            // 「上边界」下移
            upper_bound++;
        }

        // 从上到下
        // 「右边界」要在「左边界」右边
        if (right_bound >= left_bound) {
            // 从「上边界」开始，到「下边界」截止
            for (int i = upper_bound; i <= lower_bound; i++) {
                matrix[i][right_bound] = ++count;
            }
            // 「右边界」左移
            right_bound--;
        }

        // 从右到左
        // 「下边界」要在「上边界」下面
        if (lower_bound >= upper_bound) {
            // 从「右边界」开始，到「左边界」截止
            for (int j = right_bound; j >= left_bound; j--) {
                matrix[lower_bound][j] = ++count;
            }
            // 「下边界」上移
            lower_bound--;
        }

        // 从下到上
        // 「左边界」要在「右边界」左边
        if (left_bound <= right_bound) {
            // 从「下边界」开始，到「上边界」截止
            for (int i = lower_bound; i >= upper_bound; i--) {
                matrix[i][left_bound] = ++count;
            }
            // 「左边界」右移
            left_bound++;
        }
    }
    return matrix;
}