最多可达成的换楼请求数目

标签: 位运算 数组 回溯 枚举

难度: Hard

我们有 n 栋楼，编号从 0 到 n - 1 。每栋楼有若干员工。由于现在是换楼的季节，部分员工想要换一栋楼居住。

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

一开始 所有楼都是满的，所以从请求列表中选出的若干个请求是可行的需要满足 每栋楼员工净变化为 0 。意思是每栋楼 离开 的员工数目 等于 该楼 搬入 的员工数数目。比方说 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 交换他们的楼，以满足他们的请求。
我们可以让 y，a 和 z 三人在三栋楼间交换位置，满足他们的要求。
所以最多可以满足 5 个请求。

示例 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

Submission

运行时间: 48 ms

内存: 16.7 MB

class Solution:
    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:
        graph = defaultdict(list)
        N = len(requests)
        for i in range(N):
            f,t = requests[i]
            graph[f].append([t,i])

        MASK = 2**N - 1
        def find(mask,start,f,cnt):
            # print(bin(mask),start,f,cnt,graph[f])
            if f==start:
                return [(mask,cnt)]
            ret = []
            for t,i in graph[f]:
                if mask & (1<<i)>0:
                    
                    ret += find(mask^(1<<i),start,t,cnt+1)
            return ret 


        @cache
        def dfs(mask):
            if mask==0:
                return 0
            selectMask = mask&(-mask)
            i = int(log(selectMask,2))
            print(i)
            nmask = selectMask^mask
            f,t = requests[i]
            # use current i 
            candidates = find(nmask,f,t,1)
            ret = 0
            # print(i,bin(mask),candidates)
            for m,c in candidates:
                ret = max(dfs(m)+c,ret)
            # skip current i 
            ret = max(dfs(nmask),ret)
            return ret 
        return dfs(MASK)

Explain

这个题解使用了回溯（枚举所有可能的请求组合通过二进制掩码表示）结合深度优先搜索（DFS）来找到最多可以满足的请求。首先，创建一个图来表示每个楼栋的请求，即从某楼出发的目标楼和对应的请求索引。然后使用一个二进制掩码来表示所有的请求是否被选择（1代表被选择，0代表未被选择）。对于每个掩码，如果最低位为1，意味着当前请求被选择。根据这个请求，我们尝试寻找一个环路，使得从一个楼栋出发，最终可以回到原楼栋，并在此过程中满足其他的请求。使用DFS来递归地尝试所有可能的选择或不选择当前请求的情况，从而找到最大的可满足请求数。如果找到一个有效的环路，将其加入到结果中并继续尝试其他可能性。这个策略通过枚举所有子集和验证每个子集的合法性来尝试找到最优解。

时间复杂度: O(N*2^N)

空间复杂度: O(N + 2^N)

class Solution:
    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:
        graph = defaultdict(list)
        N = len(requests)
        for i in range(N):
            f, t = requests[i]
            graph[f].append([t, i])

        MASK = 2**N - 1
        def find(mask, start, f, cnt):
            if f == start:
                return [(mask, cnt)]
            ret = []
            for t, i in graph[f]:
                if mask & (1 << i) > 0:
                    ret += find(mask ^ (1 << i), start, t, cnt + 1)
            return ret 

        @cache
        def dfs(mask):
            if mask == 0:
                return 0
            selectMask = mask & (-mask)
            i = int(log(selectMask, 2))
            nmask = selectMask ^ mask
            f, t = requests[i]
            candidates = find(nmask, f, t, 1)
            ret = 0
            for m, c in candidates:
                ret = max(dfs(m) + c, ret)
            ret = max(dfs(nmask), ret)
            return ret 
        return dfs(MASK)

Explore

使用回溯和二进制掩码的方法虽然可行，但在请求的数量非常大时可能导致效率低下。这种方法的时间复杂度是指数级的，因为需要枚举所有可能的请求组合，这些组合的总数是2的N次幂（N是请求的数量）。当N较大时，比如超过20，计算量会非常巨大，导致运行时间非常长。因此，这种方法适用于请求数量较少的情况。

DFS在这里用于寻找是否存在一个合法的路径，即从一个楼栋出发，经过一系列的请求后，可以返回到原始的楼栋。这样的路径形成了一个闭环，确保了在这个环路中，每个楼栋的员工数量的净变化为0（即每个楼栋移出的员工数量等于移入的员工数量）。通过递归地探索所有可能的请求组合，并验证这些组合能否形成闭环，DFS帮助确保了每个楼栋的员工净变化为0。

`find`函数的目的是寻找从某个楼栋出发，经过一系列请求后，能够返回到原始楼栋的环路。这个环路是由请求组成的，其中每个请求代表从一个楼栋移动到另一个楼栋的员工。当我们找到这样的环路时，就表明这组请求是合法的，因为它保证了所有涉及的楼栋在完成所有请求后，员工数量保持不变（即每个楼栋的员工净输入和输出相等）。这样的验证是必要的，因为只有当所有相关的请求都能形成闭环，这些请求才是可行的，从而确保了总请求的最大化可以在合法的条件下实现。

在二进制数中，`mask & (-mask)`的操作用于快速找到最低位的1，这是因为`-mask`是`mask`的二进制补码表示形式。该操作的结果是一个只含有最低位1的数，其他位均为0。这种方法用于确定在遍历子集或请求组合时，哪个请求是当前考虑的第一个请求。此技术是基于位运算的效率高的特性，可以快速地在回溯算法中进行选择和剔除，帮助减少不必要的计算和简化逻辑处理。