leetcode 617(트리) 1351(구현), 1104(트리), 1472(구현)

617 https://leetcode.com/problems/merge-two-binary-trees/
재귀 연습하기 좋은 기초문제다. 이런 비슷한 문제를 앞에서 여러번 풀어봤지만 그래도 좋다고 생각해서 가져온다..

class Solution(object):
    def mergeTrees(self, t1, t2):
        if not t1 or not t2:  # 둘중 하나가 없으면 있는 노드 리턴
            return t1 or t2
        node = TreeNode(t1.val + t2.val)
        node.left = self.mergeTrees(t1.left, t2.left)
        node.right = self.mergeTrees(t1.right, t2.right)
        return node

1351 https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/
이문제는 단순히 풀고 끝 보다는  https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/discuss/514468/4-Python-Solutions이 답을 읽고 모두 이해해보자.

간단히 3번의 경우에 대해 간단하게 코멘트를 단다.
3. O(m+n)
행이 증가할수록, 열이 증가할수록 값이 작아지는 경향이 있다.
가장 (마지막) 행의 j번째 열에서 음수가 나왔다면, (마지막-1) 행에서 음수는 최소 j번째열, 아니면 j+1번째 열에서 나올것이다. 이러한 성질을 이용해서 가장 마지막 행부터 위로 올라가며 음수의 위치를 계산해준다. 모든 행(m)을 돌면서 열(n)은 한번씩만 순환할 것이므로 O(m+n)이 된다.

class Solution(object):
    def countNegatives(self, grid):
        i = len(grid)-1
        j = 0
        count = 0
        while i>=0 and j < len(grid[0]):
            print(i,j)
            if grid[i][j] < 0:
                count +=len(grid[0])-j
                i -= 1
            else:
                j +=1
        return(count)

1104 https://leetcode.com/problems/path-in-zigzag-labelled-binary-tree/
지그재그 이진 트리이다. 맨 아래의 label에서 위로 부모를 구해주면서 올라간다. 부모의 값은 자식의 인덱스 위치/2이다. 자식의 상대적인 인덱스 값은 (최대값 + 최소값 - 자식값)이다.

class Solution(object):
    def pathInZigZagTree(self, label):
        level = 0
        while 2**level <= label:  # 몇단까지 있는지를 먼저 구해준다.
            level += 1
        
        ret = []
        while level > 0:
            ret.append(label)
            _min, _max = 2**(level-1), (2**level)-1
            label = int((_max + _min - label)/2)  # 부모는 자식의 인덱스/2
            level -= 1
        return ret[::-1]

1472 https://leetcode.com/problems/design-browser-history/submissions/
브라우저 히스토리를 구현하는 문제이다. 히스토리 전, 후, 방문을 구현해야 한다. 새 웹페이지 방문시 이전에 있던 forward 히스토리의 최신값을 새 웹페이지로 유지해주는걸 잊지말자. 딕셔너리로 구현했다.

class BrowserHistory(object):
    def __init__(self, homepage):
        self.index = 0
        self.end_index = 0
        self.history = {self.index: homepage}
        
    def visit(self, url):
        #print 'visit', self.index, self.end_index, self.history
        self.index += 1
        self.end_index = self.index
        self.history[self.index] = url
        
    def back(self, steps):
        #print 'back',steps, self.index, self.end_index, self.history
        self.index -= steps
        if self.index < 0:
            self.index = 0
        return self.history[self.index]
        
    def forward(self, steps):
        #print 'forward',steps, self.index, self.end_index, self.history
        self.index += steps
        if self.index > self.end_index:
            self.index = self.end_index
        return self.history[self.index]