leetcode 134(그리디), 543(트리), 228(구현), 55(구현), 1306(dfs)

134 https://leetcode.com/problems/gas-station/

일단 포인트를 잡으면 이동은 무조건 i에서 i+1로 가고 cost[i]만큼 든다. 충전할수 있는 gas보다 드는 비용인 cost가 더 많으면 돌아올수 없으므로 종료를 시켜주고 시작한다. 

마을을 순회하면서 충전되는 양보다 드는 비용이 더 많을 경우 0 ~ 현재위치까지는 시작해봐야 -가 되어서 못 간다는 의미이니 시작점을 다음으로 초기화시켜준다.

class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        if sum(gas) < sum(cost):
            return -1
        start, gas_left = 0, 0
        for i in xrange(len(gas)):
            gas_left += (gas[i] - cost[i])
            if gas_left < 0:
                gas_left = 0
                start = i+1
        return start

543 https://leetcode.com/problems/diameter-of-binary-tree/

문제를 보자마자 예전에 https://qkqhxla1.tistory.com/748 에서 풀었던 백준 1967번 생각이 났다.

그래서 예전에 풀었던 방식으로 풀었다. dfs로 그래프 개념으로 트리를 구성하고, dfs로 root에서 가장 먼 거리의 점을 찾고, dfs로 한번더 그 점에서 가장 먼 거리를 찾았다. 풀면서 뭔가 비효율적이라는 생각을 하긴 했는데 역시 다른답을 보니 그냥 왼쪽 자식으로 가장 먼 점과 오른쪽 자식으로 가장 먼 점을 찾아서 거리를 더하는 방식으로 다들 풀었다.

from collections import deque

class Solution(object):
    def diameterOfBinaryTree(self, root):
        self.tree = {}
        if not root:
            return 0
        
        queue = deque([[root, None]])
        while queue:
            n, parent = queue.popleft()
            if parent:
                self.tree[n] = self.tree.get(n, []) + [parent]
            if n.left:
                self.tree[n] = self.tree.get(n, []) + [n.left]
                queue.append([n.left, n])
            if n.right:
                self.tree[n] = self.tree.get(n, []) + [n.right]
                queue.append([n.right, n])

        if not self.tree:
            return 0
        return self.dfs(self.dfs(root)[0])[1]
        
    def dfs(self, node):
        queue = deque([[node, 0]])
        visited = set([node])
        max_node = [None, 0]
        while queue:
            n, distance = queue.popleft()
            if distance > max_node[1]:
                max_node = [n, distance]
            for _next in self.tree[n]:
                if _next not in visited:
                    visited.add(_next)
                    queue.append([_next, distance + 1])

        return max_node

228 https://leetcode.com/problems/summary-ranges/

medium인데 특별한게 없다.... 그냥 구현한다. 기발한 답들을 구경해보자. 

https://leetcode.com/problems/summary-ranges/discuss/63193/6-lines-in-Python

https://leetcode.com/problems/summary-ranges/discuss/63474/Idea-%2B-1-Liner%3A-Group-by-number-index

class Solution(object):
    def summaryRanges(self, nums):
        if not nums:
            return []
        
        nums += [nums[-1]]
        consecutive = nums[0]
        ret = []
        for i in xrange(len(nums)-1):
            if nums[i] + 1 != nums[i+1]:
                if consecutive == nums[i]:
                    ret.append(str(consecutive))
                else:
                    ret.append('{}->{}'.format(consecutive, nums[i]))
                consecutive = nums[i+1]
        return ret

55 https://leetcode.com/problems/jump-game/

구현한다. 특별한 알고리즘이 있는건 아닌데 생각을 좀 해야 한다. 처음에 보자마자 별생각없이 dfs로 풀었다가 시간초과나와서 다시 풀었다.

class Solution(object):
    def canJump(self, nums):
        _max = 0
        for i in xrange(len(nums)):
            if i > _max:
                return False
            _max = max(i + nums[i], _max)
            if _max >= len(nums)-1:
                return True

1306 https://leetcode.com/problems/jump-game-iii/

위에 55번에서 살짝 바뀐 문제인데 이번 문제가 진짜 dfs이다.

from collections import deque

class Solution(object):
    def canReach(self, arr, start):
        stack = deque([start])
        visited = set([start])
        last_index = len(arr)-1
        while stack:
            cur_index = stack.pop()
            if arr[cur_index] == 0:
                return True
            for _next in [cur_index - arr[cur_index], 
                      cur_index + arr[cur_index]]:
                if _next not in visited and 0 <= _next <= last_index:
                    visited.add(_next)
                    stack.append(_next)
        return False