題目描述

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

給你一個(gè)數(shù)組 requests?，其中?requests[i] = [fromi, toi]?，表示一個(gè)員工請求從編號為?fromi?的樓搬到編號為?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ù)目。

樣例

輸入：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è)請求。

輸入：n = 3, requests = [[0,0],[1,2],[2,1]]

輸出：3

解釋：請求列表如下：

從樓 0 離開的員工為 x ，且他想要回到原來的樓 0 。

從樓 1 離開的員工為 y ，且他想要搬到樓 2 。

從樓 2 離開的員工為 z ，且他想要搬到樓 1 。

我們可以滿足所有的請求。

輸入：n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]

輸出：4

算法分析

模擬 + 位運(yùn)算

1、題目說到：從請求列表中選出的若干個(gè)請求是可行的需要滿足 每棟樓員工凈變化為 0?，在滿足某些部分人請求的情況下，一定會使得每棟樓 離開?的員工數(shù)目 等于?該樓 搬入?的員工數(shù)數(shù)目

2、先看數(shù)據(jù)范圍，最多只有16個(gè)請求，其中每個(gè)請求有允許 和 不允許兩個(gè)狀態(tài)，因此總的情況最多是2^16種

3、枚舉所有請求允許和不允許的所有情況，當(dāng)枚舉到第i種狀態(tài)時(shí)，第j位是1表示，表示第j個(gè)條件滿足。其中cnt表示i狀態(tài)有多少個(gè)1，并且記錄每棟樓進(jìn)入in的所有人數(shù)，和出去out的所有人數(shù)，但每棟樓k都滿足in[k] == out[k]時(shí)，則表示當(dāng)前狀態(tài)i滿足題意，用cnt更新ans

時(shí)間復(fù)雜度 $O(2^m * max(n, m))$

Java 代碼

class Solution {

public int maximumRequests(int n, int[][] requests) {

int m = requests.length;

int[] out = new int[n];//記錄每棟樓出去多少人

int[] in = new int[n];//記錄每棟樓進(jìn)來多少人

int ans = 0;

for(int i = 0;i < 1 << m;i ++)

{

Arrays.fill(out, 0);

Arrays.fill(in, 0);

int cnt = 0;

for(int j = 0;j < m;j ++)

{

if((i >> j & 1) == 1)

{

cnt ++;

out[requests[j][0]] ++;

in[requests[j][1]] ++;

}

}

boolean flag = true;

for(int j = 0;j < n;j ++)

{

if(out[j] != 0 && out[j] != in[j])

{

flag = false;

break;

}

}

if(flag) ans = Math.max(ans, cnt);

}

return ans;

}

}

總結(jié)

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

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