贪心算法(7)

贪心算法(7)贪心算法练习记录:leetcode 452 https://leetcode-cn.

欢迎大家来到IT世界,在知识的湖畔探索吧!

贪心算法练习记录:

leetcode 452 https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/

题目描述:

用最少数量的箭引爆气球,一个区间代表一个气球,现有一个区间集合(二维数组),如果要戳破这些气球最少需要多少箭呢?(箭只能朝着一个方向前进)

思路:

和前面记录的贪心算法(5)一样对二维数组排序(按照区间起始值大小顺序排序),排序完成后只要有区间重叠的用一根箭就可以引爆气球,维护一个左右值表示区间的重叠区间,循环遍历各个区间(二维数组中的一维数组),只要不重叠计数加一得到最少得箭。(如果每次循环时如果判断当前区间的起始值与重叠区间的右值的情况,只需要维护一个右值就行)。

代码实现:

贪心算法(7)

C语言代码实现

#include<stdio.h>
#include<stdlib.h>
int comp(const void* a, const void* b)
{
	int *m = *(int **)a;
	int *n = *(int **)b;
	return m[0] < n[0] ? -1 : 1;   
	// if ((*(int**)a)[0] < (*(int**)b)[0])
	//  { return -1; }
	// return 1;
}
 int findMinArrowShots( int** points,  int pointsSize,  int* pointsColSize)
{
	if (pointsSize == 1)
	{
		return 1;
	}
	qsort(points, pointsSize, sizeof(points[0]), comp);
	 int  i=1,count = 1;
	bool flag = false; 
	 int start = points[0][1];
	while(i<pointsSize-1   )
	{
	 if(points[i][0]>start) 
		{
			start = points[i][1];
			count++;
			i++;
		}
	 else  if (points[i][0] <start)
	 {	
		 if(points[i][1]<start || points[i][0] == start)
		 {
			 start = points[i][1];
		 }
		 i++;
	 }
	}
	if (points[pointsSize-1][0]>start )
	{
		count++;
	}
	return count;
}
 int main()
{
	 int row =8;
	 int ** a = ( int**)malloc(sizeof( int*)*row);
	for ( int i = 0;i<row;i++)
	{
		( int *)a[i] = ( int*)malloc(sizeof( int)*2);
	}
	a[0][0] = 4; a[0][1] = 12;
	a[1][0] = 7; a[1][1] = 8;
	a[2][0] = 7; a[2][1] = 9;
	a[3][0] = 7; a[3][1] = 9;
	a[4][0] = 2; a[4][1] = 8;
	a[5][0] = 6; a[5][1] = 7;
	a[6][0] = 5; a[6][1] = 14;
	a[7][0] = 4; a[7][1] = 13;
	 int result = findMinArrowShots(a,row,( int*)2);
	printf("%d" ,result);
	for ( int i = 0; i<row; i++)
	{
		free(a[i]);
	}
	free(a);
}

欢迎大家来到IT世界,在知识的湖畔探索吧!

采坑点:

区间可以是负数,负数减去正数就溢出了,所以使用qsort函数时应用如下方式:

欢迎大家来到IT世界,在知识的湖畔探索吧!	int *m = *(int **)a;
	int *n = *(int **)b;
	return m[0] < n[0] ? -1 : 1;   
	// if ((*(int**)a)[0] < (*(int**)b)[0])
	//  { return -1; }
	// return 1;

使用以下方式会出错:


	if ((*(int**)a)[0] == (*(int**)b)[0])
	return (*(int**)a)[1] - (*(int**)b)[1];//此处则表示先按第一项排序,第一项相同的情况下按第二项
return  (*(int**)a)[0] - (*(int**)b)[0];

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/49432.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们YX

mu99908888

在线咨询: 微信交谈

邮件:itzsgw@126.com

工作时间:时刻准备着!

关注微信