前往
大廳
主題

LeetCode - 2512. Reward Top K Students 解題心得

Not In My Back Yard | 2023-11-11 12:00:24 | 巴幣 0 | 人氣 81

題目連結:


題目意譯:
你被給定兩字串陣列 positive_feedback 和 negative_feedback,其分別包含著正面以及負面的意見回饋之字詞。注意到,沒有任何字詞同時是正面和負面的。

一開始每一位學生都是 0 分。當學生在意見回饋報告中每收到一個正面字詞,分數便會增加 3;而每收到一個負面字詞則分數減去 1。

你被給定 n 個以一個索引值從 0 開始的字串陣列 report 表示之意見回饋報告以及一個索引值從 0 開始的整數陣列 student_id,其中 student_id[i] 代表著收到 report[i] 這份意見回饋報告的學生之 ID。每一位學生的 ID 是獨一無二的。

給定一整數 k,回傳根據學生們的分數排序後排名前 k 高者。為了保險起見,如果有多位學生有著相同的分數,則有著較小 ID 值者排名較高。

限制:
1 ≦ positive_feedback.length, negative_feedback.length ≦ 10 ^ 4
1 ≦ positive_feedback[i].length, negative_feedback[j].length ≦ 100
positive_feedback[i] 和 negative_feedback[j] 都由小寫英文字母組成。
沒有字詞同時出現於 positive_feedback 和 negative_feedback 之中。
n == report.length == student_id.length
1 ≦ n ≦ 10 ^ 4
report[i] 由小寫英文字母以及空白 ' ' 所組成。
在 report[i] 中每個字詞之間都有一個空白。
1 ≦ report[i].length ≦ 100
1 ≦ student_id[i] ≦ 10 ^ 9
student_id[i] 中的數值彼此相異。
1 ≦ k ≦ n



範例測資:
範例 1:
輸入: positive_feedback = ["smart","brilliant","studious"], negative_feedback = ["not"], report = ["this student is studious","the student is smart"], student_id = [1,2], k = 2
輸出: [1,2]
解釋:
兩位學生都有著 1 個正面回饋和 3 分。但由於學生 1 有著更小的 ID 值,因此他的排名比較高。

範例 2:
輸入: positive_feedback = ["smart","brilliant","studious"], negative_feedback = ["not"], report = ["this student is not studious","the student is smart"], student_id = [1,2], k = 2
輸出: [2,1]
解釋:
- ID 值是 1 的學生有著 1 正面回饋以及 1 個負面回饋,所以他有 3 - 1 = 2 分。
- ID 值是 1 的學生有著 1 正面回饋,所以他有 3 分。
由於學生 2 有更多分數,因此我們回傳 [2,1]。


解題思維:
直接計算出每一位學生的分數,而為了處理學生 ID 與其對應分數值的資料,我們可以使用雜湊表(Hash Table)來儲存。

得到所有學生的分數之後,接著就跟一般的自定義排序(如這題)一樣把分數和 ID 綁在一起形成一個結構(Struct)。最後根據題目定義的規則排序後取前 k 個學生的 ID 即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作