力扣 1601. 最多可达成的换楼请求数目

最新推荐文章于 2025-05-29 23:21:11 发布

三更鬼

最新推荐文章于 2025-05-29 23:21:11 发布

阅读量232

点赞数

分类专栏： DFS 文章标签： leetcode 深度优先

本文链接：https://blog.csdn.net/csdn_muxin/article/details/123177471

版权

DFS 专栏收录该内容

28 篇文章

订阅专栏

这篇博客介绍了一种利用深度优先搜索（DFS）策略来解决LeetCode上的一个问题，即在保持每栋楼人数不变的情况下，确定最多能实现多少个人的搬家请求。博主通过创建一个表示楼层数量变化的数组d，并使用回溯方法遍历所有可能的请求组合，以找到满足条件的最大请求数量。在遍历过程中，博主通过维护一个标记变量zero来跟踪没有变化的楼层数量，以此来判断是否满足题目要求。最终，通过比较每次搜索的结果，得出可以满足的最大请求数。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目来源：https://leetcode-cn.com/problems/maximum-number-of-achievable-transfer-requests/

大致题意：
给一个整数 n，表示有 n 栋楼，然后给一个二维数组 requests 表示请求，其中每个一维数组表示有一个人想从 requests[i][0] 对应的楼搬到 requests[i][1] 对应的楼。
求出在保证最终每栋楼人数不变的情况下，最多可以满足多少个请求

思路

可以用一个数组 d 表示每栋楼的人数变化情况，然后使用 dfs 遍历请求，遍历时，记录满足的请求个数。若请求遍历结束时，数组 d 的所有值都为 0，那么更新满足请求的最大值。

dfs + 回溯

使用 dfs 遍历请求
每遍历到一个请求，可以选择满足或者不满足
当遍历结束后，根据数组 d 的所有值是否为 0，决定是否更新结果

具体实现时，可以使用一个标记 zero 表示数组 d 中值为 0 的元素个数，那么对于请求 requests[i]，设 requests[i][0] 为 x，requests[i][1] 为 y

若 d[x] 之前为 0，那么 zero 的值减 1。然后将 d[x] 减 1，若 d[x] 减 1 后为 0，那么 zero 值加 1
若 d[y] 之前为 0，那么 zero 的值减 1。然后将 d[y] 加 1，若 d[y] 加 1 后为 0，那么 zero 值加 1

代码：

public class MaximumRequests {
    int n, zero, count, ans;
    int[] d;

    public int maximumRequests(int n, int[][] requests) {
        // 初始化
        d = new int[n]; // 每栋楼人数变化对应的数组
        this.n = n; // 楼的总数
        zero = n;   // 标记没有变化的楼的个数
        ans = 0;    // 可以满足的最大请求数
        count = 0;  // 每次搜索时已经满足的请求数
        // 开始 dfs
        dfs(requests, 0);
        return ans;
    }

    public void dfs(int[][] requests, int pos) {
        // 若请求遍历结束，根据 zero 的情况决定是否更新结果
        if (pos == requests.length) {
            if (zero == n) {
                ans = Math.max(ans, count);
            }
            return;
        }
        // 不满足当前位置的请求，直接跳过
        dfs(requests, pos + 1);
        
        // 若满足当前位置请求，需要更新当前的状态
        int temp = zero;
        int x = requests[pos][0];
        int y = requests[pos][1];
        zero -= d[x] == 0 ? 1 : 0;
        d[x]--;
        zero += d[x] == 0 ? 1 : 0;
        zero -= d[y] == 0 ? 1 : 0;
        d[y]++;
        zero += d[y] == 0 ? 1 : 0;
        count++;    // 满足的请求个数 +1
        // 满足当前位置请求，搜索下一个位置
        dfs(requests, pos + 1);
        
        // 回溯
        d[x]++;
        d[y]--;
        zero = temp;
        count--;
    }
}