题目

给定一个二进制矩阵 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. 用 1 - 当前值，得到的就是0和1的翻转
2. 用 1 ^ 当前值，得到的也是0和1的反转。这个符号是异或，相同为0，相异为1
在所有方法里这两种翻转的方法都可以互换，不做深究

方法一：照本宣科法

思路

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

代码

class Solution:
    def flipAndInvertImage(self, A: List[List[int]]) -> List[List[int]]:
        for row in A:       
            for k,_ in enumerate(row): row[k] = 1 - row[k]        # Python 风格的循环, 1和0反转
            i, j = 0, len(row) - 1
            while i < j:
                row[i], row[j] = row[j], row[i] # Python 特有的交换
                i, j = i + 1, j - 1
        return A

复杂度

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

方法二：见缝插针法

思路

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

代码

class Solution:
    def flipAndInvertImage(self, A: List[List[int]]) -> List[List[int]]:
        for row in A:
            for j in range((len(row) + 1) // 2):
                if row[j] == row[-1-j]:             # 采用Python化的符号索引
                    row[j] = row[-1-j] = 1 - row[j]    
        return A

复杂度

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

方法三：花样一行法

思路

主要运用生成器的技巧，在一行生成复合要求的列表
一般要用切片，map等方法
主要操作还是和方法一一样，按部就班地翻转
有多种一行写完的方法（不区分异或和被1减的情况下）

代码

第一种

1	return [[j ^ 1 for j in row[::-1]] for row in A]

这个思路是对每一行先翻转，再对每一行异或。其中这里的切片是完整取row然后逆序，生成新的一个list。

第二种

1	return [list(map(lambda x:1-x,row[::-1])) for row in A]

这个思路一样，只是利用了map和lambda。map是指对第二个参数的每一项执行第一个参数（函数）。相当于

1	map(function,list)

等价于

1 2	for x in list: function(x)

最后需要一个list()将map对象转为list对象
lambda是匿名函数，就是将函数写在一行，以lambda x:1-x 为例，就相当于

1 2	def function(x): return 1 - x

当然可以省略掉map和lambda，变成

1	return [1 - x for x in row[::-1] for row in A]

就和第一种一样了。

复杂度

时间复杂度 $O(N)$ ,遍历一遍
空间复杂度 $O(n)$ ,切片是需要额外空间的，这里的n为行数，而不是元素总数。
实测效果，是中等速度的。因为虽然复杂度更大，但是用了内置函数，效率更高。所以介于方法一和方法二之间。

希望能够帮到大家！