【贪心算法初级训练】在花坛上是否能种下n朵花、碰撞后剩余的行星

本文主要是介绍【贪心算法初级训练】在花坛上是否能种下n朵花、碰撞后剩余的行星，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、在花坛上是否能种下n多花

一个很长的花坛，一部分地已经种植了花，另一部分却没有，花不能种植在相邻的地块上否则它们会争夺水源，两者都会死去。给你一个整数数组表示花坛，由若干个0和1组成，0表示没种植花；1表示种植了花。

给定一个数n，请设计一个算法验证在该花坛上能不能种下n朵花？

仅需判断要种花的位置，和它的左位置，右位置已经有花的情况，再下来就是要注意访问数组时索引的范围要在数组范围内。

class Solution
{
public:bool canPlantFlower(int* a, int size, int n){int i = 0;int count = 0;while(i < size){if (i - 1 > 0 && 1 == a[i - 1])//先判断要种花位置的左边有花的情况i += 1;else if (1 == a[i])//判断要种花的位置有花的情况i += 2;else if (i + 1 < size && 1 == a[i + 1])//判断要种花的位置右边有花的情况i += 3;else{a[i++] = 1;count++;if (n == count)return true;}}return false;}
};

2、碰撞后剩余的行星

给定一个整数数组，表示在同一行的行星。每一个元素的绝对值表示行星的大小，正负号表示行星的移动方向，正表示向右移动；负表示向左移动，每一颗行星以相同的速度移动。

行星碰撞规则：

1.两行星碰撞，较小的行星会爆炸。

2.如果大小相同，则两行星都爆炸。

3.两颗移动方向相同的行星，永远不会发生碰撞。

请设计一个算法，表示出最后剩余的行星。

对于这道题我的思路是：

1.首先我们先从数组的0位置开始对数组元素进行两两判断，只判断行星爆炸的情况，将爆炸的行星值改为0，第一遍将数组遍历完后，此时还没有结束！数组还剩下没有发生爆炸的行星。

2.遍历数组将没有发生爆炸的行星(即值!=0的行星)的值从头覆盖原数组的值（这里并没有创建新数组，只是对旧数组进行覆盖），覆盖后的数组里的值就是没有发生爆炸的行星，然后重复该过程，创建一个count变量用来作为循环终止判断。

class Solution
{
public:vector<int> existPlanet(int* array, int n){int newn = n;//newn没有爆炸行星的个数int ni = 0;int count = 1;while (count > 0){count = 0;ni = 0;int i = 0;while (i + 1 < newn){if (array[i] > 0 && array[i + 1] < 0)//接下来只需要考虑两颗行星碰撞的情况{if ( array[i] + array[i + 1] < 0)//左行星爆炸{array[i++] = 0;count++;}else if (array[i] + array[i + 1] > 0)//右行星爆炸{array[i + 1] = 0;i++;count++;}else if (0 == array[i] + array[i + 1])//两颗行星都爆炸{array[i] = array[i + 1] = 0;i++;count++;}}elsei++;}for (int j = 0;j < newn;j++){if (array[j])array[ni++] = array[j];}newn = ni;}vector<int> v;for (int j = 0;j < newn;j++){if (array[j])v.push_back(array[j]);}return v;}
};