Redian新闻
>
修真门派掌门路 【第371章】见识那一刀
avatar
修真门派掌门路 【第371章】见识那一刀# paladin - 谈古论金,黄梁一梦
g*y
1
一道算法老题,josephus环,N个数的循环,从第一个数开始,逆时针每跳一次,count
++,当count==M的时候,删掉当前的数,count清零
例如,1 2 3 4 5 6 7, M=3,删除数的顺序就是 3 6 2 7 5 1 4
现在给定 N,M<=N, M=O(N),求一个算法找到删除数的顺序
没做过的同学拿来思考下还是不错的~
答案在42楼,还有个注释过的cpp
avatar
m*n
2
如题,
万分感谢
avatar
q*2
3
思过山,一位老妪独自坐在山峰顶端,阳光将白发染成了金黄,皱纹的眼窝里,目光深
邃恬静。
灵木盟和龙家联军选择由博北城出发,一路向西,占领天引山矿坑后,向南方急转
,切断思过山和南方山门的联系,在思过山东南方,扎下一个面向西北,半圆盾牌形的
阵势。其主力专注防御南楚和思过山方向,精锐小部队分散出击,轻松收割掉楚秦山、
双联山、楠笼山等南方山门,以及担任警戒的二十四家散修宗门,楚秦南方,龙兴之地
尽陷敌手。
博木城中以低阶修士为主的大军,随后开始徐徐北上。
“这便是我的最后一战了啊。”
老妪轻轻叹道,提了提腿上快要滑落的皮毡。
齐休屠灭了她的家族,却又使她两次使免遭耻辱,她就是跟了这么个既是仇人,又
是恩人的掌门,又被他指婚给莫剑心续弦,在楚秦门过了算是幸福充实的一辈子,现在
,终于要到告别的时候了。
罗小小一百零五岁,生命已快走到尽头。
“虢修、沙飞、小锤不愿投降,都死了。”
莫剑心走到身后,抚着老妻的肩,轻轻说道。
罗小小干枯的手抬上肩头,和夫君相握,“齐妆在外听到这消息,应该会很伤心吧
……”
……
“道友可是后悔了?要不要到此为止?”
龙越云随手磕飞一柄【心生蜂云剑】,看见齐妆忽然仰头望天,眼眶里噙满泪水。
俩人接战,齐妆只用在醒狮谷里剩下的七柄【心生蜂云剑】,和他周旋。
一剑化三,二十一柄飞剑又组不成啥强大阵势,虽然将龙越云围在中心穿梭飞舞,
水火同济声势惊人,但只要是稍具眼光的修士,都能看出不过徒有其表而已。
龙越云手执一柄云刀,刀身似云似雾,内有电光闪烁,刀柄是某种黄色瑞兽角制成
,乃辟除邪异的好物。都懒得祭出,直接信手挥舞,轻松写意地挡住攻击。
打着打着,齐妆忽然停手,望天流起了泪。
“打哭了?”
擂台外观战的数百位各儒家宗门修士,表面不显山露水,但纷纷心中暗笑。
儒门不喜互相动手,正气坊中的擂台场所并不大,但是比黑河坊原来广汇阁那间可
供比斗的级数要高,金丹比斗,若不是后期对轰,尽可支撑。但两人打得波澜不惊,连
某些筑基级别的激烈程度都不如,不免令人意兴阑珊。
眼下那外道女人竟然哭起了鼻子,几位中人回想起一开始签生死契约的郑重场面,
顿时觉得有些可笑。
“都离我而去了……”
修士心中的感应,玄奥非常,抚养多年的秦小锤死去,齐妆立刻感知到了,本来万
念俱灰,毫无战意,但哭着哭着,心灵深处似乎升起道熟悉的声音,不停呼喊,让自己
坚持下去。
“好好活下去……”
“齐道友?”
“噢,抱歉。”
齐妆醒觉,对龙越云真诚说道:“你人不错,可惜,我必须杀死你。”
场外儒修们再憋不住,发出一阵轻声哄笑。
“哼!给脸不要!”
任再好的脾气,也有些按捺不住了,“若不是看你是个女人,我哪会和一个白山外
道奸妄啰嗦!”
龙越云执刀之手含怒一顿,背后天空,现出一团云雾虚影,其中隐约雷电闪烁。
然后脚步虚踏,人影消息不见。
“就是用这种遁术,想杀死掌门师兄的么?”
齐妆情绪渐渐收敛,再度回到平静无波的状态,家里有一个会【星遁】的秦长风,
对遁术之神妙也不觉吃惊。
“云遁需要的条件可比星遁要苛刻多了,无云可遁,你能奈何?”
心中打定主意,缁衣无风自动,背后显出本命【簪花幻月剑匣】虚影,法宝【灵狐
剑匣】被她随手抱在手中,一只【奉剑灵狐】器灵出现,接过心生蜂云剑控制权,水剑
火剑纷纷化去,七柄本剑悬在空中,布成一个七星阵势,星柄所指,正是龙越云藏身的
雷云。
【七星定身阵】,剑气将云雾罩住,幸好在这擂台场中,没有第二朵云供其藏身,
这也是顾叹的计谋,只有让齐妆提出正式的比斗,才能把战场挪到对龙越云不利的此地!
如果不行此法,在龙家山门里看家,身具遁法的龙越云,凭这两个人是无论如何杀
不死的。
赌的就是龙越云的骄傲和愚直!
对一个人来说,他的书往往比他的言行更能体现出真实的内心世界,顾叹读懂了他
,也想依此要他的命。
“咦?”藏在云中的龙越云一声轻呼。
这剑阵乃是顾叹几天前才买来,齐妆临时抱佛脚,无法发挥出威力,只是让他有些
不舒服而已,但仍能感受到对自己的克制。
“倒是准备得很足!”龙越云心中暗凛,不再轻敌,‘嗖’!【挂角云刀】从云雾
中飞出,第一刀无声无息,毫无一点烟火之气,仿佛闲云孤鹤,斩却尘心。
转瞬即到,齐妆打出一张二阶怪兽召唤符,挡在身前。
【污沼怪】,体型巨大,全是烂泥和臭污,云刀在内几乎无碍穿梭,电光霹雳作响
,将这个污沼怪割得愤怒嘶吼,泥水四溅,恶臭冲天。
自从齐休从历次生死之战里体会到怪兽召唤符的好来,他便一直四处求购,这玩意
消耗灵力巨大,而且属性单一,极易被克,但是如果对症,攻击一些阵法死物,或者克
制对手,那便往往事半功倍,极为好用。
云刀犀利,齐妆身上没啥克制物品,还是顾叹带了张【污沼怪】,生命力极其顽强
的此物,纯粹拿命硬抗,两相抵消,以齐妆的剑阵威能,需要的也就是时间而已。
‘嗞啦……’
云刀从臭污之中穿出,污沼怪的身体已开始慢慢愈合,仍旧活蹦乱跳,刀身的雷电
之力却被污染得有点暗弱。
“让我见识见识龙一刀吧……”
齐妆说道,见七星剑阵没用,索性收回,再次一化为三,二十一柄虚虚实实的飞剑
合而为一,一柄巨剑向云中猛斩。
云雾雷光一闪,巨剑穿出,同样无功而返。
“在我儒门面前,行此污秽……”
龙越云第二刀祭出,云刀如蛇,缠住天空巨剑,雷电缠绕,灵力互拼,很快占到上
风。
腾出手来,一本书卷向那污浊怪打去,堂堂皇皇的儒门浩然正气,冲刷涤荡,污浊
怪的身体黑烟直冒,眼看不久后就会被净化消融。
“顾叹果然料事如神。”
齐妆见龙越云的反应步步在顾叹算中,虽然讨厌此人,但不得不承认他的确是个人
才。
“邪魔外道,破!”
龙越云灵力加速输出,眼看很快要将污浊怪净化得一干二净。
天空飞剑之斗也已分出胜负,数刀之后,二阶极品的心生蜂云剑哪里挡得住,散乱
炸开,被奉剑灵狐收回剑匣之中。如果还有一百零八柄虚实飞剑,可能还能拼上一拼,
云刀毕竟是三阶极品。
阶位档次在那里,自然有他的道理。
云刀得胜,收回之后疾速再出,第三刀,迅若奔雷,辅以书卷法器的浩然正气镇压
,刀光正气,相辅相成,向齐妆笼罩而下。
“本心通明,浩然加身,谢了!”
齐妆突然冷喝,她的功法,可是大周书院那里得的,正宗根本道法【通明经】!
通明心,浩然气,齐妆志不在此,不代表她怕这个!
源源不断的浩然正气,如若穿过一道透明的水晶,从齐妆身体穿过,竟然毫发不能
伤,而且助其本心一动,剑道真意突然汹涌而出,决绝之中,一丝悲伤意念夹杂,带动
灵狐剑匣法宝,光华大放!
“唯喻,小锤,我会活着,还会活得很好,为了你们……”
剑匣之中,一柄又一柄飞剑接连飞出,仿佛无穷无尽,等阶不高,不过二阶中品,
乃是天理门附近,最常见的儒门【昆玉浩然剑】,【坚固】【浩然】【辟邪】三属性,
如此而已。
“多谢了,不是你这点浩然之气,我还真引不动这种浩然剑。”
‘蓬’!
第一柄飞剑斩到云雾跟前,剑匣里飞剑还在陆续飞出。
围观各家修士终于动容。
“这从没听说过的什么白山剑魔,果然名不虚传!而且功法飞剑,都有些我儒门根
脚!”
一名金丹修士惊呼失声。
“可惜为虎作伥……”
感应到周围不悦的目光,旋即补上一句,机智的将自家立场表达清晰。
一百零八柄,第四层蜂云剑阵罩定龙越云。
一百零八柄,护住周身。
还来一百零八柄,一柄贴一柄,合成宏伟巨剑直指空中云朵,毫不犹豫,呼啸斩下。
第四个一百零八柄,化作十二座九剑蜂云剑阵第一层,在场中到处游移飞舞,宛若
那四处觅食的隼鹰,在奉剑灵狐御使下,啄食漏网的敌人。
最后七柄心生蜂云剑,再作天上七星,星柄牢牢锁定,这次龙越云感觉不到不舒服
,但自身气机分明被对方锁定。
“好个剑魔!”
许多儒修一下子站了起来,擂台场中剑阵蜂拥已然成势,如若蝗群过境,龙越云那
朵藏身之云,陡然之间变成了自作自受的牢笼之云,再难动一分了!
“这!可恶!”
龙越云不想形势突变,那像尼姑的女人一旦行动,竟有如此疯狂的声威,前面全是
装的吗?!
再顾不得保持风度,从储物袋里拿出各种道具法器,往外轰出。
轰隆隆,霹雳雳,各种宝光闪现,灵力肆虐,巨兽嘶吼,傀儡现身。
终于有金丹修士对轰的威势。
“好!有戏!”
“越云!加油啊!别给我儒门丢脸!”
场外儒修,见到龙越云的反击很是轰坏了一些飞剑,顿时醒悟,这二阶中品剑对于
金丹修士比斗的程度来说,还是不够!
只要龙越云把大部分飞剑拼掉,就可以翻身!
‘轰!轰轰!’
龙越云又放出一个三阶雷系单体符篆,巨大的雷法威力将齐妆护身剑阵轰散,不过
还未及体,便被一个三阶召唤巨龟的鬼壳挡住。
战局从此再度演变,进入拼消耗斗身家的中盘胶着期,齐妆陆续有近百柄飞剑损坏
,掉在擂台上叮叮铛铛作响,但龙越云掏身家的速度,还有灵力输出眼看越来越跟不上
,而齐妆一人一狐,却还气定神闲。
剑匣本命,飞剑数量对灵力消耗影响甚微,不愧是剑修逆天本命。
龙越云不好了!
有眼力的都能看出端倪。
偶有儒修开始大声鼓噪,再没君子有礼的风度了。
“这龙家虽然眼看着在附近势力里快排不上号了,但毕竟多年元婴宗门底蕴,那白
山土包子女人身家竟然也有如此厚度?”
“不是对面黑风谷派来捣乱的罢?”
“是啊,生死之斗,本就不该是我儒修所为。”
“邪魔外道,不用跟他们讲什么仁义,我们进去救人罢!”
说时迟,那时快,他们还在争吵,龙越云已死命轰出围困自家剑阵一个缺口,背后
虚影再闪,齐妆背后一团云雾凭空生成,【雷云遁】一闪,人便遁入其内。
“你不是想领教我那一刀么?让你见识见识罢!”
龙越云双手高举,云刀祭于头顶,空气中灵力杀意急速奔涌,正要使出这最强一招
,齐妆冷冷说道:“对不起,我不感兴趣了。”
说着单手轻轻一捏,场中所有飞剑,甚至地上的破损剑体,统统如毒蛇活物一般,
将剑尖对准龙越云,然后同时向【七星定身阵】气机锁定之处攒刺!
就像一团棉花,突然向中心塌陷,最后所有物体,统统凝结到其中一点。
【万剑钻心】,齐妆在感应到秦小锤死的那一刻,才领悟到的天赋技能。
一个由剑身交缠组合而成的巨大铁球,夹杂着淡淡的血色,掉落在擂台之上,砸出
老大声音。
而后,擂台内外一片死寂。
龙一刀,终于没有机会使出那一刀。
avatar
a*n
4
TopCoder原题
avatar
g*y
5
所以我说是老题嘛
我是在CLRS上看的思考题
记得codejam08 第一轮也有个这个题目的变种

