Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

example Input: s = ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()".

Solution

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        res=0
        cur=0 #most important variable
        stk=[]

        for c in s:
            if c=="(":
                stk.append(cur) 
                cur=0
            elif c==")":
                if stk:
                    cur=stk.pop()+cur+1 #important
                    if cur>res:
                        res=cur
                else:#don't forget to initialize cur unable to make a  pair.
                    cur=0

        return res*2

이 풀이에서 가장 중요한 개념은 variable cur이다. 우선 open parenthese의 개수를 level로 생각하였다. (()())에서 맨 바깥 소괄호는 같은 level이고, 안에 있는 ()()가 같은 level이 되는 것이다.

이 때 cur의 의미는 같은 레벨에서 이미 만들어진 parentheses pair 갯수이다. 따라서 각 문자를 iterate할 때 cur은 다음과 같다.

<iteration 과정>

(()()) - 같은 레벨에서는 이미 만들어진 괄호쌍이 없다. 따라서 cur=0이 스택에 쌓인다. (()()) - 마찬가지로 같은 레벨에서는 괄호쌍이 없다. 바로 앞의 괄호는 다른 레벨이다. 따라서 스택에 0이 하나더 쌓인다. (()()) - cur=stk.pop()+cur+1 연산이 실행된다. 이 때 stk.pop()은 이전에 같은 레벨에서 만들어진 괄호쌍을 의미하고 cur은 지금 닫고 있는 괄호 안에 있는 괄호 쌍을 의미한다.(한 단계 아래 레벨에서 만들 수 있는 괄호 쌍) 그리고 1은 자기 자신이다. (()()) - 같은 레벨에서 괄호 쌍이 하나 만들어졌기 때문에 cur이 1이다. 따라서 stack에 1이 쌓인다. (()()) - 이 때 stk.pop()이 1이고, cur은 0이므로, 최종적으로 cur=stk.pop()+cur+1=2가 된다. (()()) - stk.pop()은 0이고(첫번째 줄에서 넣은 0) cur은 2가 되므로 최종적으로 cur은 3이 된다.

처음에는 cur=stk.pop()+1이라고 했다가 테스트 케이스에서 걸러졌다. 또한 close parenthese 갯수가 더 많은 경우, 유효한 괄호 쌍으로 확장할 수 없는 경우임으로 cur을 0으로 초기화하는 것도 잊지 않아야 한다.

A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).

Return a list of all MHTs' root labels. You can return the answer in any order.

The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

Solution

from collections import deque
class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        ans=[]
        cnt=n #to track the left number of nodes(not visited)
        inDegrees=[0]*n #inDegree means number of connected node except for visited node
        graph=[[] for _ in range(n)]

        if n<=2:
            return [i for i in range(n)]


        for a,b in edges:
            graph[a].append(b)
            graph[b].append(a)
            inDegrees[a]+=1
            inDegrees[b]+=1

        lst= deque([i for i in range(n) if inDegrees[i]==1])
        #make first deque with leaf nodes.

        while lst:
            l=len(lst)
            cnt-=l
            if cnt<=2: #the number of answer root node is only 1 or 2.
                break

            for _ in range(l):#like BFS searching.
                cur=lst.popleft()
                for nxt in graph[cur]:
                    if inDegrees[nxt]==1:
                        continue

                    inDegrees[nxt]-=1
                    if inDegrees[nxt]==1:
                        lst.append(nxt)

    #finding out root node
        for i,v in enumerate(inDegrees):
            if v!=1:
                ans.append(i)
                cnt-=1
                if cnt==0:
                    break


        return ans

처음에 감이 안 잡혀서, topic 보고 topological sorting을 처음으로 발견했다. 이 문제를 풀기 전에 GeeksForGeeks에서 topologicla sorting을 먼저 공부해야한다.

Topological sorting은 DFS 방식과 Kahn's Algorithm 방식 두 가지가 있다. 모두 알아두면 좋을 것 같다.

풀이 과정은 아래 그림을 보면서 insight를 얻을 수 있었다.(그림 크기 조절이 왜 안 될까)

특히 내가 사용한 방식은 inDegree를 이용하는 Kahn's algorithm을 이용하였다. 사실 GeeksForGeeks를 봐도 아이디어가 생각나지 않았다. 그래서 discussion 게시글에서 다음과 같은 한 줄을 읽고 힌트를 얻어서 풀었다.

We are basically trying to delete all leaf nodes at every step. This is very similar to Kahn's Algo or sometimes known as BFS Topological Sort. (ref)

이를 해석하면 다음과 같다. 우리가 찾는 node는 minimum height을 가진 root node이다. 따라서 inDegree가 1이 되는 node, 즉 leaf node를 제거하면서 root node에 가까워질 수 있다.

또한 leetcode 자체 힌트도 도움이 되었다.

How many MHTs can a graph have at most?

나올 수 있는 root node가 하나 아니면 두 개 인 것을 발견할 수 있다.

Problem

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times. [0,1,2,4,5,6,7] if it was rotated 7 times. Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Solution

class Solution:
    def findMin(self, nums: List[int]) -> int:
        l=len(nums)
        minN=nums[0]
        maxN=nums[-1]

        #l==1 or rotated n times
        if l==1 or minN<maxN:
            return nums[0]

        le=0
        ri=l-1

        while le<ri:
            mid=(le+ri)//2
            #print(nums[mid])
            if nums[mid]>=minN:
                le=mid+1
            else:
                ri=mid

        return nums[le]

배열을 두 개 적어놓고 관찰하니까, 빠르게 해답을 찾을 수 있었다. 우선 나는 n rotate한 상황을 배제해서, 정답 후보군을 항상 오른쪽에 두려고 했다. 그런 다음 바이너리 서치를 했다. 맨 왼쪽보다 더 큰 숫자이면 후보군을 mid 오른쪽으로 좁히고, 아니면 오른쪽을 mid로 후보군을 좁혔다.

