분류 전체보기267 [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. [LeetCode] Minimum Depth of Binary Tree 파이썬 (recursion) class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: # @param root, a tree node # @return an integer def minDepth(self, root): if root is None: return 0 if root.left and root.right: return min(self.minDepth(root.left), self.minDepth(root.right)) + 1 else: return max(self.minDepth(root.left), self.minDepth(root.right)) + 1 max와 다른 점은 leaf node 까지의.. 2021. 4. 1. [LeetCode] Balance Binary Tree python 파이썬 (recursion) # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def maxDepth(self, root): if root == None: return 0 else: return max( self.maxDepth(root.left), self.maxDepth(root.right)) + 1 def isBalanced(self, root): """ :type root: TreeNode :rtype: bool """ if root == No.. 2021. 4. 1. [LeetCode] Convert Sorted Array to Binary Tree python 파이썬 (recursion, median) 솔루션을 보기 전에는 어떤식으로 풀어야 하는지 감이 안왔다. 솔루션을 보고 나니 Binary Search 개념을 사용해서 mid 지점만 root 가 되도록 하면 되는 것이다. class Solution: def sortedArrayToBST(self, nums: List[int]) -> TreeNode: def sortToBST(nums): if len(nums) == 0: return None mid = nums[len(nums) // 2] root = TreeNode(mid) root.left = sortToBST(nums[:len(nums) // 2]) root.right = sortToBST(nums[len(nums) // 2 + 1:]) return root return sortToBST(num.. 2021. 4. 1. [LeetCode] Maximum Depth of Binary Tree 파이썬 (recursion) 40ms class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: # @param root, a tree node # @return an integer def maxDepth(self, root): if root is None: return 0 else: return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1 출처:github.com/jiapengwen/LeetCode/blob/master/Python/maximum-depth-of-binary-tree.py class Solution: def maxDepth(se.. 2021. 3. 31. 이전 1 ··· 9 10 11 12 13 14 15 ··· 30 다음
