原文链接: https://leetcode-cn.com/problems/flipping-an-image

英文原文

Given an n x n binary matrix image, 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: image = [[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: image = [[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]]

 

Constraints:

• n == image.length
• n == image[i].length
• 1 <= n <= 20
• images[i][j] is either 0 or 1.

中文题目

给定一个二进制矩阵 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减的情况下）

  代码

  第一种

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

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

  第二种

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

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

  []
  map(function,list)

  等价于

  []
  for x in list:
      function(x)

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

  []
  def function(x):
      return 1 - x 

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

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

  就和第一种一样了。

  复杂度

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

希望能够帮到大家！

统计信息

通过次数	提交次数	AC比率
87206	109604	79.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言