題目

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

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

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

請你從原請求列表中選出若干個請求，使得它們是一個可行的請求列表，并返回所有可行列表中最大請求數(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 個請求。
示例 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

題解

class Solution {private int max = 0;private int[][] requests;private int[] buildings;private int cnt = 0;public int maximumRequests(int n, int[][] requests) {buildings = new int[n];this.requests = requests;dfs(0);return max;}private void dfs(int i) {if (check()) {max = Math.max(cnt,max);}if (i == requests.length) {return;}for (int j = i; j < requests.length; j++) {buildings[requests[j][0]]--;buildings[requests[j][1]]++;cnt++;dfs(j+1);//返回操作buildings[requests[j][0]]++;buildings[requests[j][1]]--;cnt--;}}//判斷是否分配合理private boolean check() {for (int i : buildings) {if (i != 0) {return false;}}return true;}
}