問題描述

小R正在組織一個比賽，比賽中有 n 支隊伍參賽。比賽遵循以下獨特的賽制：

• 如果當前隊伍數為 偶數，那么每支隊伍都會與另一支隊伍配對。總共進行 n / 2 場比賽，且產生 n / 2 支隊伍進入下一輪。
• 如果當前隊伍數為 奇數，那么將會隨機輪空并晉級一支隊伍，其余的隊伍配對。總共進行 (n - 1) / 2 場比賽，且產生 (n - 1) / 2 + 1 支隊伍進入下一輪。

小R想知道在比賽中進行的配對次數，直到決出唯一的獲勝隊伍為止。

測試樣例

樣例1：
輸入：n = 7
輸出：6

樣例2：
輸入：n = 14
輸出：13

樣例3：
輸入：n = 1
輸出：0

解決思路

數學歸納法和遞歸思想。題目描述了一個比賽配對的過程，要求計算從 n 支隊伍開始，直到決出唯一獲勝隊伍為止的總配對次數。通過觀察可以發現，每次配對后，隊伍數會減少一半（偶數情況）或減少一半加一（奇數情況）。最終，隊伍數會減少到1，此時不再需要配對。因此，問題的核心在于計算從 n 到 1 的過程中，總共進行了多少次配對。通過數學歸納法可以證明，從 n 支隊伍到決出唯一獲勝隊伍，總共需要進行 n - 1 次配對。

1. 初始狀態：從 n 支隊伍開始。
2. 遞歸配對：每次配對后，隊伍數減少一半（偶數情況）或減少一半加一（奇數情況）。
3. 終止條件：當隊伍數減少到1時，不再需要配對。
4. 總配對次數：通過數學歸納法可以證明，從 n 支隊伍到決出唯一獲勝隊伍，總共需要進行 n - 1 次配對。

時間復雜度：O(1)。直接返回 n - 1，不需要額外的計算。
空間復雜度：O(1)。只使用了常數級別的額外空間。

代碼

def solution(n: int) -> int:# 初始化配對次數pairs = 0# 當隊伍數大于1時，繼續進行比賽while n > 1:# 如果隊伍數為偶數if n % 2 == 0:# 進行 n / 2 場比賽pairs += n // 2# 剩余 n / 2 支隊伍n //= 2else:# 如果隊伍數為奇數# 進行 (n - 1) / 2 場比賽pairs += (n - 1) // 2# 剩余 (n - 1) / 2 + 1 支隊伍n = (n - 1) // 2 + 1return pairsif __name__ == '__main__':print(solution(7) == 6)print(solution(14) == 13)print(solution(1) == 0)

簡單的代碼為：

def solution(n:int)->int:return n - 1if __name__ == '__main__':print(solution(n = 7) == 6)print(solution(n = 14) == 13)print(solution(n = 1) == 0)