최소 경로 합 Leetcode 솔루션

문제 설명 최소 경로 합 LeetCode 솔루션 – "최소 경로 합"은 음이 아닌 정수로 구성된 주어진 anxm 그리드와 경로를 따라 모든 숫자의 합을 최소화하는 왼쪽 상단에서 오른쪽 하단까지의 경로를 찾아야 한다고 말합니다. . 우리는 움직일 수 밖에...

자세히보기

문자열 Leetcode 솔루션 디코딩

문제 설명 문자열 디코딩 LeetCode 솔루션 – "문자열 디코딩"은 인코딩된 문자열을 디코딩된 문자열로 변환하도록 요청합니다. 인코딩 규칙은 k[encoded_string]입니다. 여기서 대괄호 안의coded_string은 k가 양의 정수인 경우 정확히 k번 반복됩니다. 예: 입력: s = ”3[a]2[bc]” 출력: “aaabcbc” …

자세히보기

이진 트리를 연결 목록 LeetCode 솔루션으로 병합

이진 트리를 연결 목록 LeetCode 솔루션으로 병합 라고 말한다 – 주어진 root 이진 트리의 경우 트리를 "연결 목록"으로 병합합니다.

  • "연결된 목록"은 같은 것을 사용해야 합니다. TreeNode 클래스 right 자식 포인터는 목록의 다음 노드를 가리키고 left 자식 포인터는 항상 null.
  • "연결된 목록"은 다음과 같은 순서여야 합니다. 예약 주문 순회 이진 트리의.

 

예 1 :

이진 트리를 연결 목록 LeetCode 솔루션으로 병합입력:

 root = [1,2,5,3,4,null,6]

출력:

 [1,null,2,null,3,null,4,null,5,null,6]

예 2 :

입력:

 root = []

출력:

 []

예 3 :

입력:

 root = [0]

출력:

 [0]

 

알고리즘 –

아이디어 -

  • 이진 트리를 평면화하기 위해 먼저 왼쪽 하위 트리의 가장 오른쪽 요소를 찾고 가장 오른쪽 요소를 얻은 후 해당 노드의 오른쪽 포인터를 주어진 트리의 오른쪽 하위 트리와 연결합니다.
  • 2단계에서 루트 노드의 오른쪽 포인터를 왼쪽 하위 트리와 연결하고 왼쪽 하위 트리를 null로 설정합니다.
  • 3단계에서 루트 노드는 오른쪽 하위 트리 노드입니다. 이 노드에서 동일한 프로세스가 발생하고 모든 왼쪽 부분이 null이 될 때까지 프로세스가 계속 계속됩니다.

연결 목록 Leetcode 솔루션에 이진 트리 평면화 접근 방식 –

– 처음에는 while(root != null) 루프를 실행한 다음 두 개의 변수를 사용하여 왼쪽 하위 트리를 저장합니다.

– 그런 다음 while(k.left != null)을 사용하여 왼쪽 하위 트리의 가장 오른쪽 노드를 확인하고 (k.right = root.right)를 사용하여 해당 노드를 오른쪽 하위 트리와 연결합니다.

– 그런 다음 루트 노드의 오른쪽 포인터를 왼쪽 하위 트리(root.right = left)와 연결하고 루트 노드의 왼쪽 포인터를 null(root.left=null)로 설정하고 ( root = root.right ) 업데이트하므로 이제 루트가 오른쪽입니다. 하위 트리 노드.

– 이 프로세스는 모든 왼쪽 하위 트리 부분이 오른쪽 하위 트리가 될 때까지 계속됩니다. 따라서 이진 트리가 평평해집니다.

 

이진 트리를 연결 목록 LeetCode 솔루션으로 병합

이진 트리를 연결 목록 LeetCode 솔루션으로 병합

파이썬 솔루션:

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        while(root):
            
            if root.left:
                
                k = root.left
                temp = root.left
            
            
                while(k.right):
                    k = k.right
            
                k.right = root.right
            
                root.right = temp
            
                root.left = None
            
            root = root.right

자바 솔루션:

