SQL 分群語法 公車上車的最後一位乘客 Leetcode #1204

更新於 發佈於 閱讀時間約 5 分鐘

題目敘述

題目會給我們一張資料表Queue,代表乘客排隊上車的情境。

裡面分別有person_id、 person_name 、weight、turn等欄位,分別代表乘客ID、乘客姓名、乘客重量、乘客排隊的順序。其中person_id做為主鍵Primary key

要求我們判斷,在不超重(乘客總重量在1000 公斤以內)的條件下,最後一位上車的乘客是誰?

題目額外保證,一定存在一組解答。


詳細的題目可在這裡看到


測試範例

Example 1:

Input: 
Queue table:
+-----------+-------------+--------+------+
| person_id | person_name | weight | turn |
+-----------+-------------+--------+------+
| 5 | Alice | 250 | 1 |
| 4 | Bob | 175 | 5 |
| 3 | Alex | 350 | 2 |
| 6 | John Cena | 400 | 3 |
| 1 | Winston | 500 | 6 |
| 2 | Marie | 200 | 4 |
+-----------+-------------+--------+------+

Output:
+-------------+
| person_name |
+-------------+
| John Cena |
+-------------+

Explanation: The folowing table is ordered by the turn for simplicity.
+------+----+-----------+--------+--------------+
| Turn | ID | Name | Weight | Total Weight |
+------+----+-----------+--------+--------------+
| 1 | 5 | Alice | 250 | 250 |
| 2 | 3 | Alex | 350 | 600 |
| 3 | 6 | John Cena | 400 | 1000 | (last person to board)
| 4 | 2 | Marie | 200 | 1200 | (cannot board)
| 5 | 4 | Bob | 175 | ___ |
| 6 | 1 | Winston | 500 | ___ |
+------+----+-----------+--------+--------------+

演算法

主要有兩個考察點。

  1. 聯想到用Prefix sum前綴和: 用乘客體重的前綴和,方便之後去判斷最後一位可以安全上車的乘客是誰
  2. 使用分群 和 排序語法,輸出最後一位可以安全上車的乘客ID。


  1. 計算乘客體重的前綴和
# Write your MySQL query statement below
SELECT q1.person_name
FROM Queue AS q1
INNER JOIN Queue AS q2
# Prefix sum of weight to each passenger
ON q1.turn >= q2.turn


  1. 結合 分群GROUP BY 排序 ORDER BY語法,輸出最後一位可以安全上車的乘客ID。
GROUP BY q1.turn

# Weight limit 1000 Kg
HAVING SUM(q2.weight) <= 1000

# Sort total weight on descending order
ORDER BY SUM(q2.weight) DESC
# Last one
LIMIT 1;

程式碼

換行的空白只是方便讀者閱讀理解,實際上可以拿掉。

SELECT q1.person_name
FROM Queue AS q1
INNER JOIN Queue AS q2
# Prefix sum of weight to each passenger
ON q1.turn >= q2.turn
GROUP BY q1.turn

# Weight limit 1000 Kg
HAVING SUM(q2.weight) <= 1000

# Sort total weight on descending order
ORDER BY SUM(q2.weight) DESC
# Last one
LIMIT 1;

關鍵知識點

  1. 聯想到用Prefix sum前綴和: 用乘客體重的前綴和,方便之後去判斷最後一位可以安全上車的乘客是誰。這點比較困難,可以在學會之後,多在紙筆或SQL平台上練習幾次,增加熟練度。


  1. 使用分群 和 排序語法,輸出最後一位可以安全上車的乘客ID。

Reference:

[1] MySQL by prefix sum of weight [w/ Comment] - Last Person to Fit in the Bus - LeetCode

