좋은 스타일의 LeetCode 솔루션

이 문서는 알고리즘 및 데이터 구조 문제에 대한 초보자 친화적인 튜토리얼과 비디오 솔루션을 제공하는 리소스인 LeetCode-Solutions-in-Good-Style에 대한 포괄적인 개요를 제공하며, 명확한 코드, 자세한 설명 및 구축에 중점을 둔 구조화된 접근 방식을 제공합니다. 경쟁적인 코딩보다는 기본 개념에 대한 강한 이해.

LeetCode-좋은 스타일의 솔루션

설명: 대부분의 반 친구들처럼 나도 공부하고 요약하는 일을 동시에 합니다. 더 많은 정보를 공유하고 유용한 지식을 제공하도록 노력하겠습니다. 지속적인 지원에 감사드립니다.

안녕하세요 여러분, 이것은 "알고리즘 및 데이터 구조"에 대한 입문 튜토리얼입니다. 알고리즘에 대한 기초가 전혀 없는 학생과 알고리즘 대회를 준비하는 학생에게는 적합하지 않습니다. 제가 전달하고 싶은 요점은 명확한 논리로 코드를 작성했기 때문에 제가 작성한 코드는 엄격한 사고를 거쳐야 한다는 것입니다. 형식은 매우 표준적이고 개인적인 스타일이 아니며, 줄이기 위해 빈 줄이나 주석을 쓰지 않을 것입니다. 코드 줄 수. 여기 있습니다:

저를 웨이웨이라고 부르시면 됩니다. 제가 아는 질문에 대해서는 제 능력과 시간이 허락하는 한 최선을 다해 답변해 드리겠습니다. 제 시간에 답변을 드릴 수 없는 질문이 있으시면 제가 사이트에서 알림을 보지 못했기 때문일 수 있습니다. [email protected]으로 이메일을 보내주세요.

내가 녹화한 비디오 솔루션

2019년 9월부터 영상 솔루션 녹화를 시작했습니다. 처음에는 제가 이야기하고 싶은 내용을 여러 번 녹음하곤 했어요. 이제 지식 포인트를 설명할 때 축어적 초안을 작성하세요. 실제로는 소규모의 체계적인 강좌가 많이 축적되어 있어 모든 분들께 도움이 되었으면 좋겠습니다.

0. 알고리즘 초보 사용자가 LeetCode를 어떻게 사용할 수 있나요? 【유용한 정보 공유】

1. 시간복잡도와 공간복잡도

이 영상에서는 시간 복잡도가 점근적 개념이므로 역동적인 관점에서 이해해야 한다고 언급했습니다. 그리고 시간 복잡도의 엄격한 정의(극한 형식)를 설명하여 누구나 시간 복잡도 계산 규칙을 ​​이해할 수 있도록 합니다. 또한 다음과 같이 지적했습니다. 시간 복잡성은 프로그램의 실행 시간이 아닙니다. "시간을 위한 공간"을 사용해야 하며 "시간 복잡성"을 최적화하는 데 더 많은 주의를 기울여야 합니다.

2. 바이너리 검색

이 영상에서는 이진 검색 알고리즘을 작성하는 방법을 소개합니다. 비록 이진 검색에 대한 자세한 내용이 있지만, 올바른 문제 해결 아이디어를 익히고, 더 많이 연습하고, 부지런히 생각하고, 더 많은 요약을 만드는 한, 이진 검색 문제는 해결되지 않습니다. 더 이상 어려울 수 있습니다.

다음 영상에서는 이진 검색의 몇 가지 예시 질문을 설명합니다. 질문의 의미를 분석하고 질문에 제공된 조건을 사용하여 검색 범위를 점차 좁히는 방법에 중점을 둡니다.

