Algorithm

832. 翻转图像

题目

给定一个二进制矩阵 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]]

解法

func flipAndInvertImage(A [][]int) [][]int {
    if A == nil || len(A) == 0 {
        return nil
    }

    for i := 0; i < len(A); i++ {
        for j := 0; j < int(math.Ceil(float64(len(A[i]))/2)); j++ {
            tmp := A[i][j]
            A[i][j] = 1 ^ A[i][len(A[i])-j-1]
            A[i][len(A[i])-j-1] = 1 ^ tmp
        }
    }

    return A
}

Review

What Is Readable Code?
文章直接了当的指出了代码可读性的终极目标，就是为了能够安全并且容易的进行修改，增加新特性、修复bug等等，所以首先要保证代码易于安全的修改，在保证了这各之后，代码的可读性往往也就随之而提升了。
作者的观点十分犀利，不过确实是这么一回事。所谓要保证代码的可读性，其实就是保证代码的可维护性，在写代码的时候往往舍本求末，为了使用所谓的技巧而使用，没有深入思考是否真的值得使用。这样的后果往往导致代码最后一团糟，修改成本极大。所以以后在写代码的时候一定要保证代码的可修改性，这样才能让代码可读性提升。

Tip

这周一个面试中，被问到快速排序，只记得个大概，现场没有写出来，所以后面回来之后就温习了一下，发现了两种不同的写法，效率差的还是有点多的。
快排的原理主要是设置一个主元，然后把所有比主元小的都放到主元前面，比主元大的都放到主元后面，然后把主元之前和之后的分别递归，继续这个流程。
假设现在要排序的数组为：[3,2,5,1,4]
方式1流程如下：

image.png

方式2流程如下：

image.png
这两种方式的主要区别在于方式1中的i、j移动的方向是相同的，而方式2
中的i、j是相反的，还有就是方式1中主元最终只移动了一次，而方式2中主元不停的在移动。
下面是参考代码：

package algorithms.chapter7;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = generatorArray(10000000);
//      System.out.println(Arrays.toString(arr));

        QuickSort s = new QuickSort();
        long currTime = System.currentTimeMillis();
        s.quickSort(arr);
        long used = System.currentTimeMillis() - currTime;

//      System.out.println(Arrays.toString(arr));
        System.out.println("used: " + used + "ms");
    }

    static int[] generatorArray(int len) {
        Random ran = new Random(System.currentTimeMillis());
        int arr[] = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = ran.nextInt(len * 100);
        }
        return arr;
    }

    public void quickSort(int[] arr) {
        quickSorting(arr, 0, arr.length - 1);
    }

    private void quickSorting(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }

        int p = partion(arr, start, end);
        quickSorting(arr, start, p - 1);
        quickSorting(arr, p + 1, end);
    }

    // 方式2，排序一千万条数据比方式一慢四百多毫秒，应该是不停的在交换主元
    private int partion2(int[] arr, int start, int end) {
        int pivot = arr[start];
        int i = start;
        int j = end;

        while (i < j) {
            while (i < j && pivot <= arr[j]) {
                j--;
            }
            if (i < j) {
                int tmp = arr[j];
                arr[j] = arr[i];
                arr[i] = tmp;
            }
            while (i < j && pivot >= arr[i]) {
                i++;
            }
            if (i < j) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }

        arr[i] = pivot;
        return i;
    }

    // 方式1
    private int partion(int[] arr, int start, int end) {
        int pivot = arr[end];
        int i = start - 1;
        int j = start;

        for (; j < end; j++) {
            if (arr[j] < pivot) {
                i++;
                int tmp = arr[j];
                arr[j] = arr[i];
                arr[i] = tmp;
            }
        }

        arr[end] = arr[i + 1];
        arr[i + 1] = pivot;
        return i + 1;
    }
}

随机生成包含一千万个数据的数组，用这两种方式进行排序，但是结果差了有大概五百毫秒的时间，我觉得主要还是方式2不停的在交换主元，和代码实现的原因。

Share

android消息机制