1900. 最早和最晚相遇的轮次

Hard

题目描述

有一场锦标赛，共有 n 名选手参加。选手们站成一排，按照初始位置从 1 到 n 编号（选手 1 是第一位，选手 2 是第二位，以此类推）。

锦标赛包含多轮比赛（从第 1 轮开始）。在每一轮中，排在前面的第 i 位选手与排在后面的第 i 位选手比赛，获胜者进入下一轮。当当前轮次的选手数量为奇数时，中间的选手自动晋级到下一轮。

例如，如果这一排选手为 1, 2, 4, 6, 7：

选手 1 与选手 7 比赛
选手 2 与选手 6 比赛
选手 4 自动晋级到下一轮

每轮结束后，获胜者会根据他们最初分配的编号重新排列（升序排列）。

编号为 firstPlayer 和 secondPlayer 的选手是锦标赛中最强的。他们可以击败任何其他选手，除非他们相互比赛。如果任何其他两名选手相互比赛，他们中的任何一个都可能获胜，因此你可以选择这一轮的结果。

给定整数 n、firstPlayer 和 secondPlayer，返回一个包含两个值的整数数组，分别表示这两名选手相互比赛的最早可能轮次和最晚可能轮次。

示例 1:

输入：n = 11, firstPlayer = 2, secondPlayer = 4
输出：[3,4]

示例 2:

输入：n = 5, firstPlayer = 1, secondPlayer = 5
输出：[1,1]

提示：

2 <= n <= 28
1 <= firstPlayer < secondPlayer <= n

解题思路

这是一个复杂的动态规划问题，需要模拟锦标赛的每一轮比赛过程。

核心思路：

使用记忆化搜索，状态表示为当前轮次中还剩余的选手集合
对于每个状态，我们需要计算在这种情况下两个目标选手相遇的最早和最晚轮次
由于选手总是按照原始编号重新排列，我们可以用位掩码表示当前剩余的选手

具体步骤：

使用位掩码表示当前轮次中剩余的选手，1表示该选手还在比赛中
对于每一轮，模拟配对过程：前i个选手与后i个选手比赛
如果目标两选手在同一轮中配对，直接返回当前轮次
否则，尝试所有可能的比赛结果组合，递归计算下一轮的状态
使用记忆化避免重复计算相同状态

优化要点：

由于n≤28，状态空间较大，必须使用记忆化
对于非目标选手的比赛，我们需要尝试所有可能的结果来找到最早和最晚的情况
目标选手总是能击败其他选手，这简化了某些比赛的结果

代码实现

class Solution {
private:
    map<pair<int, pair<int, int>>, pair<int, int>> memo;
    
public:
    vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
        int mask = (1 << n) - 1;
        auto result = dfs(mask, firstPlayer - 1, secondPlayer - 1, 1);
        return {result.first, result.second};
    }
    
private:
    pair<int, int> dfs(int mask, int first, int second, int round) {
        if (__builtin_popcount(mask) == 1) return {-1, -1};
        
        auto key = make_pair(mask, make_pair(first, second));
        if (memo.count(key)) return memo[key];
        
        vector<int> players;
        for (int i = 0; i < 32; i++) {
            if (mask & (1 << i)) players.push_back(i);
        }
        
        int n = players.size();
        if (n == 2) {
            return memo[key] = {round, round};
        }
        
        // Check if first and second are paired this round
        int firstPos = find(players.begin(), players.end(), first) - players.begin();
        int secondPos = find(players.begin(), players.end(), second) - players.begin();
        
        if (firstPos + secondPos == n - 1) {
            return memo[key] = {round, round};
        }
        
        int minRound = INT_MAX, maxRound = 0;
        function<void(int, int)> backtrack = [&](int pos, int nextMask) {
            if (pos >= n / 2) {
                auto result = dfs(nextMask, first, second, round + 1);
                if (result.first != -1) {
                    minRound = min(minRound, result.first);
                    maxRound = max(maxRound, result.second);
                }
                return;
            }
            
            int left = players[pos], right = players[n - 1 - pos];
            
            if (left == first || left == second) {
                backtrack(pos + 1, nextMask | (1 << left));
            } else if (right == first || right == second) {
                backtrack(pos + 1, nextMask | (1 << right));
            } else {
                backtrack(pos + 1, nextMask | (1 << left));
                backtrack(pos + 1, nextMask | (1 << right));
            }
        };
        
        backtrack(0, 0);
        return memo[key] = {minRound, maxRound};
    }
};

class Solution:
    def earliestAndLatest(self, n: int, firstPlayer: int, secondPlayer: int) -> List[int]:
        memo = {}
        
        def dfs(mask, first, second, round_num):
            if bin(mask).count('1') == 1:
                return (-1, -1)
                
            key = (mask, first, second)
            if key in memo:
                return memo[key]
            
            players = []
            for i in range(32):
                if mask & (1 << i):
                    players.append(i)
            
            n_players = len(players)
            if n_players == 2:
                memo[key] = (round_num, round_num)
                return memo[key]
            
            # Check if first and second are paired this round
            try:
                first_pos = players.index(first)
                second_pos = players.index(second)
                if first_pos + second_pos == n_players - 1:
                    memo[key] = (round_num, round_num)
                    return memo[key]
            except ValueError:
                pass
            
            min_round = float('inf')
            max_round = 0
            
            def backtrack(pos, next_mask):
                nonlocal min_round, max_round
                if pos >= n_players // 2:
                    result = dfs(next_mask, first, second, round_num + 1)
                    if result[0] != -1:
                        min_round = min(min_round, result[0])
                        max_round = max(max_round, result[1])
                    return
                
                left = players[pos]
                right = players[n_players - 1 - pos]
                
                if left == first or left == second:
                    backtrack(pos + 1, next_mask | (1 << left))
                elif right == first or right == second:
                    backtrack(pos + 1, next_mask | (1 << right))
                else:
                    backtrack(pos + 1, next_mask | (1 << left))
                    backtrack(pos + 1, next_mask | (1 << right))
            
            backtrack(0, 0)
            memo[key] = (min_round, max_round)
            return memo[key]
        
        mask = (1 << n) - 1
        result = dfs(mask, firstPlayer - 1, secondPlayer - 1, 1)
        return [result[0], result[1]]

