第二周作业2

2019-11-06 07:43:58

字体：大中小

来源：转载

供稿：网友

1. 题目描述

Given n non-negative integers rePResenting an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. 这里写图片描述

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

2. 解决思路

按照高度一行一行的迭代计算容积。每一行的迭代方式是找到容积的开始边界，然后找结束边界，结束减开始就是中间的容积，然后另开始边界等于结束边界再去找下一个结束边界，直到每行结束，所有容积累加。最后把每行的容积加起来就是总容积

3. 完整代码

#include <stdio.h>#include <malloc.h>int factorial(int n); //求一个数的阶乘bool bS3Exist(int* s3[3], int len, int i1, int i2, int i3); //判断三元组是否重复，如果三个数完全一样则为重复int main(){ int* S = NULL; //存储数组 int len = 0; printf("请输入数组的长度：/n"); scanf("%d", &len); while (len<= 0) { printf("长度必须大于0，请重新输入：/n"); scanf("%d", &len); } S = (int*)malloc(sizeof(int) * len); //数组分配内存 printf("请输入数组的每一位数(必须是非负数)：/n"); for (int i = 0; i<len; ++i) { scanf("%d", &S[i]); } int max = S[0]; for (int i= 0; i<len; ++i) //求数组的最大值 { max = max > S[i] ? max : S[i]; } int start = 0; int end = -1; int* iSum = (int *)malloc( sizeof(int) * max); //存储每行的容量 for (int i=0; i<max; ++i){ iSum[i] = 0;} for (int j = 0; j< max; ++j) { bool bfindstart = false; bool bfindend = false; for (int i = 0; i< len; ++i) { if (S[i] >= j+1) { bfindstart = true; start = i; end = i; break; } } if (bfindstart) { for (int i = start+1; i<len; ++i) { if (S[i] >= j+1) { bfindend = true; end = i; iSum[j] += (end - start -1); start = end; } } } } int sum =0 ; for (int i = 0; i< max; ++i) { sum += iSum[i]; } //输出结果 printf("可以装水的总量为: %d/n", sum); scanf("%d", &len); //加个输入让窗口停下来 free(S); //释放内存 free(iSum); return 0;}int factorial(int n){ int sum = 1; if (1 == n) { return 1; } sum = n * factorial(n - 1); return sum;}bool bS3Exist(int* s3[3], int len, int i1, int i2, int i3){ for (int i = 0; i< len; ++i) { int a = s3[0][i]; int b = s3[1][i]; int c = s3[2][i]; if ((a == i1 && b == i2 && c == i3) || (a == i1 && b == i3 && c == i2) || (a == i2 && b == i1 && c == i3) || (a == i2 && b == i3 && c == i1) || (a == i3 && b == i1 && c == i2) || (a == i3 && b == i2 && c == i1)) { return true; } } return false;}

上一篇：297. Serialize and Deserialize Binary Tree

下一篇：空闲任务(Idle Task)和统计任务

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注