阿里巴巴的网站二维码怎么做,2023最建议买10款手机,c2c电子商务网站策划,创意设计pc文章目录 思路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]是一个指向一维数组的一级指针所以需要取地址。