"Likou"(두 개의 양수 배열의 중앙값 찾기)의 질문 4 분석을 통해 이 기술을 소개했습니다. 찾고 있는 대상 요소의 속성이 더 복잡한 경우 이 속성을 반전시킬 수 있습니다. , 그리고 문제 범위를 쉽게 줄일 수 있는 논리문을 작성하세요.

3. 정렬 관련 문제

"병합 정렬"과 "빠른 정렬"은 매우 중요한 정렬 알고리즘입니다. 이에 대한 깊은 이해는 "재귀" 기능의 작동 메커니즘을 이해하는 데 매우 도움이 되는 동시에 "분할 및 정복" 사고의 전형적인 응용이기도 합니다. ". "역순쌍"과 "네덜란드 국기 문제(색상 분류)"도 매우 고전적인 알고리즘 문제입니다.

"역순 쌍"을 계산하는 것은 전적으로 "병합 정렬" 개념에 기초합니다.

"색상 분류" 문제에 대한 설명에서 우리는 코드를 작성하는 과정에서 "프로그램 실행 전"과 "실행 중"에서 사용되는 변수의 의미를 항상 준수해야 하는 "루프 불변성"을 도입했습니다. "실행이 종료된" 후에도 변경되지 않습니다. "루프 불변성"에 대한 자체 정의를 준수하는 것은 올바른 코드를 작성하는 중요한 방법입니다.

"첫 번째 누락된 양수"는 고전적인 알고리즘 문제입니다. 사용된 아이디어는 "버킷 정렬" 알고리즘(당근 1개, 구덩이 1개, 버킷 1개)의 특수 적용으로 이해될 수 있는 "내부 해싱"입니다. 요소를 저장합니다. 이렇게 할 수 있다는 사실은 입력 배열 요소의 값과 밀접한 관련이 있다는 점을 강조하고 싶습니다.

4. 슬라이딩 윈도우

"슬라이딩 윈도우" 문제는 코딩 및 디버깅 능력을 테스트하는 "루프 불변"을 적용하여 해결되는 일반적인 문제입니다.

5. 스택 관련 문제

"스택"을 사용하여 해결된 문제는 특정 예를 사용하여 문제 해결이 "후입 선출" 규칙과 일치하는지 확인해야 합니다.

다음 두 가지 질문을 익히는 것은 구체적인 예를 연구하고 일반적인 규칙을 요약하는 것과 분리될 수 없습니다.

"스택"의 가장 널리 사용되는 응용 프로그램 중 하나는 "재귀", "깊이 우선 탐색" 및 "분할 및 정복 알고리즘"에 대한 데이터 구조 지원입니다.

6. 통합검색

"Union Search Set" 데이터 구조는 현재 인터뷰에서 거의 사용되지 않습니다. 알고리즘 인터뷰를 준비하는 경우 건너뛸 수 있습니다.

7. 나무

많은 트리 문제는 "깊이 우선 순회" 또는 "너비 우선 순회"를 사용하여 해결할 수 있습니다.

8. 역추적 알고리즘

"역추적 알고리즘"은 실제로 질문에 포함된 "트리 구조"의 깊이 우선 순회입니다. 이런 유형의 문제를 풀 때는 메모지에 트리 구조 다이어그램을 그리는 것이 중요합니다.

9. 동적 프로그래밍

10. 너비 우선 순회 및 위상 정렬

11. 해시 테이블

12. 비트 연산 관련

내 개인 웹사이트 및 알고리즘 연구 노트

위챗 그룹과 QQ 그룹

질문을 함께 해결할 친구가 필요하다면 WeChat 그룹과 QQ 그룹에 가입할 수 있습니다.

마이리트북

다음은 저를 위한 프로모션입니다. 저는 최근 "LeetBook": Learning Algorithms from Zero(이전에는 "LeetCoin"을 사용한 알고리즘 및 데이터 구조 학습)"에서 나만의 LeetBook을 출시했습니다. 제로 기초 알고리즘과 데이터 구조에 대한 기본 지식을 설명합니다.

