给定产生1到5范围内的随机整数的函数,写一个产生1到7范围内随机整数的函数.
最近我一直在我的iPhone上玩一款名为Scramble的游戏.有些人可能认为这个游戏是Boggle.基本上,当游戏开始时你得到一个像这样的字母矩阵:
F X I E
A M L O
E W B X
A S T U
游戏的目标是尽可能多地找到可以通过将字母链接在一起形成的单词.你可以从任何字母开始,并且它周围的所有字母都是公平的游戏,然后一旦你继续下一个字母,围绕那个字母的所有字母都是合理的游戏,除了以前使用的任何字母.因此在上面的网格,例如,我能想出的话LOB,TUX,SEA,FAME,等词必须至少有3个字符,并且不超过N×N个字符以上,这将是本场比赛16,但可以在一些实现改变.虽然这个游戏很有趣且令人上瘾,但我显然不是很擅长它而且我想通过制作一个可以给我最好的单词的程序来作弊(单词越长,得分就越多).
样本博格http://www.boggled.org/sample.gif
遗憾的是,我不熟悉算法或效率等等.我第一次尝试使用字典,如这一个(〜2.3MB),并确实试图以配合字典条目组合线性搜索.这需要很长时间才能找到可能的单词,而且由于每轮只有2分钟,所以根本就不够.
我很想知道Stackoverflowers是否可以提供更有效的解决方案.我主要是在寻找使用Big 3 Ps的解决方案:Python,PHP和Perl,尽管Java或C++也很酷,因为速度至关重要.
当前的解决方案:
BOUNTY:
我正在为这个问题增加一笔赏金,作为我向所有投入他们计划的人表示感谢的方式.不幸的是,我只能向你们中的一个人提供接受的答案,所以我将测量7天后谁拥有最快的晃动解算器,并奖励获胜者赏金.
赏金奖励.感谢所有参与的人.
给定具有0和1的NxN矩阵.将包含a的每一行设置0为all 0s并将包含a的每一列设置0为all 0s.
例如
1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
结果是
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0
微软工程师告诉我,有一个解决方案不涉及额外的内存,只有两个布尔变量和一个通过,所以我正在寻找答案.
顺便说一句,想象它是一个位矩阵,因此只允许1s和0s在矩阵中.
几个月前,我找到了一段代码,我正在编写面试.
根据我的评论,它试图解决这个问题:
给定一美分的美分价值(例如200 = 2美元,1000 = 10美元),找到构成美元价值的所有硬币组合.只有便士(1¢),镍(5¢),角钱(10¢)和四分之一(25¢).
例如,如果给出100,答案应该是:
4 quarter(s) 0 dime(s) 0 nickel(s) 0 pennies
3 quarter(s) 1 dime(s) 0 nickel(s) 15 pennies
etc.
我相信这可以通过迭代和递归方式解决.我的递归解决方案非常错误,我想知道其他人如何解决这个问题.这个问题的难点在于尽可能提高效率.
不是严格意义上的问题,更多的是谜题......
多年来,我参与了一些新员工的技术访谈.除了询问标准"你知道X技术"的问题之外,我还试图了解他们如何处理问题.通常情况下,我会在面试前一天通过电子邮件向他们发送问题,并希望他们在第二天提出解决方案.
通常结果会非常有趣 - 错误但有趣 - 如果他们能解释为什么采取特定的方法,那么这个人仍会得到我的建议.
所以我想我会向Stack Overflow的观众抛出我的一个问题.
问题:您可以想到最有效的方式来编码国际象棋游戏(或其子集)的状态是什么？也就是说,给定具有合法排列的棋盘的棋盘,编码该初始状态和游戏中的玩家所采取的所有后续合法移动.
答案不需要代码,只是您将使用的算法的描述.
编辑:正如其中一张海报所指出的,我没有考虑移动之间的时间间隔.随意作为一个可选的额外:)考虑到这一点:)
EDIT2:只是为了进一步说明......请记住,编码器/解码器是规则感知的.唯一真正需要存储的是玩家的选择 - 编码器/解码器可以假设其他任何东西.
EDIT3:在这里挑选一个胜利者很难:)很多很棒的答案!
我曾经得到以下面试问题:
我在想一个正整数n.想出一个可以在O(lg n)查询中猜出它的算法.每个查询都是您选择的数字,我将回答"较低","较高"或"正确".
这个问题可以通过修改后的二进制搜索来解决,在该搜索中,列出2的幂,直到找到超过n的值,然后在该范围内运行标准二进制搜索.我认为这很酷的是,你可以比无限的力量更快地搜索特定数字的无限空间.
不过,我的问题是对这个问题稍加修改.假设我在0和1之间选择一个任意有理数,而不是选择正整数.我的问题是:您可以使用什么算法来最有效地确定我选择的有理数？
现在,我所拥有的最佳解决方案是在最多O(q)时间内通过隐式地走Stern-Brocot树(在所有有理数上的二叉搜索树)中找到p/q .但是,我希望运行时更接近我们为整数情况得到的运行时,可能是O(lg(p + q))或O(lg pq).有没有人知道如何获得这种运行时？
我最初考虑使用区间[0,1]的标准二进制搜索,但这只会找到具有非重复二进制表示的有理数,这几乎错过了所有的有理数.我还想过使用其他一些方法来枚举有理数,但是我似乎找不到一种方法来搜索这个空间给出更大/更小/更少的比较.
我的朋友说,有可能编写一个C程序,打印出"hello world",不IF/WHILE/FOR带分号,不带分号.经过极少的研究,我告诉她这是不可能的.可能吗？
如何使用独特的解决方案生成数独板？我想的是初始化一个随机板然后删除一些数字.但我的问题是如何保持解决方案的独特性？
什么是产生字谜的最佳策略.
Run Code Online (Sandbox Code Playgroud)An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once; ex.
- 十一加二是十二加一的字谜
- 小数点是我是一个圆点的字谜
- 天文学家是月球凝视者的字谜
起初它看起来很简单,只是混杂字母并生成所有可能的组合.但是,只生成字典中的单词的有效方法是什么呢？
我遇到了这个页面,在Ruby中解决了字谜.
但你有什么想法？