【在 a****n 的大作中提到】
: TopCoder原题
avatar
w*h
6
def josring(N, M):
index = M-1
cntM = 0
pout = 1
ring = range(1,(N+1))

print ring[index]
ring[index] = -1

while (pout < N):
index = index + 1
if ring[index%N] != -1:
cntM = cntM + 1
if cntM%M == 0:
print ring[index%N]
ring[index%N] = -1
pout = pout + 1


if __name__ == "__main__":
josring(7,3)

【在 g*******y 的大作中提到】
: 所以我说是老题嘛
: 我是在CLRS上看的思考题
: 记得codejam08 第一轮也有个这个题目的变种

avatar
a*a
7
你算法很强啊。topcoder和codejam都搞,很强了。

【在 g*******y 的大作中提到】
: 所以我说是老题嘛
: 我是在CLRS上看的思考题
: 记得codejam08 第一轮也有个这个题目的变种

avatar
g*y
8
这个是O(N^2)
想想能不能再优化

【在 w*******h 的大作中提到】
: def josring(N, M):
: index = M-1
: cntM = 0
: pout = 1
: ring = range(1,(N+1))
:
: print ring[index]
: ring[index] = -1
:
: while (pout < N):

avatar
g*y
9
没有,我很少做topcoder的题,codejam也就9月份的时候做了练了三个星期,呵呵,当
时水平不行,只是想碰碰运气,看能不能靠这个加点分好拿个google的面试,呵呵。
不过因为水平不够,加上发挥也不怎么好,最后只进到第二轮就挂了,不过还是拿到了
个google的面试,毕竟是google自己家的比赛,所以可能还是有点用。
所以我觉得这也是一条路,如果你觉得你算法coding比较强的,不妨早准备多练练
codejam的题,看一些程序竞赛的资料,9月份参赛如果能进个什么第三轮或者决赛,肯
定拿个google onsite没问题的,哪怕就进个第二轮,也可能能够拿个电面。其实预赛
和第一轮都不难,多练习的话,至少进第二轮没什么问题的。

