4

（这不是 CS 课的作业，即使看起来很像）

我使用位域来表示 0 到 22 之间的范围。例如，作为输入，我有几个不同的范围（顺序无关紧要）。我用于.和0为了X更好1的可读性。

.....XXXXX..............
..XXXX..................
.....XXXXXXXXXXXXXXX....
........XXXXXXX.........
XXXXXXXXXXXXXXXXXXXXXXXX

位域范围的数量通常低于 10，但可能会高达 100。从该输入中，我想计算互斥的连续范围，如下所示：

XX......................
..XXX...................
.....X..................
......XX................
........XX..............
..........XXXXX.........
...............XXXXX....
....................XXXX

（同样，输出顺序无关紧要，它们只需要相互排斥和连续，即它们不能有洞。.....XXX.......XXXXX....必须分成两个单独的范围）。

我尝试了几种算法，但最终都变得相当复杂和不优雅。对我有极大帮助的是一种检测.....XXX.......XXXXX....有孔的方法以及一种确定孔中一个位的索引的方法。

编辑：位域范围代表地图上的缩放级别。它们旨在用于为 Mapnik（OpenStreetMap 使用的平铺渲染系统等）输出 XML 样式表。

4

2 回答 2

0

至少我会对你的子问题进行一次测试。

对我有极大帮助的是一种检测 .....XXX.......XXXXX....有孔的方法以及一种确定孔中一个位的索引的方法。

在位掩码中找到最低和最高集合（“1”）位是一个很好解决的问题；例如，ffs(3)参见 glibc，或参见http://en.wikipedia.org/wiki/Bit_array#Find_first_one

给定位图的第一个和最后一个索引，将它们称为i和j，您可以计算具有所有位之间i和j设置的位图M = ((1 << i) - 1) & (~((1 << j) - 1))（对于任何一个错误的错误表示歉意）。

然后，您可以通过将原始位图与 M. 如果不匹配，您可以使用输入 xorM查找孔并重复。

于 2011-02-02T05:17:54.483 回答
0

我假设您在评论中提到的解决方案是这样的：

从左侧或右侧开始（因此 index = 0），并扫描设置了哪些位（最多 100 次操作）。将该集合命名为 x。还要设置一个变量 block=0。

在 index=1 处，重复并存储以设置 y。如果 x XOR y = 0，则两者都是相同的集合，所以继续索引 = 2。如果它 x XOR y = z != 0，则范围 [block, index) 是连续的。现在设置 x = y，block = index，然后继续。

如果您有 100 个长度为 22 的位数组，则这需要大约 2200 次操作。

这是一个最佳解决方案，因为无法进一步减少操作 - 在每个阶段，如果另一个集合与您的集合不匹配，您的范围就会被破坏，因此要检查范围是否被破坏，您必须检查所有 100 位。

于 2011-02-04T06:03:09.180 回答