提出链表的简单公式

Question

老实说，我已经为此好几天了。我已经实现了这个函数的困难部分，但现在只剩下一件小事了。我要写的方法是删除链表中blockSize的每第N块。因此，如果我有一个大小为 7 的链表 {1,2,3,4,5,6,7}, N=2, blockSize=2，我想删除每个第 N(2nd) 个大小为 blockSize(2) 的块，因此删除 3,4,7。现在，为了让 for 循环正常工作，我需要为我创建的名为 numBlocksRemoved 的 int 值编写一个表达式。它计算要删除的块的总数。在本例中，它将是 2。这就是我所拥有的：

numBlockRemoved=(size/blockSize)/N;

但是，这只在数字看起来不错的情况下有时有效。如果我有 size=8,N=2, blockSize=2，那么我会得到 numBlockRemoved=2，这是正确的。但是，对于上面的示例，我输入的 int 值是 1，这是不正确的。我想要 2。我已经想了很长时间了，这很荒谬。我只是想不出适用于 numBlockRemoved 的公式。有什么想法吗？

Answer 1

尝试

floor(ceil(size/blockSize)/N)

floor(ceil(7/2)/3) = 1
floor(ceil(7/2)/2) = 2
floor(ceil(8/2)/2) = 2

您拥有的块数：

blocks = ceil(size/blockSize)

ceil，因为您不介意未满的块。

然后你跳过每一个 N，所以：

floor(blocks/N)

floor 因为你要么计算一个块，要么不计算。

Answer 2

当计算块的数量时，应向上舍入，因为不完整的块仍然是一个块（但在计算删除的块的数量时则不是）：

numBlockRemoved=((size+blockSize-1)/blockSize)/N;

Answer 3

(大小 + (块大小 - 1)) / (块大小 * N)

Answer 4

只要系统地考虑一下 - 如果你采用每第 N 个大小为 blockSize 的块，那么你就有效地删除了大小为 (N * blockSize) 的“超级块”。因此，对于第一个近似值，

nBlocks = floor [size / (N * blockSize)]

现在，从您的示例来看，即使您最后没有得到完整的块，您仍然想删除它。如果删除最后一个完整块后的余数多于 (N-1) 个完整块，就会发生这种情况。所以算法是

superblock = N * blockSize
nBlocks = floor (size / superblock)
remainder = size - (nBlocks * superblock)
if remainder > (N - 1) * blockSize {
  nBlocks += 1
}

你​​可以将最后的 +1 调整折叠到公式中，方法是添加一个量，该量将使整个超级块的大小倾斜，当且仅当它距离小于一个块时（类似于通过添加 0.5 进行四舍五入，然后取地面）。由于如果我们在超级块的最后一个块中只有一个数字，就会发生这种情况，因此我们必须添加 (blockSize - 1)，这给我们提供了

(size + (blockSize - 1)) / (blockSize * N)

上面的 aaz 公式。因此，您可以继续将他的答案标记为已接受；我只是想解释一下他是如何得出这个公式的。