各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 31 天。今天力扣上的每日一题是「832. 翻转图像」。

解题思路

今天这个题是 Easy，不用想太多，直接按照题目要求来就行。下文我提供了三种方法。

技巧：题目要求让 0 变成 1，1 变成 0，可以使用 $1 - x$，也可以使用**x ^ 1**。

方法一：两次遍历

  1. 先左右翻转每行；
  2. 再把该行的所有元素 0 变成 1，1 变成 0.

这种方法对每个元素遍历了两次。

  1. class Solution:
  2.     def flipAndInvertImage(self, A):
  3.         """
  4.         :type A: List[List[int]]
  5.         :rtype: List[List[int]]
  6.         """
  7.         rows = len(A)
  8.         cols = len(A[0])
  9.         for row in range(rows):
  10.             A[row] = A[row][::-1]
  11.             for col in range(cols):
  12.                 A[row][col] ^= 1
  13.         return A
  • 时间复杂度：$O(2*N^2)$，超过了85.52%的提交。
    - 空间复杂度：$O(1)$。

方法二：一次遍历

也可以遍历一次解决：一边左右翻转，一边修改数字。

可以用数学公式表示为：$A, B = 1 - B, 1 - A$。

这个方法需要注意的是：因为我们是同时修改了左右对称的元素，所以我们只用遍历到每一行的中间位置（含）。

  1. class Solution:
  2.     def flipAndInvertImage(self, A: List[List[int]]) -> List[List[int]]:
  3.         N = len(A)
  4.         for i in range(N):
  5.             for j in range((N + 1)//2):
  6.                 A[i][j], A[i][N - 1- j] = 1 - A[i][N - 1 -j], 1- A[i][j]
  7.         return A
  • 时间复杂度：O(N ^ 2)，超过了96%的提交。
    - 空间复杂度：O(1)。

方法三：额外空间

还有一种方法是，我们不原地修改数组 A，而是开辟了新空间，把结果放在新空间里。

同样地，只用把每个元素遍历一次，$res[i][j] = 1 - A[i][N - 1 - j]$，同时实现左右翻转 以及 0和1的翻转。

  1. class Solution(object):
  2.     def flipAndInvertImage(self, A):
  3.         """
  4.         :type A: List[List[int]]
  5.         :rtype: List[List[int]]
  6.         """
  7.         M, N = len(A), len(A[0])
  8.         res = [[0] * N for _ in range(M)]
  9.         for i in range(M):
  10.             for j in range(N):
  11.                 res[i][j] = 1 - A[i][N - 1 - j]
  12.         return res

在 Python 中该方法也可以优化成一行。

  1. class Solution(object):
  2.     def flipAndInvertImage(self, A):
  3.         """
  4.         :type A: List[List[int]]
  5.         :rtype: List[List[int]]
  6.         """
  7.         return [[1 - A[i][len(A) - 1 - j] for j in range(len(A))] for i in range(len(A))]
  • 时间复杂度：O(N^2)，超过了6.22%的提交。
  • 空间复杂度：O(N^2)。

刷题心得

今天这个题是 Easy，没有啥意思，不过可以趁机复习一下异或运算。分享一下真实世界的异或运算。

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！