LeetCode刷题：航班预订统计

前言

前几天，有一哥们发我一个LeetCode题目链接，紧跟着附上了自己的提交记录，一个2ms，另一个1451ms...

我一看，这题有点意思啊，不同的思路竟然时间差这么多。搞它。

题目描述

这里有n个航班，它们分别从1到n进行编号。

我们这儿有一份航班预订表，表中第i条预订记录bookings[i] = [i, j, k]意味着我们在从i到j的每个航班上预订了k个座位。

请你返回一个长度为n的数组answer，按航班编号顺序返回每个航班上预订的座位数。

示例：

❝输入：bookings = [ [1,2,10], [2,3,20], [2,5,25] ], n = 5 输出：[10,55,45,25,25] ❞

O(m*n)解法

根据题意初始化长度为n的answer数组，代表1到n号航班预订的座位数量，外层遍历 bookings，内层遍历bookings[i] = [i, j, k]，计算航班号i到j的座位数量，即当前座位数量加k。

public int[] corpFlightBookings(
        int[][] bookings, int n) {

    int[] answer = new int[n];

    // 遍历整个bookings数组
    for (int[] b : bookings) {
        // 内层循环把每个航班预订数加上
        for (int i = b[0] - 1;
             i <= b[1] - 1; i++) {
            answer[i] += b[2];
        }
    }
    return answer;
}

O(n)解法

思考

O(m*n)解法中关键一点，内层循环我们一直重复的在[i, j]之间加上k，怎么将这循环变成O(1)，成为问题的关键！

[i, j]之间加上k，这让我想到了等差数列，这不就是公差为k的等差数列吗？然后呢？

分析

设answer[i]表示第i个航班预订的座位数。定义一个差分数组d[]，d[i]表示第i个航班与第i-1个航班预订座位的差值，即d[i] = answer[i] - answer[i - 1]。

这样，我们每次遍历到bookings[i] = [i, j, k]，就只需要将d[i]增加k，d[j + 1]减少k即可，因为i到j之间，航班预订数量是没有变化的。

最后，计算answer[i] = answer[i - 1] + d[i]，返回answer即可。

推演

好吧，这样说可能有人没懂，我们按照题目的例子推演一次：

• 初始航班预订数量数组 answer = [0,0,0,0,0]，差分数组d = [0,0,0,0,0]
• 当遍历到bookings[0] = [1,2,10]的时候，差分数组第1位加10，第3位减10，变成d = [10,0,-10,0,0]
• 同理，当遍历到bookings[1] = [2,3,20]的时候，差分数组变成d = [10,20,-10,-20,0]
• 当遍历到bookings[2] = [2,5,25]的时候，差分数组变成d = [10,45,-10,-20,0]，第6位要减25，我们也不需要了
• 最后计算answer数组的值，answer[0] = d[0] = 10，answer[1] = d[1] + answer[0] = 45 + 10 = 55，answer[2] = d[2] + answer[1] = -10 + 55 = 45...
• 最最后发现，只申请一个数组表示d[]和answer[]就可以了，over！

代码

public int[] corpFlightBookings(
        int[][] bookings, int n) {

    int[] answer = new int[n];

    // 遍历bookings 计算航班i+1 对航班i 变化的预订数
    for (int[] b : bookings) {
        // 增加的预订数
        answer[b[0] - 1] += b[2];
        // 防止数组越界
        if (b[1] < n) {
            // 减少的预订数量
            answer[b[1]] -= b[2];
        }
    }

    // 航班i的预订数等于,i-1的预订数，加i时刻变化的预定数
    for (int i = 1; i < n; i++) {
        answer[i] += answer[i - 1];
    }
    return answer;
}

拼车

❝你以为这就完了吗？不要太天真。再来看一下这个题，或许会给你带来新思路。 ❞

题目描述

假设你是一位顺风车司机，车上最初有 capacity 个空座位可以用来载客。由于道路的限制，车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向，你可以将其想象为一个向量）。

这儿有一份行程计划表 trips[][]，其中 trips[i] = [num_passengers, start_location, end_location] 包含了你的第 i 次行程信息：

必须接送的乘客数量；乘客的上车地点；以及乘客的下车地点。这些给出的地点位置是从你的 初始 出发位置向前行驶到这些地点所需的距离（它们一定在你的行驶方向上）。

请你根据给出的行程计划表和车子的座位数，来判断你的车是否可以顺利完成接送所用乘客的任务（当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false）。

示例 1：

❝输入：trips = [[2,1,5],[3,3,7]], capacity = 4 输出：false ❞

示例 2：

❝输入：trips = [[2,1,5],[3,3,7]], capacity = 5 输出：true ❞

提示：

• 你可以假设乘客会自觉遵守 “先下后上” 的良好素质
• trips.length <= 1000
• 1 <= trips[i][0] <= 100

题目分析

这道题实际上就是问，车的座位数量是否能满足每个行程i的乘客，即每个乘客都坐上座位，能则返回true，否则返回false。

如果我们能计算出，行程i，要乘车的乘客的数量，然后跟capacity对比一下，就能得到答案了。

很显然，「要乘车的乘客的数量 = 车上原来乘客的数量 - 下车乘客数量 + 上车乘客数量」。

思路

我们可以用数组或者Map记录，行程i，下车乘客的数量和上车乘客的数量，然后行程开始到结束，计算要乘车的乘客数量，并与capacity比较。

代码实现Map版

public boolean carPooling(
        int[][] trips, int capacity) {
    // 使用TreeMap 是为了让元素根据key排序
    TreeMap<Integer, Integer> map =
            new TreeMap<>();
    for (int[] t : trips) {
        int v = map.getOrDefault(t[1], 0) + t[0];
        // 上车乘客数量
        map.put(t[1], v);
        v = map.getOrDefault(t[2], 0) - t[0];
        // 下车乘客数量
        map.put(t[2], v);
    }

    int cur = 0;

    for (Map.Entry<Integer, Integer> entry
            : map.entrySet()) {
        Integer value = entry.getValue();
        // 当前数量=之前数量+变化的数量
        cur += value;

        if (cur > capacity) {
            return false;
        }
    }
    return true;
}

代码实现数组版

public boolean carPooling(
        int[][] trips, int capacity) {

    // 最远行程 数组长度
    int max = 0;
    for (int[] t : trips) {
        max = Math.max(max, t[2]);
    }

    // 所有要乘车的乘客数量
    int[] passengers = new int[max + 1];
    for (int[] t : trips) {
        passengers[t[1]] += t[0];
        passengers[t[2]] -= t[0];
    }

    int cur = 0;
    for (int passenger : passengers) {
        // 当前数量 = 之前数量 + 变化的数量
        cur += passenger;
        if (cur > capacity) {
            return false;
        }
    }

    return true;
}

回头

「拼车」的代码与场景感觉好理解一些，因为生活中我们就是这样，先下后上，能不能坐上座，就看车上原来有多少人，还有下车多少人。

我们再回来来看「航班预订统计」这题，实际上跟「拼车」是完全一样的题目。

我看到有人问，计算bookings[i] = [i, j, k]预订变化数量的时候，为啥是第j + 1的位置要减k，而不是j的位置呢？因为，j - 1的位置，航班预订座位数量应该加k，而j的位置，航班预订座位数量也加k，所以j和j - 1之间数量是没有变化的。但是，j + 1的位置航班数量不再加k了，所以j + 1相对于j位置航班预订数量是减少k的。

而「拼车」这道题，trips[i][j]，在j位置，车到站了，乘客就下车了，再坐一站就过站了...

总之，两道题本质是完全一样的，只不过略微有些细节不同。

END