leetcode 605(구현), 1302(트리), 56,57(구현, 그리디같은거), 654(트리, 재귀)

605 leetcode.com/problems/can-place-flowers/
꽃을 심는데 반드시 꽃 사이사이에 한칸씩 공간이 있어야 한다.

class Solution(object):
    def canPlaceFlowers(self, fb, n):
        i = 0
        while i < len(fb) and n > 0:
            if i == len(fb) -1 and fb[i-1] == 0 and fb[i] == 0:
                fb[i] = 1
                n -= 1
                break
            elif i < len(fb) -1 and fb[i] == 0 and fb[i+1] == 0:
                fb[i] = 1
                n -= 1
                i += 2
            elif i < len(fb) -1 and fb[i] == 1 and fb[i+1] == 0:
                i += 2 
            else:
                i += 1
        return n == 0
                

1302 leetcode.com/problems/deepest-leaves-sum/
비슷한 종류의 문제를 많이 풀었다... 트리문제는 대부분 포맷이 비슷비슷한듯...

class Solution(object):
    def deepestLeavesSum(self, root):
        all_nodes = []
        queue = [[root, 0]]
        max_depth = 0
        while queue:
            node, depth = queue.pop(0)
            max_depth = max(max_depth, depth)
            all_nodes.append([node.val, depth])
            for child in [node.left, node.right]:
                if child:
                    queue.append([child, depth+1])
        return sum([n for n,d in all_nodes if d == max_depth])

57 leetcode.com/problems/insert-interval/
좋은 문제인것 같다. 새로운 interval이 들어오면 그걸 넣어서 새 범위를 리턴하는 문제이다. 인터벌 포맷이 그리디 문제에서 자주 보이는 그런 포맷이다.
1. 새 인터벌이 들어오면 이전 인터벌과 합쳐서 시작점을 기준으로 정렬해준다.
2. 새로운 인터벌을 넣을 new_interval을 만든 다음 거기에 앞에서부터 차곡차곡 넣으면서 현 인터벌의 시작점이 마지막으로 넣었던 인터벌의 종료점보다 앞이면 서로 합칠수 있으므로, 합친 다음 새로운 인터벌을 구성한다.
56번 leetcode.com/problems/merge-intervals/도 동일한 소스코드로 풀이가 가능하다.

class Solution(object):
    def insert(self, intervals, newInterval):
        #intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
        #newInterval = [4,8]

        new_interval = []
        intervals = sorted(intervals + [newInterval], key=lambda x:x[0])
        for i in xrange(len(intervals)):
            if new_interval and intervals[i][0] <= new_interval[-1][1]:
                new_interval[-1] = [new_interval[-1][0], max(intervals[i][1], new_interval[-1][1])]
            else:
                new_interval.append(intervals[i])
        #print 'new =',new_interval
        return new_interval
    

654 leetcode.com/problems/maximum-binary-tree/
기본적인 재귀함수 구현하는 문제이다.

class Solution(object):
    def constructMaximumBinaryTree(self, nums):
        if not nums:
            return None
        root = TreeNode(max(nums))
        root.left = self.constructMaximumBinaryTree(nums[:nums.index(max(nums))])
        root.right = self.constructMaximumBinaryTree(nums[nums.index(max(nums))+1:])
        return root