832. 翻转图像
832. 翻转图像
🟢 🔖 位运算
数组
双指针
矩阵
模拟
🔗 力扣
LeetCode
题目
Given an n x n
binary matrix image
, flip the image horizontally , then invert it, and return the resulting image.
To flip an image horizontally means that each row of the image is reversed.
- For example, flipping
[1,1,0]
horizontally results in[0,1,1]
.
To invert an image means that each 0
is replaced by 1
, and each 1
is replaced by 0
.
- For example, inverting
[0,1,1]
results in[1,0,0]
.
Example 1:
Input: image = [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]
Example 2:
Input: image = [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Constraints:
n == image.length
n == image[i].length
1 <= n <= 20
images[i][j]
is either0
or1
.
题目大意
给定一个 n x n
的二进制矩阵 image
,先 水平 翻转图像,然后 **反转 **图像并返回 结果 。
水平 翻转图片就是将图片的每一行都进行翻转,即逆序。
- 例如,水平翻转
[1,1,0]
的结果是[0,1,1]
。
反转 图片的意思是图片中的 0
全部被 1
替换, 1
全部被 0
替换。
- 例如,反转
[0,1,1]
的结果是[1,0,0]
。
示例 1:
输入: image = [[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:
输入: image = [[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]]
提示:
n == image.length
n == image[i].length
1 <= n <= 20
images[i][j]
==0
或1
.
解题思路
翻转和取反同时操作:
- 使用双指针从行的两端开始,逐步交换对应位置的元素(水平翻转)。
- 在交换元素的同时,对元素进行取反操作:
- 使用位运算
^ 1
实现取反操作(0 ^ 1 = 1
,1 ^ 1 = 0
)。
- 使用位运算
- 注意要兼容列数为奇数的情况。
遍历整个二维数组,对二维数组的每一行都应用上述操作。
修改二维数组后直接返回。
复杂度分析
- 时间复杂度:
O(m * n)
,二维数组有m
行,每行长度为n
, 对每一行,我们需要遍历O(n / 2)
次。 - 空间复杂度:
O(1)
,只使用常数级额外空间。
代码
/**
* @param {number[][]} image
* @return {number[][]}
*/
var flipAndInvertImage = function (image) {
const n = image[0].length; // 行的长度
for (let row of image) {
// 双指针从两端进行翻转和取反
for (let i = 0; i < Math.floor(n / 2); i++) {
// 交换并取反
let temp = row[i];
row[i] = row[n - i - 1] ^ 1; // 取反
row[n - i - 1] = temp ^ 1; // 取反
}
// 如果长度是奇数,处理中间元素
if (n % 2 === 1) {
row[Math.floor(n / 2)] ^= 1;
}
}
return image;
};