12.3做题

一.车队问题

1.思路:

先把所在位置进行排序,升序排序,

计算出每辆车在不受其余车的影响时，行驶到终点需要的时间

从后往前看

对于相邻的两辆车 S 和 F，F 的起始位置大于 S，如果 S 行驶到终点需要的时间小于等于 F，那么 S 一定会在终点前追上 F 并形成车队。这是因为在追上 F 之前，S 的行驶速度并不会减小，而 F 却有可能因为追上前面的车辆而速度减小，因此 S 总能在终点前追上 F。

如果相邻的两辆车,在不受其余车的影响时，前者比后者行驶到终点需要的时间短，那么后者永远追不上前者，即从后者开始的若干辆车辆会组成一个新的车队；如果前者不比后者行驶到终点需要的时间短，那么后者可以在终点前追上前者，并和前者形成车队。此时我们将后者到达终点的时间置为前者到达终点的时间。

先建立车的类

里面存放到达终点的时间和初始位置

然后建立一个车的数组

按照距离升序排列

从后往前看,

前面的车比后面的车到达终点的时间长,后面的车就一定能追上 就把前面的时间置为后面的车时间 相当于一个车队

但是不能++.因为还没统计完

如果前面的车比后面的车到达终点的时间短,因为我们的车从后往前看.相同的都置为一个车队了.就不存在有前面车影响导致速度下降,所以是永远追不上的,所以就让车队数++.继续往前统计

统计到最后,因为第一辆车没办法再循环里,所以一定是所有车队+1

方法1:类

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int N=position.length;
        Car[] car=new Car[N];//定义一个车队数组
        for(int i=0;i//初始化数组,把值放在数组里
            car[i]=new Car(position[i],(double)(target-position[i])/speed[i]);//根据构造方法初始化
        }
        //升序排序
        Arrays.sort(car,new Comparator(){
            public int compare(Car a,Car b){
                return a.position-b.position;
            }
        });//这里涉及自定义比较,需要实现接口
        //从后往前遍历 
        int ans=0;
        int i=N;
        while(--i>0){
            if(car[i-1].time>car[i].time){
                ans++;
            }else{
                car[i-1].time=car[i].time;
            }
        }
        return ans+1;
    }
}

这里有很多问题

我们需要复习一下自定义类的比较

一个就是就是建立一个内部类

根据数组的方法

就实现一个比较

要求升序,就是前面的减去后面的

还有就是在定义的时候就实现好.

或者实现一个Comparable接口,并重写comparTo方法,但是数组的话只能调用sort方法然后实现比较内部类

还有一种方法就是写一个比较器类并重写comparer方法 但是还是不行

注意事项:实现的时候记得要引入相应的包

方法2 二维数组

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        int N = position.length;
        if (N <= 1) {
            return N;//只有一种的情况
        }
        double[][] cars = new double[N][2];
        for (int i = 0; i < N; i++) {
            cars[i][0] = position[i];
            cars[i][1] = (double) (target - position[i]) / speed[i];
        }//初始化
        Arrays.sort(cars, Comparator.comparingDouble(a -> a[0])); // 以初始位置排序，离出发点近的在前
        int ans = 0;
        for (int i = N - 1; i >= 1; i--) { // 从最靠近终点的车往出发点看（从终点往后看）
            if (cars[i][1] < cars[i - 1][1]) {
                ans++; // 如果比后一辆车到达终点的耗时短，那么后车一定追不上，所以当前车独立为一个车队
            } else {
                cars[i - 1] = cars[i]; // 如果比后一辆车慢或同时到达终点，那么将后车到达终点的时间置为本车到达终点的时间。（被当前车阻碍）
            }
        }
        return ans + 1; // 最后一个车队
    }
}