. 사전식 숫자

386. 사전식 숫자

난이도:중

주제: 깊이 우선 검색, Trie

정수 n이 주어지면 사전순으로 정렬된 [1, n] 범위의 모든 숫자를 반환합니다.

O(n) 시간에 실행되고 O(1) 추가 공간을 사용하는 알고리즘을 작성해야 합니다.

예 1:

• 입력: n = 13
• 출력: [1,10,11,12,13,2,3,4,5,6,7,8,9]

예 2:

• 입력: n = 2
• 출력: 4
• 설명: [1,2]

제약조건:

• 1 4

해결책:

깊이 우선 검색(DFS)과 유사한 전략을 사용하여 접근할 수 있습니다.

주요 통찰력:

• 사전순은 본질적으로 루트 노드가 1에서 시작하고 각 노드에 숫자(0~9)를 추가하여 형성되는 최대 9개의 하위 항목이 있는 가상 n항 트리에 대한 선주문 순회입니다.
• 1부터 시작하여 반복적으로 숫자를 추가하여 주어진 n을 초과하지 않는 방식으로 선주문 순회를 시뮬레이션할 수 있습니다.

접근하다:

1. 숫자 1부터 시작하여 10을 곱하여 더 깊이 들어가 보세요(예: 다음 숫자와 다음 사전식 숫자).
2. 더 깊게(10을 곱하는 것) 불가능할 경우(예: n을 초과하는 경우) 숫자를 늘려서 10을 넘어 잘못된 점프가 발생하지 않도록 합니다(예: 19에서 20으로 증가).
3. 현재 번호를 더 이상 연장할 수 없는 경우 역추적하여 다음 유효한 번호로 이동합니다.
4. n까지의 ​​모든 숫자가 처리될 때까지 계속합니다.

이 솔루션을 PHP로 구현해 보겠습니다. 386. 사전식 숫자

<?php
/**
 * @param Integer $n
 * @return Integer[]
 */
function lexicalOrder($n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$n1 = 13;
print_r(lexicalOrder($n1));

$n2 = 2;
print_r(lexicalOrder($n2));
?>

설명:

• 현재 숫자를 유지하고 다음 사전순 숫자를 얻기 위해 10을 곱하여 최대한 깊이 들어가려고 노력합니다.
• 곱할 수 없는 경우(n을 초과하므로) 숫자를 늘립니다. 우리는 후행 0을 확인하고 이에 따라 현재 숫자를 조정하여 증분이 20, 30 등과 같은 숫자로 이어지는 경우를 처리합니다.
• 사전순으로 n까지의 모든 숫자를 추가할 때까지 루프가 계속됩니다.

예제 연습:

입력: n = 13

1. 1시부터 시작하세요.
2. 1에 10을 곱하기 -> 10.
3. 11, 12, 13을 추가하세요.
4. 2로 돌아가서 최대 9까지 계속 증가합니다.

산출:

[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]

입력: n = 2

1. 1시부터 시작하세요.
2. 2로 이동

산출:

[1, 2]

시간 복잡도:

• 1부터 n까지의 각 숫자는 정확히 한 번만 처리되므로 O(n)입니다.

공간 복잡도:

• O(1) 추가 공간이 사용됩니다(결과 배열에 사용된 공간 무시).

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 . 사전식 숫자의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!