小编CaT*_*aTs的帖子

我正在尝试解决编码挑战，但我的解决方案性能不是很好，我正在寻找有关如何改进算法的意见或建议。

谜题如下：

给你一个代表果园的单元格网格，每个单元格可以是空地 (0) 或果树 (1)。一位农民希望知道果园内距离所有果树 k 距离内有多少个空点。

使用出租车几何形状计算距离，例如：

k = 1

[1, 0]
[0, 0]

the answer is 2 as only the bottom right spot is >k distance from all trees.

我的解决方案是这样的：

1. 循环网格并存储所有树位置
2. 从第一个树位置开始进行 BFS 并存储所有空点，直到我们到达超出 k 距离的邻居
3. 从下一个树位置开始进行 BFS 并存储空点的交集
4. 重复步骤 3，直到迭代完所有树位置
5. 返回所有交叉点后剩余的空点数量

我发现对于 k 值较大的大型网格，我的算法变得非常慢，因为我最终多次检查网格中的每个点。经过一些研究，我找到了一些类似问题的解决方案，建议采用两个最极端的目标节点，然后仅比较与它们的距离：

• https://www.codingninjas.com/codestudio/problem-details/count-nodes-within-k-distance_992849
• https://www.geeksforgeeks.org/count-nodes-within-k-distance-from-all-nodes-in-a-set/

然而，鉴于某些输入，这对我的挑战不起作用，如下所示：

k = 4

[0, 0, 0, 1]
[0, 1, 0, 0]
[0, 0, 0, 0]
[1, 0, 0, 0]
[0, 0, 0, 0]

使用极端节点方法，即使右下角的空点距中间树 5 距离，也会对其进行计数。

有人能指出我一种更有效的方法吗？我对这些类型的问题仍然很陌生，所以我发现很难看到我应该采取的下一步。

我正在创建一个视图，其中包含通过 ActiveStorage 存储的视频。目前我正在显示这样的视频：

%video{ controls: true, preload:"metadata" }
    %source{ src: rails_blob_path(@video.source), type: "TODO: Content Type" }

我想找到一种从附件中获取内容类型的方法。我发现我可以通过使用来获得它，@video.source.attachment.blob.content_type但这看起来很笨重。还有另一种更简单的方法来解决它video.source.content_type吗？不幸的是，使用video_tag助手对我来说不是一个可行的解决方案。