CodeWars 題目

Link

難度

5 kyu

題目

這是頗有歷史的邏輯、或者說是數學題。

以下內容摘自wiki：

1. 人們站在一個等待被處決的圈子裡。
2. 計數從圓圈中的指定點開始，並沿指定方向圍繞圓圈進行。
3. 在跳過指定數量的人之後，處刑下一個人。
4. 對剩下的人重複該過程，從下一個人開始，朝同一方向跳過相同數量的人，直到只剩下一個人，並被釋放。

Wiki Link

思路

程式的參數 items 是陣列，也就是人們所站著的「圈子」；k 表示跳過指定數量的人後，下一個要處刑。但是參照題目所提供的範例：

[1,2,3,4,5,6,7]
[1,2,4,5,6,7]
[1,2,4,5,7]
[1,4,5,7]
[1,4,5]
...依此類推

這裡題目給出的 k=3，但實際上並非「跳過指定數量 k」，而是「第 k 個人被處刑」。

「圈子」表示這個陣列會頭尾相接的一直循環，直到剩下最後一個值；但本題目要求的是一個個被移出陣列後的元素，以此為順序產生的另外一個陣列。

利用變數紀錄要 push 的第 k 個元素，filter 重複過濾陣列，直到 items 被清空為止。

pseudo code

result = []
start = 1

while loop items.length > 0
items.filter(item =>{
	if(start === k) push(item)
	else
	start++;
})

實作

function josephus(items, k) {
   if (k === 1 || items.length < 1) return items;
   let result = [];
   let start = 1;
  
   while (items.length > 0) {
     items = items.filter((item) => {
       if (start === k) {
         result.push(item);
         start = 1;
         return false;
       } else {
         start++;
         return true;
       }
     });
   }
   return result;
}

當 k = 1，或者 items 為空陣列；前者是直接從頭被序列 push 到尾，後者是直接回傳空陣列，因此開頭先寫 if 的判斷條件，直接返回 items。

result 儲存陣列元素的新順序，start 從 1 開始計數。

filter 判斷目前 start 是否已經到 k，如果已經到達 k，則把元素 push 到 result，start 重新回到 1 計數，並回傳 false 給 filter 表示該元素要被過濾掉。

如果 start < k，則繼續累加 start 並且回傳 true 表示該元素要保留。
最後 items.length 等於 0 達到 while loop 停止條件，輸出 result 即為解答。

他人的解法

function josephus(items, k){
  var result = [], index = 0;
  while (items.length > 0){
    index = (index + k - 1) % items.length;
    result = result.concat(items.splice(index, 1));
  }
  return result;
}

index 表示要被移除的陣列索引，從 0 開始計數，(k - 1) 是「跳過指定 k - 1 數量」。

以 [1,2,3,4,5,6,7]，k = 3 為例：

index = 0, k-1 = 2, length = 7 => 2
index = 2, k-1 = 2, length = 6 => 4
index = 4, k-1 = 2, length = 5 => 1
...依此類推

由於這個陣列是以圓圈為概念，並且會隨著循環而縮減，取餘的用意是確保當索引到達陣列尾時會回到開頭。
(index + k - 1) 這段，作用是計數要相隔的元素與被刪除的元素本身，例如 length = 5，(index + k - 1) = 6，想像成 1 - 5 的序列數六次，最後一次從頭開始數到 1，也就是取餘。

splice 會回傳被移除的值，利用 concat 從空陣列拼接，其實也雷同於 result.push 的作用。

心得

第十五天！