【在 a********a 的大作中提到】
: 你算法很强啊。topcoder和codejam都搞,很强了。
avatar
m*f
10
topcoder的门槛其实很低的, 除非是红名
不过可以当成一个练习面试的工具

【在 a********a 的大作中提到】
: 你算法很强啊。topcoder和codejam都搞,很强了。
avatar
a*1
11
topcoder挺好的啊,而且可以看别人的代码。。。

【在 g*******y 的大作中提到】
: 没有,我很少做topcoder的题,codejam也就9月份的时候做了练了三个星期,呵呵,当
: 时水平不行,只是想碰碰运气,看能不能靠这个加点分好拿个google的面试,呵呵。
: 不过因为水平不够,加上发挥也不怎么好,最后只进到第二轮就挂了,不过还是拿到了
: 个google的面试,毕竟是google自己家的比赛,所以可能还是有点用。
: 所以我觉得这也是一条路,如果你觉得你算法coding比较强的,不妨早准备多练练
: codejam的题,看一些程序竞赛的资料,9月份参赛如果能进个什么第三轮或者决赛,肯
: 定拿个google onsite没问题的,哪怕就进个第二轮,也可能能够拿个电面。其实预赛
: 和第一轮都不难,多练习的话,至少进第二轮没什么问题的。

avatar
a*n
12
topcoder比较平民化, 据说大公司面试的难度相当于 SRM div I,第一题
而且都有官方的题解
不过我只做过些练习题。。。
avatar
a*1
13
差不多吧,不过topcoder时间内code 3道还是有点难的