public class Solution {
    private Dictionary<(int, int, int), (int, int)> memo = new Dictionary<(int, int, int), (int, int)>();
    
    public int[] EarliestAndLatest(int n, int firstPlayer, int secondPlayer) {
        int mask = (1 << n) - 1;
        var result = DFS(mask, firstPlayer - 1, secondPlayer - 1, 1);
        return new int[] { result.Item1, result.Item2 };
    }
    
    private (int, int) DFS(int mask, int first, int second, int round) {
        if (System.Numerics.BitOperations.PopCount((uint)mask) == 1) {
            return (-1, -1);
        }
        
        var key = (mask, first, second);
        if (memo.ContainsKey(key)) {
            return memo[key];
        }
        
        var players = new List<int>();
        for (int i = 0; i < 32; i++) {
            if ((mask & (1 << i)) != 0) {
                players.Add(i);
            }
        }
        
        int nPlayers = players.Count;
        if (nPlayers == 2) {
            memo[key] = (round, round);
            return memo[key];
        }
        
        int firstPos = players.IndexOf(first);
        int secondPos = players.IndexOf(second);
        
        if (firstPos + secondPos == nPlayers - 1) {
            memo[key] = (round, round);
            return memo[key];
        }
        
        int minRound = int.MaxValue;
        int maxRound = 0;
        
        void Backtrack(int pos, int nextMask) {
            if (pos >= nPlayers / 2) {
                var result = DFS(nextMask, first, second, round + 1);
                if (result.Item1 != -1) {
                    minRound = Math.Min(minRound, result.Item1);
                    maxRound = Math.Max(maxRound, result.Item2);
                }
                return;
            }
            
            int left = players[pos];
            int right = players[nPlayers - 1 - pos];
            
            if (left == first || left == second) {
                Backtrack(pos + 1, nextMask | (1 << left));
            } else if (right == first || right == second) {
                Backtrack(pos + 1, nextMask | (1 << right));
            } else {
                Backtrack(pos + 1, nextMask | (1 << left));
                Backtrack(pos + 1, nextMask | (1 << right));
            }
        }
        
        Backtrack(0, 0);
        memo[key] = (minRound, maxRound);
        return memo[key];
    }
}

var earliestAndLatest = function(n, firstPlayer, secondPlayer) {
    const memo = new Map();
    
    function dfs(players, pos1, pos2) {
        if (pos1 > pos2) [pos1, pos2] = [pos2, pos1];
        
        const key = `${players.length}-${pos1}-${pos2}`;
        if (memo.has(key)) return memo.get(key);
        
        const n = players.length;
        if (n === 1) return [1, 1];
        
        // Check if they compete in this round
        const pairs = Math.floor(n / 2);
        for (let i = 0; i < pairs; i++) {
            if ((i + 1 === pos1 && n - i === pos2) || (i + 1 === pos2 && n - i === pos1)) {
                return [1, 1];
            }
        }
        
        let minRound = Infinity, maxRound = 0;
        
        function backtrack(idx, winners, newPos1, newPos2) {
            if (idx === pairs) {
                // Add middle player if odd
                if (n % 2 === 1) {
                    const mid = Math.floor(n / 2) + 1;
                    winners.push(players[mid - 1]);
                    if (mid === pos1) newPos1 = winners.length;
                    if (mid === pos2) newPos2 = winners.length;
                }
                
                const [subMin, subMax] = dfs(winners, newPos1, newPos2);
                minRound = Math.min(minRound, 1 + subMin);
                maxRound = Math.max(maxRound, 1 + subMax);
                
                if (n % 2 === 1) winners.pop();
                return;
            }
            
            const left = idx + 1;
            const right = n - idx;
            
            // Left player wins
            winners.push(players[left - 1]);
            let nextPos1 = newPos1, nextPos2 = newPos2;
            if (left === pos1) nextPos1 = winners.length;
            if (left === pos2) nextPos2 = winners.length;
            
            if ((left === pos1 || left === pos2) || (right !== pos1 && right !== pos2)) {
                backtrack(idx + 1, winners, nextPos1, nextPos2);
            }
            
            winners.pop();
            
            // Right player wins
            winners.push(players[right - 1]);
            nextPos1 = newPos1; nextPos2 = newPos2;
            if (right === pos1) nextPos1 = winners.length;
            if (right === pos2) nextPos2 = winners.length;
            
            if ((right === pos1 || right === pos2) || (left !== pos1 && left !== pos2)) {
                backtrack(idx + 1, winners, nextPos1, nextPos2);
            }
            
            winners.pop();
        }
        
        backtrack(0, [], 0, 0);
        
        const result = [minRound, maxRound];
        memo.set(key, result);
        return result;
    }
    
    const players = Array.from({length: n}, (_, i) => i + 1);
    return dfs(players, firstPlayer, secondPlayer);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析
时间复杂度	O(3^n)，最坏情况下需要遍历所有可能的比赛结果组合
空间复杂度	O(2^n)，记忆化存储的状态数量最多为2^n个不同的选手集合

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析