LC 832. 翻转图像
题目描述
这是 LeetCode 上的 832. 翻转图像 ,难度为 简单。
给定一个二进制矩阵 A,我们想先水平翻转图像,然后反转图像并返回结果。
水平翻转图片就是将图片的每一行都进行翻转,即逆序。例如,水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。
反转图片的意思是图片中的 0 全部被 1 替换, 1 全部被 0 替换。例如,反转 [0, 1, 1] 的结果是 [1, 0, 0]。
示例 1:1
2
3
4输入:[[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
2
3
4输入:[[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() 得到「深拷贝数组」,而对于多维数组而言,得到的是「浅拷贝数组」。
1 |
|
1 |
|
- 时间复杂度:$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 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!