if nums[mid]>=minN:

처음에 이 부분에서 등호를 넣지 않았다가, [2,1] 테스트케이스를 통과하지 못 했다.

Better Solution

class Solution:
    # @param num, a list of integer
    # @return an integer
    def findMin(self, num):
        first, last = 0, len(num) - 1
        while first < last:
            midpoint = (first + last) // 2
            if num[midpoint] > num[last]:
                first = midpoint + 1
            else:
                last = midpoint
        return num[first]

아래 부분이 내 풀이와 가장 큰 차이점이다.

if num[midpoint] > num[last]

num[last]와 num[midpoint]와 비교를 하면 된다.** num[last] 내가 가진 후보군 중에서 가장 큰 숫자가 되어야한다. 반면 num[first]는 후보군 중에서 가장 작은 숫자가 되어야한다.** 이러한 숫자를 찾기 위해 바이너리 서치를 돌리면 위와 같다.

며칠간 시험공부하고 와야겠다.

Problem

You have n boxes. You are given a binary string boxes of length n, where boxes[i] is '0' if the ith box is empty, and '1' if it contains one ball.

In one operation, you can move one ball from a box to an adjacent box. Box i is adjacent to box j if abs(i - j) == 1. Note that after doing so, there may be more than one ball in some boxes.

Return an array answer of size n, where answer[i] is the minimum number of operations needed to move all the balls to the ith box.

Each answer[i] is calculated considering the initial state of the boxes.

문제 유형은 잘 모르겠다. 그냥 array인가보다. 오늘 daily challenge 문제, Q.1271가 easy 이길래, medium 하나 더 풀려고 challenge 문제와 연관된 문제를 풀었다. 사실 이 1769번도 acceptance가 되게 높은 축에 속한다. 이 문제를 brute force로 풀면 time complexity O(n^2)이 나오는데 O(n)이 나오는 것을 목표로 풀어보려고 했다.

Solution

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        ans=[0]
        leftZero=0
        rightZero=0

        for i,v in enumerate(boxes):
            if v=="1": 
                ans[0]+=i
                rightZero+=1

        if boxes[0]=="1":
            leftZero=1
            rightZero-=1
        #print(ans)

        for i,v in enumerate(boxes[1:],start=1):
            #print(i,v)
            val=ans[-1]-rightZero+leftZero
            ans.append(val)

            if v=="1":
                leftZero+=1
                rightZero-=1

        return ans

스트링을 처음부터 끝까지 한 번 읽어서 ans[0]을 우선 먼저 계산한다. 그 다음 중요한 것은 iteration 과정에서 왼쪽에 있는 0의 개수(leftZero)와 오른쪽에 있는 0의 개수(rightZero)이다.

val=ans[-1]-rightZero+leftZero

이 부분이 가장 중요하다. iteration하는 문자 기준으로 오른쪽에 있는 0 개수만큼은 전체 거리가 가까워 지고, 왼쪽에 있는 0 개수만큼 전체 거리가 멀어지기 때문에 위와 같은 val이 결정된다.

for i,v in enumerate(boxes[1:],start=1):

개인적으로 기억하고 싶은 코드는 위 코드이다. enumerate할 때, index 1부터 읽고 싶을 때, 위와 같이 하면 된다.

Another Solution

class Solution:
    def minOperations(self, boxes: str) -> List[int]:
        n = len(boxes)
        answer = [0] * n
        curr, steps = 0, 0
        for i in range(n):
            answer[i] += steps
            curr += int(boxes[i])
            steps += curr
        curr, steps = 0, 0
        for i in reversed(range(n)):
            answer[i] += steps
            curr += int(boxes[i])
            steps += curr
        return answer

자기보다 왼쪽에 있는 1 개수를 answer[i]에 담는다. 이 때, 1 개수는 누적되기 때문에, steps에 저장할 수 있다.(일종의 dp로 볼 수 있다.) O(N)이 소모된다. 이제 반대로 자기보다 오른쪽에 있는 1 개수를 answer에 저장한다. 이 과정도 O(N)이 소모된다.

한 번 정방향으로 읽었다가, 반대 방향으로 읽는 풀이가 종종 보인다. 기억해뒀다가, 나도 다음에 써먹어야겠다.

서버 만드는 과제하러 가야하는데, 많이 어렵다. 조금 막막하다. 차근차근 해내야겠다.

Problem

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

대표적인 dp 유형 문제인 도둑질 문제다. 이번에는 BST에서 도둑질한다. 문제 가정이 조금 웃기다.

Solution

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:

        def goDFS(node) -> tuple:
            if not node:
                return (0,0)

            if not node.right and not node.left:
                return (node.val,0)

            le1,le2=goDFS(node.left)
            ri1,ri2=goDFS(node.right)

            return (max(node.val+le2+ri2,le1+ri1),le1+ri1)


        dp1,dp2=goDFS(root)



        return max(dp1,dp2)

처음에 잘못된 풀이로 갔다가,거기서 발생하는 오류에서 아이디어를 얻어 다음과 같이 풀이 방법을 생각해냈다. 이 문제를 풀기 전에 반드시 198. House Robber를 푸는 것을 권장한다. BST를 탐색하지 않고 array를 탐색하는 문제인데, 이러한 도둑질 유형 문제의 프로토타입이라고 할 수 있기 때문이다.

우선 기본적으로 트리를 DFS 방식으로 traversing한다. 그리고 goDFS에서 올라올 때마다 튜플로 두 가지 값을 전달한다. (dp1, dp2)라고 하자. dp1은 leaf에서 방금 탐색한 노드까지의 최대합이다. dp2는 leaf부터 방금 탐색한 노드의 자식까지의 최대합이다. (198번 문제에서 dp를 array로 설정했다면 dp1은 dp[i], dp2는 dp[i-1]에 대응한다.)

return (max(node.val+le2+ri2,le1+ri1),le1+ri1)

