二进制数的有趣运算、解决顺/逆时针旋转矩阵、扭曲矩阵等问题

分享一些巧妙的二进制数运算。只要你有常识，以后遇到类似的问题就不会手足无措。 。

顺时针/逆时针旋转矩阵

旋转二进制数是常见的笔试题。第48题“图像处理”很常见：

这道题很容易理解，只为你二维矩阵顺时针旋转90度，难点在于改变“在他的位置”。函数签名如下：

void rotate(int[][] matrix)

如何“就地”操作二维矩阵？仔细想想，手术似乎非常困难。可能需要构建一个智能算法机制来旋转“旋转”矩阵：

但事实上，这个问题并不是用通常的方式解决的，在解释智能解决方案之前，我们先来看看。 Google 热身的另一道算法题：

给你一个包含多个单词和空格的字符串s，请写一个算法，代替单词。

，例如，如果给您这样的字符串：

s = "hello world labuladong"

您需要将单词置于此字符串中的单词：to空格将分成多个单词，然后颠倒这些单词的顺序，最后输入这些单词的顺序。 这些词将成为一个句子。但这种方法使用了额外的空间，并且不会“反转”单词的位置。

正确的做法是把整条线颠倒S：

s = "gnodalubal dlrow olleh"

，然后将每个单词颠倒：

s = "labuladong world hello"

这样，原来的顺序就可以恢复到所有单词了。

我为什么要问这个问题？

我们的目标是表明，有时我们头脑中的传统思维可能不是最优雅的计算机；但计算机认为最美的想法对我们来说并不那么明显。也许这就是算法的美妙之处。

回到前面提到的二维矩阵顺时针旋转的问题，常见的思路就是找到原坐标和旋转后的坐标之间的映射规则，但是我们能不能允许思维跳跃一下尝试平移和旋转反映。矩阵？诸如不对称之类的工作可以带来新的发展。

我们可以从左上到右下对角反射n x n矩阵矩阵：♿：

并找到答案是 的结果矩阵顺时针旋转90度：

将上述读者评论翻译成代码来解决这个问题：你可能会想，如果你从来没有问过这个问题，你怎么会得到这个想法？

其实这一点我觉得很好理解。如果你学过线性代数，算法题的核心是矩阵变换，你就能搞清楚。

即使你从来没有学过线性代数，翻转二维矩阵的难点就在于将“行”变成“列”，将“列”变成“行”。这可以通过遵循对角线的对称函数轻松完成。现在很容易看出对称运算后的规则了。

说了这么多，我们可以稍微跑题了，把矩阵逆时针旋转90度怎么样？

同一点。只要将对称矩阵与另一条对角线进行比较，重复每一行，就会得到逆时针旋转的结果：

// 将二维矩阵原地逆时针旋转 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) { /* 见上文 */}

现在，旋转矩阵问题就解决了。矩阵的螺旋遍历过渡。 。基本上，它是按相反的顺序进行的。 。

今天我们来讨论第54题“螺旋矩阵”，看看如何优雅地遍历二维矩阵：

函数签名如下：

List<Integer> spiralOrder(int[][] matrix)

解决问题的基本思路是遵循right、bottom、and 从左到左遍历数组，用四个变量包围不变元素的边界：

遍历螺旋时平行边界会减小。直到螺旋穿过整个阵列：

如果仍然存在 在这个概念中很容易破解代码：

List<Integer> spiralOrder(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int upper_bound = 0, lower_bound = m - 1;
    int left_bound = 0, right_bound = n - 1;
    List<Integer> res = new LinkedList<>();
    // res.size() == m * n 则遍历完整个数组
    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 (left_bound <= right_bound) {
            // 在右侧从上向下遍历
            for (int i = upper_bound; i <= lower_bound; i++) {
                res.add(matrix[i][right_bound]);
            }
            // 右边界左移
            right_bound--;
        }

        if (upper_bound <= lower_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;
}

问题 59 “螺旋矩阵 II”是一个类似的问题，相反，允许您创建螺旋顺序矩阵：

函数签名如下：

int[][] generateMatrix(int n)

有了上面的描述，稍微修改一下代码就可以回答这个问题：

int[][] generateMatrix(int n) {
    int[][] matrix = new int[n][n];
    int upper_bound = 0, lower_bound = n - 1;
    int left_bound = 0, right_bound = n - 1;
    // 需要填入矩阵的数字
    int num = 1;

    while (num <= n * n) {
        if (upper_bound <= lower_bound) {
            // 在顶部从左向右遍历
            for (int j = left_bound; j <= right_bound; j++) {
                matrix[upper_bound][j] = num++;
            }
            // 上边界下移
            upper_bound++;
        }

        if (left_bound <= right_bound) {
            // 在右侧从上向下遍历
            for (int i = upper_bound; i <= lower_bound; i++) {
                matrix[i][right_bound] = num++;
            }
            // 右边界左移
            right_bound--;
        }

        if (upper_bound <= lower_bound) {
            // 在底部从右向左遍历
            for (int j = right_bound; j >= left_bound; j--) {
                matrix[lower_bound][j] = num++;
            }
            // 下边界上移
            lower_bound--;
        }

        if (left_bound <= right_bound) {
            // 在左侧从下向上遍历
            for (int i = lower_bound; i >= upper_bound; i--) {
                matrix[i][left_bound] = num++;
            }
            // 左边界右移
            left_bound++;
        }
    }
    return matrix;
}

目前，两个螺旋也已经解决了矩阵问题。