题目描述
https://leetcode.com/problems/flipping-an-image/
Given a binary matrix A, we want to 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: [[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: [[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]]
Notes:
1 <= A.length = A[0].length <= 20
0 <= A[i][j] <= 1
博主第一次提交的代码
不够极致，看下面的别人的代码
class Solution {
public int[][] flipAndInvertImage(int[][] A) {
int[][] result = new int[A.length][A[0].length];
for(int i = 0; i < A.length; i++){
for(int j = 0; j < A[i].length; j++){
result[i][j] = A[i][ A[i].length - 1 - j] == 1 ? 0:1;
}
}
return result;
}
}
他人的优秀代码
https://leetcode.com/problems/flipping-an-image/discuss/130590/C%2B%2BJavaPython-Reverse-and-Toggle
这段代码可以细细品味
- 一次处理在水平上对称的两个元素
- 因为是水平的元素翻转，如果不同的元素变换了之后，再取值翻转，相当于没有变化，这是这段代码的一个优化点
public int[][] flipAndInvertImage(int[][] A) {
int n = A.length;
for (int[] row : A)
for (int i = 0; i * 2 < n; i++)
if (row[i] == row[n - i - 1])
row[i] = row[n - i - 1] ^= 1;
return A;
}
总结
这个写法看起来时间复杂度像O(n^2),但是实际上时间复杂度是O(n)，因为我们对所有元素都指遍历了一次。
