-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathtrappingRainWater.cc
More file actions
110 lines (102 loc) · 2.42 KB
/
trappingRainWater.cc
File metadata and controls
110 lines (102 loc) · 2.42 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/*
* trappingRainWater.cc
*
* Created on: May 28, 2013
* Author: Xin
* http://leetcode.com/onlinejudge#question_42
*/
#include <iostream>
#include "assert.h"
using namespace std;
class Solution
{
public:
bool haveMiddleHigherPoint(const int elevation[], size_t range_begin,
size_t range_end, size_t& index, int& value)
{
int boundary_value = min(elevation[range_begin], elevation[range_end]);
value = 0;
bool result = false;
for (size_t i = range_begin + 1; i < range_end; i++)
{
if (elevation[i] > boundary_value)
{
result = true;
if (elevation[i] > value)
{
value = elevation[i];
index = i;
}
}
}
return result;
}
int water_amount(int elevation[], size_t range_begin, size_t range_end)
{
size_t middle_high_index;
int middle_high_value;
if (haveMiddleHigherPoint(elevation, range_begin, range_end,
middle_high_index, middle_high_value))
{
return water_amount(elevation, range_begin, middle_high_index)
+ water_amount(elevation, middle_high_index, range_end);
}
else
{
int high_value = min(elevation[range_begin], elevation[range_end]);
int mount = 0;
for (size_t i = range_begin; i <= range_end; i++)
{
if (elevation[i] < high_value)
{
mount += high_value - elevation[i];
}
}
return mount;
}
}
int trap(int A[], int n)
{
if (n>0)
return water_amount(A, 0, n - 1);
else
return water_amount(A, 0, 0);
}
};
/*
*
input output expected
[] 0
[0] 0
[1] 0
[0,2,0] 0
[2,0,2] 2
[4,2,3] 1
[2,1,0,2] 3
[5,4,1,2] 1
[4,2,0,3,2,5] 9
[4,2,0,3,2,4,3,4] 10
[5,5,1,7,1,1,5,2,7,6] 23
[0,1,0,2,1,0,1,3,2,1,2,1] 6
[6,4,2,0,3,2,0,3,1,4,5,3,2,7,5,3,0,1,2,1,3,4,6,8,1,3] 83
* */
int main()
{
Solution s1;
struct test
{
int l;
int expect;
int a[256];
};
struct test cases[] =
{
{12 , 6, {0,1,0,2, 1,0,1,3, 2,1,2,1}}, //0
{0,0,{1}},//1
{1,0,{1}},//2
{1,0,{1}},//3
{27,83,{6,4,2,0, 3,2,0,3, 1,4,5,3, 2,7,5,3, 0,1,2,1, 3,4,6,8, 1,3}}//4
};
for(int i=0;i<5;i++)
assert(s1.trap(cases[i].a, cases[i].l)==cases[i].expect);
}