方块下降问题的错误实现

Question

所以我正在解决 the falling squares 问题。

There are several squares being dropped onto the X-axis of a 2D plane.

You are given a 2D integer array positions where positions[i] = [lefti, sideLengthi] represents the ith square with a side length of sideLengthi that is dropped with its left edge aligned with X-coordinate lefti.

Each square is dropped one at a time from a height above any landed squares. It then falls downward (negative Y direction) until it either lands on the top side of another square or on the X-axis. A square brushing the left/right side of another square does not count as landing on it. Once it lands, it freezes in place and cannot be moved.

After each square is dropped, you must record the height of the current tallest stack of squares.

Return an integer array ans where ans[i] represents the height described above after dropping the ith square.

思考过程：

初始化并记住第一个点（x 和 y 坐标）。
一个接一个地迭代，如果盒子一个接一个地叠在一起，增加高度。
如果不是这种情况，请查看当前高度或 max_height 中哪个更大，并将其添加到结果列表中。

这是我的代码：

class Solution:
    def falling_squares(self, positions: List[List[int]]) -> List[int]:
        x_coordinate = positions[0][0]
        y_coordinate = positions[0][1]
        max_height = y_coordinate
        result = [max_height]
        for left,position in positions[1:]:
            if left<x_coordinate+y_coordinate:
                max_height+=position
                result.append(max_height)
            else:
                max_height = max(max_height,position)
                result.append(max_height)
            x_coordinate=left
            y_coordinate = position
        return result

这是输出

请告诉我我的逻辑中缺少什么。

Answer 1

你的代码中有很多错误我试图通过修复一些逻辑来改进它但是它为你提供的其他 leetcode 测试用例弹出另一个逻辑错误。我最终重写了代码。

class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        ret = []
        blocks = {}
        for drop in positions:
            x_coordinate = drop[0]
            checked = False
            elongation = drop[1]
            for (block_x, block_xe), prev_h in blocks.copy().items():
                if x_coordinate < block_xe and x_coordinate+elongation > block_x:
                    if blocks.get((x_coordinate,x_coordinate + elongation)):
                        if blocks.get((x_coordinate,x_coordinate + elongation)) < elongation + prev_h:
                            blocks[(x_coordinate,x_coordinate + elongation)] = elongation +prev_h
                    else:
                        blocks[(x_coordinate,x_coordinate + elongation)] = elongation +prev_h
                    checked = True
            if not checked:
                blocks[(x_coordinate, x_coordinate+elongation)] = elongation
            ret.append(max(blocks.values()))
        return ret

解释如下：

第 1 行：初始化 return 列表。

第 2 行：初始化块的哈希映射。我之所以不做你所做的，是因为在某些情况下，块落在一个块上，这个块是在一些迭代之前记录的，而不是刚刚之前的迭代，并且它的高度大于 max_height。这也是鼓励我重写您的代码的主要原因。

第 7 行：遍历 blocks 的副本，因为我正在循环中修改它。

第 8-15 行：检查块的 x 是否小于第二个块的 x + 其伸长率，并检查块的 x + 其伸长率是否大于第二个块的 x .这是为了检查该块是否落在任何其他块的顶部。

正在检查当前块是否有副本。如果是，那么我们只会在它大于它的欺骗时才添加它。否则如果没有重复就添加它。

第 17 行：如果该块已经落在任何其他块上，则 checked 切换 True，如果没有，则将其添加到哈希中地图.

显然有一种更快的方法：

Runtime: 883 ms, faster than 26.06% of Python3 online submissions for Falling Squares.
Memory Usage: 15 MB, less than 51.41% of Python3 online submissions for Falling Squares.

方块下降问题的错误实现

Incorrect Implementation of falling squares problem

python

logic

解释如下：

显然有一种更快的方法：