使用斯卡拉翻转硬币

我想解决从scala中的codechef翻转硬币问题。问题陈述如下：使用斯卡拉翻转硬币

有N个硬币保留在表中，编号为0至N - 1 Initally，每个硬币保持尾部向上。您必须执行两种类型的操作：1）翻转编号在A和B之间的所有硬币。这是由命令“0 A B”表示的 2）回答A和B之间有多少枚编号为的硬币抬头。这由命令“1 A B”表示。输入：第一行包含两个整数N和Q.接下来的Q行中的每一行都是上面提到的中提到的“0 A B”或“1 A B”形式。

输出：对于形式为“1 A B” 的每个查询输出1行，其中包含相应查询所需的答案。

样品输入：

样本输出：

限制条件：1 < = N < = 100000 1 < = Q < = 100000 0 < = A < = B < = N - 1

在最简单的方法，想到在阶初始化整数数组的如下：

var coins = new Array[Int](1000)

如果我遇到命令0 AB，我将简单地A的索引设定直到B + 1到1如下：

for(i <- 5 until 8){ 
     coins(i) = 1 
    }

如果我遇到命令1 AB，我将在阵列的切片从A到B + 1和计数的数目1在那个给定的切片和我将在下面做：

val headCount = coins.slice(5,8).count(x => x == 1)

这样看来，操作采取为O（n）在最坏的情况下，显然这可以优化在对数时间来解决。

有人可以指出我可能在这里做错了什么，以及如何以最优方式解决这个问题。

由于

来源

2012-05-01 sc_ray

而不是数组来存储头可以找到的间隔。请参阅间隔树wiki文章，了解如何实现您的功能。 – ElKamina

@Elkamina - 谢谢。也许在scala中实现间隔树会适用于这种特殊情况。需要阅读更多的内容。 –

这些天我对scala了解不多，但是我可以为更一般的关于O（log（n））的问题提供一个答案。通常这样的算法使用树，我想你可以在这里做。

如果您构建一棵平衡树，将硬币作为树叶，那么您可以在每个节点中存储该节点下面的树叶总数和树叶头数。你可以设想一下代码，它可以翻转硬币，从节点信息中找出要访问的叶子，并在O（n）时间内工作（你仍然需要翻转硬币）。但是如果翻转代码也更新了节点数据，那么头部的数量就是O（log（n）），因为你可以使用节点信息 - 你不需要去叶子。

这样就给你一个命令的O（n）和另一个命令的O（log（n））。

但你可以比这更好。我想你也可以做翻转操作O（log（n））。要做到这一点，你会为每个节点添加一个“翻转”标志。如果设置，则该点以下的所有节点都将翻转。有一些簿记细节，但总体思路在那里。

如果你把这个看作是合乎逻辑的结论，你实际上并不需要存储叶子，至少在开始的时候。您只需在处理命令时添加具有所需细节级别的节点。在这一点上，你基本上有评论中提到的区间树。

来源

2012-05-01 22:50:26

谢谢。是的，似乎我需要努力实现红黑树的增强版，以便在对数时间内解决上述问题。 –

好吧，如果你想避免在最坏的情况下出现问题，你需要一棵平衡的树，而红黑树是一个很好的平衡树实现。如果你还没有找到类似的东西，快速搜索http://www.devdaily.com/java/jwarehouse/scala/src/library/scala/collection/immutable/RedBlack.scala.shtml。 –

ps我建议先不要太担心平衡树。为不平衡树取得簿记权将会容易得多（当然更容易调试）。一旦你有这个工作，然后使其平衡（重新平衡的过程将要求你周围的旗帜和计数 - 这将是棘手的，如果你已经知道不平衡的代码工作更容易）。 –

一个干净的方式进行建模，这是作为一个BitSet，其中该集合中的整数值表示在板上的头的索引。然后，你可以翻转硬币的范围是这样的：

def heads(coins: BitSet, a: Int, b: Int) = (coins & BitSet(a to b: _*)).size

还是（可能更快）可变java.util.BitSet版本：

import java.util.BitSet 

def flip(coins: BitSet, a: Int, b: Int) { coins.flip(a, b + 1) } 
def heads(coins: BitSet, a: Int, b: Int) = coins.get(a, b + 1).cardinality

def flip(coins: BitSet, a: Int, b: Int) = coins^BitSet(a to b: _*)

你可以在一个范围内同样算头

这不一定是最佳的，但它是一个相当有效的方法，因为你只是在翻转位。

来源

2012-05-01 21:24:54

谢谢。语句BitSet（a到b：_ *）做什么？ –

使用斯卡拉翻转硬币

回答

相关问题