貪婪計數Python C++解Leetcode 2491 Divide Players Into Teams of Equal Skill

An-Wen Deng
4粉絲
21 次觀看·2024年10月16日
貪婪計數Python C++解Leetcode 2491 Divide Players Into Teams of Equal Skill
貪婪演算+counting sort加上2-pointer這樣就完成打敗100趴的快速C++解答
-----
Greedy algorithm+ counting sort + 2-pointer complete the quick C++ solution to defeat 100%.
[codes on Leetcode]https://leetcode.com/problems/divide-players-into-teams-of-equal-skill/solutions/5866450/greedy-sort-frequency-count-2-pointers-14ms-beats-100/
[Leetcode Playlist]https://www.youtube.com/watch?v=B1GQlUN08lk&list=PLYRlUBnWnd5IdDHk2BjqXwesydU17z_xk
[Python C++計數速解Leetcode 945 Minimum Increment to Make Array Unique]https://www.youtube.com/watch?v=tS-kunvQwcc
好,我們來解今天DECODE的問題
今天是第2491題
所謂的Divide Players into Teams of Equal Scale
好,那它的題目大約是這樣的
就是說,它有一個正整數的一個陣列
就叫SCALE
它的一個長度是偶數
SCALE在I的詞代表就是
第一個玩家他的SCALE
基本上呢
這些玩家呢
你要把它分成二分之N的隊伍
每個隊伍的SIZE當然是2
所以當然是偶數
N當然是偶數
使得他們的SCALE的核呢
也就是說在team裡面SCALE的核是相同的
好,那麼它的問題是問
每個team它有一個所謂的
Chemistry 化學
代表就是說他們這兩個SCALE的成績
所以它要去返回這個Chemistry的核
總核
如果沒有辦法去分成這樣的一個team
那就返回-1
OK,那我們來看它這裡的一個例題
像第一個例題
它答案是22
我們看它是怎麼分的
基本上
根據它這裡面的數值
所以15合起來是6
2跟4合起來是6
3跟3合起來是6
所以每個team的TOTAL SCALE當然是6
這個當然你要先能夠分成teams
如果不行的話就返回-1
然後再將它的所謂的Chemistry
成績的核
把它算出來
所以答案是22
如果它只有兩個那就很簡單
3跟4乘起來就12
這沒有問題
第三個問題是
它是沒有的
你沒有辦法把它分成這樣的team
怎麼分都不可能
那我們看一下它的Constraints
它SCALE的長度是介於2到10萬之間
10到5次方
那SCALE的Length它一定是偶數
所以一開始這個可以不用去檢查
那SCALE的值是介於1到1000之間
所以根據這個Constraints
我們其實可以用所謂的Counting Sort來解這樣的問題
接下來我們看看我們怎麼去解
我們看到這邊的一個Note
基本上我們的解決方式大概有幾個步驟
當然是用所謂的貪婪演算
貪婪演算裡面呢
它有大概幾個步驟
第一個當然是先把它正面的所謂SCALE
把它的總和把它算出來
因為我們打算是用所謂的計數排序
當然後面至少用到前面
計數的這樣一個
所謂的Frequency Count的一個步驟會用到
我們同時也計算它裡面的最大值跟極小值
然後再來用所謂的Two Pointer的一個方式
類似下面這樣C++的
之前我們的解答這樣的一個方式
那我們就根據這樣一個Note
我們來用Python來實作
那步驟1跟2其實原則上
來講我們
在這邊的話我們因為根據它的一個條件
所以我們可以先設Frequency
Frequency的值一開始全部都是0
那基本上它的SCALE的
根據它的Constraint它是1到1000
所以這邊我們就乘以1001
然後我們透過
我們要考慮它的一個總和
總和的話我們就用大寫的SUM
然後我們有極小值
極大值
那SUM一開始當然是0
然後Min的話一開始
我們當然先給1000
極大值一開始我們就先給1
那透過一個迴圈
我們其實就可以這樣步驟1跟2就把它完成
我們用一般的迴圈
所以X就是在這個SCALE裡面
好,我們的Frequency
在X的值當然就加等於1
那我們的SUM也是將X把它加進來
再來我們的Min
就是取Min
Smin跟X的Min
那Xmax就是取Max
這個當然就是Xmax跟目前的X
這樣去取
所以這個應該是第一個部分
那我們當然要看它在一些情況之下
它會所謂的Early Start
所以我們這邊再設一個變數叫做
n underscore 2
基本上它就是
SCALE的N除以2
那我們看看它是不是一開始
它就會不會有這樣的一個問題
如果我們的SUM
去罵掉n underscore 2
如果是不等於0的話
如果它不整除的話
基本上它那個Ting就沒有辦法完成
所以這個時候就return-1
那所謂的Ting Scale
也就是每個Ting它的總和
基本上它應該是SUM
就是除以這個n underscore 2
基本上是這樣
那所以下面的話
我們當然就是根據左邊的方式
我們再把它改寫成Python
所以下面我們這邊就是改寫
所謂的Chaining開始值是0
然後我們的L
L的初值它是從最小
S當中的最小的
我們用一行來寫好了
L跟R的值
L是從Xmin開始
R是從Xmax開始
基本上這邊我們透過Python
當然就是用File Loop去寫
所以當L只要是小於R
我們都去進行這個Loop裡面的事情
當然我們要去算L的Frequency
我們這邊就設FL
那R的Frequency
我們這邊就FR
分別當然就是Frequency
在R的值
以及Frequency在R跟L的值
這邊
OK 這邊應該沒有問題
然後呢
如果我們的R加L加R
如果不等於我們的Team Skill
就代表這個出問題了
就那個Team就沒辦法組
或者呢
他們的Frequency不相同
這個也沒辦法配對了
這樣的一個情況
這個時候呢
當然我們就直接做Return
-1
好
我們的K-mean
他們就加等於
我們的Frequency的值
再乘上L
再乘上R
這個在計算上當然會比較快一些
那這個時候你不要忘記
我們的L要往上加1
R要往下減1
那問題是我們
這個有可能到後來
你跳出迴圈的時候
L跟R它是相等的
那就代表中間它會
會有會合的地方
所以如果
L等於等於R的時候呢
那我們這邊就要考慮
如果L等於等於R
而且呢
也就是L的值兩倍
它又等於剛好是等於
等於Team Skill的話
代表我們當然要把中間那一項
也要把它加進來
這樣的一個情形
所以這個時候就是要將
K-mean
要加等於
所以我們的Frequency
在L或R反正都一樣的值
要除以除以
2再乘以L的平方
那這樣應該就好了
其他的話中間剛好如果是
最後跳出迴圈L跟R是不相等的
那當然就不用處理
所以最後我們的答案應該就是
K-mean
我們看看這樣有沒有什麼問題
執行一次
有一點問題
主要的問題是在剛剛這邊
這邊一個小Bug
我們將這個X弄很大型
當然後面就
就第一次沒有讓對
經過除錯之後我們再重新執行一次
然後這三個Case都OK
好我們Submit
所以他這樣當然是不快
因為我們用兩個迴圈去做
我們把它
弄在這邊
所以我們基本上是完全照
我們之前C++的一個方式去做
至少這是OK的
那我們再看C++的一個情況
基本上是相同的一個邏輯
那我們讓他執行
Submit
所以基本上如果是採用C++
甚至14毫秒
就完成了
好那我們就談到這裡
