【算法百题之二十二】20网易面试题-水平线研发

【算法百题之二十二】水平线研发

 

    大家好，我是Lampard~~

    很高兴又能和大家见面了，接下来准备系列更新的是算法题，一日一练，早日升仙！

 

   今天的问题是：

    由于远古的宇宙战争的原因，伞屉文明是一个二维世界里的文明，所以你可以这样理解发电基站的位置与他们的链接关系：给你一个一维数组a，长度为n，表示了n个基站的位置高度信息。数组的第i个元素a[i]表示第i个基站的海拔高度是a[i],而下标相邻的基站才相邻并且建立链接，即x号基站与x-1号基站、x+1号基站相邻。特别的，1号基站仅与2号相邻，而n号基站仅与n-1号基站相邻。当一场海拔高度为y的洪水到来时，海拔高度小于等于y的基站都会被认为需要停止发电，同时断开与相邻基站的链接。

   你作为伞屉国的洪水观察员，有着这样的任务：在洪水到来时，计算出发电集群被洪水淹没后被拆分成了多少个集群。

  

思路：

害！题目老长结果贼简单，就是要判断一个一维数组（发电机站）里面被海拔j分成了多少块。

所以第一步：判断一个数组里被海拔J分成了多少块：

int HowMany(int* array,int n, int Water)
{
	int num=0;

	for (int i = 0; i < n; i++)
	{
		int j = i;
		if (array[j] <= Water)
			continue;            // 如果发电机站比洪水小就不记录

		while (array[j] > Water)
		{
			j++;
		}

		num++;
		i = j;
	}

	return num;
}

第二步：用一个向量记录每一组数据的块数，，然后循环输出就可：

for (int i = 0; i < NumOfW; i++)
	{
		MyVector.push_back(HowMany(arrayE, NumOfE, arrayW[i]));
	}

	for (int i = 0; i < MyVector.size(); i++)
	{
		cout << MyVector[i] << endl;
	}

测试用例和结果：

 

OK，今天的博客就到这里，谢谢大家！！！