LeetCode偶尔一题 —— 832. 翻转图像

题目描述

分析题目

按照题意我们只要先对每个子数组先做逆序,再做 0 –> 1 和 1 –> 0 的替换即可,于是我们可以写出以下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @param {number[][]} A
* @return {number[][]}
*/
var flipAndInvertImage = function(A) {
for (let i = 0; i < A.length; i++) {
let j = 0, k = A[i].length - 1
while (j < k) {
[A[i][j], A[i][k]] = [A[i][k], A[i][j]]
A[i][j] = A[i][j] ? 0 : 1
A[i][k] = A[i][k] ? 0 : 1
j++, k--
}
if (j === k) {
A[i][j] = A[i][j] ? 0 : 1
}
}
return A
};

优化

对于 0 –> 1 和 1 –> 0 的替换,我们大可不必用三元运算符,而是采用异或运算,可以把代码简化如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @param {number[][]} A
* @return {number[][]}
*/
var flipAndInvertImage = function(A) {
for (let i = 0; i < A.length; i++) {
let j = 0, k = A[i].length - 1
while (j < k) {
[A[i][j], A[i][k]] = [A[i][k], A[i][j]]
A[i][j] ^= 1
A[i][k] ^= 1
j++, k--
}
if (j === k) {
A[i][j] ^= 1
}
}
return A
};

进阶

仔细观察题目中提供的测试用例,我们发现,左右两个数不相等时可以直接忽略,于是最终版的程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @param {number[][]} A
* @return {number[][]}
*/
var flipAndInvertImage = function(A) {
for (let i = 0; i < A.length; i++) {
let j = 0, k = A[i].length - 1
while (j < k) {
if (A[i][j] === A[i][k]) {
A[i][j] ^= 1
A[i][k] ^= 1
}
j++, k--
}
if (j === k) {
A[i][j] ^= 1
}
}
return A
};
  • 时间复杂度O(n * k / 2)
  • 空间复杂度O(1)

原题地址: https://leetcode-cn.com/problems/flipping-an-image/
代码不定时更新,欢迎 star 我的 repo