설명하다:

LeetBook의 처음 두 장은 무료로 읽을 수 있습니다. 다음 장은 비회원 가격이 99위안이고 현재 보고 있는 홈페이지 디렉토리는 69위안입니다. LeetBook과 동일합니다. 추가 부분만 해당됩니다.

LeetBook의 강좌 제목, 예제, 연습 및 지원 코드 저장소(현재 보고 있는 저장소)는 완전히 공개됩니다. LeetBook에서 디자인된 콘텐츠(연습 포함)를 이미 마스터한 경우 구매를 권장하지 않습니다.

투자되는 에너지는 차트 작성 시 LeetBook이 좀 더 자세하게 작성한다는 점만 제외하면 일반적인 솔루션 작성과 동일합니다. 유료 콘텐츠는 튜토리얼 제작에 소요되는 시간과 에너지, 제작 및 리뷰에 "Likou" 직원 및 전문가의 참여로 독서 경험이 더 좋아질 것입니다. 나는 보통 LeetBook보다 문제 해결 지식 포인트를 더 많이 쓴다는 점을 배제하지 않습니다.

중급 및 고급 사용자는 주의해서 구매하시기 바랍니다.

"Likou" 사이트나 저의 다른 소셜 계정에서 강좌 내용에 대해 저에게 상담하실 수도 있고, 이 창고에 문제를 제출하실 수도 있습니다. 강좌 구매 여부에 관계없이 제가 알고 있는 질문(시간이 허락하고 능력 내에서)에 최선을 다해 답변해 드리겠습니다. 저에게 지속적인 지원을 해주신 모든 분들께 감사드립니다. 제안이나 의견이 있으면 누구나 저와 소통할 수 있습니다.

내가 설명하는 지식은 내가 모든 사람에게 추천한 책, 내가 쓴 블로그, 문제 해결 방법, 노트에 항상 공유되며, 시간과 에너지가 있는 한, 계속 공유하고 Q&A하겠습니다.

저에게 강좌를 수강할 수 있는 기회를 주시고 작은 소망을 이루도록 도와주신 "Likou"에게 매우 감사드립니다.

"르코우" 분류 및 문제 해결 디렉토리 (LeetBook 장별로 정리, 16장 이후는 현재 LeetBook에 포함되지 않은 장입니다)

참고: 질문 범주는 내 LeetBook 장에 해당합니다.

1장 시간 복잡도

시간 복잡도의 개념을 소개하는 부분입니다. [영상해설]을 완전 무료로 시청하실 수 있습니다. 이 장에는 연습문제가 없습니다.

2장 이진 검색

질문 유형 1: 두 지점에서 아래 첨자를 찾으세요

설명하다:

관행:

질문 유형 2: 2포인트 범위의 정수를 결정합니다(2포인트 답변).

알고리즘적 사고: 줄이고 정복하세요. 질문에서 정수를 찾아야 하고 이 정수에 특정 범위가 있는 경우 이진 검색을 통해 점차 범위를 좁히고 마지막으로 숫자에 접근할 수 있습니다.

질문 유형 3: 복소 판별 함수(최대화 문제)

참고: 이 유형의 질문은 본질적으로 "질문 유형 2"(2점 답변)이지만 처음 배울 때 약간 혼란스러울 수 있습니다. 이 유형의 질문도 같은 방식으로 질문됩니다. 키워드는 "연속"과 "양의 정수"입니다.

3장 기본 정렬 알고리즘

이 부분에는 선택 정렬, 삽입 정렬, 힐 정렬, 버블 정렬의 네 가지 기본 정렬 알고리즘이 포함되어 있습니다.

"Likou" 질문 912: 정렬된 배열에 대한 솔루션: 정렬 문제에 대한 몇 가지 핵심 사항과 학습 자료를 요약합니다. 정렬 문제부터 알고리즘 학습을 시작할 수 있습니다.