class Solution {
    public void flatten(TreeNode root) {       
        while (root != null) {
            if (root.left != null) {
                TreeNode k = root.left;
                TreeNode temp = root.left;
                while (k.right != null) k = k.right;
                k.right = root.right;
                root.right = temp;
                root.left = null;
            }
            root = root.right;
        }
    }
}

시간 복잡도: O(N)

공간 복잡성 : O (1)

한 번만 탐색했으므로 시간 복잡도는 o(n)입니다.

추가 공간을 사용하지 않았으므로 공간 복잡성은 o(1) 일정한 추가 공간이 됩니다.

비슷한 질문 – https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

삽입 삭제 GetRandom O(1) Leetcode 솔루션

문제 설명 Insert Delete GetRandom O(1) LeetCode 솔루션 – “Insert Delete GetRandom O(1)”은 O(1) 시간 복잡도에서 이 네 가지 기능을 구현하도록 요청합니다. insert(val): val을 무작위 집합에 삽입하고 요소가 처음에 집합에 없으면 true를 반환합니다. 다음과 같은 경우 false를 반환합니다.

자세히보기

홀수 짝수 연결 목록 Leetcode 솔루션

문제 설명 홀수 연결 목록 LeetCode 솔루션 – "홀수 연결 목록"은 비어 있지 않은 단일 연결 목록이 제공됨을 나타냅니다. 홀수 인덱스를 가진 모든 노드를 그룹화하고 짝수 인덱스를 가진 노드를 그룹화하고 재정렬된 목록을 반환해야 합니다. 둘 다 내부의 상대적 순서에 유의하십시오 ...

자세히보기

Two Numbers II Leetcode 솔루션 추가

문제 설명 두 개의 숫자 추가 II LeetCode 솔루션 – "두 개의 숫자 추가 II"는 비어 있지 않은 두 개의 연결 목록이 가장 중요한 숫자가 먼저 오고 각 노드가 정확히 한 숫자를 포함하는 두 개의 음이 아닌 정수를 나타냅니다. 두 숫자를 더하고 합을 다음과 같이 반환해야 합니다.

자세히보기

리더보드 Leetcode 솔루션 설계

문제 설명 The Design A Leaderboard LeetCode 솔루션 – "Design A Leaderboard"는 3가지 기능을 완료하도록 요청합니다. addScore(playerId, score): 주어진 플레이어의 점수에 점수를 추가하여 리더보드를 업데이트합니다. 플레이어가 없으면 리더보드에 해당 ID를 추가합니다. top(K): ...의 상위 합계를 반환합니다.

자세히보기

두 정수 나누기 Leetcode 솔루션

문제 설명 두 개의 정수 나누기 LeetCode 솔루션 – "두 개의 정수 나누기"는 두 개의 정수 피제수와 제수가 주어졌다고 말합니다. 피제수를 제수로 나눈 몫을 반환합니다. 32비트 부호 있는 정수 내에서 정수를 저장할 수 있는 환경을 다루고 있다고 가정합니다.

자세히보기

n Leetcode 솔루션의 k번째 인수

문제 설명 n Leetcode 솔루션의 k번째 인수: 두 개의 양의 정수 n과 k가 주어졌음을 나타냅니다. 정수 n의 인수는 n % i == 0인 정수 i로 정의됩니다. 오름차순으로 정렬된 n의 모든 인수 목록을 고려하고 이 목록에서 k번째 인수를 반환하거나 n이 k보다 작은 경우 -1을 반환합니다. 요인. 예 1: 입력: …

자세히보기

일일 온도 Leetcode 솔루션

문제 설명 The Daily Temperatures Leetcode 솔루션: 주어진 정수 온도 배열이 일일 온도를 나타내고, 대답[i]가 더 따뜻한 온도를 얻기 위해 i번째 날 이후에 기다려야 하는 일 수와 같은 배열 응답을 반환한다고 명시합니다. 이것이 가능한 미래의 날이 없다면 대신 answer[i] == 0을 유지하십시오. …

자세히보기

Translate »