留言
avatar-img
留言分享你的想法!
avatar-img
小松鼠的演算法樂園
96會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/01/01
題目敘述 題目會給我們兩張資料表,第一張是Sales,第二張是Product。 第一張是Sales表格,裡面分別有sale_id、 product_id、year、quantity、price等欄位。其中(sale_id、 product_id)做為複合主鍵Primary key Table:
Thumbnail
2024/01/01
題目敘述 題目會給我們兩張資料表,第一張是Sales,第二張是Product。 第一張是Sales表格,裡面分別有sale_id、 product_id、year、quantity、price等欄位。其中(sale_id、 product_id)做為複合主鍵Primary key Table:
Thumbnail
2023/12/29
題目敘述 題目會給我們兩張資料表。 第一張資料表是Employees 裡面分別有id、name等欄位。這張資料表的id是主鍵。 第二張資料表是EmployeeUNI 裡面分別有id、unique_id等欄位。 題目要求我們列出每位員工對應到的Unique ID
Thumbnail
2023/12/29
題目敘述 題目會給我們兩張資料表。 第一張資料表是Employees 裡面分別有id、name等欄位。這張資料表的id是主鍵。 第二張資料表是EmployeeUNI 裡面分別有id、unique_id等欄位。 題目要求我們列出每位員工對應到的Unique ID
Thumbnail
2023/12/26
題目敘述 題目會給我們一張Tweets資料表。裡面分別有tweet_id、content等欄位。這張資料表的tweet_id是主鍵Primary key。 題目要求我們列出所有非法的推文。輸出順序不拘。 非法推文的定義,推文內容的長度超過15個字元。
Thumbnail
2023/12/26
題目敘述 題目會給我們一張Tweets資料表。裡面分別有tweet_id、content等欄位。這張資料表的tweet_id是主鍵Primary key。 題目要求我們列出所有非法的推文。輸出順序不拘。 非法推文的定義,推文內容的長度超過15個字元。
Thumbnail
看更多
你可能也想看
Thumbnail
常常被朋友問「哪裡買的?」嗎?透過蝦皮分潤計畫,把日常購物的分享多加一個步驟,就能轉換成現金回饋。門檻低、申請簡單,特別適合學生與上班族,讓零碎時間也能創造小確幸。
Thumbnail
常常被朋友問「哪裡買的?」嗎?透過蝦皮分潤計畫,把日常購物的分享多加一個步驟,就能轉換成現金回饋。門檻低、申請簡單,特別適合學生與上班族,讓零碎時間也能創造小確幸。
Thumbnail
嗨!歡迎來到 vocus vocus 方格子是台灣最大的內容創作與知識變現平台,並且計畫持續拓展東南亞等等國際市場。我們致力於打造讓創作者能夠自由發表、累積影響力並獲得實質收益的創作生態圈!「創作至上」是我們的核心價值,我們致力於透過平台功能與服務,賦予創作者更多的可能。 vocus 平台匯聚了
Thumbnail
嗨!歡迎來到 vocus vocus 方格子是台灣最大的內容創作與知識變現平台,並且計畫持續拓展東南亞等等國際市場。我們致力於打造讓創作者能夠自由發表、累積影響力並獲得實質收益的創作生態圈!「創作至上」是我們的核心價值,我們致力於透過平台功能與服務,賦予創作者更多的可能。 vocus 平台匯聚了
Thumbnail
題目敘述 Number of Senior Citizens 給定一個旅客的車票字串陣列,美個字串的最後第四個和第三個數字代表旅客的年齡。 例如: XXX...XXX2015 代表旅客年齡為20歲。 總請計算共有多少位乘客的年齡 > 60 歲
Thumbnail
題目敘述 Number of Senior Citizens 給定一個旅客的車票字串陣列,美個字串的最後第四個和第三個數字代表旅客的年齡。 例如: XXX...XXX2015 代表旅客年齡為20歲。 總請計算共有多少位乘客的年齡 > 60 歲
Thumbnail
題目敘述 題目會給我們一張Views資料表。裡面分別有article_id、author_id、viewer_id、view_date等欄位。題目說這張資料表沒有主鍵Primary key,而且可能有重複欄位。 題目要求我們列出所有讀過自己寫的文章的作者ID 輸出答案時,請以作者ID做升序排列
Thumbnail
題目敘述 題目會給我們一張Views資料表。裡面分別有article_id、author_id、viewer_id、view_date等欄位。題目說這張資料表沒有主鍵Primary key,而且可能有重複欄位。 題目要求我們列出所有讀過自己寫的文章的作者ID 輸出答案時,請以作者ID做升序排列
Thumbnail
題目會給我們一張資料表Queue,代表乘客排隊上車的情境。 裡面分別有person_id、 person_name 、weight、turn等欄位,分別代表乘客ID、乘客姓名、乘客重量、乘客排隊的順序。 要求我們判斷,在不超重的條件下,最後一位上車的乘客是誰。
Thumbnail
題目會給我們一張資料表Queue,代表乘客排隊上車的情境。 裡面分別有person_id、 person_name 、weight、turn等欄位,分別代表乘客ID、乘客姓名、乘客重量、乘客排隊的順序。 要求我們判斷,在不超重的條件下,最後一位上車的乘客是誰。
Thumbnail
題目敘述 題目會給我們一張Courses資料表,裡面分別有student、class等欄位。其中(student, class) 是這張資料表的複合主鍵Primary key pair。 要求我們,以課程做分群,列出至少有五位同學的課程。 輸出的順序不拘。 Table: Courses
Thumbnail
題目敘述 題目會給我們一張Courses資料表,裡面分別有student、class等欄位。其中(student, class) 是這張資料表的複合主鍵Primary key pair。 要求我們,以課程做分群,列出至少有五位同學的課程。 輸出的順序不拘。 Table: Courses
Thumbnail
題目敘述 題目會給我們一張Customer資料表,裡面分別有id、name、referee_id 等欄位,其中id 是主鍵Primary Key。 要求我們列出所有推薦人ID referee_id不等於2的顧客,印出順序不拘。
Thumbnail
題目敘述 題目會給我們一張Customer資料表,裡面分別有id、name、referee_id 等欄位,其中id 是主鍵Primary Key。 要求我們列出所有推薦人ID referee_id不等於2的顧客,印出順序不拘。
Thumbnail
題目會給我們一個routes 陣列,裡面都是分別代表每一條公車路線所對應的公車站編號。 題目要求我們計算出,從起點站source到終點站target的最精簡公車路線搭乘次數是幾次? 也就是說,就是在最少轉乘的前提下,旅途中需要搭乘幾條公車路線?
Thumbnail
題目會給我們一個routes 陣列,裡面都是分別代表每一條公車路線所對應的公車站編號。 題目要求我們計算出,從起點站source到終點站target的最精簡公車路線搭乘次數是幾次? 也就是說,就是在最少轉乘的前提下,旅途中需要搭乘幾條公車路線?
Thumbnail
題目會定義一組類別和介面,要求我們實做餐廳訂位報號系統。 SeatManager(int n) : 初始化餐廳最多有n個座位,n 最少是1 int reserve() : 要求返回最小的可讓客人入座的空座位編號。 void unreserve(int seatNumber) : 取消訂位,這個座位歸
Thumbnail
題目會定義一組類別和介面,要求我們實做餐廳訂位報號系統。 SeatManager(int n) : 初始化餐廳最多有n個座位,n 最少是1 int reserve() : 要求返回最小的可讓客人入座的空座位編號。 void unreserve(int seatNumber) : 取消訂位,這個座位歸
Thumbnail
題目敘述 這題是一個經典的資料結構實作題,要求我們實作指定長度為k的環狀佇列。 請記得,佇列最重要的特質就是先進先出 First In First Out 又簡稱為 FIFO
Thumbnail
題目敘述 這題是一個經典的資料結構實作題,要求我們實作指定長度為k的環狀佇列。 請記得,佇列最重要的特質就是先進先出 First In First Out 又簡稱為 FIFO
Thumbnail
班上闖來了一個陌生人!該如何快狠準揪出他?這道經典考題的解法,遠比你想的還要多種 ......
Thumbnail
班上闖來了一個陌生人!該如何快狠準揪出他?這道經典考題的解法,遠比你想的還要多種 ......
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News