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]
제약조건:
해결책:
깊이 우선 검색(DFS)과 유사한 전략을 사용하여 접근할 수 있습니다.
주요 통찰력:
- 사전순은 본질적으로 루트 노드가 1에서 시작하고 각 노드에 숫자(0~9)를 추가하여 형성되는 최대 9개의 하위 항목이 있는 가상 n항 트리에 대한 선주문 순회입니다.
- 1부터 시작하여 반복적으로 숫자를 추가하여 주어진 n을 초과하지 않는 방식으로 선주문 순회를 시뮬레이션할 수 있습니다.
접근하다:
- 숫자 1부터 시작하여 10을 곱하여 더 깊이 들어가 보세요(예: 다음 숫자와 다음 사전식 숫자).
- 더 깊게(10을 곱하는 것) 불가능할 경우(예: n을 초과하는 경우) 숫자를 늘려서 10을 넘어 잘못된 점프가 발생하지 않도록 합니다(예: 19에서 20으로 증가).
- 현재 번호를 더 이상 연장할 수 없는 경우 역추적하여 다음 유효한 번호로 이동합니다.
- 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에 10을 곱하기 -> 10.
- 11, 12, 13을 추가하세요.
- 2로 돌아가서 최대 9까지 계속 증가합니다.
산출:
[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
로그인 후 복사
입력: n = 2
- 1시부터 시작하세요.
- 2로 이동
산출:
시간 복잡도:
-
1부터 n까지의 각 숫자는 정확히 한 번만 처리되므로 O(n)입니다.
공간 복잡도:
-
O(1) 추가 공간이 사용됩니다(결과 배열에 사용된 공간 무시).
연락처 링크
이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!
이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.
위 내용은 . 사전식 숫자의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!