沈阳网站建设搜q479185700,深圳网站建设兼职,涉县网站,网站建设 讲话文章目录 思路AC CODE总结 题目链接#xff1a;2580. 统计将重叠区间合并成组的方案数 思路
一个区间合并的板子#xff0c;计算出区间数目之后#xff0c;每个区间都有放左和放右两种选法#xff0c;所以最后的答案就是 2 k 2^k 2k。但是需要用c进行二维数组的排序2580. 统计将重叠区间合并成组的方案数 思路
一个区间合并的板子计算出区间数目之后每个区间都有放左和放右两种选法所以最后的答案就是 2 k 2^k 2k。但是需要用c进行二维数组的排序我不会qsort()就写了一个数组的快排然后用了快速幂计算答案。 AC CODE
void cmp(int **i, int **j){int *tmp *i;*i *j;*j tmp;
}void quick_sort(int **q, int l, int r){if(l r) return;int i l - 1, j r 1, x q[(l r) 1][0];while(i j){do i; while(q[i][0] x);do j--; while(q[j][0] x);if(i j) cmp(q[i], q[j]);}quick_sort(q, l, j); quick_sort(q, j 1, r);
}long long qmi(long long a, long long b, int mod){long long res 1 % mod;while(b){if(b 1) res (res * a) % mod;a a * a % mod;b 1;}return res;
}int countWays(int** ranges, int rangesSize, int* rangesColSize) {const int mod 1e9 7;int st -1, ed -1;long long res 0;quick_sort(ranges, 0, rangesSize - 1);for(int i 0; i rangesSize; i){int seg ranges[i][0];if(seg ed) ed fmax(ed, ranges[i][1]);else{res;st seg;ed ranges[i][1];}}res qmi(2, res, mod);return res % mod;
}总结
交换一维数组时用了取二维地址然后交换跟交换变量一个道理。q[i]是一个指向一维数组的一级指针所以需要取地址。
