题目描述
这是 LeetCode 上的 832. 翻转图像。
Tag : 「双指针」
给定一个二进制矩阵 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 进行翻转
当前有一些「小细节」需要注意：
- 题目要求我们对参数图像进行翻转，并返回新图像。因此我们不能对输入直接进行修改，而要先进行拷贝再处理
- 由于我们将「翻转」和「反转」合成了一步，因此对于「奇数」图像，需要对中间一列进行特殊处理：仅「反转」
对于 Java 的基本类型拷贝，有三种方式进行拷贝：
- System.arraycopy() : 底层的数组拷贝接口，具体实现与操作系统相关，调用的是系统本地方法。需要自己创建好目标数组进行传入，可指定拷贝长度，实现局部拷贝。
- Arrays.copyOf() : 基于
System.arraycopy()封装的接口，省去了自己目标数组这一步。但无法实现局部拷贝。 - clone() : Object 的方法。会调用每个数组成员的 clone() 方法进行拷贝。因此对于一维数组而言，可以直接使用 clone() 得到「深拷贝数组」，而对于多维数组而言，得到的是「浅拷贝数组」。
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; } } 复制代码
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(n2)
- 空间复杂度：使用了同等大小的空间存储答案。复杂度为 O(n^2)O(n2)
补充
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 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
