算法学习：数组 - 双指针法

832. 翻转图像

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

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

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

背景：二维数组

目的：数组反转；替换数据

方法：双指针来使数组反转；位运算来替换1和0

解题思路

双指针是最好的方法来解决反转数组问题；1替换成0，0替换成1，最适合用位运算来解决。

一个简单的方案如下：以矩阵每一行为单位进行处理，处理数组反转和位运算。

直接附上正确的代码：

class Solution {
public:
    vector<vector<int>> flipAndInvertImage(vector<vector<int>> &image)
    {
        for (int i = 0; i < image.size(); i++)
        {
            flipImage(image[i]);
            invertImage(image[i]);
        }
        return image;
    }

private:
    void flipImage(vector<int> &image)
    {
        int head = 0;
        int tail = image.size() - 1;
        while (head <= tail)
        {
            std::swap(image[head++], image[tail--]);
        }
    }
    void invertImage(vector<int> &image)
    {
        for (int i = 0; i < image.size(); i++)
        {
            image[i] = image[i] ^ 1;
        }
    }
};

我在解题的过程中犯了一个错误：

for(auto i : image)
{
	flipImage(i);
    invertImage(i);
}

这里的auto仅仅获得了image当中的拷贝，对i进行修改并不会影响到image内部，正确的做法应该获得image元素的引用：

for(auto& i : image)
{
	flipImage(i);
    invertImage(i);
}

不过这并不是最合适的解法，在水平翻转的过程中就可以完成图像反转。

Tips ：C++中数组的反转可以用标准库来完成

#include <algorithm>
std::reverse(image.begin(),image.end());