ARTS第四周

Algorithm

题一：leetCode 812 Largest Triangle Area
You have a list of points in the plane. Return the area of the largest triangle that can be formed by any 3 of the points.
所有结果中取3点，返回构成三角形最大的面积。结果取6位小数。
思路
排列所有结果计算面积，取最大结果。（演变的出来主要代码就是求三角形面积）

假如、、中最长，面积即为，只需要计算h高度


可以求得

code

public double largestTriangleArea(int[][] points) {
        double max = 0;
        double temp;
        for (int i = 0; i < points.length; i++) {
            for (int j = i + 1; j < points.length; j++) {
                for (int k = j + 1; k < points.length; k++) {
                    temp = calculateArea(points[i], points[j], points[k]);
                    if (temp > max) {
                        max = temp;
                    }
                }
            }
        }
        return new BigDecimal(max).setScale(6, RoundingMode.DOWN).doubleValue();
    }

    private double calculateArea(int[] point1, int[] point2, int[] point3) {
        if (point1[0] == point2[0] && point1[0] == point3[0] || point1[1] == point2[1] && point1[1] == point3[1]) {
            return 0.0D;
        }
        int flag = 1;
        double a = Math.pow(point1[0] - point2[0], 2) + Math.pow(point1[1] - point2[1], 2);
        double b = Math.pow(point1[0] - point3[0], 2) + Math.pow(point1[1] - point3[1], 2);
        double c = Math.pow(point2[0] - point3[0], 2) + Math.pow(point2[1] - point3[1], 2);
        if (b > a) {
            flag = 2;
            if (c > b) {
                flag = 3;
            }
        } else if (c > a) {
            flag = 3;
        }
        if (flag == 1 || flag == 3) {
            // max a || max c
            return Math.sqrt(4 * a * c - Math.pow(a + c - b, 2)) / 4;
        } else {
            // max b
            return Math.sqrt(4 * b * c - Math.pow(b + c - a, 2)) / 4;
        }
    }

其他人的思路
分成3个三角形计算面积，挺好的
链接：https://leetcode.com/problems/largest-triangle-area/discuss/122711/C%2B%2BJavaPython-Solution-with-Explanation-and-Prove

题二：1个细胞的生命周期是 3 小时，1 小时分裂一次。求 n小时后，容器内有多少细胞？请你用已经学过的递归时间复杂度的分析方法，分析一下这个递归问题的时间复杂度。

第0小时遍历个，第1小时需要遍历个，第2小时遍历，第3小时遍历，第n小时遍历，时间复杂度

Review

查询排序面试问题

Tip

Markdown编辑公式 https://en.wikibooks.org/wiki/LaTeX/Mathematics

Share

深度优先搜索学习（一）