Leetcode算法题1001-1100

1001-1010¶

1011-1020¶

1021-1030¶

1031-1040¶

1041-1050¶

1051-1060¶

1061-1070¶

1071-1080¶

1081-1090¶

1091-1100¶

1094. 拼车¶

本题可以抽象为在数组中指定位置增加或减少，即转化为差分问题。

class Solution {
public:
    bool carPooling(vector <vector<int>> &trips, int capacity) {
        vector<int> people(1001);
        for (auto &item: trips) {
            people[item[1]] += item[0];
            people[item[2]] -= item[0];
        }
        // 注意这里直接算前缀和会漏掉第0位元素，需要进行特判。或者这里用sum来计算累加和直接比较
//        if (people[0] > capacity) return false;
//        for (int i = 1; i <= 1000; i++) {
//            people[i] += people[i - 1];
//            if (people[i] > capacity) return false;
//        }
        for (int i = 0, sum = 0; i <= 1000; i++) {
            sum += people[i];
            if (sum > capacity) return false;
        }
        return true;
    }
};