- 博客主頁：誓則盟約
- 系列專欄：IT競賽 專欄
- 關注博主，后期持續更新系列文章
- 如果有錯誤感謝請大家批評指出，及時修改
- 感謝大家點贊👍收藏?評論??
2491.劃分技能點相等的團隊【中等】
題目：
給你一個正整數數組?skill?，數組長度為?偶數?n?，其中?skill[i]?表示第?i?個玩家的技能點。將所有玩家分成?n / 2?個?2?人團隊，使每一個團隊的技能點之和?相等?。
團隊的?化學反應?等于團隊中玩家的技能點?乘積?。
返回所有團隊的?化學反應?之和，如果無法使每個團隊的技能點之和相等，則返回?-1?。
示例 1：
輸入：skill = [3,2,5,1,3,4] 輸出：22 解釋： 將玩家分成 3 個團隊 (1, 5), (2, 4), (3, 3) ，每個團隊的技能點之和都是 6 。 所有團隊的化學反應之和是 1 * 5 + 2 * 4 + 3 * 3 = 5 + 8 + 9 = 22 。
示例 2：
輸入：skill = [3,4] 輸出：12 解釋： 兩個玩家形成一個團隊，技能點之和是 7 。 團隊的化學反應是 3 * 4 = 12 。
示例 3：
輸入：skill = [1,1,2,3] 輸出：-1 解釋： 無法將玩家分成每個團隊技能點都相等的若干個 2 人團隊。
分析問題：
思路1：
????????這里可以先根據數組的長度來獲得平均和key值，然后對skill數組進行一個排序，那么如果想等于key值的話，只能讓最大值+最小值，如果有一個不符合題意則直接return -1。將符合題意的兩個值的乘積全部加起來，最后return 就是結果。思路很簡單。但是時間復雜度相比之下略高。
思路2：
????????首先計算出所有技能值的總和以及每個團隊理想的技能值總和。然后通過遍歷技能值及其出現次數，判斷能否將技能值兩兩分組，使得每組的技能值總和都等于理想值，同時計算出所有分組產生的化學效能總和。如果在過程中出現無法滿足分組條件的情況，就返回 -1 ，否則返回計算得到的化學效能總和。
代碼實現：
思路1代碼實現：
class Solution:def dividePlayers(self, skill: List[int]) -> int:skill.sort()ans, s = 0, skill[0] + skill[-1]for i in range(len(skill) // 2):x, y = skill[i], skill[-1 - i]if x + y != s: return -1ans += x * yreturn ans
??
思路2代碼實現：?
class Solution:def dividePlayers(self, skill: List[int]) -> int:# 計算所有技能值的總和s = sum(skill)# 計算團隊數量（因為要兩兩分組，所以團隊數量是技能值個數的一半）n = len(skill) // 2# 如果總和不能被團隊數量整除，說明無法平均分配，返回 -1if s % n:return -1# 計算每個團隊的理想技能值總和t = s // n# 初始化最終的化學效能總和為 0ans = 0# 使用 Counter 統計每個技能值出現的次數cnt = Counter(skill)# 遍歷統計得到的技能值for k in list(cnt.keys()):# 如果當前技能值 k 與理想值 t - k 相等if k == t - k:# 如果該技能值的出現次數為奇數，無法兩兩配對，返回 -1if cnt[k] % 2:return -1# 計算該技能值兩兩配對產生的化學效能，并累加到總和中ans += k*k*cnt[k]//2else:# 如果當前技能值 k 和 t - k 的出現次數相等if cnt[k] == cnt[t - k]:# 計算它們配對產生的化學效能，并累加到總和中ans += k*(t - k)*cnt[k]# 將這兩個技能值的出現次數置為 0，表示已經處理完cnt[k] = cnt[t - k] = 0else:# 如果出現次數不相等，無法滿足兩兩配對的條件，返回 -1return -1# 返回最終的化學效能總和return ans
?
總結：
?????????兩種方法，思路1較容易想出來但是復雜度略高。思路2相比于思路1可能沒那么容易想出來，但是復雜度還是很優的。下面對思路2進行代碼詳解：
思路2代碼詳解：
????????首先，通過計算技能值的總和以及團隊數量，來判斷是否能夠平均分配技能值。如果不能整除，說明無法實現平均分組，直接返回?-1?。
????????然后，創建一個計數器?cnt?來統計每個技能值出現的次數。
????????接下來，遍歷所有的技能值。對于每個技能值?k?，分兩種情況處理：
- 如果?
k?與理想差值?t - k?相等，需要檢查其出現次數是否為偶數，因為只有偶數次才能兩兩配對。如果是偶數次，計算?k?兩兩配對產生的化學效能并累加到結果中。 - 如果?
k?與理想差值?t - k?不相等，那么需要檢查?k?和?t - k?的出現次數是否相等，如果相等則計算它們配對產生的化學效能，否則說明無法滿足兩兩配對的條件，直接返回?-1?。
????????最后，如果整個遍歷過程都沒有出現無法配對的情況，就返回計算得到的化學效能總和。
考點：
- 數學計算，如求和、整除判斷。
- 數據結構?
Counter?的使用。 - 條件判斷和邏輯處理。
收獲：
- 學習如何有效地處理整數列表的分組問題，包括總和計算、平均分配判斷等。
- 掌握使用?
Counter?來高效統計元素出現次數的方法。 - 提升通過遍歷和條件判斷來解決復雜邏輯問題的能力。
- 了解如何在代碼中確保數據滿足特定條件，不滿足時進行錯誤處理返回特定值。