【在 a****n 的大作中提到】
: topcoder比较平民化, 据说大公司面试的难度相当于 SRM div I,第一题
: 而且都有官方的题解
: 不过我只做过些练习题。。。

avatar
a*n
14
我是说topcoder single round match比较容易参与,codejam 好像就是多轮比赛
至于难度, 我没做过codejam, 不知道
avatar
a*a
15
不是有点难吧?能做出三道题的谁还在这里混?

【在 a********1 的大作中提到】
: 差不多吧,不过topcoder时间内code 3道还是有点难的
avatar
g*y
16
1 2 3 4 5 6 7, M=3
指针从左往右走(循环的)
指针指到1的时候,count=1
指针指到2的时候,count=2
指针指到3的时候,count=3=M,所以第一个删除的数是3,然后count清零
指针指到4的时候,count=1
指针指到5的时候,count=2
指针指到6的时候,count=3=M,第二个删除的是6
指针指到7的时候,count=1
指针指到1的时候,count=2
指针指到2的时候,count=3=M,第三个删除的是2
指针指到4的时候,count=1
指针指到5的时候,count=2
指针指到7的时候,count=3=M,第四个删除的是7
。。。。。。
M写个code出来,要求O(NlogN)

count

【在 g*******y 的大作中提到】
: 一道算法老题,josephus环,N个数的循环,从第一个数开始,逆时针每跳一次,count
: ++,当count==M的时候,删掉当前的数,count清零
: 例如,1 2 3 4 5 6 7, M=3,删除数的顺序就是 3 6 2 7 5 1 4
: 现在给定 N,M<=N, M=O(N),求一个算法找到删除数的顺序
: 没做过的同学拿来思考下还是不错的~
: 答案在42楼,还有个注释过的cpp