이 때 goDFS가 다음과 같은 리턴값을 가지는 것이 핵심이다. dp1에서 node.val+le2+ri2가 더 크다는 말은 node의 val를 포함하고 node의 자식을 건너뛴 그 아래 자식들과 합을 선택하겠다는 의미이다. le1+ri1은 node를 포함하지 않아도 최대합을 만들 수 있다는 이야기다. dp2는 leaf에서 node의 자식단계까지의 최대 합이므로 le1+ri1이 되는 것은 명확하다.

return (node.val+le2+ri2,le1+ri1)

처음에 이렇게 코드를 짰다가, 테스트 코드에서 에러가 났다. 이렇게 코드를 짤 경우 다음과 같은 상황을 고려하지 못한다. 2-1-1-4 인 경우 (4가 루트이고 자식을 하나씩 가지는 경우), 정답은 2+4=6이 되어야 한다. 하지만 위와 같은 코드는 (2+1) , (1+4)만 고려하기 때문에 오답을 리턴한다. 이러한 유형에서 대표적으로 생각해줘야하는 케이스인 (선택하고, 안하고, 안하고, 다시 선택하는) 케이스를 반영하지 못하게 된다.

Wrong Solution

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:

        if not root:
            return 0

        if not root.right and not root.left:
            return root.val


        leftVal= self.rob(root.left)
        rightVal=self.rob(root.right)
        notSelect=leftVal+rightVal

        select=root.val
        if root.left:
            select+=self.rob(root.left.right)
            select+=self.rob(root.left.left)
        if root.right:
            select+=self.rob(root.right.right)
            select+=self.rob(root.right.left)

        return max(notSelect,select)

처음에 시도했던 잘못된 풀이이다. 테스트 케이스 122/124를 맞은 것을 보니 로직 자체로는 문제가 없다. 하지만 time limit excess error가 난다. 위 풀이는 tree의 특성 상 재귀함수를 이용해서 풀려고 시도한 것이다. 그런데 같은 node가 rob에서 중복으로 호출되어서 쓸데없는 연산을 반복적으로 하게 된다. (dynamic programming이 아니다.)

Problem

Design an algorithm that accepts a stream of characters and checks if a suffix of these characters is a string of a given array of strings words.

For example, if words = ["abc", "xyz"] and the stream added the four characters (one by one) 'a', 'x', 'y', and 'z', your algorithm should detect that the suffix "xyz" of the characters "axyz" matches "xyz" from words.

Implement the StreamChecker class:

StreamChecker(String[] words) Initializes the object with the strings array words. boolean query(char letter) Accepts a new character from the stream and returns true if any non-empty suffix from the stream forms a word that is in words.

character stream에서 char 하나를 받으면서 단어를 형성한다고 할 때, 해당 char를 마지막으로 하는 단어에서, word 안에 surfix를 가지고 있는가를 확인해주는 알고리즘이다.

Poor Solution

class Node:
    def __init__(self,val=None):
        self.val=val
        self.child={}

class Trie:
    def __init__(self):
        self.head=Node()

    def insert(self,chars):
        cur=self.head

        for char in chars:
            if char not in cur.child:
                cur.child[char]=Node(char)
            cur=cur.child[char]
        cur.child['*']=Node('*')

    def search(self,chars):
        cur=self.head

        for char in chars:
            if char not in cur.child:
                return False
            cur=cur.child[char]
        if '*' in cur.child:
            return True

    def nextNode(self,node,ch):
        if ch not in node.child:
            return None

        node=node.child[ch]
        return node


class StreamChecker:

    def __init__(self, words: List[str]):
        self.trie=Trie()
        for word in words:
            self.trie.insert(word)
        self.cands=[]

    def query(self, letter: str) -> bool:
        ans=False
        tmp=[]
        for cand in self.cands:
            if letter not in cand.child:
                continue
            trav= cand.child[letter]
            if '*' in trav.child:
                ans=True
            tmp.append(trav)

        if letter in self.trie.head.child:   
            cur= self.trie.head.child[letter]
            if '*' in cur.child:
                ans=True
            tmp.append(cur)

        self.cands=tmp

        return ans

처음에 word를 trie에 저장을 한다. 그리고 stream을 한 글자씩 받아들인다. 그리고 그 글자를 cands에 넣어 가능한 surfix가 있을 때까지 trie에서 next Node를 찾게한다. trie는 처음 구현해보기 때문에 다음을 참고했다.

하지만 가능한 모든 상황을 하나하나 검토하기 때문에 시간이 너무 오래 걸린다. 아래 Best Solution과 비교해서 봐야한다. 내 풀이는 i 번째 스트림을 읽어올 때, 이미 그전에 읽어들였던 스트림 character를 대상으로 만들 수 있는 surfix를 traverse한다. 따라서 문자 하나를 볼 때도, cand이라는 리스트를 통해 surfix 후보를 여러개 두개 된다. 그래서 testcase 통과도 아슬아슬하게 했다. (처음 Trie의 메소드, nextNode를 호출해서 하다가 시간이 너무 길어져서, 쓰지 않게 고쳤더니 통과했다.) 하지만 아래의 풀이는 문자 하나 당 여러개의 후보를 두는게아니라, surfix를 거꾸로 저장해두고, streame도 거꾸로 읽어서 해당 문자에 가능한 surfix만 특정해서 찾게 된다.

Best Solution

class TrieNode():
    def __init__(self):
        self.children = {}
        self.isEnd = False

class Trie():
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.isEnd = True

class StreamChecker:
    def __init__(self, words: List[str]):
        self.letters = []
        self.trie = Trie()
        for w in words:
            self.trie.insert(w[::-1])

    def query(self, letter: str) -> bool:
        self.letters.append(letter)
        i = len(self.letters) - 1
        node = self.trie.root
        while i >= 0:
            if node.isEnd:
                return True
            if self.letters[i] not in node.children:
                return False
            node = node.children[self.letters[i]]
            i -= 1
        return node.isEnd

