분류 전체보기267 [LeetCode] Repeated Substring Pattern 파이썬 (KMP) 문제 풀이하기전에 KMP 알고리즘이 무엇인지 알아보자 이 문제를 Brute Force로 풀면 풀리긴 하지만. O(n*m)의 문제를 O(n)으로 풀 수 있는 KMP 알고리즘으로 풀어보자 알고리즘 자체는 어렵지 않지만 설명이 어쩔 수 없이 길어지는 알고리즘이다. 요약: LPS 라는 table을 생성 ( Longest Prefix and also Suffix ) LPS 테이블을 활용해서 이미 searched된 pattern은 skip. LPS 테이블에서 0이 아닌 sub-pattern부터 탐색 가능하기 때문에 효율적인 방식. class Solution(object): def repeatedSubstringPattern(self, str): """ :type str: str :rtype: bool """ def.. 2021. 4. 18. [LeetCode] Assign Cookies 파이썬 (greedy) class Solution: def findContentChildren(self, g: List[int], s: List[int]) -> int: g.sort() s.sort() result, i = 0, 0 for j in range(len(s)): if i == len(g): break if s[j] >= g[i]: result += 1 i += 1 return result 우선 sort 하고 two pointer(i,j) i를 g의 pointer로 사용하고 j는 s의 pointer로 사용하면서 하나씩 체크해 나간다. i == len(g) 를 통해 g의 모든 element를 체크했으면 exit s의 j-th 원소와 g의 i-th 원소를 비교하면서 조건에 맞으면 result에 count + 1 i를 한.. 2021. 4. 17. [LeetCode] Find All Numbers Disappeared in an Array 파이썬(set.difference) class Solution: def findDisappearedNumbers(self, nums: List[int]) -> List[int]: n = len(nums) nums1 = list(range(1,n+1)) return list(set(nums1).difference(nums)) 2021. 4. 16. [LeetCode] Arranging Coins 파이썬 (Binary Search, maximize) class Solution2(object): def arrangeCoins(self, n): """ :type n: int :rtype: int """ left, right = 1, n while left int: left, right = 0, n while left n: right = mid - 1 else: left = mid + 1 return right # need maximum value 문제를 직사각형으로 확장하면 쉽게 풀리지만 그걸 떠올리기가 쉬운지는 모르겠음. 높이(k)가 3일 경우, o x x o o x o o o 이런식으로 만들어 진다. 여기에 1열을 추가한다면 o x x x o o x x o o o x 이렇게 k * k+1의 직사각형의 면적의 절반이 n개의 코인을 위치시킬 수 있는 최.. 2021. 4. 16. [LeetCode] Number of Segments in a String 파이썬 (white space as None) class Solution: def countSegments(self, s: str) -> int: return len([i for i in s.strip().split(' ') if i]) strip은 안전하게 양쪽 끝의 공백을 제거하는 용도로 넣어준 듯. if i 라는 조건을 통해 whitespace가 아닐 경우만 새로운 list의 원소로 추가. str.strip str.strip([chars]) Return a copy of the string with the leading and trailing characters removed. 2021. 4. 16. [LeetCode] Fizz Buzz 파이썬 (여러 솔루션) class Solution: def fizzBuzz(self, n: int) -> List[str]: res = [] k = 1 while k 2021. 4. 16. [LeetCode] Longest Palindrome 파이썬 (bitwise &, Counter) from collections import Counter class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: int """ odds = 0 for k, v in Counter(s).items(): odds += v & 1 return len(s) - odds + int(odds > 0) lambda, map을 사용해서 홀 수 인 s 구하기 def longestPalindrome2(self, s): """ :type s: str :rtype: int """ odd = sum(map(lambda x: x & 1, Counter(s).values())) return len(s) - odd + int(odd > 0) 홀.. 2021. 4. 16. [LeetCode] Sum of Left Leaves 파이썬 (Tree) class Solution(object): def sumOfLeftLeaves(self, root): """ :type root: TreeNode :rtype: int """ def sumOfLeftLeavesHelper(root, is_left): if not root: return 0 if not root.left and not root.right: return root.val if is_left else 0 return sumOfLeftLeavesHelper(root.left, True) + sumOfLeftLeavesHelper(root.right, False) return sumOfLeftLeavesHelper(root, False) leaf 노드 까지 탐색한다. left일 경우에만 + 출처: .. 2021. 4. 15. [LeetCode] Is Subsequence 파이썬 (pointer, relative position) class Solution: def isSubsequence(self, s: str, t: str) -> bool: if not s: return True i = 0 for c in t: if c == s[i]: i += 1 if i == len(s): return True return False i를 pointer로 사용해서 relative position 위치 정보를 고려해서 순차적으로 i를 하나씩 업데이트 다 찾은 경우 (i==len(s)) return. 출처: github.com/jiapengwen/LeetCode/blob/master/Python/is-subsequence.py 2021. 4. 15. 이전 1 2 3 4 5 6 7 8 ··· 30 다음
