BFS를 BFF로 만들기
이 박문은 무엇에 관한 것입니까?
BFS가 무엇인지 잘 알고 있습니다.그게 문제가 아니야.문제는 인코딩 문제를 해결할 때 BFS를 사용할 수 있느냐 하는 것이다.이 블로그는 BFS를 사용하는 인코딩 문제를 논의할 것이다.문제는 두 갈래 나무의 수평 순서에 집중되어 점차적으로 문제를 분해할 것이다.
그러나 만약 당신이 BFS에 대해 아무것도 모른다면 두려워하지 마세요!Vaidehi Joshi는 BFS에 관한 기사wonderful blog post를 썼습니다.사실 그녀는 깊이 우선 검색 (DFS) 에 관한 글을 쓴 적이 있다. another post of hers사실 그녀Base CS 블로그 시리즈의 모든 작품을 봐라.나는 그녀가 나를 도와 얼마나 많은 알고리즘과 데이터 구조를 배웠는지 강조할 수 없다.감사합니다. Vaidehi!
두 갈래 나무 레벨 순서 반복
문제: 두 갈래 나무를 정해 놓고, 한 개의 그룹을 채워서 그 나무의 등급을 표시한다.각 단계의 모든 노드의 값을 단독 하위 그룹에서 왼쪽에서 오른쪽으로 채워야 합니다.
대부분의 BFS 문제와 마찬가지로 큐를 사용하여 검색을 수행합니다.다른 한편, DFS 알고리즘은 일반적으로 스택과 반복을 이용하여 검색을 수행합니다.만약 창고와 대기열이 생소하다면, 이 useful resource 를 사용해서 진도를 가속화하세요.마찬가지로 나무에 녹이 슬면 이other useful resource를 사용해 속도를 높여라.
이 문제의 예상 결과는 쉽게 얻을 수 있을 것 같다.그것은 트리의 다른 단계를 대표하는 플러그인 그룹일 뿐이다.하위 그룹의 요소는 각 단계의 각 노드의 값을 포함합니다.
그러나 우리는 어떻게 해야만 결과를 얻을 수 있습니까?우리는 대열을 사용한다.Vaidehi는 BFS 게시물에서 한 단계의 노드가 연결되지 않아도, 이 단계의 모든 트리 노드를 대기열로 밀어넣고, 이 요소의 값을 하위 그룹에 추가하고, 하위 그룹은 주 그룹에 추가할 수 있다고 논의했다.
비밀 번호
이 문제를 해결하는 코드를 봅시다.코드를 통독하고 가능한 한 그것을 이해해라.그리고 우리는 그것을 완전히 이해할 수 있도록 한 걸음 한 걸음 볼 수 있다.
다음은 이 알고리즘이 채택한 절차입니다:
루트 노드를 대기열에 밀어넣기
가 대기열이 비어 있을 때까지 교체됩니다.이것은 더 많은 나무 노드가 없을 때
는 매번 교체할 때마다 대기열의 원소 수량을 통계해야 합니다.이것은 이 단계의 하위 그룹을 정확한 길이로 설정하고, 정확한 교체 횟수를 허용합니다
그리고 대기열에서 이 단계의 노드를 삭제하고 그 값을 하위 그룹에 추가
노드가 대기열에서 제거될 때 각 하위 노드를 대기열에 삽입
대기열이 비울 때까지 계속 이렇게 하세요
몇몇 삽화
나는 무엇이 유용한지 안다!차라리 우리가 삽화로 알고리즘에서 무슨 일이 일어났는지 이해하는 것을 돕는 것이 낫다
그림 a를 보십시오. 루트 노드가 대기열로 밀려납니다.이것은 코드의 20줄에서 발생했다.큐의 Java 구현에 익숙하지 않은 경우 docs를 참조하십시오.22 줄은 대기열의 노드 수를 추적하기 위한 가변 levelSize를 만들었습니다
그림 A
다음 단계는 levelSize와 같은 노드 수를 대기열 (25 줄) 에서 이동합니다.현재 levelSize=1.따라서 값이 1인 노드는 대기열에서 제거되고 하위 그룹(27줄)에 추가됩니다.그러나 이 노드가 떠날 때, 어떤 하위 노드가 있으면, 대기열에 추가됩니다. (29-32 줄)이것은 그림 B와 같습니다. 마지막으로 하위 그룹은 결과 목록에 추가됩니다. (34 줄)
그림 B
값이 1인 노드는 더 이상 대기열의 일부분이 아닙니다.현재, 그것의 하위 노드는 대기열에서 유일한 노드이다.이 원소들은 현재 안에 계산되어 있다.그림 C에서 levelSize가 현재 어떻게 2와 같은지 주의하세요
그림 C
현재, level Size=2시, 24줄의 for 순환은 대기열의 두 요소를 훑어볼 수 있도록 합니다.또한 23 줄에 levelSize 길이의 하위 그룹을 만들었습니다.값 2를 포함하는 노드와 값 3을 포함하는 노드가 대기열에서 삭제되어 결과 목록에 추가됩니다.그러나 그들이 떠날 때 2 아이와 3 아이는 대열에 추가되었다.그림 D와 같이
그림 D
노드 2와 3은 더 이상 대기열에 없습니다.노드 4, 5, 6, 7이 대기열에 있습니다.그것들은 계수되었다. levelSize=4.이것은 그림 E와 같다. 29-32번 줄 기억나?이 노드들은 하위 노드가 없다.그것들은 대기열에서 삭제되지만 하위 노드가 없기 때문에 대기열에 다른 노드를 추가하지 않습니다
그림 E
노드 4, 5, 6, 7이 삭제되어 결과 목록에 추가되었기 때문에 대기열에 노드를 추가하지 않았습니다.대기열이 비어 있습니다.이것은 21 줄의while 순환을 종료합니다.그림 F를 보십시오. 트리와 빈 대기열, 그리고 우리가 원하는 결과를 포함하는 충전 목록이 있습니다.너무 좋아요
그림F
출력:
Level order traversal: [[1], [2, 3], [4, 5, 6, 7]]
시간 복잡성
이 알고리즘의 시간 복잡도는 O(N)입니다."N"은 트리의 총 노드입니다.이것은 노드마다 한 번씩 반복하기 때문입니다
공간 복잡성
이 알고리즘의 공간 복잡도는 O(N)입니다.반환된 결과 목록에는 트리에 처음 포함된 총 노드 수(N)가 포함됩니다.또한 대기열에 O(N) 공간이 필요하다는 것을 잊지 마십시오.대기열에는 최대 N/2개의 노드가 포함되어 있지만 Big-O는 상수를 무시한다는 것을 기억하십시오. 따라서 O(N/2)는 사실상 O(N)과 유사하며 결과 목록의 공간 복잡도와 대기열의 공간 복잡도는 상쇄되지 않습니다.마지막 공간 복잡성은 O(N)
당신이 더 많은 큰 O 기교를 원한다면, 나는 아주 좋은 곳을 알고 있다start
알고리즘 수준 향상!
알고리즘과 데이터 구조는 매우 복잡하다.그들은 틀림없이 내가 그들의 요령을 터득할 수 있도록 시간이 필요할 것이다.하지만 이곳에는 좋은 자원이 있습니다. 저에게 가장 도움이 되는 자원을 공유할 의무가 있다고 생각합니다.만약 내가 당신에게 도움이 되는 내용을 빠뜨렸다면 반드시 댓글에
코딩 면접 해독 - 좋은 자원.정말 면접에서 올바른 마음가짐을 유지할 수 있게 해준다.그러나 때때로 나는 인코딩의 스타일이 사람을 곤혹스럽게 할 수도 있다고 생각한다.This repo 빈칸을 채우는 데 아주 잘했다
코딩 면접을 모색하는 것은 아무리 강조해도 부족하다.나는 많은 사람들이 언급한 것을 본 적이 없다.서로 다른 인코딩 도전 문제에 나타난 모델을 설명한다.발생할 수 있는 모든 서로 다른 알고리즘 문제의 큰 그림을 제공하는 데 매우 뛰어나다.봐봐here
어린 케빈 노튼 - 대단합니다.문제 해결에 뛰어나고 유용한 조언을 해주십시오
-
Base CS-Vaidehi Joshi는 알고리즘과 데이터 구조의 기초 지식을 논술하는 데 매우 잘했다.블로그 시리즈here를 참조하십시오.그녀도 podcast의 이름을 가지고 있는데, 나는 이것에 대해 칭찬을 아끼지 않는다
인코딩 도전 사이트 - 선택할 수 있는 사이트가 많습니다.HackerRank,CodeWars와Edabit 모두 인기가 많은 것 같다.개인적으로 사용합니다LeetCode.당신에게 어울리는 것을 찾으세요
악작극-모의 인터뷰!빠르면 빠를수록 좋다!Pramp 도움이 많이 됐어요
나는 이것이 유용하길 바란다.제 게시물을 읽어주셔서 감사합니다. 데이터 구조와 알고리즘을 배우는 데 행운을 빕니다
Reference
이 문제에 관하여(BFS를 BFF로 만들기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/danielleskosky/make-bfs-your-bff-4l2e텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
