【LeetCode】832. 翻转图像

发表于 更新于 分类于 Valine：
本文字数： 921 阅读时长 ≈ 1 分钟

832. 翻转图像

思路

  1. 找规律
  2. 异或

情况一：A[$i$][$left$]=0,A[$i$][$right$]=0。对第 $i$ 行进行水平翻转之后，A[$i$][$left$]=0,A[$i$][$right$]=0。进行反转之后，A[$i$][$left$]=1,A[$i$][$right$]=1。

情况二：A[$i$][$left$]=1,A[$i$][$right$]=1。对第 $i$ 行进行水平翻转之后，A[$i$][$left$]=1,A[$i$][$right$]=1。进行反转之后，A[$i$][$left$]=0,A[$i$][$right$]=0。

情况三：A[$i$][$left$]=0,A[$i$][$right$]=1。对第 $i$ 行进行水平翻转之后，A[$i$][$left$]=1,A[$i$][$right$]=0。进行反转之后，A[$i$][$left$]=0,A[$i$][$right$]=1。

情况四：A[$i$][$left$]=1,A[$i$][$right$]=0。对第 $i$ 行进行水平翻转之后，A[$i$][$left$]=0,A[$i$][$right$]=1。进行反转之后，A[$i$][$left$]=1,A[$i$][$right$]=0。

情况一和情况二 元素被反转

情况三和情况四 元素值发生了两次改变，恢复原状

遍历矩阵的每一行。对于矩阵的第 $i$ 行，初始化 $left=0$ 和 $right=n−1$，进行如下操作：

  • 当$left<right$,判断A[$i$][$left$]和A[$i$][$right$]是否相等，如果相等则对A[$i$][$left$]和A[$i$][$right$]的值进行反转，如果不相等则不进行任何操作

  • 将 $left$ 的值加1，将 $right$ 的值减1，重复上述操作，直到 $left \ge right$

  • 如果 $n$ 是奇数，则上述操作结束时，$left$ 和 $right$ 的值相等，都指向第 $i$ 行的中间元素，此时需要对中间元素的值进行反转。

拓展

  1. $n$为偶数时，n^=1 n=n+1 例：n=0 n^=1 -> n=1
    $n$为奇数时，n^=1 n=n-1 例：n=1 n^=1 -> n=0

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) {
        int n = A.size();
        for (int i = 0; i < n; i++) {
            int left = 0, right = n - 1;
            while (left < right) {
                if (A[i][left] == A[i][right]) {
                    A[i][left] ^= 1;
                    A[i][right] ^= 1;
                }
                left++;
                right--;
            }
            if (left == right) {
                A[i][left] ^= 1;
            }
        }
        return A;
    }
};