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

题目链接

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

题解思路

状态压缩，根据数据范围可以得出，假设请求长度为m，就是有m个请求，那么就有 1 << m种情况

直接遍历每种情况，求出最大符合条件的情况

代码

python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:
        m = len(requests)
        res = 0
        def GetCnt(x):
            s = 0
            while x:
                if x & 1:
                    s += 1
                x = x >> 1
            return s
        def check(x: int) -> bool:
            cnt = [0] * n
            for i in range(m):
                if (x >> i) & 1:
                    a = requests[i][0]
                    b = requests[i][1]
                    cnt[a] = cnt[a] - 1
                    cnt[b] = cnt[b] + 1
            for i in cnt:
                if i:return False
            return True
        for i in range((1 << m)):
            x = GetCnt(i)
            if x <= res:
                continue
            if check(i): 
                res = x
        return res

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    int n, m;
    int [][] rs;
    public int maximumRequests(int n, int[][] requests) {
        this.n = n;
        rs = requests;
        m = rs.length;
        int res = 0;
        for(int i = 0; i < (1 << m); i++){
            int x = GetCnt(i);		//查看二进制有多少位1
            if(x <= res)continue;
            if(check(i))res = x;	//检查是否合法
        }
        return res;
    }
    public int GetCnt(int x){
        int s = 0;
        for(int i = x; i > 0; i -= (i & -i)) s++;	//i & -i是代表从右往左数第一个为 1 的位的权值。
        return s;
    }
    public boolean check(int x){
        int[] cnt = new int[n];
        for(int i = 0; i < m; i++){
            if(((x >> i) & 1) == 1){	//第i位是1
                int a = rs[i][0], b = rs[i][1];
                cnt[a] --;
                cnt[b] ++;
            }
        }
        for(int i = 0; i < n; i++)if(cnt[i] != 0)return false;
        return true;
    }
}

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    vector<vector<int>> rs;
    int n;
public:
    int GetCnt(int x){
        int s = 0;
        for(int i = x; i > 0; i -= (i & -i)){      //i & -i是代表从右往左数第一个为 1 的位的权值。
            s ++;
        }
        return s;
    }
    bool check(int x){
        vector<int> cnt(n);
        for(int i = 0; i < rs.size(); i++){
            if(((x >> i) & 1) == 1){    //第i位是1
                int a = rs[i][0], b = rs[i][1];
                cnt[a]--;
                cnt[b]++;
            }
        }
        for(int i = 0; i < n; i++){
            if(cnt[i] != 0)return false;
        }
        return true;
    }
    int maximumRequests(int n, vector<vector<int>>& requests) {
        rs = requests;
        this->n = n;
        int m = rs.size();
        int res = 0;
        for(int i = 0; i < (1 << m); i++){
            int x = GetCnt(i);          //查看二进制有多少位1
            //cout << x << endl;
            if(x <= res)continue;       //如果位数小于之前的位数就直接跳过
            if(check(i))res = x;        //检查是否合法
        }
        return res;
    }
};