文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

我們有 n 棟樓，編號(hào)從 0 到 n - 1 。每棟樓有若干員工。由于現(xiàn)在是換樓的季節(jié)，部分員工想要換一棟樓居住。

給你一個(gè)數(shù)組 requests ，其中 requests[i] = [fromi, toi] ，表示一個(gè)員工請求從編號(hào)為 fromi 的樓搬到編號(hào)為 toi 的樓。

一開始 所有樓都是滿的，所以從請求列表中選出的若干個(gè)請求是可行的需要滿足 每棟樓員工凈變化為 0 。
意思是每棟樓 離開 的員工數(shù)目 等于 該樓 搬入 的員工數(shù)數(shù)目。
比方說 n = 3 且兩個(gè)員工要離開樓 0 ，一個(gè)員工要離開樓 1 ，一個(gè)員工要離開樓 2 ，如果該請求列表可行，應(yīng)該要有兩個(gè)員工搬入樓 0 ，一個(gè)員工搬入樓 1 ，一個(gè)員工搬入樓 2 。

請你從原請求列表中選出若干個(gè)請求，使得它們是一個(gè)可行的請求列表，并返回所有可行列表中最大請求數(shù)目。

示例 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 個(gè)請求。

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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-number-of-achievable-transfer-requests
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

數(shù)據(jù)規(guī)模比較小，直接暴力回溯，時(shí)間復(fù)雜度 $O(n?2^{req.length})$

class Solution {int max_satisfied = 0; public:int maximumRequests(int n, vector<vector<int>>& requests) {vector<int> count(n, 0);dfs(requests, count, 0, 0);return max_satisfied;}void dfs(vector<vector<int>>& requests, vector<int>& count, int idx, int satisfied){if(satisfied+requests.size()-idx <= max_satisfied)return;//剩余的假如都可以滿足，都不可能超過最大的，剪枝if(idx == requests.size()){for(int i = 0; i < count.size(); i++){if(count[i] != 0)return;}max_satisfied = max(max_satisfied, satisfied);return;}int from = requests[idx][0], to = requests[idx][1];count[from]--;count[to]++;dfs(requests, count, idx+1, satisfied+1);//選count[from]++;count[to]--;dfs(requests, count, idx+1, satisfied);//當(dāng)前不選} };

48 ms 8.8 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1601. 最多可达成的换楼请求数目（回溯+剪枝）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。