昨天我把干净的洗衣店的袜子配对,弄清楚我做的方式效率不高.我正在做一个天真的搜索 - 挑选一个袜子并"迭代"堆,以找到它的对.这需要迭代在n/2*N/4 = N 2 /8上平均的袜子.
作为一名计算机科学家,我在想我能做什么？当然,为了实现O(NlogN)解决方案,我们会想到排序(根据大小/颜色/ ...).
哈希或其他非就地解决方案不是一种选择,因为我无法复制我的袜子(尽管如果可能的话可能会很好).
所以,问题基本上是:
给出一堆n袜子,包含2n元素(假设每个袜子只有一对匹配),有效配对多达对数额外空间的最佳方法是什么？(我相信如果需要的话我会记住那些信息.)
我将感谢一个解决以下方面的答案:
我最近偶然发现了2048游戏.您可以通过在四个方向中的任意一个方向上移动它们来合并类似的图块,以制作"更大" 每次移动后,新的图块会出现在随机空位置,其值为2或4.当所有框都被填充并且没有可以合并图块的移动时,或者您创建值为的图块时,游戏会终止2048.
一,我需要遵循明确的战略来实现目标.所以,我想为它编写一个程序.
我目前的算法:
while (!game_over) {
for each possible move:
count_no_of_merges_for_2-tiles and 4-tiles
choose the move with a large number of merges
}
我做的是在任何时候,我会尝试合并与价值观的瓷砖2和4,就是我努力2和4瓷砖,尽可能最小.如果我这样尝试,所有其他瓷砖自动合并,策略似乎很好.
但是,当我实际使用这个算法时,我只能在游戏结束前获得大约4000点.AFAIK的最高分数略高于20,000分,远高于我目前的分数.有比上面更好的算法吗？
我有一段时间有一个有趣的面试经历.问题开始很简单:
Q1:我们有包含数字的袋子
1,2,3,...,100.每个数字只出现一次,因此有100个数字.现在从包里随机挑出一个号码.找到丢失的号码.
当然,我之前听过这个采访问题,所以我很快回答了以下问题:
A1:嗯,这些数字的总和
1 + 2 + 3 + … + N是(N+1)(N/2)(见维基百科:算术系列之和).因为N = 100,总和是5050.因此,如果包中存在所有数字,则总和将是精确的
5050.由于缺少一个数字,总和将小于此数值,差异就是该数字.所以我们可以在O(N)时间和O(1)空间中找到丢失的数字.
在这一点上,我认为我做得很好,但突然之间,这个问题发生了意想不到的变化:
Q2:这是正确的,但是现在如果缺少两个数字你会怎么做？
我之前从未见过/听过/考虑过这种变化,所以我惊慌失措,无法回答这个问题.面试官坚持要知道我的思考过程,所以我提到也许我们可以通过与预期产品进行比较来获得更多信息,或者可能在从第一遍获得一些信息后再做第二遍,但我真的只是拍摄在黑暗中而不是实际上有一条清晰的解决方案.
面试官确实试图鼓励我说有第二个等式确实是解决问题的一种方法.在这一点上,我有点不高兴(因为事先不知道答案),并询问这是一般的(阅读:"有用")编程技术,还是只是一个技巧/问题答案.
面试官的回答让我感到惊讶:你可以概括一下找到3个缺失数字的技巧.实际上,您可以将其概括为找到k个缺失的数字.
Qk:如果行李中缺少k个号码,您会如何有效地找到它？
这是几个月前,我仍然无法弄清楚这种技术是什么.显然有一个?(N)时间下限,因为我们必须扫描所有数字至少一次,但是访问者坚持解决技术的时间和空间复杂度(减去O(N)输入扫描的时间)在k而不是N中定义.
所以这里的问题很简单: