237. Delete Node in a Linked List
https://leetcode.com/problems/delete-node-in-a-linked-list/
My Answer 1: Accepted (Runtime: 40 ms - 60.14% / Memory Usage: 14.7 MB - 62.98%)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
n = node.next
while node:
node.val = n.val
n = n.next
if n is None:
node.next = None
node = node.next주어지는 node 는 항상 마지막 노드가 아니므로 n = node.next
node 부터 보면서 next 값을 node 에 덮어씌움
Solution 1: Accepted (Runtime: 36 ms - 84.58% / Memory Usage: 14.7 MB - 62.98%)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
node.val = node.next.val
node.next = node.next.next저번에 푼 건데
그냥 현재 node 에 node.next 를 바로 덮어씌우기
value 값만 복사해주고 next 값은 node.next.next 로
242. Valid Anagram
https://leetcode.com/problems/valid-anagram/
My Answer 1: Accepted (Runtime: 48 ms - 67.91% / Memory Usage: 14.9 MB - 21.46%)
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if sorted(s) == sorted(t):
return True
return False정렬한 값이 같은지 확인
s 와 t 의 Count 를 구해서 비교해도 될 듯
138. Copy List with Random Pointer
https://leetcode.com/problems/copy-list-with-random-pointer/
My Answer 1: Wrong Answer (2 / 19 test cases passed.)
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
nodelists = {}
ans = Node(head.val)
h = head
while head:
nextt = None
if head.next:
if head.next.val in nodelists:
nextt = nodelists[head.next.val]
else:
nextt = Node(head.next.val)
nodelists[head.next.val] = nextt
random = None
if head.random:
if head.random.val in nodelists:
random = nodelists[head.random.val]
else:
random = Node(head.random.val)
nodelists[head.random.val] = random
if head.val in nodelists:
nodelists[head.val].next = nextt
nodelists[head.val].random = random
else:
newNode = Node(head.val, nextt, random)
nodelists[head.val] = newNode
head = head.next
return nodelists[h.val]nodelists 에 새로 만든 노드들을 넣어줌 ex) 7: Node(7, next, random)
head 를 돌려보면서 next 와 random 이 nodelists 에 없으면 새로 생성
있으면 존재하는 노드 가져와서 사용
그러나.. value 가 중복될 경우 처리가 안됨
=> key 값이 value 이기 때문...^^
Solution 1: Accepted (Runtime: 32 ms - 86.68% / Memory Usage: 14.9 MB - 63.34%)
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if head is None:
return None
mapping = {}
cur = head
while cur:
mapping[cur] = Node(cur.val,None,None)
cur = cur.next
cur = head
while cur:
if cur.next:
mapping[cur].next = mapping[cur.next]
if cur.random:
mapping[cur].random = mapping[cur.random]
cur = cur.next
return mapping[head]mapping 에 original 노드 자체를 key 값으로 하고 새 노드 생성
=> 이게 포인트였나보다... 내 풀이에도 key 값만 바꿔줬더니 패스함ㅠ
다시 head 부터 보면서 next 와 random 연결
하지만 이 풀이가 더 간단하니까 이걸로 알아두자~
139. Word Break
https://leetcode.com/problems/word-break/
My Answer 1: Time Limit Exceeded (35 / 45 test cases passed.)
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
words = set(wordDict)
def func(s, w):
if s in words or len(s) == 0:
return True
a = 0
for i in range(len(s), 0, -1):
if s[:i] in words:
words.add(w+s[:i])
a |= func(s[i:], w+s[:i])
return a
return func(s, "")words 에 가능한 조합들을 모두 저장
더 긴 word 부터 처리하기 위해 거꾸로 보면서 s[:i] 가 사전에 있을때만 재귀 돌리기
w+s[:i] => 사전 내 단어들의 새로운 조합들
|(or) 연산자로 하나라도 True 가 있으면 return True
Solution 1: Accepted (Runtime: 44 ms - 36.06% / Memory Usage: 14.6 MB - 14.52%)
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [False for i in range(len(s) + 1)] #(1)
dp[0] = True
for i in range(len(s) + 1): #(2)
for j in range(i):
if dp[j] and s[j:i] in wordDict: #(3)
dp[i] = True
break #(4)
return dp[len(s)] #(5)
#(1) dp[i] = s[0:i] is breakable
#(2) Considering all possible substrings of s.
#(3) If s[0:j] is breakable and s[j:i] is breakable, then s[0:i] is breakable. Equivalently, if dp[j] is True and s[j:i] is in the wordDict, then dp[i] is True.
#(4) Our goal is to determine if dp[i] is breakable, and once we do, we don't need to consider anything else. This is because we want to construct dp.
#(5) dp[len(s)] tells us if s[0:len(s)] (or equivalently, s) is breakable.s 길이 만큼의 dp 사용 / 시작 값은 dp[0] = True
s[0:i] 가 사전 조합으로 이뤄졌으면 dp[i] = 1
if dp[j] and s[j:i] in wordDict:
=> j 는 0 ~ i 범위
=> j 앞 부분도 유효하고 s[j:i] 도 유효하면 0 ~ i 까지는 다 유효하니까 dp[i] = True
T/F 누적된 값인 dp[len(s)] 를 return 하면 끝~
꼭 알아두자!!!
