📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2589| 回复: 4
跳转到指定楼层
上一主题 下一主题
收起左侧

Google : Calculate volume

🔗
wwwyhx | 只看该作者 |倒序浏览
全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
Given a non-negative integer array representing an elevation map whereas
the width of each bar is 1, compute how much water it can contain after
raining. For example, given [0,1,0,2,1,0,1,3,2,1,2,1], returns 6. What is
the complexity of your solution?

感觉大致能说出个解法, 但是要注意的细节太多了

上一篇:Google : Write a function to reverse digits of an integer
下一篇:Microsoft: 打印最优路径
🔗
 楼主| wwwyhx 2011-10-28 10:43:51 | 只看该作者
全局:
本帖最后由 wwwyhx 于 2011-10-28 10:46 编辑

Similar to the largest rectangle in a histogram problem I posted before.
The point is to use a stack to store the index of the elements. The correspondent value of the array refers by the index in the stack should always in decreasing order. If a new element is larger than the value refers by the top of the stack, we need to pop the index in the stack to calculate the volume, until the stack is empty or the number refers by the top of the stack is bigger. The difference between two indexes represents the width of the rectangle.

  1. int GetContain(int a[], int n)
  2. {
  3.         assert(a && n > 0);
  4.         stack<int> stk;
  5.         
  6.         int nRet = 0;
  7.         for (int i = 1; i < n; i++)
  8.         {
  9.                 if (stk.empty() || a[i] < a[stk.top()])
  10.                 {
  11.                         stk.push(i);
  12.                 }
  13.                 else
  14.                 {
  15.                         int nLev = a[stk.top()];

  16.                         while (!stk.empty() && a[stk.top()] <= a[i])
  17.                         {
  18.                                 if (a[stk.top()] > nLev)
  19.                                 {
  20.                                         nRet += (i - stk.top() - 1) * (a[stk.top()] - nLev);
  21.                                         nLev = a[stk.top()];
  22.                                 }

  23.                                 stk.pop();
  24.                         }

  25.                         if (!stk.empty() && a[i] != nLev)
  26.                                 nRet += (i - stk.top() - 1) * (a[stk.top()] - a[i]);

  27.                         stk.push(i);
  28.                 }
  29.         }

  30.         return nRet;
  31. }
复制代码
回复

使用道具 举报

🔗
nooneknow 2011-10-31 09:30:22 | 只看该作者
全局:
本帖最后由 nooneknow 于 2011-10-31 09:37 编辑
Similar to the largest rectangle in a histogram problem I posted before.
The point is to use a stack to store the index of the elements. The correspondent value of the array refers by the index in the stack should always in decreasing order. If a new element is larger than the value refers by the top of the stack, we need to pop the index in the stack to calculate the volume, until the stack is empty or the number refers by the top of the stack is bigger. The difference between two indexes repr ...
wwwyhx 发表于 2011-10-28 10:43



没看懂stack在干嘛。如果一碰到一个比栈顶要大的就出栈计算,后面更大的元素怎么考虑啊。
我写了个,核心是不断找peak的那个点。peak的定义是,左右元素都比peak小。不用额外O(n)空间。
两个peak之间才能装得下东西。每个元素扫两遍,复杂度O(2n)

import java.util.*;

public class computeVol {
        public static void main(String[] args){
                List<Integer> arr = new ArrayList<Integer>(Arrays.asList(0,1,0,2,1,0,1,3,2,1,2,1));
                System.out.println(compV(arr));
        }
        
        public static int compV(List<Integer> arr){
                if(arr == null || arr.size() == 0) return 0;
                int vol = 0, size = arr.size(), hi1 = -1, hi2 = -1, lowerHi, index, result = 0, diff;
                //get the first peak
                for(index = 1; index < size; index++)
                        if(arr.get(index) < arr.get(index - 1)){
                                hi1 = index - 1;
                                break;
                        }
                if(hi1 == -1) return 0;
                hi2 = getNextPeak(arr, hi1);
                if(hi2 == -1) return 0;

                while(hi2!=-1){
                        lowerHi = arr.get(hi1) < arr.get(hi2)? arr.get(hi1):arr.get(hi2);
                        for(int i = hi1; i <= hi2; i++){
                                diff = lowerHi - arr.get(i);
                                if(diff> 0) result += diff;
                        }
                        hi1 = hi2;
                        hi2 = getNextPeak(arr, hi2);
                }               
                return result;
        }
        public static int getNextPeak(List<Integer> arr, int start){
                boolean isAscending = false;
                for(int i = start + 1; i < arr.size(); i++)
                        if(isAscending){
                                if(arr.get(i) < arr.get(i - 1))
                                        return i-1;
                        }
                        else{
                                if(arr.get(i) > arr.get(i - 1))
                                        isAscending = true;
                        }
                if(isAscending)
                     return arr.size()-1;
                else
                     return -1;   
     }
}
回复

