leetcode p1762(구현), 2079(꽃에 물주기,시뮬레이션), p1676(LCA), 394(stack, regex, 구현)

1762 https://leetcode.com/problems/buildings-with-an-ocean-view/
왼쪽에서부터 검사하면 오른쪽에 높은 벽이 나타났을때 다시 왼쪽의 케이스를 체크해야한다. 그런데 오른쪽에서부터 왼쪽으로 가면서 하면 다시 오른쪽의 케이스를 체크할 필요가 없다. 오른쪽에서 왼쪽으로 가면서, 최대값을 유지해주고 현재까지의 최대 높이보다 높아지는 왼쪽 높이가 나오면 그 인덱스를 저장해두면 된다.

class Solution:
    def findBuildings(self, h: List[int]) -> List[int]:
        cur_max = 0
        ret = []
        for i in range(len(h)-1, -1, -1):
            if h[i] > cur_max:
                ret.append(i)
                cur_max = h[i]
        return ret[::-1]

2079 https://leetcode.com/problems/watering-plants/
무식하게 구현하기전에 규칙을 한번 생각해보자.
i = 1에서 plant[2]가 커서 되돌아가야한다고 가정하면 0,-1,0,1,2 -> 5,
i = 2에서 plant[3]이 커서 되돌아가야한다고 가정하면 1,0,-1,0,1,2,3 -> 7 이다.
매 회차에 한걸음씩 미리 더하되, plant[i]가 커서 되돌아가야하는경우는 미리 더한 값을 반환하는게 아니라 i*2만 더해주면 된다.  위의 5는 (1 + 2*2)로 표현가능하고, 7은 (1 + 2*3)으로 표현가능하다.

class Solution:
    def wateringPlants(self, plants: List[int], capacity: int) -> int:
        ret = 0
        original_capacity = capacity
        for i, plant in enumerate(plants):
            ret += 1
            if plants[i] > capacity:
                ret += 2 * i
                capacity = original_capacity
            capacity -= plant
        return ret

1676 https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iv/
이진 트리에서의 LCA의 좋은 코드 템플릿을 봐서 적어놓는다.

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', nodes: 'List[TreeNode]') -> 'TreeNode':
        nodes = set(nodes)
        def fn(node):
            """Return LCA of nodes."""
            # leaf노드이면 일단 올리고, 현 노드가 lca를 구해야 하는 대상자 노드면 대상자 노드 리턴. 대상자 노드 아래는 잘라버림.
            if not node or node in nodes:  
                return node 
            left, right = fn(node.left), fn(node.right)  # 대상자 노드가 아니면 끝까지 내려감.
            # 둘다 있으면 부모 노드 리턴. LCA는 공통 최소 조상이므로 현재보다 밑단에서 left, right두 자식이 존재할 경우 위로 올리면서 경우의 수를 줄여준다.
            if left and right:  
                return node
            # lca를 구해야 하는 대상 노드도 아니고 아무것도 아닌 leaf노드는 여기서 None이 리턴됨.
            return left or right
        return fn(root)

394 https://leetcode.com/problems/decode-string/
딱 봐도 스택 문제이다. 근데 문제를 관찰하다가 정규식으로도 풀수 있을거라고 생각해서 정규식으로 짰는데 됐다.

import re

class Solution:
    _group = re.compile('(\d+)\[([a-z]+)\]')
    def decodeString(self, s: str) -> str:
        while True:
            found = [r for r in re.finditer(self._group, s)]
            if not found:
                break
            for f in found:
                matched_string = f.group()
                num, char = f.groups()
                replaced = char * int(num)
                s = s.replace(matched_string, replaced)
        return s