연속 번호 시퀀스 찾기

번호 배열 배열에서 가장 긴 연속 번호 시퀀스를 찾는 방법은 무엇입니까? 각 숫자 배열은 결과 시퀀스에서 하나 또는 숫자를 나타냅니다. -연속 번호 시퀀스 찾기

예 ([]()는 자바 스크립트와 같은 배열을 나타내는)

[ 
    [1, 5, 6], 
    [7], 
    [22, 34], 
    [500, 550], 
    [60, 1], 
    [90, 100], 
    [243], 
    [250, 110], 
    [150], 
    [155], 
    [160] 
]

정확한 출력 될 것이다 : [1, 7, 22, 60, 90, 110, 150, 155, 160]

자세한 출력 :

가

1, -- index 1 all 1, 5 and 6 would match here, pick the smallest 
7, -- index 2 
22, -- index 3 
    -- index 4 skipped, the sequence would end here or wouldn't be the longest possible 
60, -- index 5 picked 60, because 1 wouldn't continue in the sequence 
90, -- index 6 
    -- index 7 skipped, the sequence would end here or wouldn't be the longest possible 
110, -- index 8 
150, -- index 9 
155, -- index 10 
160 -- index 11

출처

2011-10-31 Lukáš Novotný

는 당신이 "올바른 출력"을 얻었는지 설명 할 수 메모이 제이션와 재귀을 기반으로? 나는 어떤 패턴도 여기에서 보지 않는다. .. – NickLH

NickLH가 말했던 것. – Patrick87

@NickLH : {1,5,6} 중 하나만 사용할 수 있다는 점을 제외하고는 가장 길게 증가하는 서브 시퀀스처럼 보입니다. –

가능한 접근법이 사용하는 고려해야 할 첫 번째 하위 배열의 인덱스와 마지막 값을 매개 변수로 사용하는 동적 프로그래밍.

이

는 파이썬에서 솔루션

data = [[1, 5, 6], 
     [7], 
     [22, 34], 
     [500, 550], 
     [60, 1], 
     [90, 100], 
     [243], 
     [250, 110], 
     [150], 
     [155], 
     [160]] 

def longest(x0, i, _cache=dict()): 
    if i == len(data): 
     return [] 
    try: 
     return _cache[x0, i] 
    except KeyError: 
     best = longest(x0, i+1) 
     for x in data[i]: 
      if x >= x0: 
       L = [x] + longest(x, i+1) 
       if len(L) > len(best): 
        best = L 
     _cache[x0, i] = best 
     return best 

print longest(0, 0)

출처

2011-10-31 15:33:29 6502

연속 번호 시퀀스 찾기

답변

관련 문제