一起学算法-832. 翻转图像

一、题目

LeetCode-832. 翻转图像
链接：https://leetcode-cn.com/problems/flipping-an-image/

难度：简单
给定一个二进制矩阵 A，我们想先水平翻转图像，然后反转图像并返回结果。

水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。

反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。例如，反转 [0, 1, 1] 的结果是 [1, 0, 0]。

示例 1：
输入：[[1,1,0],[1,0,1],[0,0,0]]
输出：[[1,0,0],[0,1,0],[1,1,1]]
解释：首先翻转每一行: [[0,1,1],[1,0,1],[0,0,0]]；然后反转图片: [[1,0,0],[0,1,0],[1,1,1]]

示例 2：
输入：[[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
输出：[[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
解释：首先翻转每一行: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]]；然后反转图片: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

提示：
1 <= A.length = A[0].length <= 20
0 <= A[i][j] <= 1

二、解题思路

按照题目思路进行操作。首先，进行水平翻转，我们对每一行通过双指针进行交换。然后反转图片，对每一位与1进行异或运算。

    for(int i = 0;i < image.size(); i++){
        int l = 0,r = image[i].size() - 1;
        while(l < r){
            int temp = image[i][l];
            image[i][l] = image[i][r];
            image[i][r] = temp;
            l++;
            r--;
        }
        for(int j = 0;j < image[i].size();j++){
            image[i][j] ^= 1; 
        }
    }
    return image;

三、实现过程

代码优化，先把第二次for循环与while合并一下，再处理一下左右指针相等时的情况即可。

c++

class Solution {
public:
    vector<vector<int>> flipAndInvertImage(vector<vector<int>>& image) {
    for(int i = 0;i < image.size(); i++){
        int l = 0,r = image[i].size() - 1;
        while(l < r){
            int temp = image[i][l] ^ 1;
            image[i][l] = image[i][r] ^ 1;
            image[i][r] = temp;
            l++;
            r--;
        }
        if(l == r){
            image[i][l] ^= 1; 
        }
    }
    return image;
    }
};

PHP

class Solution {

    /**
     * @param Integer[][] $image
     * @return Integer[][]
     */
    function flipAndInvertImage($image) {
    $len1 = count($image);
    for($i = 0;$i < $len1; $i++){
        $l = 0;
        $r = $len1 - 1;
        while($l < $r){
            $temp = $image[$i][$l] ^ 1;
            $image[$i][$l] = $image[$i][$r] ^ 1;
            $image[$i][$r] = $temp;
            $l++;
            $r--;
        }
        if($l == $r){
            $image[$i][$l] ^= 1; 
        }
    }
    return $image;
    }
}

JavaScript

/**
 * @param {number[][]} image
 * @return {number[][]}
 */
var flipAndInvertImage = function(image) {
    // for(let i = 0;i < image.length; i++){
    //     let l = 0,r = image[i].length - 1;
    //     while(l < r){
    //         let temp = image[i][l];
    //         image[i][l] = image[i][r];
    //         image[i][r] = temp;
    //         l++;
    //         r--;
    //     }
    //     for(let j = 0;j < image[i].length;j++){
    //         image[i][j] ^= 1; 
    //     }
    // }
    // return image;
    for(let i = 0;i < image.length; i++){
        let l = 0,r = image[i].length - 1;
        while(l < r){
            let temp = image[i][l] ^ 1;
            image[i][l] = image[i][r] ^ 1;
            image[i][r] = temp;
            l++;
            r--;
        }
        if(l == r){
             image[i][l] ^= 1;
        }
    }
    return image;
};

四、小结

1. 时间复杂度：O(N^2 )，其中N^2是矩阵行列数之积。
2. 空间复杂度：O(1)