翻转图像 图解题解

这道题到底在问什么

输入

image=[[1,1,0],[1,0,1],[0,0,0]]

输出

[[1,0,0],[0,1,0],[1,1,1]]

输入

一行 [1,1,0]

输出

先逆序成 [0,1,1],再取反成 [1,0,0]

最优解：一步一步想明白

1. 3记牢这把尺子:两端相等就各翻一次,两端不同就不动,正中间单独翻一次。下面每一帧都在套它。
2. 4原图共 3 行 3 列,每格非 0 即 1这是原始图片,绿色格是 1、蓝色格是 0。我们一行一行地处理,每行用左右两个指针向中间收。
3. 5第 0 行 = [1, 1, 0],左指针 i = 0,右指针 j = 2轮到第 0 行,内容是 [1, 1, 0]。把左指针放在头、右指针放在尾,紫色标出这两端,准备向中间收。
4. 6左端值 1,右端值 0 → 不同看这一行的两端:位置 0 是 1,位置 2 是 0。它们不同。互换后再取反正好抵消,所以这两端最终保持原样,不用动。
5. 7位置 0 与 2 维持 1 和 0两端不同,什么都不用改,位置 0 还是 1、位置 2 还是 0。两个指针各自向中间挪一格。
6. 8左右指针在位置 1 相遇,中点值 1两个指针在位置 1 相遇,这是正中间那一格,值是 1。它水平翻转后位置不变,所以没有「互相抵消」这回事,只需要老老实实取反一次。
7. 9中点位置 1 取反为 0中点从 1 取反成 0(红色闪一下)。这一行所有格子都处理完了。
8. 10第 0 行最终 = [1, 0, 0]第 0 行收工,结果是 [1, 0, 0]。已完成行数加一,接着处理下一行,套路完全一样。
9. 11第 1 行 = [1, 0, 1],左指针 i = 0,右指针 j = 2轮到第 1 行,内容是 [1, 0, 1]。把左指针放在头、右指针放在尾,紫色标出这两端,准备向中间收。
10. 12左端值 1,右端值 1 → 相等看这一行的两端:位置 0 是 1,位置 2 是 1。它们相等。水平翻转会把它俩互换,换完仍相等,再各取反,等于两端都要翻一次。
11. 13位置 0 与 2 翻转为 0 和 0两端相等,各翻一次:位置 0 变 0、位置 2 变 0(红色闪一下表示刚翻)。这一帧就同时做完了这对格子的翻转和取反。
12. 14左右指针在位置 1 相遇,中点值 0两个指针在位置 1 相遇,这是正中间那一格,值是 0。它水平翻转后位置不变,所以没有「互相抵消」这回事,只需要老老实实取反一次。
13. 15中点位置 1 取反为 1中点从 0 取反成 1(红色闪一下)。这一行所有格子都处理完了。
14. 16第 1 行最终 = [0, 1, 0]第 1 行收工,结果是 [0, 1, 0]。已完成行数加一,接着处理下一行,套路完全一样。
15. 17第 2 行 = [0, 0, 0],左指针 i = 0,右指针 j = 2轮到第 2 行,内容是 [0, 0, 0]。把左指针放在头、右指针放在尾,紫色标出这两端,准备向中间收。
16. 18左端值 0,右端值 0 → 相等看这一行的两端:位置 0 是 0,位置 2 是 0。它们相等。水平翻转会把它俩互换,换完仍相等,再各取反,等于两端都要翻一次。
17. 19位置 0 与 2 翻转为 1 和 1两端相等,各翻一次:位置 0 变 1、位置 2 变 1(红色闪一下表示刚翻)。这一帧就同时做完了这对格子的翻转和取反。
18. 20左右指针在位置 1 相遇,中点值 0两个指针在位置 1 相遇,这是正中间那一格,值是 0。它水平翻转后位置不变,所以没有「互相抵消」这回事,只需要老老实实取反一次。
19. 21中点位置 1 取反为 1中点从 0 取反成 1(红色闪一下)。这一行所有格子都处理完了。
20. 22第 2 行最终 = [1, 1, 1]第 2 行收工,结果是 [1, 1, 1]。三行全部处理完毕,下一帧返回结果。
21. 23三行都做完,返回 [[1,0,0],[0,1,0],[1,1,1]]三行全部处理完,矩阵变成 [[1,0,0],[0,1,0],[1,1,1]]。每一行都是「逆序 + 取反」的结果,而我们只用一遍双指针就一次性做完了两步。
22. 24先逐行逆序、再整张取反,得到一模一样的矩阵换个老实办法验证一下:把每行先逆序、再把全图 0 和 1 互换,得到的矩阵和上一帧完全相同。可见双指针那套「相等才翻、不同不动、中点单翻」确实等价于规规矩矩的两步法。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问