【leetcode_1601】【困难】maximum-number-of-achievable-transfer-requests / 最多可达成的换楼请求数目

URL

链接：https://leetcode-cn.com/problems/maximum-number-of-achievable-transfer-requests/

题目

分析

源码

#include <stdio.h> 
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>int maximum_requests(int n, int **requesets, int requeset_size, int *requeset_col_size){int * delta = (int *)malloc(sizeof(int) * n);  	// n栋楼int ans = 0, m = requeset_size;					// m个请求for (int  mask = 0; mask < (1 << m); ++mask){int cnt = __builtin_popcount(mask);  		// GCC 内建函数 统计mask中1的个数， 平台不通用，不一定可移植if( cnt <= ans){  							// 如果当前可响应的请求 <= 已经响应过的请求个数(现在楼层变化的数量) ，则判断下一个请求是否可行continue;}memset(delta, 0, sizeof(int) * n);   		// n栋楼的变化数量δ for (int i = 0; i < m; i++){				// 遍历m个请求if (mask & (1 << i)){					// 如果第i个请求被选中，则from楼增加的人数++，to楼的人数--++delta[requesets[i][0]];--delta[requesets[i][1]];}}bool flag = true;/* 遍历n栋楼的变化是否==0，不为0则表示响应后无法满足楼层变化相同的要求，也即无法响应这次请求 */for (int i = 0; i < n; ++i){if (delta[i] != 0){flag = false;break;}}/* 如果请求可被满足，则可响应请求数ans++ */if (flag){ans = cnt;}}return ans;
}int main()
{
#ifdef TEST_1int n = 5; int **requesets = (int **)malloc(sizeof(int *) * 6);int arr[6][2] = {{0,1},{1,0},{0,1},{1,2},{2,0},{3,4}};for (int i = 0; i < 6; i++){requesets[i] = (int *)malloc(sizeof(int) * 2);}for (int i = 0; i < 6; i++){for (int j = 0; j < 2; j++){requesets[i][j] = arr[i][j];}}int ret = maximum_requests(n, requesets, 6, NULL);printf("ret : 5 = %d ?\n",ret);for (int i = 0; i < 6; i++){free(requesets[i]);}free(requesets);return 0;
#elseint n = 3; int **requesets = (int **)malloc(sizeof(int *) * 6);int arr[3][2] = {{0,0},{1,2},{2,1}};for (int i = 0; i < 3; i++){requesets[i] = (int *)malloc(sizeof(int) * 2);}for (int i = 0; i < 3; i++){for (int j = 0; j < 2; j++){requesets[i][j] = arr[i][j];}}int ret = maximum_requests(n, requesets, 3, NULL);printf("ret : 3 = %d ?\n",ret);for (int i = 0; i < 3; i++){free(requesets[i]);}free(requesets);return 0;
#endif
}

源码概述

1. 请求m长的二进制数mask存储所有的请求个数，用bit位表示第i次请求。主要是m主要用于控制遍历响应次数
2. 用delta[楼层号]表示第i次请求后楼层的变化值，为0则表示这次请求后满足“每个楼转入数=转出数”
3. 遍历上述delta[]是否为0，可被满足则进入下一次请求，即mask下一bit+1，总共m个bit位

小结

1. 用到了一个GCC的内建函数__builtin_popcount(mask)，判断bit为1的个数。学习到了，用二进制表示请求个数，配合内建函数。
2. 一个delta[]表示响应每次请求后各个楼层变化数量，每次请求可调整两栋楼的变化数量，这也是注意点。