[3부 선형 자료구조] 10장 데크, 우선순위 큐
14812 단어 파이썬 알고리즘 인터뷰pythonpython
📌 26) 원형 데크 디자인 ( 리트코드 641. Design Circular Deque )
✔ 풀이
class MyCircularDeque(object):
def __init__(self, k):
self.maxlen, self.len = k, 0
self.head = ListNode(None)
self.tail = ListNode(None)
self.head.right, self.tail.left = self.tail, self.head
def _add(self, node, new): #(추가할 노드의 위치 보다 하나 앞의 위치에 있는 노드, 추가할 노드)
n = node.right #node의 다음 node를 n으로 지정
node.right = new
n.left = new
new.left, new.right = node, n
def _del(self, node): #(삭제할 노드의 위치 보다 하나 앞의 위치에 있는 노드)
n = node.right.right #node의 다음 다음 위치에 있는 node를 n으로 지정
node.right = n
n.left = node
def insertFront(self, value):
if self.len == self.maxlen:
return False
self.len += 1
self._add(self.head, ListNode(value))
return True
def insertLast(self, value):
if self.len == self.maxlen:
return False
self.len += 1
self._add(self.tail.left, ListNode(value))
return True
def deleteFront(self):
if self.len == 0:
return False
self.len -= 1
self._del(self.head)
return True
def deleteLast(self):
if self.len == 0:
return False
self.len -= 1
self._del(self.tail.left.left)
return True
def getFront(self):
return -1 if self.len == 0 else self.head.right.val
def getRear(self):
return -1 if self.len == 0 else self.tail.left.val
def isEmpty(self):
return self.len == 0
def isFull(self):
return self.len == self.maxlen
📌 27) k개 정렬 리스트 병합 ( 리트코드 23. Merge k Sorted Lists )
✔ 풀이
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
import heapq
class Solution(object):
def mergeKLists(self, lists):
root = result = ListNode(None)
#우선순위 큐 사용 / (값, 인덱스(몇 번째 리스트인지), 연결리스트) / 인덱스(몇 번째 리스트인지)
#중복을 막기 위해 인덱스 사용 => 중복이면 error 나기 때문에
Q = []
for i, list in enumerate(lists):
if list:
heapq.heappush(Q, (list.val, i, list))
while Q:
node = heapq.heappop(Q)
idx = node[1]
result.next = node[2]
result = result.next #result이동
if result.next:
heapq.heappush(Q, (result.next.val, idx, result.next))
return root.next
Author And Source
이 문제에 관하여([3부 선형 자료구조] 10장 데크, 우선순위 큐), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@himinhee/3부-선형-자료구조-10장-데크-우선순위-큐저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)