当前位置：首页 > article >正文

Leetcode—1094.拼车【中等】

article 2025/2/24 3:42:58

2023每日刷题（四十七）

Leetcode—1094.拼车

在这里插入图片描述

模拟实现代码

bool carPooling(int** trips, int tripsSize, int* tripsColSize, int capacity) {
    int arr[1003] = {0};
    int numPassenger = 0, fromidx = 0, toidx = 0;
    for(int i = 0; i < tripsSize; i++) {
        numPassenger = trips[i][0];
        fromidx = trips[i][1];
        toidx = trips[i][2];
        for(int j = fromidx; j < toidx; j++) {
            arr[j] += numPassenger;
            if(arr[j] > capacity) {
                return false;
            }
        }
    }
    return true;
}

运行结果

在这里插入图片描述

差分数组算法思想

参考自灵茶山艾府
在这里插入图片描述

差分数组实现代码

bool carPooling(int** trips, int tripsSize, int* tripsColSize, int capacity) {
    int d[1003] = {0};
    int idxmax = 0;
    int numPassenger = 0, fromidx = 0, toidx = 0;
    for(int i = 0; i < tripsSize; i++) {
        numPassenger = trips[i][0];
        fromidx = trips[i][1];
        toidx = trips[i][2];
        d[fromidx] += numPassenger;
        d[toidx] -= numPassenger;
        idxmax = idxmax > toidx ? idxmax: toidx;
    }
    int s = 0;
    for(int i = 0; i <= idxmax; i++) {
        s += d[i];
        if(s > capacity) {
            return false;
        }
    }
    return true;
}