1给定一些线段，线段有起点和终点，求这些线段的覆盖长度，重复的部分只计算一次。
方法一：
首先说排序对于处理很多问题都是非常有效的，例如寻找兄弟单词等问题中，经过排序处理后，问题就明朗了很多；
线段覆盖长度也是这样，将线段排序后，然后扫描一遍就可以得到覆盖的长度。具体做法：排序时，先按线段的起始端点排序，如果始点相同则按照末端点排，然后从头扫描，寻找连续段；所谓连续段即下一条线段的始点不大于当前线段的末点就一直扫描，，直到找到断层的，计算当前长度，然后继续重复扫描直到最后，便得总长度。代码如下：
#include<iostream>using namespace std;/* 排序求线段覆盖长度 */#define MAXN 100 // 设线段数不超过100struct segment{int start;int end;}segArr[100];/* 计算线段覆盖长度 */int lenCount(segment * segArr, int size){int length = 0, start = 0, end = 0;for(int i = 0; i < size; ++i){start = segArr[i].start;end = segArr[i].end;while(end >= segArr[i+1].start){++i;end = segArr[i].end > end ? segArr[i].end : end;}length += (end – start);}return length;}/* 快排比较函数 */int cmp(const void * p, const void *q){if(((segment *)p)->start != ((segment *)q)->start){return ((segment *)p)->start – ((segment *)q)->start;}return ((segment *)p)->end – ((segment *)q)->end;}/* 测试线段 answer: 71 */int segTest[10][2] = {{5, 8},{10, 45},{0, 7},{2, 3}，{3, 9}，{13, 26}, {15, 38}, {50, 67},{39, 42},{70, 80}};void main(){for(int i = 0; i < 10; ++i)// 测试线段{segArr[i].start = segTest[i][0];segArr[i].end = segTest[i][1];}qsort(segArr,10,sizeof(segment),cmp);// 排序printf("length: %d\n",lenCount(segArr,10)); // 计算}
方法二：
线段树的经典应用就是求线段覆盖长度，线段树本身的数据结构很简单，关键在于怎么用，线段结构如何设计，查询、更新等操作如何具体问题具体处理。对于本题，在插入线段的时候，标记覆盖，之后统计总长度便可。代码如下：
#include<iostream>using namespace std;/* 线段树求线段覆盖长度 */#define BORDER 100 // 设线段端点坐标不超过100struct Node// 线段树{int left;int right;int isCover; // 标记是否被覆盖}segTree[4*BORDER];/* 构建线段树 根节点开始构建区间[lef,rig]的线段树*/void construct(int index, int lef, int rig){segTree[index].left = lef;segTree[index].right = rig;if(rig – 1 == lef)// 到单位1线段{segTree[index].isCover = 0;return;}int mid = (lef+rig) >> 1;construct((index<<1)+1, lef, mid);construct((index<<1)+2, mid, rig); // 非mid+1，线段覆盖[mid,mid+1]segTree[index].isCover = 0;}/* 插入线段[start,end]到线段树, 同时标记覆盖 */void insert(int index, int start, int end){if(segTree[index].isCover == 1)return; // 如已覆盖，没必要继续向下插if(segTree[index].left == start && segTree[index].right == end){segTree[index].isCover = 1;return;}int mid = (segTree[index].left + segTree[index].right) >> 1;if(end <= mid){insert((index<<1)+1, start, end);}else if(start >= mid){insert((index<<1)+2, start, end);}else{insert((index<<1)+1, start, mid);insert((index<<1)+2, mid, end);// 注：不是mid+1，线段覆盖，不能漏[mid,mid+1]}}/* 计算线段覆盖长度 */int Count(int index){if(segTree[index].isCover == 1){return segTree[index].right – segTree[index].left;}else if(segTree[index].right – segTree[index].left == 1){return 0;}return Count((index<<1)+1) + Count((index<<1)+2);}/* 测试线段 answer: 71 */int segment[10][2] = {{5, 8},{10, 45}，{0, 7},{2, 3}, {3, 9}，{13, 26}, {15, 38}, {50, 67},{39, 42},{70, 80}};void main(){construct(0,0,100);// 构建[0,100]线段树for(int i = 0; i < 10; ++i) // 插入测试线段{insert(0,segment[i][0],segment[i][1]);}printf("the cover length is %d\n", Count(0));}基于排序的方法，由于排序的缘故，复杂度为O(nlgn)；使用线段树时，因其查询和插入操作都可以在lgn的时间完成，故对于所有线段完成插入，最后查询长度，算法总的复杂度也是O(nlgn)级别。
2 旋转数组中查找某值的下标。二分查找。
3 问题描述：
则认为他们属于同一个朋友圈，
r = {{1 , 2} , {2 , 3} ,{4 , 5}}
最后请分析所写代码的时间、空间复杂度。评分会参考代码的正确性和效率。
使用并查集解决，代码如下：
//朋友圈问题#include <iostream>using namespace std;int set[10001];//带路径优化的并查集查找算法inline int find(int x){ int i,j,r; r = x; while(set[r] != r){r = set[r]; }i = x;while(i != r){j = set[i];set[i] = r;i = j;} return r; } //优化的并查集归并算法inline void merge(int x, int y){int t = find(x);int h = find(y);if(t < h) {set[h] = t; }else {set[t] = h; }}int friends(int n , int m , int r[][2]) {int i , count; //初始化并查集，各点为孤立点，分支数为nfor(i = 1 ; i <= n ; ++i){set[i] = i; }for(i = 0 ; i < m ; ++i) {merge(r[i][0] , r[i][1]); }for(i = 1 ; i <= n ; ++i){cout << set[i] <<" "; }count = 0;for(i = 1 ; i <= n ; ++i){if(set[i] == i){++count;}}return count; }void main(){int n=5;int m=3;int a[][2]={{1,2},{2,3},{4,5}};cout << friends(n,m,a) <<endl;}<strong></strong>并查集介绍参考：
版权声明：本文为博主原创文章，未经博主允许不得转载。
无做什么，记得为自己而做，那就毫无怨言。
