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
小松鼠的演算法樂園
95會員
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
TOMICA第一波推出吉伊卡哇聯名小車車的時候馬上就被搶購一空,一直很扼腕當時沒有趕緊入手。前陣子閒來無事逛蝦皮,突然發現幾家商場都又開始重新上架,價格也都回到正常水準,估計是官方又再補了一批貨,想都沒想就立刻下單! 同文也跟大家分享近期蝦皮購物紀錄、好用推薦、蝦皮分潤計畫的聯盟行銷!
Thumbnail
TOMICA第一波推出吉伊卡哇聯名小車車的時候馬上就被搶購一空,一直很扼腕當時沒有趕緊入手。前陣子閒來無事逛蝦皮,突然發現幾家商場都又開始重新上架,價格也都回到正常水準,估計是官方又再補了一批貨,想都沒想就立刻下單! 同文也跟大家分享近期蝦皮購物紀錄、好用推薦、蝦皮分潤計畫的聯盟行銷!
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
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