第六十四周ARTS总结

Algorithm

• Largest Rectangle in Histogram (opens new window)

811ms | 9.55% Run time
41.4MB | 42.75% Memory

public int largestRectangleArea(int[] heights) {
    // 最大面积
    int maxArea = 0;

    // 最小值
    int minValue;

    for (int i = 0; i < heights.length; i++) {
        minValue = heights[i];

        // [i, j]区间面积最大值
        for (int j = i; j < heights.length; j++) {
            // 重新判断最小值
            if (heights[j] < minValue) {
                minValue = heights[j];
            }

            // [i, j]区间的面积
            int area = minValue * (j - i + 1);
            if (area > maxArea) {
                maxArea = area;
            }
        }
    }

    return maxArea;
}

---

• Maximal Rectangle (opens new window)

13ms | 33.89% Run time
41.6MB | 99.08% Memory

public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0) {
        return 0;
    }

    int maxRect = 0;

    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            int[] coordinate = new int[]{i, j};

            if (isPossible(matrix, coordinate, maxRect)) {
                int rect = findMaxRectangle(matrix, coordinate);

                if (rect > maxRect) {
                    maxRect = rect;
                }
            }
        }
    }

    return maxRect;
}

/**
 * 判断当前坐标可不可能作为顶点
 *
 * @param matrix
 * @param coordinate
 * @param maxRect    目前最大矩形
 * @return
 */
private boolean isPossible(char[][] matrix, int[] coordinate, int maxRect) {
    // 如果是0不可能为顶点
    if (matrix[coordinate[0]][coordinate[1]] == 0) {
        return false;
    }

    // 如果左边的点为1，则该点也不能为顶点
    if (coordinate[1] - 1 >= 0 && matrix[coordinate[0]][coordinate[1] - 1] == 1) {
        return false;
    }

    // 如果剩余部分最大面积比maxRect还小，则不能为顶点
    if ((matrix.length - coordinate[0]) * (matrix[0].length - coordinate[1]) < maxRect) {
        return false;
    }

    return true;
}

/**
 * 以coordinate为左上顶点的最大矩形
 *
 * @param matrix
 * @param coordinate 矩形左上角坐标
 * @return
 */
private int findMaxRectangle(char[][] matrix, int[] coordinate) {
    // 最大矩形
    int maxRect = 0;

    // height行内的最小宽度
    int minWidth = matrix[0].length;

    // 高度
    int height = 1;

    // 以coordinate为顶点，第height列的首个坐标为1的情况下继续
    while (coordinate[0] + height <= matrix.length
            && matrix[coordinate[0] + height - 1][coordinate[1]] == '1') {
        int width = 0;

        for (int i = coordinate[1]; i < matrix[0].length; i++) {
            // 这里多了一个 `width < minWidth` 是为了减少比较
            if (width < minWidth && matrix[coordinate[0] + height - 1][i] == '1') {
                width++;
            } else {
                break;
            }
        }

        // 重置最小宽度
        if (width < minWidth) {
            minWidth = width;
        }

        if (minWidth * height > maxRect) {
            maxRect = minWidth * height;
        }

        height++;
    }

    return maxRect;
}

Review

• A Great Way to do Presenters (opens new window)

Tip

• 合理利用layout_marginStart与layout_goneMarginStart可以较好的处理ConstraintLayout布局中组件隐藏的情况
• String方法trim和strip的区别：
  • trim自Java 1就引入了；stripJava 11才引入
  • trim使用ASCII判断；strip使用Unicode判断
  • trim删除ASCII小于等于U+0020的字符；strip删除所有的空白字符
• APP启动过程：
  1. Launcher被调用点击事件，转到Instrumentation类的startActivity方法
  2. Instrumentation通过跨进程通信告诉AMS要启动应用的需求
  3. AMS反馈Launcher，让Launcher进入Paused状态
  4. Launcher进入Paused状态，AMS转到ZygoteProcess类，并通过socket与Zygote通信，告知Zygote需要新建进程
  5. Zygotefork进程，并调用ActivityThread的main方法，也就是APP的入口
  6. ActivityThread的main方法新建了ActivityThread实例，并新建了Looper实例，开始loop循环
  7. 同时ActivityThread也告知AMS，进程创建完毕，开始创建Application，Provider，并调用Applicaiton的attach，onCreate方法
  8. 最后就是创建上下文，通过类加载器加载Activity，调用Activity的onCreate方法
• kotlin中可以用toInt()方法把Float转为Integer
• BigDecimal比较大小用compareTo而不是equals方法，因为equals方法还会比较精度

Share

暂无内容