우선 trie에 단어를 역순(w[::-1])으로 저장한다. 그리고 문자를 하나 읽을 때마다, letter에 저장을 해둔다. letter하나당 letters를 거꾸로 indexing하면서 trie의 child로 traversing한다. 이렇게 하면, 내가 solution에서 한 것과는 다르게, 거꾸로 surfix를 만들어서 모든 상황이 아닌 확실하게 가능한 상황만 고려하게 된다. 그래서 시간이 단축된다. 또한 trie를 다른 방식으로 구현했다. 이 문제에서는 Node에 value를 가질 필요가 없어서 넣지 않았다. 그리고 isEnd라는 Flag로 대체했다.

Simple Solution

class StreamChecker:

    def __init__(self, words: List[str]):
        self.stream = deque([])
        self.trie = {}

        for word in set(words):
            node = self.trie
            for c in word[::-1]:
                if c not in node:
                    node[c] = {}
                node = node[c]
            node['$'] = word

    def query(self, letter: str) -> bool:
        self.stream.appendleft(letter)
        node = self.trie
        for c in self.stream:
            if '$' in node:
                return True
            if c not in node:
                return False
            node = node[c]
        return '$' in node

시간 복잡도가 좋은 solution example을 가져왔다. 굳이 trie를 따로 class로 구현하지 않은 모습이다. 그리고 indexing을 거꾸로하는 것이 아니라, deque를 사용해 저장해둔 stream을 정방향으로 읽게 했다.

Problems

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.

Max Subarray에서 사용한 Kadane's Algorithm과 비슷한 문제이다. 하지만 음수의 개수에 따라 Max product이 바뀔 수 있다는 점이 까다롭다.

Solution

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        l=len(nums)
        ans=max(nums)

        dp=nums.copy()

        if nums[0]<0:
            lm=0
        else:
            lm=-1   

        for i in range(1,l):
            v=nums[i]

            if v<0 and lm==-1:
                lm=i

            if dp[i-1]==0:
                continue

            if v==0:
                if lm!=-1 and lm!=i-1:
                    ans=max(ans,dp[i-1]//dp[lm])
                lm=-1
                continue

            dp[i]=dp[i-1]*v
            ans=max(ans,dp[i])

        if lm!=-1 and lm!=l-1:
                ans=max(ans,dp[l-1]//dp[lm])  

        print(dp,lm)
        return ans

dp[i]는 i번째 원소로 마지막으로하는 subarray의 누적 product이다. 여기서 lm이 등장하는데 subarray에서 leftmost 음의 element index이다. lm을 구하는 이유는, subarray에서 가장 왼쪽 음수를 포함한 왼쪽 subarray를 제외한 나머지 subarray의 product을 구하기 위함이다. 이 풀이의 단점은 corner case에 취약하다는 점이다. [-1,-2,-3,0] 등 음수가 반복적으로 나오는 상황을 따로 처리해줘야한다.

Best Solution

    if not nums:
            return 0

        if len(nums) == 1:
            return nums[0]

        min_so_far, max_so_far, max_global = nums[0], nums[0], nums[0]
        for i in range(1, len(nums)):
            max_so_far, min_so_far = max(min_so_far*nums[i], max_so_far*nums[i], nums[i]), min(min_so_far*nums[i], max_so_far*nums[i], nums[i])
            max_global = max(max_global, max_so_far)

        return max_global

아이디어가 명확하고 코드가 직관적이다. 다음과 같은 Kadane's Algorithm의 핵심 아이디어가 들어가있다.

global maximum is the larger one between a local maximum and the previous global maximum.

이 문제에서는 특히 min_so_far이 음수를 만나 max_so_far로 업데이트 된다는 특징을 잘 캐치해야한다. 따라서 max_so_far뿐만 아니라 min_so_far도 dp로 tracking한다.

Intuitive Solution

    def maxProduct(self, A):
        B = A[::-1]
        for i in range(1, len(A)):
            A[i] *= A[i - 1] or 1
            B[i] *= B[i - 1] or 1
        return max(A + B)

보다 직관적인 풀이 방법이다. 사실 lm를 두지 않더라도, 오른쪽에서부터 누적 product을 구하고 max 값을 구하면 된다는 아이디어를 가지고 있다. A[i-1]이 0이 되는 경우는 이전 숫자가 1인 것으로 처리해서, A[i]에 그 value만 남기게 해주었다.

Problem

Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Example 1:

Input: accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]] Output: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

Solution

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        dic={}
        ans=[]
        for account in accounts:
            target=None
            for i in range(1,len(account)):
                if hash(account[i]) in dic:
                    target=dic[hash(account[i])]

            if not target:
                ans.append(account)
                for i in range(1,len(account)):
                    dic[hash(account[i])]=account
            else:
                for i in range(1,len(account)):
                    if hash(account[i]) not in dic:
                        dic[hash(account[i])]=target
                        target.append(account[i])

        print(ans)         
        #sorting
        for i,v in enumerate(ans):
            tmp=v[:1]+sorted(list(set(v[1:])))
            ans[i]=tmp

        return ans

hashtable을 이용해서 쌩어거지로 풀었다. wrong answer 못 봤으면 못 풀었을 것 같다.

그래프가 안 보여도 DFS/BFS가 생각날 수 있다.

Best Solution

def accountsMerge(self, accounts):
    neighbor_dic = collections.defaultdict(set)
    name_dic = {}
    for lst in accounts:
        name = lst[0]
        for email in lst[1:]:
            neighbor_dic[email].add(lst[1])
            neighbor_dic[lst[1]].add(email)
            name_dic[email] = name

    res = []
    seen = set()
    for key in neighbor_dic.keys():
        if key not in seen:
            seen.add(key)
            stack = [key]
            tmp = [key]
            while stack:
                u = stack.pop()
                for n in neighbor_dic[u]:
                    if n not in seen:
                        seen.add(n)
                        tmp.append(n)
                        stack.append(n)
            res.append([name_dic[key]]+sorted(tmp))
    return res

