比賽中的配對次數
問題：
給你一個整數 n ，表示比賽中的隊伍數，比賽遵循一種獨特的賽制：
如果當前隊伍數是 偶數 ，那么每支隊伍都會與另一支隊伍配對，總共進行 n / 2 場比賽，且產生 n / 2 支隊伍進入下一輪，
如果當前隊伍數為 奇數 ，那么將會隨機輪空并晉級一支隊伍，其余的隊伍配對，總共進行 (n - 1) / 2 場比賽，且產生 (n - 1) / 2 + 1 支隊伍進入下一輪，
回傳在比賽中進行的配對次數，直到決出獲勝隊伍為止，
思路：
例：
輸入：n = 7
輸出：6
解釋：比賽詳情：
- 第 1 輪：隊伍數 = 7 ，配對次數 = 3 ，4 支隊伍晉級，
- 第 2 輪：隊伍數 = 4 ，配對次數 = 2 ，2 支隊伍晉級，
- 第 3 輪：隊伍數 = 2 ，配對次數 = 1 ，決出 1 支獲勝隊伍，
總配對次數 = 3 + 2 + 1 = 6
輸入：n = 14
輸出：13
解釋：比賽詳情：
- 第 1 輪：隊伍數 = 14 ，配對次數 = 7 ，7 支隊伍晉級，
- 第 2 輪：隊伍數 = 7 ，配對次數 = 3 ，4 支隊伍晉級，
- 第 3 輪：隊伍數 = 4 ，配對次數 = 2 ，2 支隊伍晉級，
- 第 4 輪：隊伍數 = 2 ，配對次數 = 1 ，決出 1 支獲勝隊伍，
總配對次數 = 7 + 3 + 2 + 1 = 13
方法一： 按照題目要求迭代求和
class Solution {
public:
int numberOfMatches(int& n) const {
if(n <= 1) return 0;
auto count = 0;
while(n > 1) {
count += n / 2;
n = n & 1 ? (n + 1) / 2 : n / 2;
}
return count;
}
};
方法二： 遞回
class Solution {
public:
int numberOfMatches(int n) const {
if(n <= 1) return 0;
return n / 2 + numberOfMatches((n + 1) / 2);
}
};
方法三：通過發現，我們的配對次數始終等于隊伍數減一
class Solution {
public:
int numberOfMatches(int n) {
if(n <= 1) return 0;
return n - 1;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/256008.html
標籤：其他
下一篇：【C++初階】淺談參考和行內函式