day006

Nim游戏

292. Nim 游戏

你和你的朋友，两个人一起玩 Nim 游戏：

• 桌子上有一堆石头。
• 你们轮流进行自己的回合， 你作为先手 。
• 每一回合，轮到的人拿掉 1 - 3 块石头。
• 拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

class Solution {
    public boolean canWinNim(int n) {//博弈论，找规律
        return n%4!=0;
    }
}

 

文物朝代判断

class Solution {
    public boolean checkDynasty(int[] places) {
       int unkown=0;
       Arrays.sort(places);
       for(int i=0;i<4;i++){
           if(places[i]==0)
                unkown++;
            else if(places[i]==places[i+1])
                    return false;
       }
       return places[4]-places[unkown] <5;//精髓
    }
}

最大三角形面积

812. 最大三角形面积

给你一个由 X-Y 平面上的点组成的数组 points ，其中 points[i] = [xi, yi] 。从其中取任意三个不同的点组成三角形，返回能组成的最大三角形的面积。与真实值误差在 10-5 内的答案将会视为正确答案。

class Solution {
    public double getLength(int[] a, int[] b) {
        return Math.sqrt(Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2));
    }
 
    public double get_area(int[] point1, int[] point2, int[] point3) {
        double a = getLength(point1, point2);
        double b = getLength(point1, point3);
        double c = getLength(point2, point3);
        double p = (a + b + c) / 2;
        return Math.sqrt(p * (p - a) * (p - b) * (p - c));
    }
 
    public double largestTriangleArea(int[][] points) {
        //无脑海伦公式，直接秒解问题
        double max = 0;
 
        for (int i = 0; i < points.length; i++) {
            for (int j = 0; j < points.length; j++) {
                for (int k = 0; k < points.length; k++) {
                    if (i == j || i == k || j == k) continue;
                    double p = get_area(points[i], points[j], points[k]);
                    if (p > max)
                        max = p;
                }
            }
        }
 
        return max;
    }
}