使用道具 举报

🔗
 楼主| wwwyhx 2011-10-31 10:04:26 | 只看该作者
全局:
没看懂stack在干嘛。如果一碰到一个比栈顶要大的就出栈计算,后面更大的元素怎么考虑啊。
我写了个,核心是不断找peak的那个点。peak的定义是,左右元素都比peak小。不用额外O(n)空间。
两个peak之间才能装得下东西。每个元素扫两遍,复杂度O(2n)

import java.util.*;

public class computeVol {
        public static void main(String[] args){
                List arr = new ArrayList(Arrays.asList(0,1,0,2,1,0,1,3,2,1,2,1));
                System.out.println(compV(arr));
        }
        
     ...
nooneknow 发表于 2011-10-31 09:30



     就是类似用stack找直方图中最大矩形的那题
回复

使用道具 举报

🔗
yjyongz 2011-12-11 07:03:30 | 只看该作者
全局:
本帖最后由 yjyongz 于 2011-12-11 07:04 编辑

Space Complexity is constant
Time Complexity is O(N)

  1. public class Calculate_Volumn {
  2.         
  3.         public static int scanFoward(int array[]){
  4.                 if(array.length <=2) return 0;
  5.                 int volumn = 0;
  6.                 for(int i=0,adv=1;i<array.length;){
  7.                         if(array[i]!=0){
  8.                                 adv = i;
  9.                                 int count = 0;
  10.                                 while(true){
  11.                                         adv++;
  12.                                         if(adv < array.length - 1&&array[adv] < array[i])
  13.                                                 count+=array[adv];
  14.                                         else break;
  15.                                 }
  16.                                 if(adv < array.length&&array[adv] >= array[i]){
  17.                                         int height = array[i];
  18.                                         int dist = adv - i - 1;
  19.                                         volumn += height * dist - count;
  20.                                 }
  21.                                 i = adv;
  22.                         }else{
  23.                                 i++;
  24.                         }
  25.                 }
  26.                 return volumn;
  27.         }
  28.         
  29.         public static int scanBackward(int array[]){
  30.                 if(array.length <=2) return 0;
  31.                 int volumn = 0;
  32.                 for(int i=array.length-1,adv=array.length-2;i>=0;){
  33.                         if(array[i]!=0){
  34.                                 adv = i;
  35.                                 int count = 0;
  36.                                 while(true){
  37.                                         adv--;
  38.                                         if(adv >=0 &&array[adv] < array[i])
  39.                                                 count+=array[adv];
  40.                                         else break;
  41.                                 }
  42.                                 if(adv>=0&&array[adv]>=array[i]){
  43.                                         int height = array[i];
  44.                                         int dist = i - adv - 1;
  45.                                         volumn += height * dist - count;
  46.                                 }
  47.                                 i = adv;
  48.                         }else{
  49.                                 i--;
  50.                         }
  51.                 }
  52.                 return volumn;
  53.         }
  54.         
  55.         public static void main(String[] args) {
  56.                 // TODO Auto-generated method stub
  57.                 try{
  58.                         int array[] = {0,1,0,2,1,0,1,3,2,1,2,1};//it should be 6
  59.                         int array_1[] = {0,1,0,2};//it should be 1
  60.                         int array_2[] = {0,1,0,2,1,0,1,3};//it should be 5
  61.                         int array_3[] = {0,1};//it should be 0
  62.                         int array_4[] = {5,4,3,2,1};//it should be 0
  63.                         int array_5[] = {1,2,3,4,5};//it should be 0
  64.                         int volumn = 0;
  65.                         
  66.                         Object obj[] = {array,array_1,array_2,array_3,array_4,array_5};
  67.                         for(int i=0;i<obj.length;i++){
  68.                                 array = (int[])obj[i];
  69.                                 // O(N)--forward
  70.                                 volumn = scanFoward(array);
  71.                                 // O(N)--backward
  72.                                 volumn += scanBackward(array);
  73.                                 System.out.println(volumn);
  74.                         }
  75.                 }catch(Exception e){
  76.                         e.printStackTrace();
  77.                 }
  78.         }
  79. }

复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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