circularArrayRotation算法ruby

idfiyjo8 于 2023-08-04 发布在 Ruby

关注(0)|答案(2)|浏览(81)

我使用的是hacker rank，我不明白为什么我的ruby代码只适用于20个测试用例中的一个。问题是：
John沃森知道一种称为对整数数组进行右循环旋转的操作。一个旋转操作将最后一个数组元素移动到第一个位置，并将所有剩余元素右移一位。为了测试夏洛克的能力，沃森向夏洛克提供了一个整数数组。Sherlock将执行旋转操作多次，然后确定给定位置处元素的值。
对于每个数组，执行若干次右循环旋转并返回给定索引处元素的值。
功能描述
在下面的编辑器中完成circularArrayRotation函数。
circularArrayRotation具有以下参数：

int a[n]：要旋转的数组
int k：旋转计数
int queries[1]：要报告的索引

退货
int[q]：m中请求的旋转a中的值
输入格式
第一行包含3个空格分隔的整数，n，k和q，整数数组中的元素数，循环计数和查询次数。第二行包含n空格分隔的整数，其中每个整数i描述数组元素a[i]（其中0 <= i < n）。q后续的每一行都包含一个整数queries[i]，这是a中要返回的元素的索引。
制约因素
样本输入0

字符串
样本输出0

2
3
1

型
下面是我的代码：

def circularArrayRotation(a, k, queries)
    q = []
    
    while k >= 1
        m = a.pop()
        a.unshift m
        k = k - 1
    end
    
    for i in queries do
     v = a[queries[i]]
    q.push v
    
    end 
    
    return q

end

型
它只适用于示例文本的情况下，但我不知道为什么。谢谢你能提供的任何帮助。

ruby

来源：https://stackoverflow.com/questions/70686162/circulararrayrotation-algorithm-ruby

2条答案

按热度按时间

q5iwbnjs1#

还没有运行任何基准测试，但这似乎是一个名为Array.rotate()的方法的工作：

def index_at_rotation (array, num_rotations, queries)
  array = array.rotate(-num_rotations)
  queries.map {|q| array[q]}
end

a = [1, 2, 3] 
k = 2
q = [0,1, 2]  

index_at_rotation(a, k, q)
#=>  [2, 3, 1]

字符串
也处理负旋转值和nil结果：

a = [1, 6, 9, 11]
k = -1
q = (1..4).to_a

index_at_rotation(a, k, q)
#=>  [9, 11, 1, nil]

型

赞(0）回复(0）举报 2023-08-04

brjng4g32#

我在你的代码中没有看到任何错误，但我想建议一种更有效的计算方法。
首先观察到，在q旋转之后，索引为i的元素将处于索引(i+q) % n。
例如，假设

n = 3
a = [1,2,3]
q = 5

字符串
然后在q旋转之后，数组将如下所示。

arr = Array.new(3)
arr[(0+5) % 3] = a[0] #=> arr[2] = 1
arr[(1+5) % 3] = a[1] #=> arr[0] = 2
arr[(2+5) % 3] = a[2] #=> arr[1] = 3
arr                   #=> [2,3,1]

型
因此我们可以写

def doit(n,a,q,queries)      
  n.times.with_object(Array.new(n)) do |i,arr|
    arr[(i+q) % n] = a[i]
  end.values_at(*queries)
end

doit(3,[1,2,3],5,[0,1,2])
  #=> [2,3,1]
doit(3,[1,2,3],5,[2,1])
  #=> [1, 3]
doit(3,[1,2,3],2,[0,1,2])
  #=> [2, 3, 1]
p doit(3,[1,2,3],0,[0,1,2])
  #=> [1,2,3]
doit(20,(0..19).to_a,25,(0..19).to_a.reverse)
  #=> [14, 13, 12, 11, 10, 9, 8, 7, 6, 5,
  #    4, 3, 2, 1, 0, 19, 18, 17, 16, 15]

的字符串
或者，我们可以观察到，在q旋转之后，索引j处的元素最初是索引(j-q) % n。
对于前面的示例，在q旋转之后，数组将为

[a[(0-5) % 3], a[(1-5) % 3], a[(2-5) % 3]]
  #=> [a[1], a[2], a[0]]
  #=> [2,3,1]

型
因此我们可以写成

def doit(n,a,q,queries)
  n.times.map { |j| a[(j-q) % n] }.values_at(*queries)
end

型

赞(0）回复(0）举报 2023-08-04

我来回答

circularArrayRotation算法ruby

2条答案

相关问题

热门标签

最新问答