[刷题笔记] 554 Brick Wall

问题

思路

这个问题解决的关键一下子就看到是累加数组了。

建立一个hash表，记录经过每个缝隙的砖块的count。

def least_bricks(wall)
    hash = {}
    wall.each do |level|
        sum = 0
        if level.length == 1
          next
        end
        level[0..-2].each do |width|
            sum += width
            if hash[sum]
                hash[sum] +=1
            else
                hash[sum] = 1
            end
        end
    end
    max = 0
    hash.each do |k,v|
      max =   max > v ? max : v
    end
    
    return wall.length - max
end

一波三折的解题过程

上面的答案看似很简单，但是一开始，我却第一个想用dp来做。

dp[i][j] 来表示第i行第j个数经过的砖块个数。

后来发现其实dp只和上一行相关。于是把i省去了。不过还是内存溢出。

再仔细一想，那么多dp，其实只有缝隙的地方我们需要记录。于是把不是缝隙的地方又都给排除了。

但是结果还是Timeout。

所以还是回过头来看一下，是不是有些细节可以稍微修改利用。