leetcode 120(dp), 226(트리), 785(이분 그래프, bipartite), 703(heap)

120 https://leetcode.com/problems/triangle/

위에서부터 내려오면서 최소 값들을 triangle리스트에 업데이트해준다. 그리고 맨 마지막까지 끝났을때 거기서 최소값을 리턴한다.

class Solution(object):
    def minimumTotal(self, triangle):
        if not triangle:
            return 
        for i in xrange(1, len(triangle)):
            for j in xrange(len(triangle[i])):
                if j == 0:
                    triangle[i][j] += triangle[i-1][j]
                elif j == len(triangle[i])-1:
                    triangle[i][j] += triangle[i-1][j-1]
                else:
                    triangle[i][j] += min(triangle[i-1][j-1], triangle[i-1][j])
        return min(triangle[len(triangle)-1])

226 https://leetcode.com/problems/invert-binary-tree/

재귀로 푼다.

class Solution(object):
    def invertTree(self, root):
        if root:
            root.left, root.right = root.right, root.left
            self.invertTree(root.left)
            self.invertTree(root.right)
        return root

문제 아래에 있는 일화가 웃기다..

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

homebrew개발자가 구글에 지원했는데 면접에서 이진 트리를 뒤집지 못해서 떨어졌나 봄. 

생각해보니까 요즘 유튜브를 보다가 자주 나오는 algoexpert라는, leetcode같이 알고리즘 해설해주는 사이트에서 광고를 하는데 이 homebrew개발자 일화를 보고 광고를 만든것같다.

https://www.youtube.com/watch?v=iOHq7BWFQRc

q : do you know what the scariest thing in the world is?

a : not knowing how to invert a binary tree in a coding interview.

785 https://leetcode.com/problems/is-graph-bipartite/

알고리즘 문제를 그래도 어느정도 풀었다고 생각했는데... 이분 그래프(bipartite)라는 개념을 이 문제에서 처음 알았다.(아니면 알았었는데 잊어버렸거나)

그래서 개념을 이해하기 위해 블로그를 찾아서 참조했다.

https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html

블로그 글을 읽고 나자, 대충 어떻게 해야할지 눈에 보였다.

1. 한 노드에서 bfs, dfs등으로 탐색을 하면서 현재 노드와 다른 색으로 칠해준다. 

2. 탐색을 하면서 다음 노드가 이미 어떤 색으로 칠해져있으면 현재 색깔이랑 비교해본다. 비교했는데 똑같으면 이분 그래프가 아니므로 false를 리턴하고, 그게 아니면 계속 칠해나간다.

from collections import deque

class Solution(object):
    def isBipartite(self, graph):
        color_dict = {}
        for node in xrange(len(graph)):
            if node in color_dict:
                continue
                
            color_dict[node] = True
            stack = deque([node])
            while stack:
                cur_node = stack.pop()
                for next_node in graph[cur_node]:
                    if next_node in color_dict:
                        if color_dict[next_node] == color_dict[cur_node]:
                            return False
                    else:
                        color_dict[next_node] = not color_dict[cur_node]
                        stack.append(next_node)
        return True
    

703 https://leetcode.com/problems/kth-largest-element-in-a-stream/

힙을 만들고 k번째 수만 빼오면 되므로 k개만 남겨놓는다. 숫자가 추가될때 숫자를 추가하고 k를 넘으면 heappop으로 k개를 유지해주고, 결국 남은 k개의 인자 중에서 루트값(0번째 인덱스)이 k번째 큰 수가 되므로 그걸 리턴해준다.

import heapq

class KthLargest(object):

    def __init__(self, k, nums):
        self.k = k
        self.nums = nums
        heapq.heapify(self.nums)
        while len(self.nums) > self.k:
            heapq.heappop(self.nums)

    def add(self, val):
        heapq.heappush(self.nums, val)
        if len(self.nums) > self.k: 
            heapq.heappop(self.nums)
            
        return self.nums[0]