說(shuō)在前面

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

題目描述

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

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

當(dāng)且僅當(dāng)你可以在所有給定的行程中接送所有乘客時(shí)，返回?true，否則請(qǐng)返回?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

解題思路

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

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

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

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

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

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

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

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;
};

公眾號(hào)

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

說(shuō)在后面

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