算法技巧：二维数组的花式遍历

顺/逆时针旋转矩阵

如何「原地」旋转二维矩阵？想一想，感觉操作起来很复杂，可能要设置巧妙的算法机制「一圈一圈」旋转矩阵

但事实上，这个问题不能走一条普通的路。在谈论巧妙的解决方案之前，让我们看看谷歌曾经测试过的另一个算法问题热身：

给你一个字符串，里面有几个单词和空间 s，请写一个算法，原地反转所有单词的顺序。

例如，给你输入这样一个字符串：

s = "hello world labuladong"

您的算法需要将字符串中的单词顺序原地反转：

s = "labuladong world hello"

传统的方式是把握 s 按空格 split 几个单词，然后 reverse 这些单词的顺序，最后是这些单词的顺序 join 句子。但是这种方法使用了额外的空间，而不是「原地反转」单词。

正确的方法是先把整个字符串起来 s 反转：

s = "gnodalubal dlrow olleh"

然后将每个单词分别反转：

s = "labuladong world hello"

package com.2023年，algorithm.two_diff_array;import java.util.Arrays;import java.util.Collections;import java.util.List;public class Demo1 {    //方法一    public String reverseWords(String s) {        StringBuilder sb = trimSpaces(s);        // 翻转字符串        reverse(sb, 0, sb.length() - 1);        // 翻转每个单词        reverseEachWord(sb);        return sb.toString();    }    public StringBuilder trimSpaces(String s) {        int left = 0, right = s.length() - 1;        // 去掉字符串开头的空白字符 移动left起点        while (left <= right && s.charAt(left) == ' ') {            ++left;        }        // 去掉字符串末尾的空白字符 移动right起点        while (left <= right && s.charAt(right) == ' ') {            --right;        }        // 去除字符串之间多余的空白字符        StringBuilder sb = new StringBuilder();        while (left <= right) {            char c = s.charAt(left);            if (c != ' ') {                sb.append(c);            } else if (sb.charAt(sb.length() - 1) != ' ') {                sb.append(c);            }            ++left;        }        return sb;    }    /**     * 反转字符串     *     * @param sb     * @param left     * @param right     */    public void reverse(StringBuilder sb, int left, int right) {        while (left < right) {            char tmp = sb.charAt(left);            sb.setCharAt(left++, sb.charAt(right));            sb.setCharAt(right--, tmp);        }    }    /**     * 翻转每个单词     *     * @param sb     */    public void reverseEachWord(StringBuilder sb) {        int n = sb.length();        int start = 0, end = 0;        while (start < n) {            // 循环到单词的末尾            while (end < n && sb.charAt(end) != ' ') {                ++end;            }            // 翻转单词            reverse(sb, start, end - 1);            // 更新start，找下一个单词            start = end + 1;            ++end;        }    }    /**     * 方法二     *     * @param s     * @return     */    public String reversewords2(String s) {        // 除去开头和结尾的空白字符        s = s.trim();        // 正则匹配连续空白字符作为分隔符分割        List<String> wordList = Arrays.asList(s.split("\\s+"));        Collections.reverse(wordList);        return String.join(" ", wordList);    }}

这样，所有单词的顺序就实现了原地反转的目的。扣第 151 题「 颠倒字符串中的单词」也就是类似的问题，你可以顺便做一下。

这个问题的目的是什么？

目的是解释，有时候我们拍脑袋的常规思维在电脑眼里可能不是最优雅的；但是电脑认为最优雅的思维对我们来说并没有那么直观。也许这就是算法的魅力所在。

回到顺时针旋转二维矩阵的问题，传统的想法是找到原始坐标和旋转后坐标的映射规则，但我们是否能让思维跳跃，尝试扭转矩阵，镜像对称，可能会有新的突破。

我们可以先将军 n x n 矩阵 matrix 镜像对称按照左上右下的对角线进行：

然后逆转矩阵的每一行:

发现的结果是 matrix 顺时针旋转 90 度的结果：

// 顺时针旋转二维矩阵 90 度public void rotate(int[][] matrix) {    int n = matrix.length;    // 对称二维矩阵先沿对角线镜像    for (int i = 0; i < n; i++) {        for (int j = i; j < n; j++) {            // swap(matrix[i][j], matrix[j][i]);            int temp = matrix[i][j];            matrix[i][j] = matrix[j][i];            matrix[j][i] = temp;        }    }    // 然后反转二维矩阵的每一行    for (int[] row : matrix) {        reverse(row);    }}// 反转一维数组void reverse(int[] arr) {    int i = 0, j = arr.length - 1;    while (j > i) {        // swap(arr[i], arr[j]);        int temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;        i++;        j--;    }}

旋转二维矩阵的困难在于「行」变成「列」，将「列」变成「行」，只有按照对角线的对称操作才能轻松完成这一点，对称操作后才能轻松发现规律。

想法是相似的，逆时针旋转矩阵的结果是通过另一个对角线镜像对称矩阵，然后逆转每一行：

// 逆时针旋转二维矩阵 90 度void rotate2(int[][] matrix) {    int n = matrix.length;    // 对称二维矩阵镜像沿左下到右上角    for (int i = 0; i < n; i++) {        for (int j = 0; j < n - i; j++) {            // swap(matrix[i][j], matrix[n-j-1][n-i-1])            int temp = matrix[i][j];            matrix[i][j] = matrix[n - j - 1][n - i - 1];            matrix[n - j - 1][n - i - 1] = temp;        }    }    // 然后反转二维矩阵的每一行    for (int[] row : matrix) {        reverse(row);    }}// 反转一维数组void reverse(int[] arr) {    int i = 0, j = arr.length - 1;    while (j > i) {        // swap(arr[i], arr[j]);        int temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;        i++;        j--;    }}