9.20 美的笔试

题1 求同在一条直线上的最大点数

对于给定的n个位于同一二维平面上的点，求最多能有多少个点位于同一条直线上

思路：同一个点视为同一条直线上，斜率相同视为同一条直线。

  public class Solution1 {
      class Point {
          int x;
          int y;

          public Point(int x, int y) {
              this.x = x;
              this.y = y;
          }
      }

      public int maxPointsNum(Point[] points) {
          // write code here
          if (points.length == 0) {
              return 0;
          }
          if (points.length < 3) {
              return points.length;
          }
          int pointAtSame = 0;
          int maxPoints = 2;
          int pointAtK = 0;
          for (int i = 0; i < points.length; i++) {
              pointAtSame = 0;
              for (int j = i + 1; j < points.length; j++) {
  //                找相同点
                  pointAtK = 1;
                  int xDistance = points[i].x - points[j].x;
                  int yDistance = points[i].y - points[j].y;
                  if (xDistance == 0 && yDistance == 0) {
                      pointAtSame++;
                  }else{
  //                    找斜率相同
                      pointAtK = 2;
                      for (int k = j+1; k < points.length; k++) {
                        int xDistance1 = points[i].x - points[k].x;
                        int yDistance1 = points[i].y - points[k].y;
                        if(xDistance * yDistance1 == yDistance * xDistance1){
                            pointAtK++;
                        }
                      }
                  }
                  if(maxPoints < (pointAtK + pointAtSame)){
                      maxPoints = (pointAtK + pointAtSame);
                  }
              }
          }
          return maxPoints;
      }

股票买卖的最佳时机（LeetCode 121）
假设你有一个数组，其中第i个元素是股票在第i天的价格
你有一次买入和卖出的机会（只有买入了股票才能卖出），请你设计一个算法求得最大收益

思路：贪心，记录最低的价格，如果有更低的价格，就更新，当大于最低价格，就记录差价，只记录最大差价。

  public class Solution{
      public double maxProfit(double[] prices){
          double max = Integer.MIN_VALUE;
          double minPrice = prices[0];
          for(double price : prices){
              if(price < minPrice){
                  minPrice = price;
              }else if((price - minPrice) > max){
                  max = (price - minPrice);
              }
          }
          return max;
      }
  }