avatar
H*M
17
谢谢解释啊.不好意思了都.. :>

【在 g*******y 的大作中提到】
: 1 2 3 4 5 6 7, M=3
: 指针从左往右走(循环的)
: 指针指到1的时候,count=1
: 指针指到2的时候,count=2
: 指针指到3的时候,count=3=M,所以第一个删除的数是3,然后count清零
: 指针指到4的时候,count=1
: 指针指到5的时候,count=2
: 指针指到6的时候,count=3=M,第二个删除的是6
: 指针指到7的时候,count=1
: 指针指到1的时候,count=2

avatar
c*p
18
一个简单方法是把原来的int[]变成circular linked list,每次删除一个node后,下
一个node成为head,然后delete head->next->next直到最后,但是这样space是O(n)...
或者用bitmap来记录删掉的,但是time就成了...呃,这个time complexity是O(n2)??
或者...这个删除的顺序能用数学公司总结吗?我折腾了半天也推不出一个genenral
formula

【在 g*******y 的大作中提到】
: 1 2 3 4 5 6 7, M=3
: 指针从左往右走(循环的)
: 指针指到1的时候,count=1
: 指针指到2的时候,count=2
: 指针指到3的时候,count=3=M,所以第一个删除的数是3,然后count清零
: 指针指到4的时候,count=1
: 指针指到5的时候,count=2
: 指针指到6的时候,count=3=M,第二个删除的是6
: 指针指到7的时候,count=1
: 指针指到1的时候,count=2

avatar
H*M
19
最后谁survive有个数学公式的。

...
??

