我在Topcoder中练习SRM问题.我遇到了这个问题
问题陈述:今天是平安夜.世界各地的人们庆祝这个假期.以下故事发生在圣诞老人居住的驯鹿之地.
驯鹿喜欢糖果.他们有n块糖果.这些糖果编号为1到n.Dasher是驯鹿之一.他想吃一个糖果.为了挑选他要吃的那个,Dasher使用以下方法:虽然有一块以上的糖果:丢弃所有用完美方块编号的糖果(即糖果1,4,9,16,25等) .重新标记剩余的k个糖果1到k,保持数字的顺序相同.只剩下一块糖果,Dasher就会吃掉它.
给你一个int n.您的方法必须计算并返回最初分配给Dasher吃掉的糖果的数字.
我使用ArrayList解决了这个问题但是我的解决方案因为非常大的数量而失败(Java Heap Sapce Exception).因此我在想是否有可能解决O(1)空间复杂性中的问题.
请提出您的建议和方法.我不希望代码只解释破解这个问题的逻辑.
我已经用问题陈述重新打开了这个问题 ,因此Stackoverflow中的大师可以帮助我在O(1)空间复杂度中解决这个问题
tem*_*def 12
我相信以下解决方案正常工作并使用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
现在,我们知道在上一次迭代中,索引1的糖果必须被吃掉.这意味着最后一个糖果实际上是在上一次的位置2:
? 2
在此之前的迭代中,我们知道,因为糖果1被吃掉了,我们的糖果实际上必须位于第3位:
? ? 3
在这一点上,我们再次回想一次迭代.我们知道糖果1被吃了,但糖果4也吃了.这意味着我们糖果的索引必须在前一次迭代中为5,因为当我们将其向下滑动到其正确位置时,它必须跳过第一个元素的一个点和第四个元素的一个点:
? ? ? ? 5
重复这个相同的逻辑,我们得到前一个索引将是7:
? ? ? ? ? ? 7
现在,为了下一步,我们知道我们会把糖果放到两个位置,因为我们放弃了第一和第四个元素.但是,这会将我们的糖果放在第9位,这将被删除.这意味着我们将糖果撞到位置10:
? ? ? ? ? ? ? ? ? 10
在这一点上,由于剩下10个糖果,我们知道我们完全颠倒了这个过程并完成了.由于我们糖果的最后一个休息点是位置10,我们知道答案是第10个糖果是吃的,这完全符合我们以前的工作!
这种方法背后的技巧是我们不需要太多内存来使其工作.特别是,在每一步我们都需要跟踪一些事情:
鉴于此,我们有以下算法:
这只需要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的例子中的行为.注意我们有三轮,其中步长是一,两个步长是2和3,等等.而不是明确地发生这些轮,我们可以改为计算使用该步长必须进行多少轮,然后立即执行所有这些步骤.这样,我们总是有一个尺寸为1的圆形,一个尺寸为2的圆形,一个尺寸为3的圆形等.为此,在每个步骤中我们将需要看到我们的下一个目标是什么; 这将是数字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)空间.时间限制的原因是算法的每个步骤移动到下一个完美的正方形,并且只有小于N的O(√N)正方形.
希望这可以帮助!
另一种变体:
a = floor(sqrt(N-1))
b = min((N-1)/a, a+1)
solution = a*b+1
或者,换句话说,
unsigned long long eats(unsigned long long N) {
unsigned long long r = (unsigned long long)sqrt(N-1);
while(r*r >= N) --r;
while(r*(r+2) < N) ++r;
if (N <= r*(r+1)) {
return r*r+1;
}
return r*(r+1)+1;
}
证据来自于分析next给出任何糖果的下一个位置的功能next(n*n) = 0,因此它不是部分功能.如果a*a < N < (a+1)*(a+1),我们有next(N) = N - a.因此,一些形式n = a*(a+1) + 1旅行
a*(a+1)+1 -> a*a + 1 -> (a-1)*a + 1 -> ... -> 2*3 + 1 ->2*2 + 1 -> 1*2 + 1 -> 1*1 + 1 -> 0*1 + 1
我们看到形式的数量也a*a +1达到1.任何其他形式的数字在某个时刻达到大于1的平方:
a*(a+1) -> a*a -> eliminated
a*(a+1) + r -> a*a + r -> (a-1)*a + r
对2 <= r <= a.如果r = a,(a-1)*a + r = a*a是一个正方形,导致立即消除.如果r < a,两步后达到的数字具有相同的形式r.继续,数量达到
(r+1)*(r+2) + r -> (r+1)*(r+1) + r -> r*(r+1) + r -> r*r + r -> r*r -> elimination.
所以我们已经看到了
n*n + 1或时,数字到达过程中的点1n*(n+1) + 1从N糖果开始到达第一个点的最后一个数字当然是不超过的最大数量N.QED.
除非我犯了一个愚蠢的错误,否则就有了这个公式.它可能会被简化,但这是我遇到的第一个.
from math import floor, sqrt, ceil
def is_square(i):
sq = int(i**0.5)
return i == sq*sq
def brute(n):
seq = range(1, n+1)
while len(seq) > 1:
seq = [x for i,x in enumerate(seq, 1) if not is_square(i)]
return seq[0]
def dasher(n):
w = lambda i: floor(sqrt(4*i+1))-1
q = lambda i: ceil((i**2+3)/4)
return q(w(n-1)+1)
并检查:
>>> b = [brute(i) for i in range(1, 10**3)]
>>> d = [dasher(i) for i in range(1, 10**3)]
>>> b[:25]
[1, 2, 3, 3, 5, 5, 7, 7, 7, 10, 10, 10, 13, 13, 13, 13, 17, 17, 17, 17, 21, 21, 21, 21, 21]
>>> b == d
True