翻转图像 图解题解

n×n 的 0/1 图片，翻转加取反要返回什么

给一个 n×n 的二进制矩阵 image，只有 0 和 1。要做两件事：每一行先水平翻转（整行首尾倒过来，[1,1,0] 逆序成 [0,1,1]），再整图取反（0 换 1、1 换 0，[0,1,1] 取反成 [1,0,0]），返回结果。题面 image=[[1,1,0],[1,0,1],[0,0,0]]，答案是 [[1,0,0],[0,1,0],[1,1,1]]。

先逆序整行、再整图取反，得多扫一趟多占一行

照题面直译：另开一行，把原行从后往前抄一遍得逆序，再逐格对调 0 和 1。一行 n 个数、扫两趟，还得为逆序结果多占一整行空间。全矩阵 n×n 个格子各碰两回，时间 O(n²)、额外空间 O(n)。这么写能过，可那两趟遍历和那份额外空间都省得掉。

一对位置交换再取反，净效果是什么

水平翻转就是把一行里对称的一对值对调——左端的 row[i] 换到右端 row[j] 的位置；取反是给每格做一次 0/1 开关。把这两件事落在一对位置上算清楚：这一对相等时，对调后仍相等、再各取反，等于两端各翻一次；这一对不同时，对调再取反恰好抵消，两端原样不动。

于是逆序和取反不必分两趟。用一个对撞双指针（左指针 i 从头、右指针 j 从尾，一起朝中间收）扫每一行：i、j 值相等就把两端各取反一次，不同就跳过，全程原地改、不再另建逆序数组。奇数长的行正中间剩一格，它对调后位置不动，单独取反一次即可。

双指针怎么收，中点为什么单独处理

对每一行，起手让 i 指向行首、j 指向行尾（下标 n−1）。i 还在 j 左边时看这一对：row[i] 等于 row[j] 就把两个都异或 1——异或 1 正好是一次 0/1 翻转，不同则原封不动；随后 i 右移、j 左移，继续朝中间收。等 i 和 j 撞上（i 等于 j），落到正中间那一格，它没有配对的另一端，循环外补一次取反。偶数行长时 i 和 j 错身而过、永不相等，全部成对处理，走不到中点这一步。

题面这三行，双指针各扫出什么

第 0 行 [1,1,0]：i 在位置 0（值 1）、j 在位置 2（值 0），两端不同，跳过；i、j 收到位置 1 相遇，这是中点，值 1，单独取反成 0，得 [1,0,0]。

第 1 行 [1,0,1]：两端都是 1，相等，各取反成 0，行成 [0,0,0]；中点位置 1 的 0 取反成 1，得 [0,1,0]。第 2 行 [0,0,0]：两端都是 0 相等，各取反成 1，行变 [1,0,1]，中点 0 取反成 1，得 [1,1,1]。三行拼起来正是题面答案 [[1,0,0],[0,1,0],[1,1,1]]。

不同的两端别去翻，奇数中点别漏掉

每个格子恰好被一个指针碰一次，n×n 个格子，时间 O(n²)；只用 i、j 两个指针原地改，空间 O(1)。真正常写坏的是两端不同那一对：它经过互换加取反本就回到原值，你若顺手也给它翻一下，反倒把对的改成错的。另一处躲在奇数边长的正中间：那格只在 i 和 j 相遇时露面，循环里 i 严格小于 j 够不到它，漏掉循环外补的那次取反，整行中央就少翻一格。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]:
        n = len(image)
        for row in image:
            i, j = 0, n - 1
            while i < j:
                if row[i] == row[j]:
                    row[i] ^= 1
                    row[j] ^= 1
                i, j = i + 1, j - 1
            if i == j:
                row[i] ^= 1
        return image

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<vector<int>> flipAndInvertImage(vector<vector<int>>& image) {
        for (auto& row : image) {
            int i = 0, j = row.size() - 1;
            for (; i < j; ++i, --j) {
                if (row[i] == row[j]) {
                    row[i] ^= 1;
                    row[j] ^= 1;
                }
            }
            if (i == j) {
                row[i] ^= 1;
            }
        }
        return image;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int[][] flipAndInvertImage(int[][] image) {
        for (int[] row : image) {
            int i = 0, j = row.length - 1;
            for (; i < j; ++i, --j) {
                if (row[i] == row[j]) {
                    row[i] ^= 1;
                    row[j] ^= 1;
                }
            }
            if (i == j) {
                row[i] ^= 1;
            }
        }
        return image;
    }
}