이메일을 node로 보면 그래프처럼 탐색할 수 있다. 혹은 하나의 그래프를 기준으로, 같은 이메일을 가진 다른 account를 확장해서 더해나간다고 생각해도 DFS, BFS로 생각할 수 있다.

Problem

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1

Solution

from collections import deque

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:

        if amount==0:
            return 0

        dp=[int(2e9)]*(amount+1)
        que=deque()

        for coin in coins:
            if coin > amount:
                continue
            elif coin==amount:
                return 1

            dp[coin]=1
            que.append(coin)

        while que:
            #print(dp)
            cur = que.popleft()

            for coin in coins:
                if cur+coin>amount:
                     continue
                elif cur+coin==amount:
                    return dp[cur]+1

                if dp[cur+coin]>dp[cur]+1:
                    dp[cur+coin]=dp[cur]+1
                    que.append(cur+coin)


        return -1

처음에 안 풀리다가, 저녁 먹고 와서, 문제 분류가 dynammic programming인 것을 보고 힌트를 얻어 풀었다. 처음에는 amount에서 출발해 greedy 문제처럼 숫자가 큰 코인으로 처리하려고했다. 하지만 코인 구성이 n진법을 구성하는 숫자 조합이 아니라 greedy가 안 된다. greedy로 했을 때는, amount에서 금액을 차감하는 식으로 구현했다. 그래서 DP를 봤을 때, 생각 흐름을 바꾼다고 시간이 걸렸다.

DP로 풀때는, 내가 만들 수 있는 금액을 작은 금액부터 목표 금액까지 계속 더해나간다. dp[i]는 i원을 만들 때 필요한 최소 코인 수이다.

What I tried first

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        global ans
        if amount==0:
            return 0
        coins.sort(reverse=True)

        l=len(coins)
        print(coins)
        def goDFS(i,num,amnt):
            global ans
            #print(i,num,amnt)
            if i==l:
                return 

            value=coins[i]

            share,remain=divmod(amnt,value)

            if remain==0:
                #print(num+share)
                if ans>num+share:
                    ans=num+share
                return


            for j in range(share,-1,-1):
                goDFS(i+1,num+j,amnt-j*value)




        ans=int(2e9)

        goDFS(0,0,amount)



        if ans==int(2e9):
            return -1
        return ans

amount에서 coin을 차감하는 식으로 recursion을 이용해 풀려고했다. 하지만 recursion하는 경우의 수가 너무 많아져 시간 초과가 발생했다. 처음에 greedy라고 생각했다가, 틀리고 고치는 과정에서 생각의 흐름이 그렇게 자연스럽게 흘러갔다.

Problem

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

BST의 각 노드에서 B+ Tree Leaves들처럼 next Pointer 만드는 문제이다.

Solution

class Solution:
    def connect(self, root: 'Node') -> 'Node':

        if not root:
            return root
        h=1
        trav=root
        while trav.right:
            trav=trav.right
            h+=1
        print(h)

        ary=[None]*h


        def goDFS(node,depth,ary):
            node.next=ary[depth]

            if not node.right:
                return

            goDFS(node.right,depth+1,ary)
            ary[depth+1]=node.right

            goDFS(node.left,depth+1,ary)
            ary[depth+1]=node.left

        goDFS(root,0,ary)


        return root

ary i번째 원소는 가장 최근 다나간 i번째 node를 저장한다. 그래서 goDFS에 들어가자 마자, node.next=ary[depth]로 간단하게 nextPointer를 찾을 수 있다. 처음에 아이디어가 떠오르지 않다가. 재귀함수를 호출하고 난뒤, ary를 업데이트하는 아이디어가 떠올라서, 문제를 해결할 수 있었다. 즉 탐색을 완료한 다음에, 다음 같은 depth에 있는 노드를 탐색할 때, 완료한 노드를 참조할 수 있도록 ary를 업데이트하는 것이다.

하지만 1)Space Complexity를 O(1)으로 맞추지 못했고, h를 미리 알아야하기 때문에 2)시간도 h만큼 더 경과했다. (마지막 solution은 딕셔너리 이용해서 높이 몰라도 되게 해뒀다.)

BestSolution

Recursion

def connect(self, root):
    def trav(root):
        if not root.left and not root.right:
            return
        if not root.next:
            root.left.next = root.right
            root.right.next = None
        else:
            root.left.next = root.right
            root.right.next = root.next.left
        trav(root.left)
        trav(root.right)
    if not root:
        return
    root.next = None
    trav(root)

제일 중요한 코드

root.right.next=root.next=left

와우... 이런건 관찰하면 보일까? 생각도 못했다. root의 next를 이용해서 root.right의 nextPointer를 결정했다. 그림을 더 잘 봐야했나?

Similiar,but better Solution

Problem

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,3,2] Output: 3 Example 2:

Input: nums = [0,1,0,1,0,1,99] Output: 99

Solution

풀이

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def num2bin(num):
            i = 0
            if num < 0:
                num = -num
                count[32] += 1
            while num > 0:
                num, r = divmod(num, 2)
                count[i] += r
                i += 1

        def bin2num(binary):
            mult = 1
            ans = 0
            for i in range(len(binary)-1):
                ans += mult*binary[i]
                mult *= 2
            return ans

        count = [0]*33
        for n in nums:
            num2bin(n)
        for i in range(len(count)):
            count[i] %= 3
        res = bin2num(count)
        return res if count[-1] == 0 else -res

