leetcode刷题 [java] 832. 翻转图像

给定一个二进制矩阵 A，我们想先水平翻转图像，然后反转图像并返回结果。

水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。

反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。例如，反转 [0, 1, 1] 的结果是 [1, 0, 0]。

示例 1:

输入: [[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,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

这道题不难，当属easy，但是方法很多
对于1和0的翻转，有两种思路
用 1 - 当前值，得到的就是0和1的翻转
用 1 ^ 当前值，得到的也是0和1的反转。这个符号是异或，相同为0，相异为1
在所有方法里这两种翻转的方法都可以互换，不做深究

方法一：照本宣科法
思路
完全走一遍题目要求的流程
对原列表做两次翻转工作
首尾反转采用双指针，一个指向头，一个指向尾，两个位置交换并且指针逐渐往中间靠
返回原列表

代码

class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        for(int i= 0;i<A.length; i++){
            int[] B = new int[A.length];
            int index = 0;
            for(int j=0;j<A[i].length; j++){
                index = A[i].length - 1 -j;
                B[j] = A[i][index];
                if(B[j] == 1){
                    B[j] = 0;
                    continue;
                }
                if(B[j] == 0){
                    B[j] = 1;
                    continue;
                }
            }
            A[i] = B;
        }
        return A;
    }
}

执行用时内存消耗 1 ms 36.6 MB

注意
第一次犯了一个非常简单的错误，在if判断是1还是0的时候，忘写了一条continue语句，导致最后输出全是1！😓

复杂度
时间复杂度 O(N)O(N)，做了两次遍历，而O(2N) = O(N)O(2N)=O(N)
空间复杂度 O(1)O(1)，只用了常量空间，没有用额外的空间
实测效果，是最low的，最慢的......

方法二：见缝插针法
思路
这应该也是作者想要我们想出来的办法
首先我们一行的第一个数，找到它对应的数，也就是这一行最后一个
如果这两个数是不同的，比如说一个是1,一个是0,那么先10反转，则一个是0,一个是1,再左右翻转，又变回一个是1,一个是0
这说明当两个数是不同的时候，不用做任何事情
当两个数相同的时候，要同时异或或被1减，即10反转
注意，循环的范围应该是((row.length+1)/2),不能忘了加一。因为，如果列数为奇数，那么中间的数虽然不要左右交换，但是10还是要反转的，因此要多一次循环，相同于中间的数与自己是相同的，要反转。
代码

class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        for(int[] row : A ){
            for(int j=0;j<(row.length+1)/2; j++){
                if(row[j] == row[row.length - 1 -j]){
                    row[j] = 1 - row[j];
                    row[row.length - 1 -j] = row[j];
                }
            }
        }
        return A;
    }
}

执行用时内存消耗 0 ms 37.2 MB

复杂度
时间复杂度 O(N)O(N)，做了一次遍历。
空间复杂度 O(1)O(1)，只用了常量空间，没有用额外的空间
实测效果，是最快的