Codewars 中的“Yes No Yes No”任务

Question

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)

Answer 1

你不能这样做，因为可能有重复的数字，比如一个示例案例。.arr.remove(j)[1,2,3,4,5,20,6,7,8,20]

我解决了这个问题，但是既然你提到了标签，答案可以是.javascriptalgorithmlanguage-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;

这意味着我们将前一个节点的值分配给当前节点的下一个节点，将下一个节点的前一个值分配给当前节点的前一个值。next

在迭代的第一步之后，我们的新（如修改后的）循环 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）

其中 是数组中的元素数。n

Answer 2

您可以使用 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]

它使用与队列类似的原理（屈服，跳过，旋转），但在数字的位上执行此操作，而不是移动数据结构中的实际元素。