-2

我进行了演示测试，结果得分为 62。我猜我的代码效率不足以达到最高分 100。那么如何有效地找到子字符串中的最低字符代码？例如，字符串是s="ACGTTAGTAC". 有效地找出子字符串中的最小字符是什么s[p,q]- 有许多重复的查询具有相同s但不同的[p,q]. 实际上，这个问题被称为范围最小查询（RMQ），并且有不止一种算法可以解决这个问题。但是我很难理解并将它们应用于这个特定的实例。谁能建议如何修复代码？

# s is a string, p and q are arrays of integers with p[i] <= q[i]
def solution (s, p, q)
  len = s.length
  a = Array.new(len,0)
  for k in 0..len-1
    case s[k]
    when 'A'
      a[k] = 1
    when 'C'
      a[k] = 2
    when 'G'
      a[k] = 3
    when 'T'
      a[k] = 4
    end
  end
  s = []
  m = p.size
  for i in 0..m-1
    s << a[p[i]..q[i]].min
  end
  s
end

由于版权问题，完整的问题没有复制到这里。您可以从此链接https://codility.com/demo/results/demoHSB3XQ-R24/阅读完整的详细信息。

4

1 回答 1

2

您缩放解决方案的问题是因为您重复扫描每个查询的输入，生成子数组并直接查找最小值。当您有很多查询要处理时，这是低效的。例如，如果任何子字符串包含“A”，则包含该子字符串的字符串也包含“A”，但您的解决方案会丢弃该先验知识并重新计算。最终结果是您的解决方案不仅可以按输入字符串的大小进行缩放，而且可以将其乘以查询的数量。当s很长并且[p,q]也很长时，这会导致性能不佳。

您可以通过预处理s为旨在最有效地回答查询的索引结构来改进代码的缩放。发现要使用的正确结构是编码问题中挑战的重要部分。获得纯粹的“正确输出”代码只是完成了一半，因此 62/100 的分数指标似乎是有效的。

这是一个索引结构，可以有效地从固定字符串中找到给定索引范围内的最小字符。

首先将字符串分析为两部分索引

s = "AGTCTTCGATGAAGCACATG"
len = s.length

# Index to answer "what count of each character type comes next in s"
# E.g.  next_char_instance["A"][7]  returns the instance number of "A" that is
# at or after position 7  ( == 1 )
next_char_instance = Hash[ "A" => Array.new(len), "C" => Array.new(len), 
  "G" => Array.new(len), "T" => Array.new(len) ]

# Index to answer "where does count value n of this character appear in s"
# E.g.  pos_of_char_instance["A"][1]  returns the index position of 
# the second "A" ( == 8 )
pos_of_char_instance = Hash[ "A" => Array.new, "C" => Array.new, 
  "G" => Array.new, "T" => Array.new ]

# Basic building block during iteration
next_instance_ids = Hash[ "A" => 0, "C" => 0, "G" => 0, "T" => 0 ]

# Build the two indexes - O( N )
(0...len).each do |i|
   next_instance_ids.each do | letter, next_instance_id |
     next_char_instance[letter][i] = next_instance_id
   end
   this_letter = s[i]
   pos_of_char_instance[ this_letter ] << i
   next_instance_ids[ this_letter ] += 1
end

那是O( N )因为您已经迭代了一次字符串，所有其他效果（实际上）都是恒定的；好的，创建数组也是O( N )，但可能快 10 倍，如果你发现自己在思考O( 1.4 * N )，那么不要惊慌，在考虑纯粹的缩放问题时，你扔掉常数 1.4。

现在您有了这个索引，就可以真正有效地依次询问“该位置或之后的下一个 A（或 C 或 G）在哪里”，您可以使用它来快速找到特定范围内的最小字符。事实上，由于它将是固定成本查找和一些比较，它将O( 1 )针对每个查询，因此O( M )总体而言：

# Example queries
p = [ 0, 3, 2, 7 ]    
q = [ 6, 4, 2, 9 ]    

# Search for each query - O( M )
p.zip(q).map do | a, b |
  # We need to find lowest character possible that fits into the range
  "ACGT".chars.find do | letter |
     next_instance_id = next_char_instance[ letter ][ a ]
     pos_next_instance = pos_of_char_instance[ letter ][ next_instance_id ]
     true if pos_next_instance && pos_next_instance <= b
  end
end
# => ["A", "C", "T", "A"] is output for example data

我已经把它映射到字母，希望你能看到输出 1,2,3,4 是微不足道的。事实上，编号和基因组字母的使用是难题中的红鲱鱼，它们对解决方案没有真正的影响（除了生成仅 4 个字母的结构更容易编码为固定值）。

上述解决方案可能是众多解决方案之一。您应该注意，它依赖于要修复的允许字母的数量，并且不能作为在单个条目为整数或浮点数的范围内找到最小值的答案。

于 2013-11-22T14:20:11.037 回答