FlippingAnImage [source code]

public class FlippingAnImage {
static
/****************************************************************************/
class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        int R = A.length;
        if (R == 0)
            return A;
        int C = A[0].length;
        if (C == 0)
            return A;
        for (int[] row : A) {
            int lo = 0, hi = C - 1;
            while (lo < hi) {
                int tmp = row[hi];
                row[hi] = 1 - row[lo];
                row[lo] = 1 - tmp;
                lo++;
                hi--;
            }
            if (lo == hi)
                row[lo] = 1 - row[lo];
        }
        return A;
    }
}
/****************************************************************************/

    public static void main(String[] args) {
        FlippingAnImage.Solution tester = new FlippingAnImage.Solution();
    }
}

好像有什么简单的规律在里面, 不过不浪费时间了, 先写;

比较简单的题目, 没有太多好说的;

UNFINISHED

editorial

Approach #1: Direct [Accepted]

Intuition and Algorithm

We can do this in place. In each row, the ith value from the left is equal to the inverse of the ith value from the right.

We use (C+1) / 2 (with floor division) to iterate over all indexes i in the first half of the row, including the center.

awice比较让人烦的就是类似这样的, 讲算法的时候自己直接自顾自的就开讲了, 根本不管实际上大部分人读到这里的时候都还没有看他的代码;

In Python, the shortcut row[~i] = row[-i-1] = row[len(row) - 1 - i] helps us find the ith value of the row, counting from the right.

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;  
    }  
}

其实跟我的做法是差不多的; 不过两个区别:

• 我的做法是用lo和hi的2pointer来完成一个iterate; 他直接用一个只走一半的方法; 这个(C + 1) / 2的写法是可以注意一下的; 如果是8, 那么得到的就是4, 如果是9, 得到的就是5 (注意, 这里这个值是一个length(1-based), 因为是放在<的后面的); 所以这个其实就是一个不包含中点的一半的算法;
• 另外一个不同的地方就是他的invert的写法; 我的做法是用1-, 他这里用xor1, 其实也是差不多的; 位运算嘛, 逼格高一点;

其他地方基本是类似的思路, 为了效率的一个关键技巧就是直接在swap操作当中同时进行一个invert操作; 这个当时也是自己想到了;

uwi: 3min

class Solution {  
    public int[][] flipAndInvertImage(int[][] a) {  
        int n = a.length;  
        int[][] ret = new int[n][];  
        for(int i = 0;i < n;i++){  
            int[] b = rev(a[i]);  
            for(int j = 0;j < b.length;j++){  
                b[j] ^= 1;  
            }  
            ret[i] = b;  
        }  
        return ret;  
    }  

    public int[] rev(int[] a)  
    {  
        int[] b = new int[a.length];  
        for(int i = 0;i < a.length;i++)b[a.length-1-i] = a[i];  
        return b;  
    }  
}

Problem Description

Given a binary matrix A, we want to flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed. For example, flipping [1, 1, 0] horizontally results in [0, 1, 1].

To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [0, 1, 1] results in [1, 0, 0].

Example 1:

Input: [[1,1,0],[1,0,1],[0,0,0]]  
Output: [[1,0,0],[0,1,0],[1,1,1]]  
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].  
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Example 2:

Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]  
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]  
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].  
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Notes:

• 1 <= A.length = A[0].length <= 20
• 0 <= A[i][j] <= 1

Difficulty:Easy
Total Accepted:1.6K
Total Submissions:1.9K
Contributor:awice

Companies
google
Related Topics
array