Hard

题目描述

我们有 n 栋楼，编号从 0 到 n - 1。每栋楼都有一定数量的员工。现在是换楼季，一些员工想要换到其他楼工作。

给你一个数组 requests，其中 requests[i] = [fromi, toi] 表示一个员工请求从 fromi 楼转到 toi 楼。

所有楼都是满员的，所以请求列表只有在每栋楼的员工净变化为零时才是可达成的。这意味着离开的员工数量等于转入的员工数量。例如，如果 n = 3，有两个员工离开 0 号楼，一个员工离开 1 号楼，一个员工离开 2 号楼，那么应该有两个员工转到 0 号楼，一个员工转到 1 号楼，一个员工转到 2 号楼。

返回可达成的最大请求数目。

示例 1:

输入: n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
输出: 5
解释: 让我们看看请求：
从 0 号楼我们有员工 x 和 y，都想转到 1 号楼。
从 1 号楼我们有员工 a 和 b，他们想分别转到 2 号楼和 0 号楼。
从 2 号楼我们有员工 z，想转到 0 号楼。
从 3 号楼我们有员工 c，想转到 4 号楼。
4 号楼没有任何请求。
我们可以通过交换 x 和 b 的位置来达成他们的请求。
我们可以通过在 3 栋楼中交换位置来达成 y、a 和 z 的请求。

示例 2:

输入: n = 3, requests = [[0,0],[1,2],[2,1]]
输出: 3
解释: 让我们看看请求：
从 0 号楼我们有员工 x，想留在同一栋楼 0。
从 1 号楼我们有员工 y，想转到 2 号楼。
从 2 号楼我们有员工 z，想转到 1 号楼。
我们可以达成所有请求。

示例 3:

输入: n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]
输出: 4

约束条件:

  • 1 <= n <= 20
  • 1 <= requests.length <= 16
  • requests[i].length == 2
  • 0 <= fromi, toi < n

解题思路

这是一个经典的子集枚举问题，需要找到满足平衡条件的最大请求子集。

核心思路：

  1. 由于请求数量最多只有16个，我们可以使用位掩码枚举所有可能的请求子集（2^16 = 65536种可能）
  2. 对于每个子集，检查是否满足平衡条件：每栋楼的净变化为0（流入员工数 = 流出员工数）
  3. 在所有满足条件的子集中，选择包含请求数量最多的那个

算法步骤：

  1. 遍历从0到2^m-1的所有位掩码（m为请求总数）
  2. 对于每个位掩码，统计对应请求子集中每栋楼的净变化
  3. 检查所有楼的净变化是否都为0
  4. 更新最大可达成请求数

优化点：

  • 使用位运算快速计算子集
  • 提前终止：如果当前子集大小已经不可能超过已知最优解，可以跳过检查
  • 从大到小枚举子集大小，找到第一个可行解即为最优解

时间复杂度虽然是指数级别，但由于约束条件限制了规模，实际运行效率可以接受。

代码实现

class Solution {
public:
    int maximumRequests(int n, vector<vector<int>>& requests) {
        int m = requests.size();
        int maxRequests = 0;
        
        // 枚举所有可能的请求子集
        for (int mask = 0; mask < (1 << m); mask++) {
            // 统计每栋楼的净变化
            vector<int> balance(n, 0);
            int count = 0;
            
            for (int i = 0; i < m; i++) {
                if (mask & (1 << i)) {
                    balance[requests[i][0]]--; // 离开
                    balance[requests[i][1]]++; // 进入
                    count++;
                }
            }
            
            // 检查是否所有楼的净变化都为0
            bool valid = true;
            for (int i = 0; i < n; i++) {
                if (balance[i] != 0) {
                    valid = false;
                    break;
                }
            }
            
            if (valid) {
                maxRequests = max(maxRequests, count);
            }
        }
        
        return maxRequests;
    }
};

class Solution:
    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:
        m = len(requests)
        max_requests = 0
        
        # 枚举所有可能的请求子集
        for mask in range(1 << m):
            # 统计每栋楼的净变化
            balance = [0] * n
            count = 0
            
            for i in range(m):
                if mask & (1 << i):
                    balance[requests[i][0]] -= 1  # 离开
                    balance[requests[i][1]] += 1  # 进入
                    count += 1
            
            # 检查是否所有楼的净变化都为0
            if all(b == 0 for b in balance):
                max_requests = max(max_requests, count)
        
        return max_requests

public class Solution {
    public int MaximumRequests(int n, int[][] requests) {
        int m = requests.Length;
        int maxRequests = 0;
        
        // 枚举所有可能的请求子集
        for (int mask = 0; mask < (1 << m); mask++) {
            // 统计每栋楼的净变化
            int[] balance = new int[n];
            int count = 0;
            
            for (int i = 0; i < m; i++) {
                if ((mask & (1 << i)) != 0) {
                    balance[requests[i][0]]--; // 离开
                    balance[requests[i][1]]++; // 进入
                    count++;
                }
            }
            
            // 检查是否所有楼的净变化都为0
            bool valid = true;
            for (int i = 0; i < n; i++) {
                if (balance[i] != 0) {
                    valid = false;
                    break;
                }
            }
            
            if (valid) {
                maxRequests = Math.Max(maxRequests, count);
            }
        }
        
        return maxRequests;
    }
}

var maximumRequests = function(n, requests) {
    let maxRequests = 0;
    
    function backtrack(index, balance, count) {
        if (index === requests.length) {
            if (balance.every(b => b === 0)) {
                maxRequests = Math.max(maxRequests, count);
            }
            return;
        }
        
        // Skip current request
        backtrack(index + 1, balance, count);
        
        // Include current request
        const [from, to] = requests[index];
        balance[from]--;
        balance[to]++;
        backtrack(index + 1, balance, count + 1);
        balance[from]++;
        balance[to]--;
    }
    
    backtrack(0, new Array(n).fill(0), 0);
    return maxRequests;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(2^m × (m + n))，其中 m 是请求数量，n 是楼数。需要枚举 2^m 个子集，每个子集需要 O(m) 时间统计和 O(n) 时间验证
空间复杂度O(n)，用于存储每栋楼的净变化数组