說在前面

🎈不知道大家對于算法的學(xué)習(xí)是一個怎樣的心態(tài)呢？為了面試還是因為興趣？不管是出于什么原因，算法學(xué)習(xí)需要持續(xù)保持。

題目描述

車上最初有?capacity?個空座位。車?只能 向一個方向行駛（也就是說，不允許掉頭或改變方向）

給定整數(shù)?capacity?和一個數(shù)組?trips?, ?trip[i] = [numPassengersi, fromi, toi]?表示第?i?次旅行有?numPassengersi?乘客，接他們和放他們的位置分別是?fromi?和?toi?。這些位置是從汽車的初始位置向東的公里數(shù)。

當(dāng)且僅當(dāng)你可以在所有給定的行程中接送所有乘客時，返回?true，否則請返回?false。

示例 1：

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

示例 2：

輸入： trips = [[2,1,5],[3,3,7]], capacity = 5
輸出： true

提示：

• 1 <= trips.length <= 1000
• trips[i].length == 3
• 1 <= numPassengersi?<= 100
• 0 <= fromi?< toi?<= 1000
• 1 <= capacity <= 10^5

解題思路

這是一道比較簡單差分?jǐn)?shù)組的應(yīng)用題：

1. 初始化一個長度為 1005 的數(shù)組 arr，用于存儲每個時間點的乘客數(shù)量。數(shù)組的索引代表時間點，數(shù)組的值代表該時間點的乘客數(shù)量。數(shù)組使用 fill(0) 初始化，意味著所有時間點的初始乘客數(shù)量為 0。

2. 遍歷 trips 數(shù)組中的每個行程 trip。對于每個行程，執(zhí)行以下操作：

   • 在出發(fā)時間 trip[1] 上增加乘客數(shù)量 trip[0]（即上車人數(shù)）。
   • 在到達時間 trip[2] 上減少乘客數(shù)量 trip[0]（即下車人數(shù)）。

3. 遍歷數(shù)組 arr，累加每個時間點的乘客數(shù)量。這樣做的目的是為了計算每個時間點的總乘客數(shù)量，考慮到之前的乘客可能在更早的時間點上車或下車。

4. 在累加過程中，檢查任何時間點的總乘客數(shù)量是否超過了車輛的容量 capacity。如果是，返回 false，表示在某個時間點，車上的乘客數(shù)量超過了車輛的容量。

5. 如果遍歷完整個數(shù)組后沒有發(fā)現(xiàn)超過容量的情況，返回 true，表示車輛可以容納所有行程的乘客。

AC代碼

/*** @param {number[][]} trips* @param {number} capacity* @return {boolean}*/
var carPooling = function (trips, capacity) {const arr = new Array(1005).fill(0);trips.forEach((trip) => {arr[trip[1]] += trip[0];arr[trip[2]] -= trip[0];});for (let i = 0; i < arr.length; i++) {arr[i] += arr[i - 1] || 0;if (arr[i] > capacity) return false;}return true;
};

公眾號

關(guān)注公眾號『前端也能這么有趣』，獲取更多有趣內(nèi)容。

說在后面

🎉 這里是 JYeontu，現(xiàn)在是一名前端工程師，有空會刷刷算法題，平時喜歡打羽毛球 🏸 ，平時也喜歡寫些東西，既為自己記錄 📋，也希望可以對大家有那么一丟丟的幫助，寫的不好望多多諒解 🙇，寫錯的地方望指出，定會認(rèn)真改進 😊，偶爾也會在自己的公眾號『前端也能這么有趣』發(fā)一些比較有趣的文章，有興趣的也可以關(guān)注下。在此謝謝大家的支持，我們下文再見 🙌。