-7

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)
4

2 回答 2

1

您可以通过交替弹出和轮换队列中的条目来使用双端队列（来自集合）来执行此操作：

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），但它是在数字的位上执行的，而不是在数据结构中移动实际元素。

于 2020-03-11T15:15:01.380 回答
1

You can't do arr.remove(j) because there can be duplicate numbers, say an example case as [1,2,3,4,5,20,6,7,8,20].

I solved this in javascript but since you mention algorithm tag, answers can be language-agnostic.

Approach:

We can create a circular doubly linked list of the given numbers. So, for [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], the list would look like: 

                                                                    _____
                                                                   |     | 
      both next and prev links(double arrow notation)              v     |
  -1 <--> 2 <--> 3 <--> 4 <--> 5 <--> 6 <--> 7 <--> 8 <--> 9 <--> 10 --  | prev link
 | ^                                                                  |  |
 | |_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _next link_ _ |  |
 |_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|

For each step, we add the current value of the node in iteration to result. Before moving on to the next to next node(because we skip in the middle), we would do below 2 steps:

  temp.prev.next = temp.next;
  temp.next.prev = temp.prev;

which means that we assign previous node's next value to next node of current node and next node's previous value to current node's previous value.

After first step of iteration, our new(as in modified) circular DLL would look like below:

                                 ______                                   
                                |      | 
    both next and prev link     v      |
  -2 <--> 4 <--> 6 <--> 8 <--> 10 --   |
 | ^                                |  |prev link
 | |_ _ _ _ _ _ _ _ _next link_ _ _ |  |
 |_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|

Likewise, you can generate how the list would look like for each step.

Snippet:

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']));

Time Complexity: O(n)

Space Complexity: O(n)

where n is number of elements in the array.

于 2020-03-11T11:16:57.153 回答