본문 바로가기

Leetcode98

[LeetCode] Reverse Linked List 파이썬 iterative way # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: ListNode) -> ListNode: prev = None curr = head while curr: nxt = curr.next curr.next = prev prev = curr curr = nxt return prev recursive way class Solution: # @param {ListNode} head # @return {ListNode} def re.. 2021. 4. 5.
[LeetCode] Isomorphic Strings 파이썬 class Solution: def isIsomorphic(self, s: str, t: str) -> bool: s2t, t2s = {}, {} for p, w in zip(s, t): if w not in s2t and p not in t2s: s2t[w] = p t2s[p] = w elif w not in s2t or s2t[w] != p: # Contradict mapping. return False return True 서로 상대방의 string을 key와 value로 map 한다. elif 문 w(p의 char)가 s의 dict인 s2t에 없거나(처음 보는 다른 char일 경우) s2t의 key는 있지만 (t의 char이 s에 있지만, 즉 기존에 mapped 되었지만), 새로운 char가 등장.. 2021. 4. 5.
[LeetCode] Count Primes 파이썬 class Solution: def countPrimes(self, n: int) -> int: return len(self.getPrimaryNum_Eratos(n)) def getPrimaryNum_Eratos(self,N): nums = [True] * (N + 1) for i in range(2, len(nums) // 2 + 1): if nums[i] == True: for j in range(i+i, N, i): nums[j] = False return [i for i in range(2, N) if nums[i] == True] 출처: somjang.tistory.com/entry/leetCode-204-Count-Primes-Python 2021. 4. 4.
[LeetCode] Remove Linked List Elements 파이썬 (linked list) class Solution: # @param {ListNode} head # @param {integer} val # @return {ListNode} def removeElements(self, head, val): dummy = ListNode(float("-inf")) dummy.next = head prev, curr = dummy, dummy.next while curr: if curr.val == val: prev.next = curr.next else: prev = curr curr = curr.next return dummy.next dummy를 만들고 dummy의 카피인 prev, curr 2개를 만들어서 문제해결 dummy 하나만 쓰고 하는 풀이 class Solution: def re.. 2021. 4. 4.
[LeetCode] Happy Number 파이썬 (dict, cycle) class Solution: def isHappy(self, n): lookup = {} while n != 1 and n not in lookup: lookup[n] = True n = self.nextNumber(n) return n == 1 def nextNumber(self, n): new = 0 for char in str(n): new += int(char)**2 return new 출처: github.com/jiapengwen/LeetCode/blob/master/Python/happy-number.py 2021. 4. 4.
[LeetCode] Fatorial Trailing Zeros 파이썬 (dp) cache = {} class Solution: def factorial_recursive(self,n): global cache if n in cache: return cache[n] elif n 1 else 1 def get_zeros(self, ls): ls = list(str(ls))[::-1] cnt = 0 for num in ls: if num == "0": cnt += 1 else: break return cnt def trailingZeroes(self, n: int) -> int: if n == 0: return 0 else: ans = self.factorial_recursive(n) ans = self.get_zeros(ans) return ans DP로 Factorial을 구하는 메.. 2021. 4. 3.
[LeetCode] Excel Sheet Column Number 파이썬 (ord) class Solution: def titleToNumber(self, columnTitle: str) -> int: result = 0 for i in range(len(columnTitle)): result *= 26 result += ord(columnTitle[i]) - ord('A') + 1 return result 첫 번째 A는 26x0 + ord("A") - ord("A") + 1 (A는 1로 문제에서 인식하기 때문에) 두 번째 B는 26x1 + ord("B") - ord("A") + 1 로 나타내기 때문에 result 초기값을 0으로 설정한 다음 계속 26을 곱해주고 해당 alphabet의 값을 더해준다 2021. 4. 3.
[LeetCode] Majority Element 파이썬 (dict, Counter, median) nums = [2,2,1,1,1,2,2] d = dict() for n in nums: if n in d: d[n] += 1 else: d[n] = 0 print(d) print(sorted(d.items(), key=lambda x: -x[1])[0][0]) # output # {2: 3, 1: 2} # [(2, 3), (1, 2)] #(key, value) # 2 dict에 넣어서 sorted key items()로 iterable하게 만든 다음 tuple로 나오는 값 중에서 뒤의 value 인 x[1]을 기준으로 오름차순으로 해야하기 때문에 -x[1] 으로 해준다. 제일 앞에 있는 tuple 중에서 key값을 return 해야되기 때문에 [0][0] 2021. 4. 2.
[LeetCode] Excel Sheet Column Title 파이썬 (divmod, chr, ord) class Solution: def convertToTitle(self, columnNumber: int) -> str: q = columnNumber ans = "" while True: if q == 0: break q, r = divmod(q-1,26) ans += chr(r + ord('A')) return ans[::-1] 0-indexing이기 때문에 q-1을 한 값에 divmod를 26으로 추출 대문자를 출력해야 되기 때문에 ord("A") ,즉 65를 기준으로 r(나머지) 를 더한 값을 chr에 인자로 넣어서 character를 ans에 추가해준다. return은 역순으로 해줘야 한다. dict을 활용한 방법 alpha = {} az = [chr(x) for x in range(ord("A.. 2021. 4. 2.