배열 문제는 프로그래밍 언어에 대한 기본 지식을 숙지해야만 풀 수 있는 문제이기 때문에 알고리즘의 "초보 분야"로 사용될 수 있습니다. 관련 데이터 구조와 알고리즘 지식을 배우지 않았더라도 다음 문제에 대한 해결책은 쉽게 생각할 수 있습니다.

지식 포인트: 루프 불변성

4장 고급 정렬 알고리즘(중요)

이 부분에서는 병합 정렬, 빠른 정렬, 힙 정렬의 세 가지 고급 정렬 알고리즘을 익히는 데 중점을 두어야 합니다.

설명하다:

5장 비비교 정렬(선택 사항)

이 부분에는 비비교 정렬의 세 가지 유형인 개수 정렬, 기수 정렬, 버킷 정렬이 포함되어 있습니다. 이러한 문제를 해결하려면 내부 해싱의 개념을 이해해야 합니다.

6장 슬라이딩 윈도우와 이중 포인터

1. 슬라이딩 윈도우

슬라이딩 윈도우의 참조 작성 방법(템플릿이 아닙니다. 그대로 복사하지 마십시오. 참고용일 뿐이므로 알고리즘 설계 아이디어를 이해하는 것이 더 중요합니다):

친절한 알림: 질문 3과 76은 귀하가 반드시 할 수 있어야 하는 기본 질문입니다. 위의 질문을 완벽하게 이해하고 나면 다음 질문에 더 쉽게 답할 수 있습니다.

주요 질문:

설명하다:

관행:

설명하다:

질문 209: 질문에 제공된 핵심 정보: 배열의 모든 요소는 양의 정수입니다. 방법은 총 3가지가 있습니다.

방법 1: 폭력적인 해결책

방법 2: 슬라이딩 윈도우(슬라이딩 윈도우를 사용할 수 있는 이유 분석)

방법 3: 접두사와 배열을 구성한 다음 이진 검색을 사용합니다.

질문 438: 질문 76과 동일합니다.

질문 567: 한정된 문장의 모음이 다르다는 점을 제외하면 질문 76과 동일합니다.

2. 이중 포인터

"이중 포인터" 문제는 실제로 순진한 알고리즘을 최적화한 것입니다. 문제의 의미를 충족하지 못하는 많은 솔루션이 한 번에 정리됩니다. "슬라이딩 윈도우" 기술도 마찬가지입니다. 이중 포인터를 사용할 수 있는 이유를 분석하는 것이 여전히 더 중요합니다.

아래 첨자를 찾는 데 사용되는 이진 검색 알고리즘도 이중 포인터 솔루션으로 간주될 수 있습니다.

7장 연결리스트

연결리스트 문제를 해결하는 매우 실용적인 기술은 "그리기"입니다. 다른 알고리즘 문제에 대한 분석 및 설명(면접관에게 설명)도 마찬가지입니다.

디버깅을 용이하게 하기 위해 연결된 목록에 대한 테스트 함수를 작성할 수 있습니다. 권장되는 구현 방법은 다음과 같습니다. ① 배열을 통해 단일 연결 목록을 만듭니다. ② 현재 노드를 기반으로 현재 노드와 후속 노드를 인쇄합니다. 이 두 가지 방법은 연결된 목록과 관련된 프로그램을 디버그하는 데 매우 편리하게 도움이 될 수 있습니다.

질문 유형 1: 기본 연결 목록 포인터 포인팅 문제

참고: 일부 문제에서는 연결된 목록의 첫 번째 노드에 대한 복잡한 분류 논의 논리를 피하기 위해 "가상 헤드 노드"를 사용해야 합니다. 우리는 "센티넬"이라고 불리는 배열에서 이 아이디어를 보았습니다.

재귀 함수를 사용하면 포인터 변수를 변경하는 복잡한 작업을 피하여 문제 해결을 간단하게 만들 수 있습니다.

