贪心算法初步学习

文章目录

• • 概述
  • 海盗船
  • 种花问题
  • 小行星碰撞

概述

每一步都根据当前的信息做出选择，一担选择，都不会改变（不会反悔）
用局部的最优解，达到整体的最优解

海盗船

海盗船
实际问题：一群海盗截获了一艘装满各种金银珠宝和古董的货船，每一件宝物都价值连城一旦打碎就失去了价值。海盗船的载重量为C，每件宝物的重量为Wi，海盗们应该如何把尽可能多的宝物装上船？

分析，每次选最小的

int main()
{
	int arr[10] = { 2,34,6,67,33,47,56,567,1,4 };
	heapsort(arr, 10);
	int max = 207;
	int n = 0, sum = 0;
	for (int i = 0; i < 10; i++)
	{
		if (sum > max)
		{
			break;
		}
		sum += arr[i];
		n++;
	}
	printf("%d ", n);
	return 0;
}

种花问题

假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n
朵花？能则返回True，不能则返回False。

注意:

1、数组内已种好的花不会违反种植规则。 2、输入的数组长度范围为 [1, 20000]。 3、n 是非负整数，且不会超过输入数组的大小。

```c

int main()
{
	int arr[5] = { 1,0,0,0,1 };
	int n = 1;
	int i = 0;
	int count = 0;
	for (i = 0; i < 5; )
	{
		if (arr[i] == 1)//遇到花就跳两格
		{
			i += 2;
		}
		else if (arr[i - 1] == 1 && i > 0)//不是花，但是他前面有花且不是第一个，跳1格
		{
			i += 1;
		}
		else if (arr[i + 1] == 1 && i+1<5)//不是花，但他后面有花，且不是最后一个，跳3格
		{
			i += 3;
		}
		else//前后都没花
		{
			arr[i] = 1;
			i += 2;//跳两格
			count++;
			if (count == n)
			{
				printf("yes");
			}
		}

	}
	return 0;
}

小行星碰撞

给定一个整数数组 asteroids，表示在同一行的小行星。

对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。

找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

示例 1：

输入：asteroids = [5,10,-5] 输出：[5,10] 解释：10 和 -5 碰撞后只剩下 10 。 5 和 10
永远不会发生碰撞。

示例 2：

输入：asteroids = [8,-8] 输出：[] 解释：8 和 -8 碰撞后，两者都发生爆炸。

示例 3：

输入：asteroids = [10,2,-5] 输出：[10] 解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下
10 。

示例 4：

输入：asteroids = [-2,-1,1,2] 输出：[-2,-1,1,2] 解释：-2 和 -1 向左移动，而 1 和 2
向右移动。 由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。

提示：

2 <= asteroids.length <= 104
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
//正数往右走，负数往左走
#include<math.h>
int* asteroidCollision(int* asteroids, int asteroidsSize, int* returnSize)
{
	int n = 0;
	while (1)
	{
		int prev = 0;
		int next = 1;
		//每次都重左到右扫描一遍
		while (next < asteroidsSize)// 每次只消一个,这个循环是把所有的都消掉,能够保证两者除0外都挨着
		{
			if (asteroids[prev] * asteroids[next] < 0)
			{
				//1.背靠背不能碰撞
				//如-9 8 32 9
				//如-9 0 8 9//我们不能够让前后都往后走一步，因为0是有隐患的，我们不走0
				//prev          next
				//          prev        next
				//-9     0      8      9
				if (asteroids[prev] < 0)//前面的往前走，后面的往后走就不符合
				{
					prev = next;
					next++;
				//背靠背不能再碰了，就进入下一个循环
					continue;
				}
				//发生了碰撞,左边大
				if (abs(asteroids[prev]) > abs(asteroids[next]))
				{
					asteroids[next]=0;
					n++;
				}
				if (abs(asteroids[prev]) < abs(asteroids[next]))
				{
					asteroids[prev] = 0;
					n++;
				}
				if (abs(asteroids[prev]) == abs(asteroids[next]))
				{
					asteroids[next] = 0;
					asteroids[prev] = 0;
					n+=2;
				}
				break;//贪心不贪婪
			}

			//如果前后相乘为0
			//0  3,左边的等于0
			if (asteroids[prev] == 0)
			{
				prev = next;
				next++;
			}
			//如果前后相乘为0
			//3  0,右边的等于0
			if (asteroids[next] == 0)//左边不动
			{
				next++;
			}
			else
			{
				//prev  next
				//7 0 0 4 -2
				//方向相同,就前进一步
				prev = next;//要跨过0

				next++;
			}
		}
		//出来了，next就大于size了
		if (next > asteroidsSize)
		{
			break;
		}
		
		
	}
	*returnSize = asteroidsSize - n;//返回剩余的
	int *ret = (int *)malloc(sizeof(int)*(asteroidsSize - n));
	int i,j=0;
	for (i = 0; i < asteroidsSize; i++)
	{
		if (asteroids[i])
		{
			ret[j++] = asteroids[i];
		}
	}
	return ret;
}