본문 바로가기

Leetcode98

[LeetCode] Two Sum II - Input array is sorted 파이썬 class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: seen = {} for i, v in enumerate(numbers): remaining = target - v if remaining in seen: return [seen[remaining]+1, i+1] seen[v] = i return [] 기존의 Two Sum 과 다른 점은 sorted array라는 점과 zero-indexed가 아니라 1-indexed이라는 점. 2021. 4. 2.
[LeetCode] Intersection of Two Linked Lists (switch) 솔루션 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: p1 = headA p2 = headB while p1 != p2: if p1: p1 = p1.next else: p1 = headB if p2: p2 = p2.next else: p2 = headA return p1 while 문 조건을 p1 != p2 기준으로 두 node가 같은 경우 while문 중단한다. node가 다른 경우 .. 2021. 4. 2.
[LeetCode] Linked List Cycle 파이썬 (is operator, id) 2가지 풀이법(1: fast & slow, 2: marked as read) 풀이 1 (fast, slow) class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: # @param head, a ListNode # @return a boolean def hasCycle(self, head): fast, slow = head, head while fast and fast.next: fast, slow = fast.next.next, slow.next if fast is slow: return True return False 어떻게 풀어야 할지 전혀 감이 안왔던 문제 fast, slow라는 2개의 head 의 c.. 2021. 4. 1.
[LeetCode] Single Number python (linear complexity) class Solution: def singleNumber(self, nums: List[int]) -> int: for i in range(len(nums)): if nums.count(nums[i]) == 1: return nums[i] count 활용해서 하긴 했는데 통과 못할 줄 알았는데 통과가 되었다. 역시 하위 93%의 속도 😱 다른 풀이(136ms): dict 사용 class Solution: def singleNumber(self, nums: List[int]) -> int: seen = {} for i in range(len(nums)): if nums[i] not in seen: seen[nums[i]] = 1 else: seen[nums[i]] += 1 for k,v in seen.i.. 2021. 4. 1.
[LeetCode] Valid Palindrome python (regex, filter, isalnum) 36ms import re class Solution: def isPalindrome(self, s: str) -> bool: s = re.sub(r'[^\w]|_', '', s.lower()) return s == s[::-1] re를 사용해서 모든 alphanumeric가 아닌 것(^) or underscore를 빈문자열로 바꾼다. 다른 풀이 class Solution: def isPalindrome(self, s: str) -> bool: cleanedString = "".join(filter(str.isalnum, s.upper()) ) return (0,1)[cleanedString == cleanedString[::-1]] str.isalnum을 사용해서 filter 내장함수 사용 return.. 2021. 4. 1.
[LeetCode] Best Time to Buy and Sell Stock II python (greedy) class Solution: # @param prices, a list of integer # @return an integer def maxProfit(self, prices): profit = 0 for i in range(len(prices) - 1): profit += max(0, prices[i + 1] - prices[i]) return profit 저점 매수 고점 매도 실제 시장에서는 불가능하지만 지금은 prices가 주어졌기 때문에 loss가 발생하기 전에 팔고 하락하자마자 다시 사면 profit maximization이 가능하기 때문에 i+1 과 i 시점에서의 차이가 0보다 클 경우 모두 더해주면 된다. 출처: github.com/jiapengwen/LeetCode/blob/master/.. 2021. 4. 1.
[LeetCode] Best Time to Buy and Sell Stocks python 1132 ms class Solution: def maxProfit(self, prices: List[int]) -> int: max_profit, min_price = 0, float("inf") for price in prices: min_price = min(min_price, price) max_profit = max(max_profit, price - min_price) return max_profit min_price를 min으로 업데이트 시켜주면서 element순서대로 작은 값으로 update max_price를 max로 업데이트 시켜주면서 price-min_price(현재 포함해서 그전까지 가장 작은 값, 만약 현재랑 같다면 0이 됨) 이런 문제는 다음에는 무조건 바로 해결해야됨. 출처: .. 2021. 4. 1.
[LeetCode] Pascal's Triangle 파이썬 (+Pascal's Triangle II) class Solution: # @return a list of lists of integers def generate(self, numRows): result = [] for i in range(numRows): result.append([]) for j in range(i + 1): if j in (0, i): # i==j(far right) or (j,0) (far left) result[i].append(1) else: result[i].append(result[i - 1][j - 1] + result[i - 1][j]) # left-leftup + left-up return result array 채우기 for j in range(i+1): fill row element Pascal's Tria.. 2021. 4. 1.
[LeetCode] Path Sum 파이썬 class Solution: # @param root, a tree node # @param sum, an integer # @return a boolean def hasPathSum(self, root, sum): if root is None: return False if root.left is None and root.right is None and root.val == sum: return True return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val) sum - curr_value 하면서 left, right node를 계속 탐색하다가 leaf 에 도착했을때 curr_value =.. 2021. 4. 1.

티스토리툴바