116 https://leetcode.com/problems/populating-next-right-pointers-in-each-node/
왼쪽에 있는 노드들의 next를 전부 오른쪽을 보게끔 하는 문제이다.
현재노드의 왼쪽자식.next = 현재노드의 오른쪽 자식. 그다음 루프를 돌때
부모쪽에서 현재 노드의 next를 만들어줬었으면 그 정보를 토대로 만들어준다. 그림을 보면서 짜면 더 편하다.
class Solution(object):
def connect(self, root):
if not root:
return None
cur = root
_next = root.left
while _next:
cur.left.next = cur.right
if cur.next:
cur.right.next = cur.next.left
cur = cur.next
else:
cur = _next
_next = cur.left
return root
117 https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
순회를 하는데 이번엔 자식이 있을수도 있고 없을수도 있다.
from collections import deque
class Solution(object):
def connect(self, root):
if not root:
return root
q = deque([root])
while q:
qq = deque()
for i in xrange(len(q)-1): # 같은 level에 있는 것들은 다음 노드를 next로 설정해줌.
q[i].next = q[i+1]
for i in xrange(len(q)): # 같은 level에 있는 노드들을 전부 순회하면서 자식이 있으면 temp q개념인 qq에 넣어두고 q를 다시 초기화해줌.
if q[i].left:
qq.append(q[i].left)
if q[i].right:
qq.append(q[i].right)
q = qq
return root
199 https://leetcode.com/problems/binary-tree-right-side-view/
위에 117번에서 약간만 변경
from collections import deque
class Solution(object):
def rightSideView(self, root):
if not root:
return []
q = deque([root])
ret = deque()
while q:
qq = deque()
ret.append(q[-1].val)
for i in xrange(len(q)):
if q[i].left:
qq.append(q[i].left)
if q[i].right:
qq.append(q[i].right)
q = qq
return ret
203 https://leetcode.com/problems/remove-linked-list-elements/
다음 노드가 제거해야하는 val이면 다음다음 노드값도 val일수 있으므로 val이 아닐때까지 이동하고 현재의 다음 노드를 그 값으로 변경해준다.
class Solution(object):
def removeElements(self, head, val):
dummy = ListNode(0, head)
head = dummy
while head:
cur = head
if cur.next and cur.next.val == val:
cur_next_next = cur.next.next
while cur_next_next and cur_next_next.val == val:
cur_next_next = cur_next_next.next
cur.next = cur_next_next
head = head.next
return dummy.next
849 https://leetcode.com/problems/maximize-distance-to-closest-person/
시키는대로 구현한다.
class Solution(object):
def maxDistToClosest(self, seats):
seated_index = [i for i,v in enumerate(seats) if v == 1] # 이미 앉은 자리를 기록해둔다.
seated_index_len = len(seated_index)
seat_len = len(seats)
if seated_index_len == 1: # 중간에 1자리만 앉았으면 첫번째 자리나 끝 자리가 답이다.
return max(seated_index[0], abs(seat_len-1 - seated_index[0]))
max_distance = -1
if seated_index[0] != 0: # 첫번째 자리를 아무도 안 앉았으면 첫번째 자리와 거기서 가장 가까운 자리의 거리를 계산해둔다.
max_distance = seated_index[0]
if seated_index[-1] != seat_len-1: # 끝 자리를 아무도 안 앉았으면 끝자리와 거기서 가장 가까운 자리의 거리를 계산해둔다.
max_distance = max(max_distance, seat_len-1 - seated_index[-1])
for i in xrange(seated_index_len-1): # 중간 자리들의 최대치를 계산해준다.
max_distance = max(max_distance, (seated_index[i+1] - seated_index[i])/2)
return max_distance