【leetcode_1601】【困难】maximum-number-of _请求

文章目录
URL题目
分析
源码
#include#include #include #include 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 (intmask = 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}
【【leetcode_1601】【困难】maximum-number-of】源码概述请求m长的二进制数mask存储所有的请求个数，用bit位表示第i次请求。主要是m主要用于控制遍历响应次数用delta[楼层号]表示第i次请求后楼层的变化值，为0则表示这次请求后满足“每个楼转入数=转出数”遍历上述delta[]是否为0 ，可被满足则进入下一次请求，即mask下一bit+1 ，总共m个bit位小结用到了一个GCC的内建函数(mask) ，判断bit为1的个数。学习到了，用二进制表示请求个数，配合内建函数。一个delta[]表示响应每次请求后各个楼层变化数量，每次请求可调整两栋楼的变化数量，这也是注意点。