기존에 Single 1이나 3의 경우는 1이 2개 있으면 0으로 소거된다는 점을 이용해 xor 연산을 이용하였다. *이번에는 1이 3번 나오면 소거되게 만든다. *(위 풀이에서는 나중에 3으로 나눈 나머지를 구해 한번에 처리한다.) count에서 i번째요소는 nums의 모든 원소에서 i번째 비트의 1 개수를 의미한다. 따라서 세 번 나오는 숫자는 무조건 비트를 3개 만들개 되고 마지막에 %3으로 소거된다.

Another Solution

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        #we need to implement a tree-time counter(base 3) that if a bit appears three time ,it will be zero.
        #curent  income  ouput
        # ab      c/c       ab/ab
        # 00      1/0       01/00
        # 01      1/0       10/01
        # 10      1/0       00/10
        # a=~abc+a~b~c;
        # b=~a~bc+~ab~c;

        a = 0
        b = 0

        for c in nums:
            ta=(~a&b&c)| (a&~b&~c)
            b=~a&~b&c|~a&b&~c
            a=ta

        return a|b

이 풀이에서는 digital circuit 로직으로 풀었다. 00 --> 01 --> 10 --> 00으로 순화하는 state 3개 만든다. 따라서 bit가 3개 쌓일 때마다 항상 초기화 해준다.

Problem

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

Example 1:

Input: nums = [1,2,1,3,2,5] Output: [3,5] Explanation: [5, 3] is also a valid answer.

Solution

from functools import reduce
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        l=len(nums)
        if l==2:
            return nums

        ans=[]

        #get xor sum
        xSum=reduce(lambda acc,cur:acc^cur,nums)

        #find the rightmost different bit
        cnt=0
        tSum=xSum
        while not tSum&1:
            tSum>>=1
            cnt+=1

        grainer= 1<<cnt

        num1=0
        for num in nums:
            if num&grainer:
                num1^=num

        return [num1,num1^xSum]

힌트 없었으면 못 풀었을 것 같다. 그런데 로직이 너무 재미있다.

136. Single Number에서 다뤘던 XOR 연산자 성질을 다시 언급하면 다음과 같다.

     a^b = b^a a^0=a

a^a=0 ...(*)

여기서 (*)이 가장 중요하다.

우선 136번과 같이 xorSum을 구해준다. 그러면 찾고자하는 숫자 num1,num2의 xor만 남게 된다. 여기서 문제는 num1^num2에서 num1만 어떻게 끄집어 낼까이다.

num1^num2에서 i번째 비트가 1이라면 num1과 num2의 i번째 비트가 다르다는 것을 의미한다. 그럼 array의 모든 elems 중에서 i번째 비트가 1인 것들만 xor 연산을 하면 num1(또는 num2)를 포함해서 쌍으로 이루어진 숫자들로 xor sum이 만들어질 것이다. 이 때, 쌍으로 이루어진 숫자는 소거되므로 xor sum은 num1과 같다. num2는 전체 xSum에서 xor하면 쉽게 구할 수 있다.

c.f) (*)에서 a를 숫자 하나가 아니라 비트하나라고 볼 수 있다. 따라서 xorSum에서 i번째 비트가 1이면 array에서 i번째 비트가 1인 elem이 홀수 개 있다고 볼 수 있다.

bit manipulation 쪽에 새롭고 재밌는 것들이 많은 것 같다.

참고. https://leetcode.com/problems/single-number-iii/discuss/1561827/C%2B%2BPython-5-Simple-Solutions-w-Explanation-or-Brute-Force-%2B-Sort-%2B-Hashmap-%2B-Hashset-%2B-Xor-O(1)

Problems

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Input: nums = [4,1,2,1,2] Output: 4

Solution

from functools import reduce
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda acc,cur:acc^cur,nums)

기존 set 쓰던 풀이에서 bit manipulation으로 바꿨다. set 쓰면 공간 n 먹어서 위 풀이가 더 효율적이다.

위 풀이를 이해하려면 bit 연산의 성질을 알아야 한다.

XOR 연산

1) commutative law 성립: a^b=b^a 2) 0^a=a 3) a^a=0

따라서 위 예제에서 모든 연산을 xor로 처리하면 다음과 같다.

4^1^2^1^2 =4^1^1^2^2 =4^0^0 = 4^0 =4

모르면 맞아야지하는 문제 같다.

이를 베이스로 260. Single Number III도 풀어보자.

Problems

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.

Solution

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l=len(nums)
        if l==1:
            return nums[0]
        dp=[0]*l#0th:
        dp[0]=nums[0]
        maxNum=dp[0]
        for i in range(1,l):
            dp[i]=max(nums[i],nums[i]+dp[i-1])
            if maxNum<dp[i]:
                maxNum=dp[i]

        return maxNum

옛날에 백준에서 풀어놓고 까먹어서 못 풀었다. 찾아보니, 해당 문제를 해결하는 알고리즘이 잘 알려져있었다.

Kadane's Algorithm

최대합 부분수열 구하는 알고리즘. O(N)

Dynamic Programming - 어떤 문제를 해결 가능한 하위 문제로 나누어 푸는 방법.

dp[i]: i번째 원소를 마지막으로 하는 subarray의 최대합. 이 때 다음과 같은 점화식이 성립한다.

dp[i]=max(nums[i],nums[i]+dp[i-1])

말로 한 번 더 정리해보자.

i번째 원소를 마지막으로 하는 최대합을 가진 subarray를 구하려면,

1) i-1번째 원소를 마지막으로 하는 최대합 subarry에다가 i번째 원소를 더하거나 2) i 번째 원소로만 subarray를 만들거나 두 가지 경우 밖에 없다.

이런 알고리즘은 그냥 기억해야하나 싶다.

Problem

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.

The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

Example 1:

Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]] Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Solution

