LC 832. 翻转图像

题目描述

这是 LeetCode 上的 832. 翻转图像 ，难度为 简单。

给定一个二进制矩阵 A，我们想先水平翻转图像，然后反转图像并返回结果。

水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。

反转图片的意思是图片中的 0 全部被 1 替换，1 全部被 0 替换。

例如，反转 [0, 1, 1] 的结果是 [1, 0, 0]。

示例 1：

输入：[[1,1,0],[1,0,1],[0,0,0]]

输出：[[1,0,0],[0,1,0],[1,1,1]]

解释：首先翻转每一行: [[0,1,1],[1,0,1],[0,0,0]]；
     然后反转图片: [[1,0,0],[0,1,0],[1,1,1]]

示例 2：

输入：[[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]

输出：[[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

解释：首先翻转每一行: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]]；
     然后反转图片: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

提示：

• $1 <= A.length = A[0].length <= 20$
• $0 <= A[i][j] <= 1$

---

双指针

对于每行而言，我们都需要对其进行「翻转」和「反转」。

这两步可以到放到一遍循环里做：

• 翻转部分：使用双指针进行数字交换
• 反转部分：将数字存储进目标位置前，使用「异或」对 0 1 进行翻转

当前有一些「小细节」需要注意：

1. 题目要求我们对参数图像进行翻转，并返回新图像。因此我们不能对输入直接进行修改，而要先进行拷贝再处理
2. 由于我们将「翻转」和「反转」合成了一步，因此对于「奇数」图像，需要对中间一列进行特殊处理：仅「反转」

对于 Java 的基本类型拷贝，有三种方式进行拷贝：

1. System.arraycopy() : 底层的数组拷贝接口，具体实现与操作系统相关，调用的是系统本地方法。需要自己创建好目标数组进行传入，可指定拷贝长度，实现局部拷贝。
2. Arrays.copyOf() : 基于 System.arraycopy() 封装的接口，省去了自己目标数组这一步。但无法实现局部拷贝。
3. clone() : Object 的方法。会调用每个数组成员的 clone() 方法进行拷贝。因此对于一维数组而言，可以直接使用 clone() 得到「深拷贝数组」，而对于多维数组而言，得到的是「浅拷贝数组」。

Java 代码（P1）：

class Solution {
    public int[][] flipAndInvertImage(int[][] a) {
        int n = a.length;
        int[][] ans = new int[n][n];
        for (int i = 0; i < n; i++) {
            // ans[i] = a[i].clone(); 
            // ans[i] = Arrays.copyOf(a[i], n); 
            System.arraycopy(a[i], 0, ans[i], 0, n); 
            int l = 0, r = n - 1;
            while (l < r) {
                int c = ans[i][r];
                ans[i][r--] = ans[i][l] ^ 1;
                ans[i][l++] = c ^ 1;
            }
            if (n % 2 != 0) ans[i][r] ^= 1; 
        }
        return ans;
    }
}

Java 代码（P2）：

class Solution {
    public int[][] flipAndInvertImage(int[][] a) {
        int n = a.length;
        int[][] ans = new int[n][n];
        // 遍历每一行进行处理
        for (int i = 0; i < n; i++) {
            // 对每一行进行拷贝（共三种方式）
            // ans[i] = a[i].clone(); 
            // ans[i] = Arrays.copyOf(a[i], n); 
            System.arraycopy(a[i], 0, ans[i], 0, n); 
            // 使用「双指针」对其进行数组交换，实现「翻转」
            // 并通过「异或」进行 0 1 翻转，实现「反转」
            int l = 0, r = n - 1;
            while (l < r) {
                int c = ans[i][r];
                ans[i][r--] = ans[i][l] ^ 1;
                ans[i][l++] = c ^ 1;
            }
            // 由于「奇数」矩形的中间一列不会进入上述双指针逻辑
            // 需要对其进行单独「反转」
            if (n % 2 != 0) ans[i][r] ^= 1; 
        }
        return ans;
    }
}

• 时间复杂度：$O(n^2)$
• 空间复杂度：使用了同等大小的空间存储答案。复杂度为 $O(n^2)$

---

补充

Q: 那么 Arrays.copyOfRange() 与 System.arraycopy() 作用是否等同呢？

A: 不等同。

Arrays.copyOf() 和 Arrays.copyOfRange() 都会内部创建目标数组。

前者是直接创建一个和源数组等长的数组，而后者则是根据传参 to 和 from 计算出目标数组长度进行创建。

它们得到的数组都是完整包含了要拷贝内容的，都无法实现目标数组的局部拷贝功能。

例如我要拿到一个长度为 10 的数组，前面 5 个位置的内容来源于「源数组」的拷贝，后面 5 个位置我希望预留给我后面自己做操作，它们都无法满足，只有 System.arraycopy() 可以。

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.832 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。