鞍山手机网站建设,网站建设的服务器,wordpress安卓客户端,网站开发和合同题目描述 题目分析#xff1a; x轴向上射箭#xff0c;12一支#xff0c;重叠的需要一支#xff0c;3-8一支#xff0c;7-16一支 返回2#xff1b; 就是让重叠的气球尽量在一起#xff0c;局部最优#xff1b;用一支弓箭#xff0c;全局最优就是最少弓箭#xff1b…题目描述 题目分析 x轴向上射箭12一支重叠的需要一支3-8一支7-16一支 返回2 就是让重叠的气球尽量在一起局部最优用一支弓箭全局最优就是最少弓箭 如何去寻找重叠的气球和记录弓箭数 1.对所有气球排序左边界排序如上图 2. if 如果第i个气球的左边界大于第i-1个气球的右边界即point[i][0] point[i-1][1] 比如上图中3 6 的左边界3大于右边界1 2 的右边界2那么弓箭数 3.else 就是重叠 右边界取最小值 如图36 48重叠右边界取6 8 的最小值6作为重叠的右边界 else 逻辑: a: 更新右边界points[i][1] min(points[i-1][1] ,points[i][1] ); b:拿这个右边界和下一个气球比较
int cmp(const void *a, const void *b)
{int *x *(int **)a;int *y *(int **)b;if (x[0] y[0]) {return x[1] y[1];}return x[0] y[0];
}int findMinArrowShots(int** points, int pointsSize, int* pointsColSize){//将points数组作升序排序qsort(points, pointsSize, sizeof(points[0]),cmp);int arrowNum 1;int i 1;for(i 1; i pointsSize; i) {//若前一个气球与当前气球不重叠证明需要增加箭的数量if(points[i][0] points[i-1][1])arrowNum;else//若前一个气球与当前气球重叠判断并更新最小的x_endpoints[i][1] fmin(points[i-1][1] ,points[i][1] );}return arrowNum;
}题目描述 分析 左边界排序 if nums[i][0] nums[i-1][1] i的左边界大于i-1的右边界表示没有重叠 else 重叠 cnt 右边界也是取最小值和上一题一样 nums[i][1] min(nums[i-1][1],nums[i][1]);
代码一
int cmp(const void *a, const void *b)
{int *x *(int **)a;int *y *(int **)b;if (x[0] y[0]) {return x[1] y[1];}return x[0] y[0];
}int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize){// 贪心算法if (intervalsSize 0) {return 0;}// end递增排序qsort(intervals, intervalsSize, sizeof(int *),cmp);int count 0;for (int i 1; i intervalsSize; i) { // i 和 i-1if (intervals[i][0] intervals[i-1][1]) {//重叠count;//后面区间和当前区间是否重叠 更新右边界intervals[i][1] fmin(intervals[i][1], intervals[i-1][1]);}}// 返回重复区间数return count;
}代码二
int cmp(const void *pa, const void *pb)
{return (*(int**)pa)[1] - (*(int**)pb)[1];
}int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize){// 贪心算法if (intervalsSize 0) {return 0;}// end递增排序qsort(intervals, intervalsSize, sizeof(int*), cmp);int x_end intervals[0][1];int start;int count 1;for (int i 1; i intervalsSize; i) {start intervals[i][0];if (start x_end) {// 不相交count;// 更新不重复区间endx_end intervals[i][1];}}// 返回重复区间数return intervalsSize - count;
}
