CTF of Z2BNS
0%

翻转图像

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

题目地址

难度：⭐

题目描述：

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

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

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

示例1：

1
2
3
4
输入: [[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
2
3
4
输入: [[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
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

遍历每一行，然后对每一行中的元素翻转交换元素的值（swap函数），再反转元素的值，注意特殊情况，矩阵行数为奇数时中间元素要特殊处理反转一次。

c++代码：(执行用时4ms，击败97.33%，内存消耗8.7M，击败28.26%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) {
        //遍历矩阵
        int n=A.size();
        for(int i=0;i<n;++i){
            for(int j=0;j<(n+1)/2;++j){
                //翻转，交换两个元素的值
                swap(A[i][j],A[i][n-j-1]);
                //反转，与1异或
                A[i][j]^=1;
                //n是奇数时，中间的元素只能反转一次。
                if(j!=(n-j-1)){
                    A[i][n-j-1]^=1;
                }
            }
        }
        return A;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法一： 模拟

我们可以不使用额外的（非常数）空间来完成翻转和反转操作。对于 A[i][j]​，我们将它和 A[i][c - j - 1]​ 进行交换（即翻转），其中 c 是数组 A 的列数。在交换的同时，我们可以将这两个数进行反转。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        int C = A[0].length;
        for (int[] row: A)
            for (int i = 0; i < (C + 1) / 2; ++i) {
                int tmp = row[i] ^ 1;
                row[i] = row[C - 1 - i] ^ 1;
                row[C - 1 - i] = tmp;
            }
        return A;
    }
}

复杂度分析

  • 时间复杂度：$O(M*N)$，其中 $M$ 和 $N$ 分别为数组 A 的行数和列数。
  • 空间复杂度：$O(1)$。
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

官方题解和我的思路一样，不过对于特殊情况比我处理的好，也不算特殊情况吧，只是我自己把它当作特殊情况处理了，主要在于我使用了vector容器中的swap成员函数来交换两个元素，这样必须反转后覆盖原值，对于奇数行数矩阵的每行中间元素反转了两次，而采用tmp辅助变量来进行交换两个元素值不涉及到覆盖问题。其实就是太执着于STL模板库中的成员函数了，自己实现交换元素的功能也挺好，相当于对源码根据实际情况进行了改进，这样才能更灵活地处理问题。

------------- THE END! THANKS! -------------