注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex42 Trapping Rain Water  

2015-05-18 21:46:13|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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.

ex42 Trapping Rain Water - HT - HT·生活


这个题需要理清思路,从左边开始确定一个ps,然后开始找到一个pe比ps大或者的等于的,然后求这个区域可以装的水。接着ps = pe+1,接着找pe。但是可能pe到了最大值之后可能循环不下去了,这个时候可以在循环的时候把最大值右边的最大值给找出来,一次把结果加上去。或者扫描两次,左边一次,右边一次。

/*
* 这题还有一个思路,里面循环到了ps是峰值的时候就找不到比他小的了
* 这个时候再让程序逆向扫一遍,最后结果加起来就行了
*/
int trap(int* height, int heightSize) {

if (heightSize <= 1)
{
return 0;
}
int ps, pe;
int result = 0;
int i, j;
int min = 0,start,end;


ps = 0;
pe = 1;
int te = 0, tmp = 0;

bool mark = false; //mark表示进入了找右边比当前大值的循环
while (ps < heightSize&&pe < heightSize)
{
mark = false;
while (pe<heightSize&&height[pe] < height[ps])
{
if (!mark)
{
mark = true;
tmp = height[pe]; //条语句用于记录当前值右边第一个值的index和 大小
te = pe;
}
else
{
if (height[pe] > tmp)
{
// 再次循环的时候,把倒数第二大的找到
te = pe;
tmp = height[pe];
}
}
pe++;
}
if (pe == heightSize)
{
//没有找到比height[ps]大的,那就找倒数第二大的
ps++; //ps后移挪一位,因为当前的pe没有用了
pe = te;

start = ps;
end = pe-1; //这个地方的end可以包括pe,也可以不用pe,因为pe就是标准值
min = height[pe]; //倒数第二大的是标准值
//测试这个分支 需要用的测试集合 是nums={4,2,3};
}
else
{
start = ps;
end = pe - 1;
min = height[ps]; //当前ps是标准值,因为找到了比他大的值
}

//结果累计
for (i = start; i <= end; i++)
{
result += min - height[i];
}
ps = pe;
pe++;


//下面的代码可以替换上面的if语句,上面的条件更加精简一些
//if (pe == heightSize)
//{
// //没有找到比height[ps]大的,那就找倒数第二大的
// ps++; //ps后移挪一位,因为当前的pe没有用了
// pe = te;
//
// start = ps;
// end = pe-1; //这个地方的end可以包括pe,也可以不用pe,因为pe就是标准值
// for (i = start; i <= end; i++)
// {
// result += height[pe] - height[i];
// }
// ps = pe;
// pe++;
//}
//else
//{
// start = ps;
// end = pe - 1;
// for (i = start; i <= end; i++)
// {
// result += height[ps] - height[i];
// }
// ps = pe;
// pe++;
//}

}
return result;
}


update java version 2015/12/7

public class TrappingRainWater {
public int trap(int[] height) {
return helper(height);
}
private int helper(int[] height) {

// 如果出现两个最高峰的话,这个方法就不能用了
//int res = 0;
//res += scan(height);
//reverse(height);
//res += scan(height);
// res;
// 第二种方法 直接依次遍历一遍做两个循环但是第二个的界限需要限定一下
//return streamFlow(height);
// 第三种方法 简化了遍历过程 从两边向中间遍历
return simplifyFlow(height);
}
private void reverse(int[] height) {
int ps = 0, pe = height.length -1, tmp;
while (ps < pe) {
tmp = height[pe];
height[pe] = height[ps];
height[ps] = tmp;
pe--;ps++;
}
}
private int scan(int[] height) {
if (height.length <= 1) {
return 0;
}
int ps = 0, pe = 1;
int low = 0, sum = 0, res = 0;
// 从左往右扫描一次
while (pe < height.length) {
low = height[ps];
sum = 0;
while (pe <= height.length - 1 && height[ps] > height[pe]) {
sum += low - height[pe];
pe++;
}
if (pe <= height.length - 1 && height[ps] <= height[pe]){
res += sum;
}
ps = pe;
pe++;
}
return res;
}
private int streamFlow(int[] height) {
if (height.length <= 1) {
return 0;
}
int ps = 0, pe = 1;
int low = 0, sum = 0, res = 0;
// 从左往右扫描一次
while (pe < height.length) {
low = height[ps];
sum = 0;
while (pe <= height.length - 1 && height[ps] > height[pe]) {
sum += low - height[pe];
pe++;
}
if (pe <= height.length - 1 && height[ps] <= height[pe]){
res += sum;
ps = pe;
}
pe++;
}
int left = ps;
// 从右往左扫描一次
pe = height.length -1;
ps = pe - 1;
while (ps >= left) {
low = height[pe];
sum = 0;
while (ps >= 0 && height[ps] < height[pe]) {
sum += low - height[ps];
ps--;
}
if (ps >= 0 && height[ps] >= height[pe]) {
res += sum;
pe = ps;
}
ps--;
}
return res;
}
private int simplifyFlow(int[] height) {
if (height.length <= 1) {
return 0;
}
int ps = 0, pe = height.length - 1;
int low = 0, res = 0, secondHec = 0;
while (ps < pe) {
if (height[ps] < height[pe]) {
secondHec = Math.max(height[ps], secondHec);
res += secondHec - height[ps];
ps++;
} else {
secondHec = Math.max(height[pe], secondHec);
res += secondHec - height[pe];
pe--;
}
}
return res;
}
}


  评论这张
 
阅读(9)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018