时间戳

首页 > 解决方案 > Cohesity 的入围测试中提出的与布尔矩阵相关的竞争性编程问题

python - Cohesity 的入围测试中提出的与布尔矩阵相关的竞争性编程问题

问题描述

给出了一个宽度为 w 和高度为 h 的 0-1 矩阵。0 表示黑色，1 表示白色。把它想象成条形码。如果整列都用 1 填充，则它是条码上的白色条带。如果 n 个连续的列用 0 填充，那么它将表示一个宽度为 n 的黑色条带。现在矩阵并不完美（有些列不是完全白色或完全黑色，即它们有一些不规则性）。

将单个 0 与 1 切换的成本是 1，反之亦然。

给定 x 和 y，其中 x 是条码中条带必须具有的最小宽度，y 是最大宽度。您必须找到将原始不完美矩阵转换为满足 x 和 y 约束的有效条形码矩阵所需的最小成本，即每个条带的宽度在 [x,y] 之间。

蛮力回溯不起作用，得到 TLE。

标签： pythonarraysmatrixdynamic-programming

解决方案

考虑一列可能是 (1) b，黑条中最右边的黑色列，和 (2) w，白条中最右边的白色列之一。让我们使用预先计算的列前缀和C来计算将一系列列及时转换为白色或黑色的函数。当该列的类型为 时，O(1)让我们f(i, type)表示直到第 th 列的条形码的最小成本。然后：itype

f(0, b) ->
  Infinity if x > 1 else C(0, 0, b) 

f(0, w) ->
  Infinity if x > 1 else C(0, 0, w)

f(i, b) ->
  min( C(j, i, b) + f(j - 1, w) )

f(i, w) ->
  min( C(j, i, w) + f(j - 1, b) )

for j = (i - y + 1) to (i - x + 1)

（显然小于零f(i)是无效的，跨越第一个索引左侧的范围的成本也是如此。）i

推荐阅读