class Solution(object):
    def intervalIntersection(self, firstList, secondList):
        """
        :type firstList: List[List[int]]
        :type secondList: List[List[int]]
        :rtype: List[List[int]]
        """
        l1=len(firstList)
        l2=len(secondList)


        #corner case
        if l1==0 or l2==0:
            return None

        i=0
        j=0
        answer=[]

        stk1=[]
        stk2=[]

        while i<l1 and j<l2:
            if firstList[i][0]<secondList[j][0]:
                if j==0:
                    i+=1
                    continue

                if secondList[j-1][1]>=firstList[i][0] and secondList[j-1][0]!=firstList[i][0]:
                    answer.append([firstList[i][0],min(secondList[j-1][1],firstList[i][1])])

                i+=1
            elif firstList[i][0]>secondList[j][0]:
                if i==0:
                    j+=1
                    continue

                if firstList[i-1][1]>=secondList[j][0] and firstList[i-1][0]!=secondList[j][0]:
                    answer.append([secondList[j][0],min(firstList[i-1][1],secondList[j][1])])

                j+=1
            else:
                answer.append([secondList[j][0],min(firstList[i][1],secondList[j][1])])
                if firstList[i][1]>secondList[j][1]:
                    j+=1
                elif firstList[i][1]<secondList[j][1]:
                    i+=1
                else:
                    i+=1
                    j+=1

        while i<l1 and firstList[i][0]<=secondList[-1][1]:
            if firstList[i][0]!=secondList[-1][0]:
                answer.append([firstList[i][0],min(firstList[i][1],secondList[-1][1])])
            i+=1

        while j<l2 and secondList[j][0]<=firstList[-1][1]:
            if secondList[j][0]!=firstList[-1][0]:
                answer.append([secondList[j][0],min(secondList[j][1],firstList[-1][1])])
            j+=1           



        return answer

i,j로 tracing하여 two pointer로 풀었다. O(n+m) 큰 틀에서 아이디어 내고 구현하는 것은 어렵지 않았지만 corner cases 처리하는 것이 많이 까다로웠다. 특히 시작점이 같은 경우를 핸들링하는데 시간을 거의다 소비했다. acceptance rate = 25%로 풀어서 아쉬웠다.

다음과 같은 상황에서 오류가 났고 수정 하였다.

Input: [[5,10]] [[5,6]] Output: [[5,6],[5,6]] Expected: [[5,6]]

Input: [[8,15]] [[2,6],[8,10],[12,20]] Output: [[8,10],[8,10],[12,15]] Expected: [[8,10],[12,15]]

딱 저 두가지 경우에 대해서만 추가로 생각해서 condition을 덧붙였다. 사실 반례를 주지 않는 다른 플랫폼에서는 푸는게 힘들었을 것 같다. 다음부터 틀려도 반례는 최대한 보면 안 되겠다. 시간이 급해도 스스로 테스트 케이스 만드는 연습도 해야한다.

Best Solution

https://leetcode.com/problems/interval-list-intersections/discuss/647482/Python-Two-Pointer-Approach-%2B-Thinking-Process-Diagrams

 class Solution:
     def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
         i = 0
         j = 0

         result = []
         while i < len(A) and j < len(B):
             a_start, a_end = A[i]
             b_start, b_end = B[j]
             if a_start <= b_end and b_start <= a_end:                       # Criss-cross lock
                 result.append([max(a_start, b_start), min(a_end, b_end)])   # Squeezing

             if a_end <= b_end:         # Exhausted this range in A
                 i += 1               # Point to next range in A
             else:                      # Exhausted this range in B
                 j += 1               # Point to next range in B
         return result

훨씬 간결햐다. 풀이에서도 코드 자체보다 아이디어 구상하는데 훨씬 투자를 많이 했다. 링크 꼭 봐야한다. 링크에서 아이디어를 떠올리는 과정이 도움이 많이 된다. 우선 overlap이 생기는 모든 경우의 수를 정리했다. 특히 A, B chunk 하나씩만 사용해서 나타내었다. criss-cross locking 알아두면 좋을 듯.

pointer를 움직이는 기준도 start value가 아닌 end value이다. exhausted하면 이동한다는 컨셉을 가지고 있다.

Problem

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4] Example 2:

Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]

Solution

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if k==0:
            return

        startIdx=0
        cnt=0
        l=len(nums)

        while cnt!=len(nums):
            idx=startIdx
            nextValue=nums[(idx+k)%l]
            nums[(idx+k)%l]=nums[idx]
            idx=(idx+k)%l
            cnt+=1

            while idx!=startIdx and cnt!=len(nums):
                tmp=nums[(idx+k)%l] 
                nums[(idx+k)%l] = nextValue            
                nextValue=tmp
                cnt+=1
                idx=(idx+k)%l


            startIdx+=1

iteration. O(n), O(1)

안 풀리다가 밥 먹고 오니까 바로 풀림. 처음에 잘못된 아이디어를 얼마나 빨리 버리는게 중요한가?

도중에 idx+=k만 했다가 한 번 에러나고, 마지막에 %l 덧붙여줘서 통과함. 코드 구현보다 아이디어 빨리 떠올리는게 중요했음. 가져온 예제로 손으로 그리면서 했음. 특히 k가 l의 약수가 되는 상황을 커버하기 위해 startIdx와 cnt 사용 사용.

Best Solution

https://leetcode.com/problems/rotate-array/discuss/202250/4-python-solutions

class Solution(object):
    def rotate(self, nums, k):
        k = k % len(nums)
        dupnums = [0] * len(nums)
        for i in range(len(nums)):
            dupnums[(i + k) % len(nums)] = nums[i]

        nums[:] = dupnums # copy dupnums to nums

O(n), O(n)

공간 n만큼 사용. nums 카피하는 것 마지막에 기억해야. 공간 사용하는게 구현은 더 쉬움. 아이디어도 떠올리기 좋고.

class Solution(object):
    def rotate(self, nums, k):
        k = k % len(nums)
        nums[:] = nums[-k:] + nums[:-k]

아이디어가 훨씬 좋아서 코드도 더 간결함. 숫자 자체를 관찰하면 만들 수 있을지도.

