1. 第一题给出一个点坐标和三角形的三个顶点坐标，求点到三角形的最短距离，若点在三角形内则返回0，在三角形外则输出最短距离。

    public static float cacluate(float[] point,float[][] triangle){
    float distances = 0;
    float area = triAngleAreas(triangle[0],triangle[1],triangle[2]);
    float a = triAngleAreas(triangle[0],triangle[1],point);
    float b = triAngleAreas(triangle[0],triangle[2],point);
    float c = triAngleAreas(triangle[1],triangle[2],point);
    if(area == a+b+c){
        return 0.0f;
    }else{
        float distances1 = triAngleDistances(triangle[0], triangle[1], point);
        float distances2 = triAngleDistances(triangle[0], triangle[2], point);
        float distances3 = triAngleDistances(triangle[1], triangle[2], point);
        distances = Math.min(distances1, Math.min(distances2, distances3));
    }
    return distances;

}

private static float triAngleDistances(float[] a, float[] b, float[] point) {
    float x1 = a[0];
    float y1 = a[1];
    float x2 = b[0];
    float y2 = b[1];
    float k = (y2-y1)/(x2-x1);
    float bb = y1-k*x1;
    float x0 = point[0];
    float y0 = point[1];
    return (float) ((k*x0 - y0 +bb)/(Math.sqrt(k*k + 1)));

}
private static float triAngleAreas(float[] a, float[] b, float[] c) {
    float x1 = a[0];
    float y1 = a[1];
    float x2 = b[0];
    float y2 = b[1];
    float x3 = c[0];
    float y3 = c[1];
    return Math.abs(x1*y2-x1*y3+x2*y3-x2*y1+x3*y1-x2*y2);
}

  2. 比较版本号

    public int compareVersion(String version1, String version2) {
     String[] nums1 = version1.split("\\.");
     String[] nums2 = version2.split("\\.");

     int m = nums1.length;
     int n = nums2.length;
     for(int i = 0;i<Math.max(m,n);i++){
         int a = i<m ? Integer.valueOf(nums1[i]):0;
         int b = i<n ? Integer.valueOf(nums2[i]):0;
         if(a<b){
             return -1;
         }else if(a>b){
             return 1;
         }
     }
     return 0;
}

  3. 搜索二维矩阵
    1.第一次二分：从第 0 列中的「所有行」开始找，找到合适的行 row
    2.第二次二分：从 row 中「所有列」开始找，找到合适的列 col

    public boolean Find(int target, int [][] array) {
   int[] row_num = new int[array.length];
   for(int i = 0;i<array.length;i++){
       row_num[i] = array[i][0];
   }
   int row = left_bound(row_num, target);
   if(row <0){
        return false;
    }
   int[] col_num = array[row];
   return bound(col_num,target);
}
public int left_bound(int[] nums,int target){
    int left = 0;
    int right = nums.length-1;
    while(left <= right){
        int mid = (left + right)/2;
        if(nums[mid] <= target){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }

    return left - 1;
}
public boolean bound(int[] nums,int target){
    int left = 0;
    int right = nums.length-1;
    while(left <= right){
        int mid = (left+right)/2;
        if(nums[mid] < target){
            left = mid +1;
        }else if(nums[mid] >target){
            right = mid - 1;
        }else if(nums[mid] == target){
            return true;
        }
    }
    return false;
}

4.接雨水

 public static long maxWater (int[] arr) {
        // write code here
        if(arr.length == 0){
            return 0;
        }
        int n = arr.length;
        long result = 0;
        long[] left_maxs = new long[n];
        left_maxs[0] = arr[0];
        long[] right_maxs = new long[n];
        for(int i = 1;i<n;i++){
            left_maxs[i] = Math.max(left_maxs[i-1],arr[i]);
        }
        right_maxs[n-1] = arr[n-1];
        for(int j = n-2;j>=0;j--){
            right_maxs[j] = Math.max(arr[j],right_maxs[j+1]);
        }
        for(int i = 1;i<n;i++){
            result += Math.min(right_maxs[i],left_maxs[i]) - arr[i];
        }
        return result;
    }

5.复原 IP 地址

class Solution {
    List<String> res;
    public List<String> restoreIpAddresses(String s) {
        res = new ArrayList<>();
        List<String> temp = new ArrayList<>();
        dfs(s,temp,0);
        return res;
    }

    public void dfs(String s,List<String> temp,int index){
        if(temp.size() >4){
            return;
        }
        if(temp.size() >= 4 && index != s.length()){
            return;
        }
        if(temp.size() == 4){
            String temps = new String(temp.get(0) + "." + temp.get(1) + "." + temp.get(2) + "." + temp.get(3));
            res.add(temps);
            return;
        }
        for(int i = index;i<s.length();i++){
            String sub = s.substring(index,i+1);
            //防止01 
            if((sub.length() >= 2 && sub.startsWith("0")) || sub.length() >3){
                continue;
            }
            int te = Integer.parseInt(sub);
            if(te <0 || te >=256){
                continue;
            }
            temp.add(sub);
            dfs(s,temp,i+1);
            temp.remove(temp.size()-1);
        }
    }
}