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'
'algorithm > problem solving' 카테고리의 다른 글
leetcode 994(bfs), 286(bfs), 5(팰린드롬), 3(sliding window) (0) | 2020.04.27 |
---|---|
leetcode 75(구현), 14(구현), 1,167(2SUM), 15(3SUM) (0) | 2020.04.23 |
leetcode 198(dp), 213(dp), 337(dp) (0) | 2020.04.19 |
leetcode 338(dp), 11(two pointer), 36, 53(dp 카데인 알고리즘, 최대 부분합), 152(최대 부분곱) (0) | 2020.04.18 |
leetcode 67(합 구현), 415, 350(구현), 1002(구현), 202(구현), 258(숫자근 digit root) (0) | 2020.04.16 |