大家好，我正在研究最長的子序列演算法，這個想法是從陣列中找到數字的子序列。我正在使用 Ruby，到目前為止我缺少子序列的最后一個數字，這是我的代碼：
def sequence_length1(array)
array.sort!
secuencia_mayor = []
array.each_with_index do |numero, indice|
numero 1 == array[indice 1] ? secuencia_mayor << numero : ''
end
return secuencia_mayor
end
p sequence_length1([100, 4, 200, 1, 3, 2]) #length=4
p sequence_length1([29, 27, 28, 55, 100, 84]) #length=3
代碼有一個錯誤：由于條件，最后一個元素永遠不會成為 secuencia_mayor 陣列的一部分，我的問題是：我應該在代碼中更改什么來克服這個問題？
非常感謝
uj5u.com熱心網友回復：
要使用您采用的方法，您需要在遍歷陣列元素時保存迄今為止發現的最長已知序列（或其起始索引和長度）。這是一種方法。
def sequence_length1(array)
array.sort!
secuencia_mayor = []
candidate = []
array.each do |numero|
if candidate.empty? || candidate.last 1 == numero
candidate << numero
else
secuencia_mayor = candidate.dup if candidate.size > secuencia_mayor
candidate = []
end
end
secuencia_mayor = candidate.dup if candidate.size > secuencia_mayor
secuencia_mayor
end
sequence_length1 [100, 4, 200, 1, 3, 2]
#=> [1, 2, 3, 4]
sequence_length1([29, 27, 28, 55, 100, 84]) #length=3
#=> [27, 28, 29]
另一種更類似于 Ruby 的方法是使用Enumerable#slice_when和Enumerable#max_by。
def seq(arr)
arr.sort.slice_when { |a,b| b != a 1 }.max_by(&:size)
end
seq [100, 4, 200, 1, 3, 2]
#=> [1, 2, 3, 4]
seq [29, 27, 28, 55, 100, 84]
#=> [27, 28, 29]
步驟如下。
arr = [100, 4, 200, 1, 3, 2]
c = arr.sort
#=> [1, 2, 3, 4, 100, 200]
enum = c.slice_when { |a,b| b != a 1 }
#=> #<Enumerator: #<Enumerator::Generator:0x00007fa9fd913238>:each>
d = enum.max_by(&:size)
#=> [1, 2, 3, 4]
通過將列舉數轉換為陣列，我們可以看到enum將生成并傳遞給的（三個）元素：max_by
enum.to_a
#=> [[1, 2, 3, 4], [100], [200]]
enum.max_by(&:size)是 的簡寫enum.max_by { |e| e.size }。
也可以使用slice_when的近親Enumerable#chunk_while：
[100, 4, 200, 1, 3, 2].sort.chunk_while { |a,b| b == a 1 }.max_by(&:size)
#=> [1, 2, 3, 4]
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/471195.html