資訊專(zhuān)欄INFORMATION COLUMN
摘要：題目描述每年六一兒童節(jié)?？投紩?huì)準(zhǔn)備一些小禮物去看望孤兒院的小朋友今年亦是如此。作為?？偷馁Y深元老自然也準(zhǔn)備了一些小游戲。其中有個(gè)游戲是這樣的首先讓小朋友們圍成一個(gè)大圈。然后他隨機(jī)指定一個(gè)數(shù)讓編號(hào)為的小朋友開(kāi)始報(bào)數(shù)。
題目描述
每年六一兒童節(jié),牛客都會(huì)準(zhǔn)備一些小禮物去看望孤兒院的小朋友,今年亦是如此。HF作為牛客的資深元老,自然也準(zhǔn)備了一些小游戲。其中,有個(gè)游戲是這樣的:首先,讓小朋友們圍成一個(gè)大圈。然后,他隨機(jī)指定一個(gè)數(shù)m,讓編號(hào)為0的小朋友開(kāi)始報(bào)數(shù)。每次喊到m-1的那個(gè)小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個(gè)小朋友開(kāi)始,繼續(xù)0...m-1報(bào)數(shù)....這樣下去....直到剩下最后一個(gè)小朋友,可以不用表演,并且拿到?？兔F的“名偵探柯南”典藏版(名額有限哦!!^_^)。請(qǐng)你試著想下,哪個(gè)小朋友會(huì)得到這份禮品呢？(注：小朋友的編號(hào)是從0到n-1)
分析這是個(gè)約瑟夫環(huán)的問(wèn)題，可以上網(wǎng)查查，很經(jīng)典的題目
簡(jiǎn)單的實(shí)現(xiàn)就是使用環(huán)形單鏈表，一圈一圈的繞，到了號(hào)為m的節(jié)點(diǎn)就刪掉繼續(xù)繞，最后只剩一個(gè)節(jié)點(diǎn)時(shí)，就可以返回了。
通過(guò)遞推出下一次的叫號(hào)和編號(hào)的關(guān)系，來(lái)遞歸操作，詳細(xì)可以看約瑟夫環(huán)
代碼實(shí)現(xiàn) 解法一function node(x){
this.val = x;
this.next = null;
}
function LastRemaining_Solution(n, m)
{
if(n < 1 || m < 1)
return -1;
// 構(gòu)造環(huán)形單鏈表
var head;
var last;
for(var i = 0;i < n;i++) {
if(i === 0){
head = new node(i);
last = head;
}else{
var temp = new node(i);
last.next = temp;
last = temp;
}
}
last.next = head;
var count = 0;
while(last !== head) {
if(++count === m){
last.next = head.next;
count = 0;
}else{
last = last.next;
}
head = head.next;
}
return head.val;
}
解法二
function LastRemaining_Solution(n, m)
{
if(n==0)
return -1;
if(n==1)
return 0;
else
return (LastRemaining_Solution(n-1,m)+m)%n;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/96352.html
摘要：歲的余宙華是少兒編程培訓(xùn)機(jī)構(gòu)阿兒法營(yíng)的創(chuàng)辦者，也是這個(gè)培訓(xùn)機(jī)構(gòu)課程體系的主要研發(fā)者。如今少兒編程培訓(xùn)行業(yè)正越來(lái)越熱，最近幾年國(guó)內(nèi)的少兒編程培訓(xùn)機(jī)構(gòu)雨后春筍般一個(gè)個(gè)地冒出來(lái)。這時(shí)，余宙華意識(shí)到是他作為父親出手的時(shí)候了。 什么是計(jì)算機(jī)的靈魂？余宙華用孩子式的語(yǔ)氣問(wèn)長(zhǎng)桌旁坐著的小女孩。 小女孩認(rèn)真地想了半天，有些靦腆地猶豫著給出了余宙華期待的答案：程序。 2018年7月，我在阿兒法營(yíng)海淀人大...
摘要：然而和他的朋友并不想遵從，要他的朋友先假裝遵從，他將朋友與自己安排在第個(gè)與第個(gè)位置，于是逃過(guò)了這場(chǎng)死亡游戲。問(wèn)最后一個(gè)人的最開(kāi)始的編號(hào)是幾先是筆者的樸素想法。這種想法雖然素樸，比較容易實(shí)現(xiàn)，但是時(shí)間復(fù)雜度為接著是數(shù)學(xué)方法。 ??筆者昨天看電視，偶爾看到一集講述古羅馬人與猶太人的戰(zhàn)爭(zhēng)——馬薩達(dá)戰(zhàn)爭(zhēng)，深為震撼，有興趣的同學(xué)可以移步：http://finance.ifeng.com/a/20...
摘要：然而和他的朋友并不想遵從，要他的朋友先假裝遵從，他將朋友與自己安排在第個(gè)與第個(gè)位置，于是逃過(guò)了這場(chǎng)死亡游戲。問(wèn)最后一個(gè)人的最開(kāi)始的編號(hào)是幾先是筆者的樸素想法。這種想法雖然素樸，比較容易實(shí)現(xiàn)，但是時(shí)間復(fù)雜度為接著是數(shù)學(xué)方法。 ??筆者昨天看電視，偶爾看到一集講述古羅馬人與猶太人的戰(zhàn)爭(zhēng)——馬薩達(dá)戰(zhàn)爭(zhēng)，深為震撼，有興趣的同學(xué)可以移步：http://finance.ifeng.com/a/20...
閱讀 1235·2021-11-23 10:04
閱讀 2478·2021-11-22 15:29
閱讀 3146·2021-11-19 09:40
閱讀 792·2021-09-22 15:26
閱讀 2194·2019-08-29 16:27
閱讀 2565·2019-08-29 16:10
閱讀 1979·2019-08-29 15:43
閱讀 3386·2019-08-29 12:43
