蔚来汽车（7.3）

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);
        }
    }
}