https://www.codewars.com/kata/573c84bf0addf9568d001299/train/python
任务：
"编写一个代码，接收一个数字或字符串数组，在取出一个值的同时逐个遍历，留下一个值，取出，离开，然后再回到开头，直到所有值都出来
这就像一群人决定每一个人都会离开，直到最后一个人出现。因此，如果数组的最后一个元素被占用，那么仍然存在的第一个元素将保留。
该代码返回一个新的重新排列的数组，数组中的取值按顺序排列。始终取初始数组的第一个值。">
示例：
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
// returns [1, 3, 5, 7, 9, 2, 6, 10, 8, 4]
var arr = ['this', 'code', 'is', 'right', 'the']
// returns ['this', 'is', 'the', 'right', 'code']
我的代码是：
def yes_no(arr):
arr1 = []
if len(arr) == 0:
return arr1
for i in range(len(arr)):
if i % 2 == 0:
arr1.append(arr[i])
for j in arr1:
arr.remove(j)
yes_no(arr)
不能执行arr.remove(j)，因为可能存在重复的数字，例如[1,2,3,4,5,20,6,7,8,20]。
我在javascript中解决了这个问题，但由于您提到了algorithm标签，所以答案可以是language-agnostic。
方法：
我们可以创建一个给定数字的循环双链表。因此，对于[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，列表看起来像：
_____
| |
both next and prev links(double arrow notation) v |
-1 <--> 2 <--> 3 <--> 4 <--> 5 <--> 6 <--> 7 <--> 8 <--> 9 <--> 10 -- | prev link
| ^ | |
| |_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _next link_ _ | |
|_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|
对于每个步骤，我们将迭代中节点的当前值添加到结果中。在移动到下一个节点之前(因为我们在中间跳过(，我们将执行以下2个步骤：
temp.prev.next = temp.next;
temp.next.prev = temp.prev;
这意味着我们将上一个节点的CCD_ 7值分配给当前节点的下一个节点。
在迭代的第一步之后，我们新的(如修改后的(循环DLL将如下所示：
______
| |
both next and prev link v |
-2 <--> 4 <--> 6 <--> 8 <--> 10 -- |
| ^ | |prev link
| |_ _ _ _ _ _ _ _ _next link_ _ _ | |
|_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|
同样，您可以生成每个步骤的列表外观。
代码段：
function yesNo(arr) {
var result = [];
var head = null,
temp = null;
for (var i = 0; i < arr.length; ++i) {
if (head == null) {
head = createNode(arr[i]);
temp = head;
} else {
var temp2 = createNode(arr[i]);
temp.next = temp2;
temp2.prev = temp;
temp = temp2;
}
}
temp.next = head;
head.prev = temp;
temp = head;
while (temp.next != temp) {
result.push(temp.value);
temp.prev.next = temp.next;
temp.next.prev = temp.prev;
temp = temp.next.next; // skip next and go to next to next
}
result.push(temp.value);
return result;
}
function createNode(val) {
return {
value: val,
prev: null,
next: null
};
}
console.log(yesNo([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])); console.log(yesNo(['this', 'code', 'is', 'right', 'the']));时间复杂性：O(n(
空间复杂性：O(n(
其中CCD_ 8是阵列中的元素的数目。
您可以使用deque(来自集合(通过交替弹出和旋转队列中的条目来实现这一点：
from collections import deque
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
result = [ (q.popleft(),q.rotate(-1))[0] for q in [deque(arr)] for _ in arr]
输出：
[1, 3, 5, 7, 9, 2, 6, 10, 8, 4]
您还可以创建一个函数，以正确的顺序计算索引，并返回这些索引处的元素：
def skipOrder(arr,skipBy=1):
N = len(arr)
b = 2**N-1 # bits of unskipped posiitons
pos = skip = 0 # current position and skip cycle
while b:
if b&1: # remaining position
if not skip: # yield and clear if not skipped
b ^= 1
yield arr[pos]
skip = (skip+1)%(skipBy+1) # cycle skipping
b = ((b&1)<<(N-1)) | (b>>1) # rotate positions bits
pos = (pos+1)%N # and index
result = list(skipOrder(arr)) # [1, 3, 5, 7, 9, 2, 6, 10, 8, 4]
它使用了和队列类似的原理(yield、skip、rotate(，但它是对数字的位执行的，而不是移动数据结构中的实际元素。