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].

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

Idea 1. Use ^ to reverse bit, 1 ^ 1 = 0, 0 ^ 1= 1; odd length, i < (n + 1) /2 or i * 2 < n

Time complexity: O(m * n) linear in terms of the number of elements in the input matrix

Space complexity: O(1)

 1 class Solution {
 2     public int[][] flipAndInvertImage(int[][] A) {
 3         int m = A.length;
 4         int n = A[0].length;
 5         
 6         for(int i = 0; i < m; ++i) {
 7             for(int j = 0; j < (n+1)/2; ++j) {
 8                 int temp = A[i][j] ^ 1;
 9                 A[i][j] = A[i][n-1-j] ^ 1;
10                 A[i][n-1-j] = temp;
11             }
12         }
13         
14         return A;
15     }
16 }

Idea 1.a Take advantage the fact value is either 1, or 0, if two flipped values are not the same, nothing is needed to do, 1 -> 0 (after flipping) -> 1 (after reversing), 0 -> 1(after flipping) -> 0(after reversing); if the same, reverse the value with ^1.

Time complexity: O(m * n)

Space complexity: O(1)

 1 class Solution {
 2     public int[][] flipAndInvertImage(int[][] A) {
 3         int m = A.length;
 4         int n = A[0].length;
 5         
 6         for(int i = 0; i < m; ++i) {
 7             for(int j = 0; 2 * j < n; ++j) {
 8                 if(A[i][j] == A[i][n-1-j]) {
 9                     A[i][j] = A[i][j] ^ 1;
10                     A[i][n-1-j] = A[i][j];
11                 }
12             }
13         }
14         
15         return A;
16     }
17 }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