설명하다:

질문 유형 2: 빠르고 느린 포인터 기술

정확히 말하면 "동기화 포인터"라고 부르는 것이 더 나을 수도 있습니다.

두 개의 포인터 변수를 사용하면 둘 다 처음에 연결된 목록의 첫 번째 노드에 위치합니다. 하나는 항상 한 번에 한 단계만 수행하고 다른 하나는 항상 한 번에 두 단계만 수행합니다. 뒤로, 동시에. 이런 식으로 빠른 포인터가 이동을 마치면 느린 포인터가 연결 리스트의 중간 위치에 도달합니다.

이러한 문제를 해결하기 위한 일반적인 특징은 두 개의 포인터 변수를 사용하여 동기적으로 이동하는 것입니다. 빠른 포인터와 느린 포인터는 같은 방향으로 움직이며, 두 단계 사이의 "차이"는 일정합니다. 이러한 확실성을 바탕으로 연결 목록의 일부 문제를 해결할 수 있습니다. 이 아이디어를 사용하면 연결 목록의 다음 문제를 해결할 수도 있습니다.

설명하다:

질문 유형 3: 데이터 구조 설계

8장. 스택과 큐

1. 스택

질문 유형 1: 스택을 사용하여 해결되는 기본 문제

다음 질문은 매우 기본적이므로 숙지해야 합니다.

관행:

질문 유형 2: 단조로운 스택

단조로운 스택은 사용 중에 "후입선출" 원칙을 준수하는 일반적인 스택이며 스택의 요소는 단조롭습니다. "단조 스택"과 "단조 대기열"의 문제는 일반적으로 매우 특별합니다. 예제와 몇 가지 연습을 익히십시오.

경험: 첨자는 일반적으로 단조로운 스택에 저장됩니다.

설명하다:

관행:

2. 대기열

질문 유형 1: 대기열을 사용하여 해결된 기본 문제

너비 우선 순회 사용 대기열을 사용하여 모든 문제가 해결되었습니다.

질문 유형 2: 단조로운 대기열

단조 대기열은 단지 일반적인 대기열입니다. 이 문제는 현재 "Likou"의 단조로운 대기열에서 발견됩니다. 핵심은 설계된 알고리즘이 대기열을 단조롭게 만드는 이유를 명확하게 분석하는 것입니다. 또한 "Knapsack Problem"에는 최적화를 위해 단조로운 대기열을 사용하는 예가 있습니다. 관심 있는 친구들은 이에 대해 배울 수 있습니다. 이것이 바로 경쟁 지식입니다.

경험: 첨자는 일반적으로 단조로운 대기열에 저장됩니다.

9장 우선순위 큐

참고: "우선 순위 큐"로 "힙"의 구현을 이해하는 것이 필요합니다. 이는 힙을 사용할 때 더 효율적이도록 제거() 및 교체()의 코딩 세부 사항을 이해하는 데 도움이 됩니다.

적용: "동적"의 의미를 이해하는 데 중점을 두고 현재 대기열에서 우선순위가 가장 높은 요소를 동적으로 선택합니다.

10장: 결합 검색

그리고 990번 문제 풀이 영상 속 지식 포인트에 대한 [영상 설명]을 확인해보세요. 기본적이고 일반적인 질문은 다음과 같습니다.

선택적인 질문:

11장 트리(이진 트리 및 이진 검색 트리)

12장 역추적 알고리즘

질문 유형 1: 기본적인 역추적 문제

이러한 질문을 통해 역추적 알고리즘의 개념을 이해할 수 있으며, 역추적 알고리즘의 지식 포인트는 "Likou"의 질문 46의 비디오 솔루션과 텍스트 솔루션에 설명되어 있습니다.

역추적은 깊이 우선 순회를 사용하여 트리(그래프)의 모든 솔루션을 검색하는 것입니다. 깊이 우선 순회는 명백한 재귀 구조를 가지고 있습니다.