Problem

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements. Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0] Example 2:

Input: nums = [0] Output: [0]

Solution

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        zIdx=-1
        for i in range(len(nums)):
            if nums[i]==0:
                zIdx=i
                break

        if zIdx==-1:
            return


        idx=0
        while idx<len(nums):

            if zIdx<idx and nums[idx]!=0:
                nums[zIdx]=nums[idx]
                nums[idx]=0
                while zIdx<len(nums):
                    if nums[zIdx]==0:
                        break
                    zIdx+=1

            idx+=1

zIdx가 항상 0에서 n으로 linear하게 증가하고, idx도 마찬가지이다. 따라서 시간 복잡도는 O(2n)==O(n)이다. 간단한 알고리즘이지만 투포인터가 익숙하지 않아서인지 처음에는 안 풀렸다. 아이디어가 부족했다.

Best Solution

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        i = 0
        for j in range(len(nums)):
            if nums[j] != 0:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1

https://leetcode.com/problems/move-zeroes/discuss/208755/Python-solution 단순하게 j로 처음부터 끝까지 iterate한다. 현재까지 완성된 배열의 인덱스를 i로 trace한다. i는 현재 보고있는 elem이 0이 아닐 때만 증가한다. 퀵소트랑 비슷하다.

BST에서 key 값을 삭제하는 문제.

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return root

        if root.val==key:
            if not root.right:
                return root.left
            par=None
            trav=root.right
            while trav.left:
                par=trav
                trav=trav.left

            if not par:
                trav.left=root.left
                return trav
            par.left=None
            trav.left=root.left
            trav.right=root.right
            return trav

        par=None
        trav=root
        leftFlag=True
        while trav and trav.val!=key:
            par=trav
            if key<trav.val:
                leftFlag=True
                trav=trav.left
            else:
                leftFlag=False
                trav=trav.right


        #no such key:
        if not trav:
            return root

        rPar=None
        rTrav=trav.right

        #no first right child
        if not rTrav:
            if leftFlag: par.left=trav.left
            else: par.right=trav.left
            return root

        while rTrav.left:
            rPar=rTrav
            rTrav=rTrav.left

        if leftFlag: par.left=rTrav
        else: par.right=rTrav

        rTrav.left=trav.left
        if rPar:
            rPar.left=rTrav.right
            rTrav.right=trav.right




        return root

<접근>

무언가를 삭제하게되면 그것을 대체할 것을 찾아야함. key의 right child에서 가장 작은 것(most left side child)로 대체를 하면 BST 조건 만족함.

예외조건이 많아서 까다로웠음.

key가 루트일 경우. trav(node with key)가 rightChild를 가지지 않을 경우. rightChild가 바로 left child를 가지지 않을 경우.

<과정>

예외조건을 state variable로 처리하려다보니 조건이 너무 많아져서 복잡했음. 그래서 갈아엎고, root.val==key인 경우만 따로 처리했음. 예외 조건 두개만 다루니까 그래도 할만 했음.

 if rPar:
            rPar.left=rTrav.right
            rTrav.right=trav.right

여기서 rPar.left=None이라고 했다가 마지막 에러를 냄. rTrav가 rigth chld를 가질 수 있음.
→ 좀 더 일반적인 상황에 대해 생각해야함.

        while rTrav.left:
            rPar=rTrav
            rTrav=rTrav.left코드를 입력하세요

while not rTrav.left라는 실수 반복함.

<솔루션>

iteration

https://leetcode.com/problems/delete-node-in-a-bst/discuss/746703/Python-iterative-solution 이전 노드를 따로 추적해야해서 불편함. 이전 노드가 있냐없냐에 따라 예외 상황 발생함. val만 바꾸고 left,right 안 바꿀 수 있었음!

recursion

def deleteNode(root, key):
    if not root: return None
    if root.val > key: 
        root.left = deleteNode(root.left, key)
    elif root.val < key: 
        root.right = deleteNode(root.right, key)
    else:
        if not (root.left and root.right): 
            return root.left or root.right
        root.val = findClosest(root.right).val
        root.right = deleteNode(root.right, root.val)
    return root

def findClosest(node):
    while node.left:
        node = node.left
    return node

https://leetcode.com/problems/delete-node-in-a-bst/discuss/254235/Python-Recursion-Hibbard-Deletion iteration에 비해 코드 간결. 작은 트리는 큰 트리에 포함됨 --> 재귀적 재귀 함수 빠지는 조건이 신기함. 밑에 자식 한 쪽없으면 가지고 있는 자식 주고 빠짐.

<개선점>

제거하고 어떤 것으로 대체해야하는지 확실한 로직가지고 코드 만들기 일반적인 예시 놓치지 않기

unsolved

106. Construct Binary Tree from Inorder and Postorder Traversal

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Solution

preorder traverse = mid->left->right inorder traverse = left->mid->right postorder traverse = left->right->mid

example

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] Output: [3,9,20,null,null,15,7]

inorder: 9->3->{15->20->7} postorder: 9 -> {15->7->20} ->3

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/discuss/1588887/Python-Arriving-at-an-O(N)-solution

code

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if len(postorder)==0:
            return None


        val=postorder[-1]
        idx=inorder.index(val)

        leftIn=inorder[:idx]
        rigthIn=inorder[idx+1:]


        leftPo=postorder[:idx]
        rightPo=postorder[idx:-1]


        return TreeNode(val,self.buildTree(leftIn,leftPo),self.buildTree(rigthIn,rightPo))

preorder: 왼 나 오 postorder:왼 오 나 어떤 한 배열을 받아도, 배열을 세 가지 파트로 나눠서 생각할 수 있음. 우선 root인 '나'를 가지고 노드를 만든다. 이 때 왼쪽과 오른쪽에 각각 서브트리가 생긴다. 이 서브트리도 똑같은 메소드로 재귀적으로 트리를 빌드한다.