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