832. 翻转图像

[xiwenAndlejian]

832. 翻转图像

思路

由题干可得条件：

1. 矩阵的行、列数相等：A.length = A[0].length
2. 矩阵的元素值一定是0或1：二进制矩阵，且0 <= A[i][j] <= 1

题目要求我们给出的输出需要满足：水平翻转且将元素值反转(0 <=> 1)。

解题

方法一

class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        for (int i = 0; i < A.length; i++) {
            horizontalFlip(A[i]);// 水平翻转
            reverse(A[i]);           // 反转
        }
        return A;
    }
    // 水平翻转    
    public void horizontalFlip(int[] A) {
        for (int i = 0; i < A.length / 2; i ++) {
            swap(A, i, A.length - 1 - i); 
        }
    }
    // 位运算交换法
    // a ^ a = 0
    // a ^ a ^ b = b
    public void swap(int[] A, int a, int b) {
        A[a] ^= A[b];
        A[b] ^= A[a];
        A[a] ^= A[b];
    }
    // 位运算：0^1 = 1, 1^1 = 0
    public void reverse(int[] A) {
        for (int i = 0; i < A.length; i++) {
            A[i] ^= 1;
        }
    }
}

解题思路

1. 迭代二维数组，每次处理一行
2. 将每行的元素先进行翻转，再进行反转

方法二：进一步优化

class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        for (int i = 0; i < A.length; i++) {
            horizontalFlip(A[i]);
        }
        return A;
    }
    // 水平翻转 & 反转    
    public void horizontalFlip(int[] A) {
        for (int i = 0; i < A.length / 2; i ++) {
            swapAndReverse(A, i, A.length - 1 - i); 
        }
        // 由于for循环无法处理数组长度是奇数时中间的那个元素，所以需要额外处理
        if ((A.length & 1) == 1) {
            A[A.length / 2] ^= 1;
        }
    }

    public void swapAndReverse(int[] A, int a, int b) {
        A[a] ^= A[b];       // a' = a ^ b
        A[b] ^= A[a] ^ 1; // b' = a' ^ b ^ 1 = a ^ b ^ b ^ 1 = a ^ 1
        A[a] ^= A[b];     // a'' = a' ^ b' = a ^ b ^ a ^ 1 = b ^ 1
    }
}