hackerrank 循环数组旋转 Python

Question

我试图解决HackerRank上的圆形数组旋转问题。https://www.hackerrank.com/challenges/circular-array-rotation/problem

以下代码传递除案例 #4 之外的所有测试用例，该用例会获得运行时错误。有人可以指出问题吗？

def circularArrayRotation(a, k, queries):
    if k < len(a):
        k = k
    elif k == len(a):
        k = 0
    else:
        k = k%a
    newList = []

    for val in queries:
        newInd = -k+val
        if abs(newInd) > len(a):
            newInd = newInd - (len(a)-1)
            newList += [a[newInd]]
        else:
            newList += [a[newInd]]        

    return newList

Answer 1

您的解决方案是正确的。但仅在该案例 4 的时限内运行。

您每次都会计算新查询的值，这需要时间。

您可以做的是一次获取旋转数组。 然后在旋转数组上运行查询。将结果保存在列表中并将其返回。

def circularArrayRotation(a, k, queries):
    new_arr = a[-k%len(a):] + a[:-k%len(a)]
    # list slicing is done here.  it will get the right rotated array 
    result = []
    for i in queries:
        result.append(new_arr[i])
        # running queries on rotated array
    return result

使用上述方法，列表切片在 O（n） 时间内完成，然后运行查询是 O（1） 时间。

Answer 2

def circularArrayRotation(a, k, queries):
    j= len(a)
    for x in range(k):
        n=a[j-1]
        a.insert(0,n)
        a.pop(j)
    newList= []
    for m in queries:
        newList.append(a[m])
    return newList

Answer 3

def circularArrayRotation(a, k, queries):
    #rotation
    for _ in range(k):
        a.insert(0, a.pop())
    #putting answer according to query
    ans = []
    for i in queries:
        ans.append(a[i])    
    return ans

Answer 4

好吧，

你可以使用deque deque是一个双端队列。它可用于从两端添加或删除元素。

from collections import deque
    def circularArrayRotation(a, k, queries):
        result=[]
        a = deque(a) 
        a.rotate(k) 
        a = list(a) 
        for v in queries:
            result.append(a[v])
        return(result)

Answer 5

我知道

这很老了，但我只是在解决这个问题，所以我想不妨顺便看看，你的其他情况是错误的！它应该是k = k % len(a)，你写了k % a，现在我写 c++，所以不知道它在 python 中有什么作用，但我很确定这不会自动放入len(a)此外，你为什么要费心把它放在if else块中，每次都只是模数，如果它更小，没有值变化，因为=>它把它固定在正确的值

Answer 6

我相信

deque是要走的方法，正如AnkushRasgon和shyamantha的回答一样。在这里，我用Java发布我的版本。所有测试均通过。

static int[] circularArrayRotation(int[] a, int k, int[] queries) {
    LinkedList<Integer> list = Arrays.stream(a).boxed()
            .collect(Collectors.toCollection(LinkedList::new));
    
    for (int i = 0; i < k; i++) {
        list.push(list.pollLast());
    }
    
    for (int i = 0; i < queries.length; i++) {
        if (queries[i] < list.size()) {
            queries[i] = list.get(queries[i]);
        }
    }
    
    return queries;
}

Answer 7

def circularArrayRotation(a, k, queries):
    reverse_a = list(reversed(a))
    reverse_a_copy = reverse_a.copy()
    for x in range(k):
        item = reverse_a[x]
        reverse_a_copy.remove(item)
        reverse_a_copy.append(item)
    line = []
    for x in queries:
        line.append(list(reversed(reverse_a_copy))[x])
    return line

Answer 8

a=[1,2,3,4,5]
s=2
def rotateList(arr,d,n):
  arr[:]=arr[d-1:n]+arr[0:d-1]
  return arr
print(rotateList(a,5,len(a)))

Answer 9

    for i in range(k):
        random_a = len(a)
        random_b = random_a - 1
        random_c = a.pop(random_b)
        a = [random_c] + a
    oz = a
    random_list = []
    for i in queries:
        z = oz[i]
        y = str(z)
        random_list.append(y)
    return random_list```
is this the correct answer