leetcode 978(구현), 103(트리), 200(bfs), 130(bfs)

978 https://leetcode.com/problems/longest-turbulent-subarray/

 

이거 푸는데 한참걸렸다.. turbulent는 내부의 값들이 올라갔다 내려가는 것들의 부분집합이다. 

이후에는 길이가 2 이상인 것들만을 처리하기 위해 일단 맨 앞에서 길이가 1인것들과 2인것들을 미리 처리해준다. 그리고 [100, 100, 100]은 길이가 3 이상임에도 답은 1이 나와야하니 이런것들도 걸러준다. 최소 len(set(arr))으로 뽑았을때 두개 이상이 나와야 turbulent가 만들어진다. [1, 0, 1, 0, 1]같이 두개로도 만들어질수 있다. 그러니 예외케이스를 걸러주고..

계산을 해야하는데 복잡하게 앞이 ><형태였으면 다음이 <>형태인지, 이전 형태값을 저장해두지 않아도 괜찮다. 단순히 i > i+1 < i+2 or i < i+1 > i+2로 조건을 걸어놓으면 아닐 경우 tur변수가 2로 초기화되므로, 계속 잘 만들어지기 때문이다.

class Solution:
    def maxTurbulenceSize(self, arr: List[int]) -> int:
        if len(arr) < 3 or len(set(arr)) == 1:
            return len(set(arr))
        
        ret = 0
        tur = 2
        for i in range(len(arr)-2):
            if arr[i] > arr[i+1] < arr[i+2] or arr[i] < arr[i+1] > arr[i+2]:
                tur += 1
            else:
                tur = 2
            ret = max(ret, tur)
        return ret

103 https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

 

순회하면서 depth키로, 값들을 리스트로 저장해둔다. 그리고 홀수들은 거꾸로 출력하도록 한다.

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        
        ret = {}
        queue = [[root, 0]]
        while queue:
            node, depth = queue.pop(0)
            ret[depth] = ret.get(depth, []) + [node.val]
            l, r = node.left, node.right
            if l:
                queue.append([l, depth+1])
            if r:
                queue.append([r, depth+1])
        ret = (v if k % 2 == 0 else v[::-1] for k,v in ret.items())
        return ret

200 https://leetcode.com/problems/number-of-islands/

 

오랫만에 보는 bfs. 쉬어가는 느낌이다.

class Solution(object):
    def numIslands(self, grid):
        self.island_count = 0
        def bfs(i,j):
            self.island_count += 1
            visited = set((i, j))
            queue = [[i,j]]
            while queue:
                p = queue.pop(0)
                grid[p[0]][p[1]] = '0'
                for pos in [[0, -1], [1, 0], [0, 1], [-1, 0]]:
                    x,y = p[0] + pos[0], p[1] + pos[1]
                    if x < 0 or y < 0 or x > len(grid) -1 or y > len(grid[0]) -1 or (x, y) in visited:
                        continue
                    if grid[x][y] == '1':
                        queue.append([x,y])
                        visited.add((x, y))
                        
        for i in xrange(len(grid)):
            for j in xrange(len(grid[0])):
                if grid[i][j] =='1':
                    bfs(i, j)
        return self.island_count

130 https://leetcode.com/problems/surrounded-regions/

 

쉬어가는 bfs문제 2. 경계에 있는 O와 이웃이면 O로 남아있는다. 그게 아니라 X로 둘러쌓여있으면 X로 변함.

 

1. 경계를 돌면서 O가 있으면 주변 O들까지 전부 '1'로 변환시켜준다.(살릴 O를 이렇게 표시해둠.)

2. grid를 다 돌면서 O가 있으면 다 X로 변환시켜준다.

3. grid를 다 돌면서 '1'을 O로 되살려준다.

class Solution(object):
    def solve(self, grid):
        if not grid:
            return []
        def bfs(i,j):
            visited = set((i, j))
            queue = [[i,j]]
            while queue:
                p = queue.pop(0)
                grid[p[0]][p[1]] = '1'
                for pos in [[0, -1], [1, 0], [0, 1], [-1, 0]]:
                    x,y = p[0] + pos[0], p[1] + pos[1]
                    if x < 0 or y < 0 or x > len(grid) -1 or y > len(grid[0]) -1 or (x, y) in visited:
                        continue
                    if grid[x][y] == 'O':
                        queue.append([x,y])
                        visited.add((x, y))

        for i in xrange(len(grid)):
            if grid[i][0] == 'O':
                bfs(i, 0)
            if grid[i][len(grid[0]) - 1] == 'O':
                bfs(i, len(grid[0]) - 1)
        for i in xrange(len(grid[0])):
            if grid[0][i] == 'O':
                bfs(0, i)
            if grid[len(grid) - 1][i] == 'O':
                bfs(len(grid) - 1, i)

        for i in xrange(len(grid)):
            for j in xrange(len(grid[0])):
                if grid[i][j] == 'O':
                    grid[i][j] = 'X'

        for i in xrange(len(grid)):
            for j in xrange(len(grid[0])):
                if grid[i][j] == '1':
                    grid[i][j] = 'O'