我在Topcoder中练习SRM问题。我遇到了这个问题
问题陈述：今天是平安夜。全世界的人
庆祝这个节日。下面的故事发生在
驯鹿，圣诞老人居住的地方。
驯鹿喜欢糖果。他们有N块糖果。碎片
糖果的编号是1到N。达舍是驯鹿之一。他
想吃一个糖果。去挑他要吃的，达舍
使用以下方法：当存在多个
糖果：丢弃所有用完美方块编号的糖果（即，
糖果1、4、9、16、25等）。重新标记剩余的K糖果1
通过k，保持数字的顺序不变。一次只有一件
剩下的糖果，达舍会吃的。
给你一个整数。你的方法必须计算并返回这个数字
最初分配给Dasher吃的糖果。
我使用ARAYLIST解决了这个问题，但是我的解决方案对于非常大的数字失败（Java堆SabCE异常）。因此，我在思考是否有可能解决O（1）空间复杂度的问题。
请给出你的建议和方法。我不希望代码只解释解决这个问题的逻辑。
我已经用问题的陈述重新打开了这个问题，以使我能在O（1）空间复杂性中帮助我解决这个问题。
最佳答案
我相信下面的解决方案是正确的，并且使用了o（1）内存，假设您可以在o（1）空间中保存一个整数。我们的想法是尝试反向运行这个过程，直到找到正确糖果的最终位置。
让我们来追踪这个问题的一个例子，其中n=10。然后我们得到这个：
1 2 3 4 5 6 7 8 9 10
X X X
2 3 5 6 7 8 10
X X
3 5 7 8 10
X X
5 7 10
X
7 10
X
10
现在，假设我们要计算这个问题的最终结果。我们知道吃完后，吃的糖果在第一位，因为只剩下一块糖果了。所以我们试着这样设置：
1
现在，我们知道在上一次迭代中，索引1处的糖果一定被吃掉了。这意味着最后的糖果实际上是在第二位：
? 2
在这之前的迭代中，我们知道自从Candy 1被吃掉之后，我们的Candy一定在位置3：
? ? 3
此时，我们再次回顾一次迭代。我们知道糖果1被吃掉了，但是糖果4也被吃掉了。这意味着，在上一次迭代中，糖果的索引必须是5，因为当我们将它移到正确的位置时，它必须跳过第一个元素的一个位置和第四个元素的一个位置：
? ? ? ? 5
重复同样的逻辑，我们得到上一个索引应该是7：
? ? ? ? ? ? 7
现在，下一步，我们知道我们会把糖果挪到两个位置，因为我们去掉了第1和第4个元素。然而，这将把我们的糖果放在位置9，这将被删除。这意味着我们要把糖果放在第10位：
? ? ? ? ? ? ? ? ? 10
在这一点上，由于还有10个糖果，我们知道，我们已经完全扭转了这一过程，并已完成。因为我们糖果的最后一个休息点是位置10，我们知道答案是，第10个糖果是被吃掉的，这完全符合我们之前的工作！
这种方法背后的诀窍是，我们不需要太多的内存来让它工作。特别是，在每一步中，我们只需要跟踪一些事情：
最后一块糖果的指数是多少？我们需要这个来知道停在哪里。
指数下面有多少个正方形？我们需要知道每一步有多少元素被删除。
下一个完美的正方形是什么？我们需要知道每次被删除的方块数何时增加。
我们最后一次探索的索引是什么？这个算法通过向后运行进程来工作，所以在某个时刻我们会意识到我们已经运行了一次太多了。当这种情况发生时，我们需要能够“备份”一个步骤，以获得最后一个没有超调的索引。
鉴于此，我们有以下算法：
将当前索引设置为1。
将较小的完美正方形数设置为1。
将下一个完美正方形设置为4。
将最后一个较小的索引设置为1。
当当前索引小于n时：
将最后一个较小的索引设置为当前索引（请记住目前的解决方案）。
设置当前索引+=较小的完美正方形的数目（将进程向后运行一步）
如果当前索引等于下一个完美正方形，则在其上添加一个（向后运行该索引的边沿情况；如果遇到完美正方形，则应超过它一步）
如果当前索引大于下一个完美正方形（现在每个步骤删除的数字更多）：
将完美的正方形设置为下一个完美的正方形。
在小于索引的完美正方形数上加一个。
返回最后一个较小的索引。
这只需要O（1）内存来保存所有值。
我们来举个例子吧！当n=20时，如果我们通过正式的过程，我们得到：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
X X X X
2 3 5 6 7 8 10 11 12 13 14 15 17 18 19 20
X X X X
3 5 7 8 10 11 13 14 15 17 18 19
X X X
5 7 10 11 13 14 17 18 19
X X X
7 10 13 14 17 18
X X
10 13 17 18
X X
13 17
X
17
如果我们运行我们的算法，我们得到
Current Index Next Square Smaller Squares
1 4 1
2 4 1
3 4 1
5 9 2
7 9 2
10 16 3
13 16 3
17 25 4
21 25 4
因为21>20，最后一个较小的索引是17，所以我们返回17，这是正确的答案！
编写为C代码，假设没有整数溢出：
int EatenCandyIndex(int n) {
int currIndex = 1;
int numSmallerSquares = 1;
/* Rather than tracking the next square, track the root of the next
* square. We can just square this to get the next square.
*/
int rootOfNextSquare = 2;
/* The last spot where the candy would be before we had Too Much Candy. */
int lastIndex = 1;
while (currIndex <= n) {
lastIndex = currIndex;
currIndex += numSmallerSquares;
if (currIndex == rootOfNextSquare * rootOfNextSquare)
++currIndex;
if (currIndex > rootOfNextSquare * rootOfNextSquare) {
++numSmallerSquares;
++rootOfNextSquare;
}
}
return lastIndex;
}
然而，如前所述，该算法不是特别有效。具体来说，在n=20的例子中看看它的行为。请注意，我们有三个回合，其中步长为1，步长为2和3的是2，等等。我们可以不显式地进行这些回合，而是计算用该步长必须进行的回合数，然后一次运行所有这些步骤。这样，我们总是有一轮一号，一轮二号，一轮三号，等等。要做到这一点，在每一步我们都需要看看我们的下一个目标是什么；这要么是数字n，要么是下一个完美的正方形。一旦我们找到了目标，我们需要看看需要多少步骤才能达到目标。如果当前索引是i，目标是t，如果步长是k，则需要采取（t-i）/k步骤才能达到目标。使用一个整数除法的小技巧，我们可以将其计算为
int numSteps = ((t - i) + (k - 1)) / k;
这为我们提供了以下更新算法：
int EatenCandyIndexFaster(int n) {
int currIndex = 1;
int numSmallerSquares = 1;
/* Rather than tracking the next square, track the root of the next
* square. We can just square this to get the next square.
*/
int rootOfNextSquare = 2;
while (true) {
/* Figure out what our target is. */
int target = min(n, rootOfNextSquare * rootOfNextSquare);
/* See how many steps are required. */
int numSteps = ((target - currIndex) + (numSmallerSquares - 1)) / numSmallerSquares;
/* See where we'd end up if we took one fewer than this many steps forward. */
int lastIndex = currIndex + (numSteps - 1) * numSmallerSquares;
/* Take that many steps forward. */
currIndex += numSmallerSquares * numSteps;
/* There is an edge case here: if we hit our number but it's a perfect square,
* we want to return the previous value.
*/
if (currIndex == n && n == rootOfNextSquare * rootOfNextSquare)
return lastIndex;
/* Otherwise, if we hit the target number exactly, return it. */
if (currIndex == n)
return currIndex;
/* Otherwise, if we overshot the target number, hand back where we'd be if we
* took one fewer step.
*/
if (currIndex > n)
return lastIndex;
/* Oh well; didn't make it. If we hit a perfect square, skip it. */
if (currIndex == rootOfNextSquare * rootOfNextSquare)
++currIndex;
++numSmallerSquares;
++rootOfNextSquare;
}
}
优化后的算法运行在o（√n）时间内，使用o（1）空间。之所以有时间限制，是因为算法的每一步都会移动到下一个完美平方，并且只有o（√n）个完美平方小于n。
希望这有帮助！
关于algorithm - 反复消除完美平方后剩下多少？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8901037/