Ruby leetcode 上的一道题,有没有更简单的解法?

wudixiaotie · 2014年11月13日 · 最后由 catfish23 回复于 2018年08月28日 · 2372 次阅读

Trapping Rain Water 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!

===============================下面是我的解法======================================= 大概思路是遍历每个节点,找到左边最高边界,找到右边最高边界,然后取这两个边界中最小的和当前高度做差,就是当前的点的蓄水量。每个点蓄水量之和就是总的蓄水量。

a = [0,1,0,2,1,0,1,3,2,1,2,1]
b = [0,0,0,0,0,7,0,0,0,0,0,0]
# https://oj.leetcode.com/problems/trapping-rain-water/
def trap(data_arr)
  total_trap = 0

  data_arr.each_with_index do |item, index|
    left_edge, right_edge = item, item
    # find left bigest edge
    (0..(index - 1)).reverse_each do |left_index|
      left_item = data_arr[left_index]
      if left_item > left_edge
        left_edge = left_item
      end
    end

    # find right bigest edge
    ((index + 1)..(data_arr.length - 1)).each do |right_index|
      right_item = data_arr[right_index]
      if right_item > right_edge
        right_edge = right_item
      end
    end

    # this point traped water
    increment = left_edge >= right_edge ? right_edge - item : left_edge - item

    # puts "index:#{index} left_edge:#{left_edge} right_edge:#{right_edge} increment:#{increment}"
    total_trap += increment
  end

  total_trap
end

p trap(a) == 6 # =》 true
p trap(b) == 0 # =》 true

============================================================================================== 或者有什么办法把代码简化?

map = [0,1,0,2,1,0,1,3,2,1,2,1]
result = 0
map.max.times.each do
   cursor = -1
   map = map.each_with_index.map do |v, i|
     if v != 0
       v-=1
       result += i - cursor - 1 if cursor>0 and cursor != i
       cursor = i
     end
     v
   end
end
p result

简单的游标方式,没有包装成方法,你看行不行?

我想到的也是楼主的左右各遍历一次。。。

分享 一个 O(n) 的:(改自别人的 java 代码)

def trap(map=[])
  left = 0
  right = map.length - 1
  traps = 0
  while(left < right)
    min = [map[left], map[right]].min
    if(map[left] == min)
      left += 1
      while((left < right) && (map[left] < min))
        traps += min - map[left]
        left += 1
      end
    else
      right -= 1
      while((left < right) && (map[right] < min))
        traps += min - map[right]
        right -= 1
      end
    end
  end
  return traps
end

很想知道那些牛人都是这么抽象思考这些问题的????

#2 楼 @jcd

觉得键点是,他把水填起来来了。把 bar 想象成可以增加的。

然后就是逻辑的严密了。我猜的,不知道对不对。

说一句,这种算法,code 都是很 cheap 的,方法更重要。

[0,1,0,2,1,0,1,3,2,1,2,1] 夹着 2 个 0, 然后非 0 项全部减去 1 [0,0,0,1,0,0,0,2,1,0,1,0] 夹着 4 个 0,然后非 0 项全部减去 1 [0,0,0,0,0,0,0,1,0,0,0,0] 没夹着 0,结束

思想就是从最底下一层一层往上数,每到第 i 层,然后看夹着几个 0 就是看这一层 (而且是如果只有这一层) 能存储几格水,所以 [0,1,0,2,1,0,1,3,2,1,2,1] 也可以把非 0 项都变成 1,[0,1,0,1,1,0,1,1,1,1,1,1],这样再看夹着几个 0,本质上就是考虑单独这一层,但是上面直接看夹着几个 0,结果是一样的。

然后到下一层 i+1, 但要把下一层当做最底层,所以非 0 项都减去 1,作为下一层的数组。

这是我直觉想到的办法,不知道有没有没有考虑到的极端情况。而且这算法复杂度是 O(n*h),n 是数组长度,h 是最大层数,估计也不是最好的办法。

俄罗斯方块解法,简单

需要 登录 后方可回复, 如果你还没有账号请 注册新账号