208. Implement Trie (Prefix Tree)
https://leetcode.com/problems/implement-trie-prefix-tree/
My Answer 1: Accepted (Runtime: 156 ms - 78.84% / Memory Usage: 25.3 MB - 96.51%)
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.words = set()
self.prefix = set()
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
if word not in self.words:
self.words.add(word)
if word not in self.prefix:
for i in range(1, len(word)+1):
self.prefix.add(word[:i])
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
if word in self.words:
return True
return False
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
if prefix in self.prefix:
return True
return False
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)words 에는 insert 된 word 들 저장
prefix 에는 word 마다 모든 prefix 들을 저장
insert)
이미 본 단어가 아닐때만 add 하도록
word 는 words 에 저장하고
0 ~ i 의 prefix 들은 모두 prefix 에 저장
search)
word 자체가 있는지 확인해야 하니까 words 에서 찾기
startsWith)
prefix 에서 찾기
Trie 노드 자체를 만드는건 모르겠다...^^
Solution 1: Accepted (Runtime: 192 ms - 43.48% / Memory Usage: 33.2 MB - 18.30%)
class TrieNode:
# Initialize your data structure here.
def __init__(self):
self.children = collections.defaultdict(TrieNode)
self.is_word = False
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = TrieNode()
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
current = self.root
for letter in word:
current = current.children[letter]
current.is_word = True
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
current = self.root
for letter in word:
current = current.children.get(letter)
if current is None:
return False
return current.is_word
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
current = self.root
for letter in prefix:
current = current.children.get(letter)
if current is None:
return False
return True
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)클래스 TrieNode 를 따로 만듦
노드들은 linkedlist 대신 dictionary 를 사용하면 된다
init) root 생성
insert)
root 부터 word 한글자씩 children 에 저장
마지막 노드의 is_word 만 True
search)
word 의 글자들이 모두 root 의 children 에 있는지 확인
get 이 실패하면 return False
나머지는 return is_word
=> word 가 root 전체를 본게 아니면 return False 가 됨
startsWith)
prefix 의 글자들이 모두 root 의 children 에 있는지 확인
get 이 실패하면 return False
모두 있으면 prefix 니까 return True
절 대 외 워 !!!
210. Course Schedule II
https://leetcode.com/problems/course-schedule-ii/
My Answer 1: Accepted (Runtime: 152 ms - 13.64% / Memory Usage: 33.4 MB - 6.41%)
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
seen = {}
dic = {}
for i in range(numCourses):
dic[i] = []
seen[i] = -1
for a, b in prerequisites:
dic[a].append(b)
self.ans = []
for i in range(numCourses):
if not dic[i]:
self.ans.append(i)
def func(course, lists):
if seen[course] == 1:
return True
seen[course] = 0
a = 1
for i in range(len(dic[course])):
if seen[dic[course][i]] == 0:
return False
a *= func(dic[course][i], lists+[course])
if a:
seen[course] = 1
if course not in self.ans:
self.ans.append(course)
return a
for a, b in prerequisites:
if seen[a] == -1:
func(a, [])
elif seen[a] == 0:
return []
return self.ans207. Course Schedule 풀었던 걸 생각하면서...
dic 에는 선수 과목들을 연결해주고 seen 은 -1 로 초기화
선수과목이 없는 과목들은 순서에 영향이 없으니까 미리 ans 에 append
과목들을 보면서 seen 이 -1 이면 재귀 돌려서 순서를 찾아줌
func)
seen 이 1 이면 유효한 게 증명된 거니까 return True
나머지는 확인이 필요하니까 seen 을 0 으로 하고
연결된 선수과목들을 모두 확인해줌
이때, 선수과목의 seen 값이 0 이면 cycle 이 생긴 거니까 return False
=> if seen[dic[course][i]] == 0:
전부 무사히 통과되면 a 는 1 이 됨
그때 증명이 됐다는 표시로 seen 을 1 로 바꾸고 ans 에 course append
모두 확인하고 나면 return ans
215. Kth Largest Element in an Array
https://leetcode.com/problems/kth-largest-element-in-an-array/
My Answer 1: Accepted (Runtime: 64 ms - 71.45% / Memory Usage: 15.1 MB - 46.44%)
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
nums.sort()
return nums[-k]sort 해서 뒤에서 k 번째 값 return
이외에 다른 정렬을 써도 nums[-k] 만 return 하면 될 듯
근데 이러면 거의 easy 급이라...
포인터 써서 어떻게 해볼까 했는데 못함..^^
Solution 1: Accepted (Runtime: 64 ms - 71.45% / Memory Usage: 15.1 MB - 76.03%)
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
heap = []
for num in nums:
heapq.heappush(heap, num)
for _ in range(len(nums)-k):
heapq.heappop(heap)
return heapq.heappop(heap)min-heap 이용
자동으로 정렬되니까 모두 heappush
len(nums)-k 만큼 pop 하고 마지막엔 k 번째 큰 값 return
partition 은 넘 어려워서 이거까지만 알아두기로~
