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)
2 回答
慕容3067478
TA貢獻1773條經驗 獲得超3個贊
你不能這樣做，因為可能有重復的數字，比如一個示例案例。.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
夢里花落0921
TA貢獻1772條經驗 獲得超6個贊
您可以使用 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]
它使用與隊列類似的原理（屈服，跳過，旋轉），但在數字的位上執行此操作，而不是移動數據結構中的實際元素。
添加回答
舉報
0/150
提交
取消