《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 583|回复: 3
收起左侧

[算法题] Trapping Rain Water 求助

[复制链接] |试试Instant~ |关注本帖
jy_121 发表于 2015-9-3 23:05:19 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
题目链接如下,要求求所能接收的最大雨水面积,自己想了一个方法,和答案不一样,但是到第七个case就过不了了:

http://www.lintcode.com/en/problem/trapping-rain-water/


大概就是只在后一个柱体比前一个高时才进行累加,并且更新高度,程序如下:
  1. public int trapRainWater(int[] heights) {
  2.         // write your code here
  3.       if(heights.length == 0 || heights.length == 1){
  4.             return 0;
  5.         }
  6.         
  7.                 int start = 0;
  8.                 int end = heights.length - 1;
  9.                 int v1 = heights[start];
  10.                 int v2 = heights[end];
  11.                 int s1 = 0;
  12.                 int s2 = 0;
  13.                
  14.                 while(start < end){
  15.                         while(heights[start] <= v1 && start < end){
  16.                                 s1 = s1 + v1 - heights[start];
  17.                                 start++;       
  18.                         }
  19.                         while(heights[end] <= v2 && start < end){
  20.                                 s2 = s2 + v2 - heights[end];
  21.                                 end--;       
  22.                         }
  23.                         v1 = heights[start];
  24.                         v2 = heights[end];
  25.                 }
  26.                 return s1 + s2;
  27.     }
复制代码
谢谢!


question.png
 楼主| jy_121 发表于 2015-9-4 09:55:48 | 显示全部楼层
已经得到了一位同学的解答。

start,end两个指针向中间移动的时候只考虑了两边的边界情况,没有考虑中间的情况,v1和v2只能取两者中小的那个 v1 = heights[start]; v2 = heights[end]; 应该改为 v1 = Math.min(heights[start],heights[end]); v2 = v1;
回复 支持 反对

使用道具 举报

find_node 发表于 2017-9-15 03:48:04 | 显示全部楼层
现在有II 了: https://leetcode.com/problems/trapping-rain-water-ii/description/ 有什么好的方法吗?
回复 支持 反对

使用道具 举报

limpalong 发表于 2017-9-16 02:51:36 | 显示全部楼层
思想是类似的,先把周围的一圈放进去,然后用priorityqueen每次poll最小的值,然后根据poll的值寻找它周围是不是有比当前小的的柱子有的话就加入result
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-19 11:17

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表