다음 문제 해결을 위한 팁: ① 그리기, 그리기, 그리기, ② 깊이 우선 순회 및 재귀 이해하기, ③ 더 많이 디버깅하기.

질문 유형 2: 문자열 역추적 문제

이해해야 할 핵심 사항: 문자열은 매번 새로운 문자를 생성하므로 상태를 재설정할 필요가 없습니다.

질문 유형 3: 홍수 채우기

질문 유형 4: 일부 게임 질문

설명하다:

13장 동적 프로그래밍(1부)

동적 프로그래밍의 두 가지 중요한 아이디어:

동적 프로그래밍에 대한 두 가지 사고 방향:

동적 프로그래밍을 사용하여 문제를 해결하려면 세 가지 조건이 충족되어야 합니다.

동적 프로그래밍의 두 가지 중요한 개념:

질문 분류 참조:

참고: 아래의 일반적인 질문이 추가됩니다(2020년 12월 2일).

1. 시작하기

"하향식" 메모리 재귀와 "상향식" 재귀의 두 가지 동적 프로그래밍 방법을 이해합니다.

2. 반복되는 하위 문제

이 부분에서는 "단계 계산 곱셈 원리"와 "범주 계산 덧셈 원리"를 사용해야 합니다.

질문 70: 피보나치 수열과 같은 질문입니다. 계산 문제는 분류 계산 원리와 단계 계산 원리를 사용합니다.

3. 최적의 하부구조

설명하다:

질문 377: 검사는 배낭 문제가 아니라는 점에 유의하세요.

4. 후유증이 없다

관행:

다음은 몇 가지 고전적인 "동적 프로그래밍" 문제입니다. 이러한 문제는 매우 중요하므로 별도의 범주에 포함됩니다.

5. 최대 하위 세그먼트 합계

관행:

6. 가장 긴 상승 부분 수열

참고: 300번 문제는 매우 고전적인 동적 프로그래밍 문제입니다. $O(N log N)$의 해는 문제 자체의 특성에 따라 상태를 정의하고, 상태 배열이 순서 배열임을 증명하여 시간 복잡도를 줄인다.

관행:

7. 가장 긴 공통 부분 문자열

8. 간격 DP와 분할 DP

간격 DP:

파티션된 DP:

9. 트리 DP

14장 동적 프로그래밍(2부)

1. 배낭 문제

배낭에 관한 9개의 강의: https://github.com/tianyicui/pack

("게임 유형 DP", "상태 압축 DP", "디지털 DP" 등이 추가됩니다.)

기타 질문

15장 탐욕 알고리즘

17장 해시 테이블

18장 접두사 합계와 해시 테이블

19장 너비 우선 순회

트리의 너비 우선 순회에 대한 몇 가지 문제와 LeetBook의 몇 가지 문제입니다.

20장 그래프 이론 알고리즘(최소 스패닝 트리)

21장 그래프 이론 알고리즘(단일 소스 최단 경로)

22장 분할 정복 알고리즘

분할 및 정복(분할 및 정복)이라는 개념은 더 큰 문제를 동일한 유형의 여러 개의 작은 하위 문제로 분할한 다음 이러한 하위 문제를 반복적으로 해결합니다. 원래 문제가 얻어졌습니다.

분할정복 알고리즘은 병렬적으로 수행될 수 있으나, 기본 알고리즘 분야에서는 분할정복 알고리즘이 깊이우선 순회 방식으로 수행된다.

분할 정복 아이디어를 적용한 일반적인 알고리즘: 병합 정렬, 빠른 정렬.

분할 정복 사고의 전형적인 문제: "검의 질문 51번 제안": "검의 질문 51번 제안" 51. 배열의 역순 쌍(비디오 설명).

기타 일반적인 질문(추가 예정)

계속 업데이트될 예정이며 친구들의 귀중한 피드백을 환영합니다!