尋找倖存者時，N多人都坐在一個圓圈

Question

嗨，我碰到這個問題，並試圖解決這個

花幾秒鐘想像你是在排成一圈100把椅子的房間。這些椅子從一個到一個百個按順序編號。 在某個時間點，第一把椅子上的人將被告知要離開房間。第二把椅子上的人將被跳過，第三把椅子上的人將被告知離開。去旁邊的是6號椅子上的人。換句話說，最初會跳過1個人，然後是2,3,4 ...等等。這種跳躍模式將繼續繞着這個圈子走，直到剩下一個人。倖存者。請注意，當人離開房間時，椅子會被移除。編寫一個程序來確定倖存者正坐在哪個椅子上。

我取得了很好的進展，但在計數達到100之後出現問題並且不確定從這裏循環，任何一個可以幫助我，這是我的代碼

import java.util.ArrayList; 

public class FindSurvivor { 

public static void main(String[] args) { 
    System.out.println(getSurvivorNumber(10)); 
} 

private static int getSurvivorNumber(int numChairs) { 
    // Handle bad input 
    if (numChairs < 1) { 
     return -1; 
    } 

    // Populate chair array list 
    ArrayList<Integer> chairs = new ArrayList<Integer>(); 
    for (int i = 0; i < numChairs; i++) { 
     chairs.add(i + 1); 
    } 


    int chairIndex = 0; 
    int lr =0; 
    while (chairs.size() > 1) { 
     chairs.remove(lr); 
     chairIndex+=1; 
     System.out.println(lr+" lr, size "+chairs.size()+" index "+chairIndex); 
     if(lr==chairs.size()||lr==chairs.size()-1) 
      lr=0; 
     lr = lr+chairIndex; 
     printChair(chairs); 
     System.out.println(); 
    } 

    return chairs.get(0); 
} 

public static void printChair(ArrayList<Integer> chairs){ 
    for(int i : chairs){ 
     System.out.print(i); 
    } 
} 
} 

Answer 1

我不知道您的刪除模式是什麼，但我可能實現這是一個循環鏈表，其中100座持有人連接回第一個座位固定器。如果您使用陣列，您將不得不擔心在每次移除後重新組織座位。

Answer 2

如果你的步驟是增量您可以使用下面的代碼：

int cur = 0; 
    int step = 1; 
    while (chairs.size() > 1) { 
     chairs.remove(cur); 
     cur += ++step; 
     cur %= chairs.size(); 
    } 
    return chairs.get(0); 

如果步固定爲1，那麼基於由@Jarlax提供的解釋，你可以用一個代碼行解決問題在O（log n）的時間：

//for long values 
public static long remaining(long numChairs) { 
    return (numChairs << 1) - (long)Math.pow(2,Long.SIZE - Long.numberOfLeadingZeros(numChairs)); 
} 

//for BigInteger values 
public static BigInteger remaining(BigInteger numChairs) { 
    return numChairs.shiftLeft(1).subtract(new BigInteger("2").pow(numChairs.bitLength())); 
} 

但是，如果你堅持的ArrayList沒有額外的變量都需要你的代碼。始終刪除第一個元素，然後刪除 - 然後添加列表末尾的下一個元素。但是，這是O（n）。

while (chairs.size() > 1) { 
     chairs.remove(0); 
     chairs.add(chairs.remove(0)); 
    } 
    return chairs.get(0); 

Answer 3

有優雅的解析解：

讓我們的人民改變編號：＃2 - >＃1，＃3 - >＃2，...，＃1 - >＃100（在最後我們只需要減去1來「修復」結果）。現在第一個人仍然或離開。假設圈內只有64人。很容易看出，在第一次淘汰傳球后，剩餘的32人將繼續從第一名開始編號。所以最終只剩下＃1。

我們有100人。在36人離開這個圈子後，我們最終會有64人 - 而且我們知道如何解決這個問題。對於每個離開房間的人員，剩下一個人，所以64人的圈子將從1 + 2 * 36 =＃73（新＃1）開始。由於第一步改變索引，最終答案將是＃72。

一般情況下res = 2 *（N - closest_smaller_pow_2）= 2 * N - closest_larger_pow_2。該代碼是微不足道：

public static long remaining(long total) { 
    long pow2 = 1; 
    while (pow2 < total) { 
     pow2 *= 2; 
    } 
    return 2*total - pow2; 
} 

此外，該算法具有O（日誌（N））的複雜性，而不是O（N），所以這是可以計算出巨大的輸入函數（其可以容易地適合於使用的BigInteger代替長）。

Answer 4

首先，我們假設椅子從0開始編號。我們將在最後切換編號 - 但通常情況下，當項目從0而不是1枚舉時，事情會更簡單。

現在，如果你有n個人，並且你開始在椅子x（x是0或1）處消除，那麼一次通過你就可以消除一半的人。那麼你就會遇到大約一半的問題（可能還有一個問題），如果你解決了這個問題，你可以通過將該子結果乘以2並且可能加上一個結構來解決原始問題。

要對此進行編碼，只需要將4個案例（n個奇數或偶數對x 0或1）右對齊。這裏有一個版本，通過使用按位欺騙來獲得正確的4個案例。

public static long j2(long n, long x) { 
    if (n == 1) return 0; 
    return j2(n/2 + (n&x), (n&1)^x) + 1-x; 
} 

與來自1和不具有額外的參數編號爲椅子的溶液現在可以寫作：

public static long remaining(long n) { 
    return 1 + j2(n, 0); 
} 

此運行在O（log n）的時間，並使用O（log n）的存儲器中。

Answer 5

答案是31.這是三個不同的實現

var lastSurvivor = function(skip, count, chairs) { 
    //base case checks to see if there is a lone survivor 
    if (chairs.length === 1) 
     return chairs[0]; 
    //remove chairs when they are left/become dead 
    chairs.splice(skip, 1); 
    //increment the skip count so we know which chair 
    //to leave next. 
    skip = (skip + 1 + count) % chairs.length; 
    count++; 
    //recursive call 
    return lastSurvivor(skip, count, chairs); 
}; 

/** TESTS ******************************************************************* 
----------------------------------------------------------------------------*/ 

var result = lastSurvivor(0, 0, chairs); 
console.log('The lone survivor is located in chair #', result); 
// The lone survivor is located in chair # 31 




/** ALTERNATE IMPLEMENTATIONS *********************************************** 
----------------------------------------------------------------------------- 

/* Implemenation 2 
-----------------*/ 

var lastSurvivor2 = function(chairs, skip) { 
    skip++; 
    if (chairs === 1) 
     return 1; 
    else 
     return ((lastSurvivor2(chairs - 1, skip) + skip - 1) % chairs) + 1; 
}; 

/** Tests 2 *******************************************************************/ 

var result = lastSurvivor2(100, 0); 
console.log('The lone survivor is located in chair #', result); 
// The lone survivor is located in chair # 31 



/* Implemenation 3 
------------------*/ 

var chairs2 = []; 
for (var i = 1; i <= 100; i++) 
    chairs2.push(i); 

var lastSurvivor3 = function(chairs, skip) { 
    var count = 0; 
    while (chairs.length > 1) { 
     chairs.splice(skip, 1); 
     skip = (skip + 1 + count) % chairs.length; 
     count++; 
    } 
    return chairs[0]; 
}; 

/** Tests 3 *******************************************************************/ 

var result = lastSurvivor3(chairs2, 0); 
console.log('The lone survivor is located in chair #', result); 
// The lone survivor is located in chair # 31