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
每年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的最精簡公車路線搭乘次數是幾次? 也就是說,就是在最少轉乘的前提下,旅途中需要搭乘幾條公車路線?
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News