【在 c****p 的大作中提到】
: 一个简单方法是把原来的int[]变成circular linked list,每次删除一个node后,下
: 一个node成为head,然后delete head->next->next直到最后,但是这样space是O(n)...
: 或者用bitmap来记录删掉的,但是time就成了...呃,这个time complexity是O(n2)??
: 或者...这个删除的顺序能用数学公司总结吗?我折腾了半天也推不出一个genenral
: formula

avatar
g*y
20
我发现这个题要写出来还是有点难度。。。

【在 H*M 的大作中提到】
: 谢谢解释啊.不好意思了都.. :>
avatar
g*y
21
这个题目不在于考推导一个数学公式,或者我变一下题目,m不是固定的值,m等于每次
删去的那个数的值
提示一下,用树来做搜索。

【在 H*M 的大作中提到】
: 最后谁survive有个数学公式的。
:
: ...
: ??

avatar
w*p
22
过年了。 我偷偷懒,等答案。
你的GOOGLE面试怎么样了? 我只闯到第二轮。那天头发昏,加上确实很没准备充分。
avatar
c*p
23
...败了,我去topcoder翻答案算了。
没想明白。关键问题是对每个i%M,都要判断是否已经被删除了,否则就往后一个个移
直到碰到还没被删掉的为止,也就是CLRS里面hash table collision的第二种处理方法
,复杂度应该是O(N*M)吧。用tree就不用判断了??

【在 g*******y 的大作中提到】
: 这个题目不在于考推导一个数学公式,或者我变一下题目,m不是固定的值,m等于每次
: 删去的那个数的值
: 提示一下,用树来做搜索。

avatar
a*a
24
你的思想跑偏了。

【在 c****p 的大作中提到】
: ...败了,我去topcoder翻答案算了。
: 没想明白。关键问题是对每个i%M,都要判断是否已经被删除了,否则就往后一个个移
: 直到碰到还没被删掉的为止,也就是CLRS里面hash table collision的第二种处理方法
: ,复杂度应该是O(N*M)吧。用tree就不用判断了??

avatar
g*y
25
常规的搜索是一个一个的往下找,找到第M个
而用树的搜索,找下一个要打印的数,可以提高到O(logN)

【在 c****p 的大作中提到】
: ...败了,我去topcoder翻答案算了。
: 没想明白。关键问题是对每个i%M,都要判断是否已经被删除了,否则就往后一个个移
: 直到碰到还没被删掉的为止,也就是CLRS里面hash table collision的第二种处理方法
: ,复杂度应该是O(N*M)吧。用tree就不用判断了??

avatar
g*y
26
呵呵,新年的开头就想想题目多好啊~
要是没人发答案的话,我一会儿晚上来贴吧
我的面试还没schedule具体的时间,一直在等消息

【在 w********p 的大作中提到】
: 过年了。 我偷偷懒,等答案。
: 你的GOOGLE面试怎么样了? 我只闯到第二轮。那天头发昏,加上确实很没准备充分。

avatar
a*a
27
第二轮就是onsite了吧?还有好多轮么?

【在 w********p 的大作中提到】
: 过年了。 我偷偷懒,等答案。
: 你的GOOGLE面试怎么样了? 我只闯到第二轮。那天头发昏,加上确实很没准备充分。

avatar
c*p
28
“找下一个要打印的数”?这又回到我开始问的问题:是否有算法可以直接算出“下一
个”,而无需比较该数已经被删除?
post一个我用linked list实现的土法:D
void RingDelete(int* values, unsigned int size, int M)
{
if (size==0) return;
printf("step: %d\n", M);
struct Node
{
int value;
Node* next;
};
Node head;
head.next = NULL;
Node* pLastNode = NULL;
// costruct a circular linked list
for(int i=0; i{
Node* pNode = new Node();
pNode->value=values[i];
if (i==0)
{


【在 g*******y 的大作中提到】
: 常规的搜索是一个一个的往下找,找到第M个
: 而用树的搜索,找下一个要打印的数,可以提高到O(logN)

avatar
h*r
29
当是抛砖引玉了
red-black tree储存所有的数字。
删除的数就从tree中也删掉。
下次要删除的数字需要在red-black tree中search.
en, 需要augment tree for order information to make sure search the ith
element can be done in o(logn)

【在 g*******y 的大作中提到】
: 常规的搜索是一个一个的往下找,找到第M个
: 而用树的搜索,找下一个要打印的数,可以提高到O(logN)

avatar
g*y
30
嗯,差不多是这个思路了。不过不需要非得是红黑树。
呵呵,其实这个就是CLRS上面augment data structure那部分后面的思考题

【在 h***r 的大作中提到】
: 当是抛砖引玉了
: red-black tree储存所有的数字。
: 删除的数就从tree中也删掉。
: 下次要删除的数字需要在red-black tree中search.
: en, 需要augment tree for order information to make sure search the ith
: element can be done in o(logn)

avatar
m*f
31
survive 那个是 F(n,k) = (F(n-1, k) + k)%n (n个人, 隔k个杀一人)
原理就是多杀一个人, 就往安全的地方退k步, 这样不死我死前面那个

【在 H*M 的大作中提到】
: 最后谁survive有个数学公式的。
:
: ...
: ??

avatar
H*M
32
或者AVL tree?总之any balanced tree..
先build好这个augmented的tree,
第一个去死的是order(M),删除掉
然后第二个去死的是,剩下来的order(M+M-1),删除
第三个去死的是,剩下来的order(M+M+M-1-1),删除
其实要做个module,如果大于这个tree里面的元素个数的话。
我的天,这个用tree的方法真比那个推公式什么的清晰多了
sigh...

【在 g*******y 的大作中提到】
: 嗯,差不多是这个思路了。不过不需要非得是红黑树。
: 呵呵,其实这个就是CLRS上面augment data structure那部分后面的思考题

avatar
H*M
33
对了,我有个问题
如果,面试中要用augmented red black tree/avl TREE咋办啊
难道还写个RB tree/AVL tree不成
我RB tree insert/delete那些function都没记,太多了
应该怎么弄呢?assume有个现成的?

【在 H*M 的大作中提到】
: 或者AVL tree?总之any balanced tree..
: 先build好这个augmented的tree,
: 第一个去死的是order(M),删除掉
: 然后第二个去死的是,剩下来的order(M+M-1),删除
: 第三个去死的是,剩下来的order(M+M+M-1-1),删除
: 其实要做个module,如果大于这个tree里面的元素个数的话。
: 我的天,这个用tree的方法真比那个推公式什么的清晰多了
: sigh...

avatar
H*M
34
这formula啥意思?

【在 m*****f 的大作中提到】
: survive 那个是 F(n,k) = (F(n-1, k) + k)%n (n个人, 隔k个杀一人)
: 原理就是多杀一个人, 就往安全的地方退k步, 这样不死我死前面那个

avatar
g*y
35
这个题不需要用RBT,AVL
想想heap是怎么用数组实现树结构的
我感觉面试不太可能让code实现RBT,AVL,有些太刁难人了。

【在 H*M 的大作中提到】
: 对了,我有个问题
: 如果,面试中要用augmented red black tree/avl TREE咋办啊
: 难道还写个RB tree/AVL tree不成
: 我RB tree insert/delete那些function都没记,太多了
: 应该怎么弄呢?assume有个现成的?

avatar
m*f
36
面试的时候实现Red Black Tree太难了吧, 也没那么多时间写啊

【在 g*******y 的大作中提到】
: 这个题不需要用RBT,AVL
: 想想heap是怎么用数组实现树结构的
: 我感觉面试不太可能让code实现RBT,AVL,有些太刁难人了。

avatar
H*M
37
那一般关于augmented data structure的题,就只能嘴上说说了
反正我不记哪些RBTree的functions.

【在 m*****f 的大作中提到】
: 面试的时候实现Red Black Tree太难了吧, 也没那么多时间写啊
avatar
a*a
38
现在的面试都到红黑树这么难的东西了?

【在 H*M 的大作中提到】
: 那一般关于augmented data structure的题,就只能嘴上说说了
: 反正我不记哪些RBTree的functions.

avatar
H*M
39
大概就是用吧,和一些特性
不是 augmented data structures被烤果好几回了

【在 a********a 的大作中提到】
: 现在的面试都到红黑树这么难的东西了?
avatar
m*f
40
我觉得没, 我所听说的几个面试也就是问问linklist, queue stack之类的东西
如果被问到红黑树, 可能是因为表现的实在太强了

【在 a********a 的大作中提到】
: 现在的面试都到红黑树这么难的东西了?
avatar
g*y
41
这个公式貌似是找最后一个数?

【在 m*****f 的大作中提到】
: survive 那个是 F(n,k) = (F(n-1, k) + k)%n (n个人, 隔k个杀一人)
: 原理就是多杀一个人, 就往安全的地方退k步, 这样不死我死前面那个

avatar
H*M
42
这个跟wiki上递推公式有点像,
不过没看懂。。

【在 g*******y 的大作中提到】
: 这个公式貌似是找最后一个数?
avatar
g*y
43
是这样的
m=3:
1 2 3 4 5最后survive的那个是第4个数
考虑1 2 3 4 5 6:
第一个删除的是3,删除3后:
1 2 4 5 6,从4开始接着往后面计数/删,因为是循环的,相当于 4 5 6 1 2,从头开
始计数/删;
又因为删了一个,所以现在只剩5个数了,这样问题就递归到5个数的情况了
不过这个公式是找最后一个数,我这个题是让你打印所有删除的数的顺序,嘿嘿,如果你还是用这个思路做,貌似还是O(N^2)的

【在 H*M 的大作中提到】
: 这个跟wiki上递推公式有点像,
: 不过没看懂。。

avatar
g*y
44
贴答案了:
思路是:
(以n=16举例,array[16]={1,2,...,16})
array的每个位置(index)写成二进制就是0000 ... 1111
可以构造一棵树,根节点统计总共还有多少个数剩下没有删。根下面,往左边走,代表bit=0,往右边走代表bit=1。这样,从根到某个节点的path,就构成了一个二进制的prefix:
比如,根的左孩子的右孩子,prefix就是01,那么该节点就用来统计array中所有包含01前缀的位置中,还有多少个数剩下还没有删。
这样,我们还可以很简便的用数组来表示这个树,只需要规定root = 1, 左孩子=root<<1, 右孩子=左孩子+1(就像书上实现heap那样)。
这个数据结构写出来后,剩下的工作就好办了。
贴一个程序:
https://webfiles.uci.edu/siyangx/public/Josephus.cpp
avatar
a*a
45
你这个太强大了。现在面试太可怕了。

表bit=0,往右
边走代表bit=1。这样,从根到某个节点的path,就构成了一个二进制的prefix:
含01前缀的位
置中,还有多少个数剩下还没有删。
root<<1, 右孩
子=左孩子+1(就像书上实现heap那样)。

【在 g*******y 的大作中提到】
: 贴答案了:
: 思路是:
: (以n=16举例,array[16]={1,2,...,16})
: array的每个位置(index)写成二进制就是0000 ... 1111
: 可以构造一棵树,根节点统计总共还有多少个数剩下没有删。根下面,往左边走,代表bit=0,往右边走代表bit=1。这样,从根到某个节点的path,就构成了一个二进制的prefix:
: 比如,根的左孩子的右孩子,prefix就是01,那么该节点就用来统计array中所有包含01前缀的位置中,还有多少个数剩下还没有删。
: 这样,我们还可以很简便的用数组来表示这个树,只需要规定root = 1, 左孩子=root<<1, 右孩子=左孩子+1(就像书上实现heap那样)。
: 这个数据结构写出来后,剩下的工作就好办了。
: 贴一个程序:
: https://webfiles.uci.edu/siyangx/public/Josephus.cpp

avatar
m*f
46
对, 最后一个数

【在 g*******y 的大作中提到】
: 这个公式貌似是找最后一个数?
avatar
s*r
47
请问topcoder算法题目的连接是哪个?

【在 c****p 的大作中提到】
: ...败了,我去topcoder翻答案算了。
: 没想明白。关键问题是对每个i%M,都要判断是否已经被删除了,否则就往后一个个移
: 直到碰到还没被删掉的为止,也就是CLRS里面hash table collision的第二种处理方法
: ,复杂度应该是O(N*M)吧。用tree就不用判断了??

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。