archives

437 https://leetcode.com/problems/path-sum-iii/ 1. 노드가 많아봐야 1000개라고 문제에 써있었으니 다른 방법이 기억 안날땐 O(n^2)으로 풀어도 된다.(제출 안하는것보다는 나으니.) from collections import deque class Solution(object): def pathSum(self, root, sum): if not root: return 0 nodelist = deque([root]) # nodelist에는 모든 노드들을 저장해놓는다. q = deque([root]) while q: p = q.popleft() if p.left: nodelist.append(p.left) q.append(p.left) if p.right: nodel..

116 https://leetcode.com/problems/populating-next-right-pointers-in-each-node/ 왼쪽에 있는 노드들의 next를 전부 오른쪽을 보게끔 하는 문제이다. 현재노드의 왼쪽자식.next = 현재노드의 오른쪽 자식. 그다음 루프를 돌때부모쪽에서 현재 노드의 next를 만들어줬었으면 그 정보를 토대로 만들어준다. 그림을 보면서 짜면 더 편하다. class Solution(object): def connect(self, root): if not root: return None cur = root _next = root.left while _next: cur.left.next = cur.right if cur.next: cur.right.next = cur...

1081 https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/ 문제를 이해하는데 시간이 좀 걸렸다. 문제를 쉽게 풀어쓰자면 중간에 중복된 단어를 지워서 결과값으로 단어가 1개씩만 나오도록 만드는데 결과값이 사전 순서상으로 가장 낮은 값이 나와야 한다. cdadabcc의 답이 abcd가 아니라 adbc가 나온 이유는 cdadabcc에서 a다음에 b가 먼저 오게 되면 b이후에는 cc밖에 없기때문에 d를 출력할수 없기 때문이다. 난 기본적으로 요 링크의 방법으로 풀었다. class Solution(object): def smallestSubsequence(self, text): order_dict = {} for i, t in e..

300 https://leetcode.com/problems/longest-increasing-subsequence/ lis문제이다. 예전에 백준에서 많이 풀었었다. 오랫만이니 리마인드해보자. https://qkqhxla1.tistory.com/763 from bisect import bisect_left class Solution(object): def lengthOfLIS(self, nums): if not nums: return 0 dp_len = max(nums)+1 if max(nums) > 0 else len(nums)+1 def lis(line): dp = [0 for i in xrange(dp_len)] size = 0 for i in xrange(len(line)): h = bisect_..

1114 https://leetcode.com/problems/print-in-order/ 쓰레드 환경에서의 lock관련된 실행 순서를 구현하는 문제이다. 반드시 first, second, third순으로 실행되게 하려면 lock으로 잠궜다 풀었다를 잘 해야 한다. lock.acquire()을 했을 경우 lock.release()를 호출해서 그 락을 풀어주기 전까지는 재차 lock.acquire()을 호출할수 없는점을 이용한다. first에는 아무런 제한 없이 출력하고 풀어준다. second에는 first에서의 락을 acquire()함으로써 first에서 release()가 호출될때까지 기다려야함으로써 first -> second호출순서가 유지된다. third도 마찬가지이다. from threading ..

733 https://leetcode.com/problems/flood-fill/ bfs문제이다. from collections import deque class Solution(object): def floodFill(self, image, sr, sc, newColor): original_color = image[sr][sc] q = deque([[sr, sc]]) visited = set() while q: x,y = q.popleft() image[x][y] = newColor for _x, _y in [[-1, 0], [0, -1], [0, 1], [1, 0]]: next_x, next_y = x + _x, y + _y if (next_x, next_y) not in visited and 0

45 https://leetcode.com/problems/jump-game-ii/ 설명은 코드에 적는다. dp문제이다. class Solution: def jump(self, nums: List[int]) -> int: dp = [99999999]*len(nums) dp[0] = 0 # 인덱스 0에서 시작함. cur_max = 0 for i in range(len(nums)): if i+nums[i] > cur_max: # 현재 갈수 있는 최대거리 이상으로 갈수있을때만 루프를 돈다. cur_max = i+nums[i] # 현재 갈수 있는 최대거리 갱신 for j in range(i+1, min(i+1+nums[i], len(nums))): # 현 위치에서 갈수있는곳들의 값을 업데이트시켜줌. dp[j] ..

134 https://leetcode.com/problems/gas-station/ 일단 포인트를 잡으면 이동은 무조건 i에서 i+1로 가고 cost[i]만큼 든다. 충전할수 있는 gas보다 드는 비용인 cost가 더 많으면 돌아올수 없으므로 종료를 시켜주고 시작한다. 마을을 순회하면서 충전되는 양보다 드는 비용이 더 많을 경우 0 ~ 현재위치까지는 시작해봐야 -가 되어서 못 간다는 의미이니 시작점을 다음으로 초기화시켜준다. class Solution(object): def canCompleteCircuit(self, gas, cost): if sum(gas) < sum(cost): return -1 start, gas_left = 0, 0 for i in xrange(len(gas)): gas_left..

442 https://leetcode.com/problems/find-all-duplicates-in-an-array/ 이전에 https://qkqhxla1.tistory.com/1044 요글의 leetcode 287번에서 중복되는 숫자 1개를 찾는 문제를 링크드 리스트에 사이클이 있다고 생각하여 사이클의 시작점을 찾는거로 풀수 있었는데, 같은 조건의 중복되는 숫자가 2개 이상일 경우에는 cycle sort라는게 있다. class Solution: def findDuplicates(self, nums: List[int]) -> List[int]: self.cyclicSort(nums) output = [] for i in range(len(nums)): if nums[i] != i+1: output.ap..

647 https://leetcode.com/problems/palindromic-substrings/ 이전에 https://qkqhxla1.tistory.com/1059 에서 leetcode 5번 문제에 대한 풀이를 적었었는데 같은 문제다. class Solution: def countSubstrings(self, s: str) -> int: ret = 0 for i in range(len(s)): l,r = i, i while 0 int: dp = [[0]*(len(word2)+1) for i in range(len(word1)+1)] for i in range(len(word1)): for j in range(len(word2)): if word1[i] == word2[j]: dp[i+1][j+1]..

24 https://leetcode.com/problems/swap-nodes-in-pairs/ 가져와서 구현해준다. https://leetcode.com/problems/swap-nodes-in-pairs/discuss/œ/Python-or-Dummynode에 좋은 풀이가 있다. 내 답은 드러워서 안적음 class Solution: def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]: dummy = p = ListNode(0) dummy.next = head while head and head.next: tmp = head.next head.next = tmp.next tmp.next = head p.next = tmp head = ..

208 https://leetcode.com/problems/implement-trie-prefix-tree/ https://qkqhxla1.tistory.com/1081?category=685988 에서 만든 코드를 갖다 쓴다. class Trie(object): def __init__(self): self.trie={} def insert(self, word): trie=self.trie for c in word: if c not in trie: trie[c]={} trie=trie[c] trie['#']='#' def search(self, word): stack = deque([[word, self.trie]]) while stack: word, trie = stack.pop() if not wo..

863 https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/ 1. 그래프 개념으로 어떤 한 노드에 연결된 모든 노드를 찾는다. 연결된 노드는 [부모, 왼쪽 자식, 오른쪽 자식]이다. 이것들을 node_list에 저장해놓는다. 2. 저장한 후에는 target을 시작점으로 [부모, 왼쪽 자식, 오른쪽 자식]을 돌면서 거리가 K인 노드들을 dfs로 탐색한다. from collections import deque class Solution(object): def distanceK(self, root, target, K): node_list = {} queue = deque([[root, None]]) # node, parent while queu..

97 https://leetcode.com/problems/interleaving-string/ dfs로 푼다. from collections import deque class Solution(object): def isInterleave(self, s1, s2, s3): s1_len, s2_len, s3_len = len(s1), len(s2), len(s3) if s1_len + s2_len != s3_len: return False stack = deque([[0, 0]]) visited = set() visited.add((0, 0)) while stack: p = stack.pop() if p[0] + p[1] == s3_len: return True if p[0] < s1_len and s1[..

79 https://leetcode.com/problems/word-search/ dfs로 푼다. from collections import deque class Solution(object): def exist(self, board, word): #board = [["A","B","C","E"], # ["S","F","E","S"], # ["A","D","E","E"]] #word = "ABCESEEEFS" #board = [["A","B","C","E"], # ["S","F","C","S"], # ["A","D","E","E"]] #word = "ABCB" queue = deque() row_len = len(board) col_len = len(board[0]) for i in xrange(row_..

224 https://leetcode.com/problems/basic-calculator/ 코드가 너무 더럽고 효율도 낮다.. ㅠㅠ 접어놓음.from collections import deque class Solution(object): def calculate(self, s): #s = "(5-(1+(5)))" stack = deque() len_s = len(s) i = 0 while i 1 and stack[-2] in ['-', '+'] and (stack[-1].isdigit() or (stack[-1][0] == '-' and stack[-1][1:].isdigit())): cur_int = int(stack.pop()) sign = stack.p..

953 https://leetcode.com/problems/verifying-an-alien-dictionary/ 시키는대로 구현한다. class Solution: def isAlienSorted(self, words: List[str], order: str) -> bool: d = {o: i for i, o in enumerate(order)} words = [[d[w] for w in word] for word in words] for i in range(max(len(w) for w in words)): check = [word[i] if len(word) > i else -1 for word in words] check = list(zip(check, check[1:])) if all(a < b..

139 https://leetcode.com/problems/word-break/ bfs로 풀었다. from collections import deque class Solution(object): def wordBreak(self, s, wordDict): #s = "catsanddog" #wordDict = ["cats", "dog", "sand", "and", "cat"] visited = set() wordDict = set(wordDict) queue = deque() for i in xrange(len(s)+1): if s[:i] in wordDict: visited.add(s[i:]) queue.append(s[i:]) #print 'queue =',queue while queue: p = q..

263 https://leetcode.com/problems/ugly-number/ ugly한 숫자란 2,3,5로만 나눴을때 나누어 떨어지는 수이다. ugly한 숫자인지 체크하자. class Solution(object): def isUgly(self, num): if num == 0: return False for p in [2, 3, 5]: while True: if num%p == 0: # num이 2,3,5중 하나로 나누어지면 안 나눠질때까지 계속 나눔. num /= p continue break return num == 1 # 1이 나오면 ugly한 숫자, 아니면 ㄴㄴ 264 https://leetcode.com/problems/ugly-number-ii/ n번째 ugly number를 구하는 ..

773 https://leetcode.com/problems/sliding-puzzle/ bfs로 모델링해서 푼다. 어려운 버전. from collections import deque class Solution(object): def slidingPuzzle(self, board): def bfs(x, y, board): queue = deque([[x, y, board[:], 0]]) visited = set([''.join(map(str, board))]) while queue: _x, _y, board, count = queue.popleft() _str = ''.join(map(str, board)) if _str == '123450': return count for __x, __y in [[-1..

560 https://leetcode.com/problems/subarray-sum-equals-k/ 딕셔너리에 https://leetcode.com/problems/two-sum/ 문제를 풀때처럼 이전까지의 합을 저장해놓는다. 그리고 현재까지의 총합 - k가 딕셔너리에 있으면 이 값은 이전 어디선가 만들어질수 있다는 뜻이므로 그만큼 +를 해준다. 그게 아니면 해당 수가 만들어질 경우의 수를 딕셔너리에 저장해준다. class Solution(object): def subarraySum(self, nums, k): d = {} d[0] = 1 total = 0 ret = 0 for i in xrange(len(nums)): total += nums[i] if total - k in d: ret += d[t..

297 https://leetcode.com/problems/serialize-and-deserialize-binary-tree/449 https://leetcode.com/problems/serialize-and-deserialize-bst/ 똑같은 문제라서 같이 올림. 문자열로 인코딩하고 디코딩해주는 문제이다. from collections import deque class Codec: def serialize(self, root): if not root: return '' ret = deque() queue = deque([root]) while queue: p = queue.popleft() if not p: ret.append('null') continue ret.append(p.val) for..

33 https://leetcode.com/problems/search-in-rotated-sorted-array/ [4,5,6,7,0,1,2] 처럼 sorted된 리스트가 두개가 있다고 생각한다. 그리고 그중에 target을 log(n)의 시간복잡도로 찾아야 한다. log(n) 보자마자 이분 탐색을 떠올려야 하고, 그러면 저렇게 반이 섞여진곳에서 어떻게 이분탐색을 할까? 생각해보자. 난 먼저 값이 변하기 시작하는 부분의 인덱스를 찾았다. (위의 [4,5,6,7,0,1,2]의 경우엔 4) 그리고 target이 변하기 시작하는 부분 전의 안에 있는지 후에 있는지 검사후 low와 high를 정한다. [4,5,6,7,0,1,2]의 경우엔 [4,5,6,7]과 [0,1,2]로 나눠질수 있는데 각각의 리스트들을 정..

322 https://leetcode.com/problems/coin-change/ 문제를 읽어보니 이전에 풀었던 백준 2293번 https://qkqhxla1.tistory.com/683 과 비슷하다. 여기서 코드를 가져와서 변형했다. class Solution(object): def coinChange(self, coins, amount): dp = [999999 for i in xrange(amount+1)] dp[0] = 0 for i in xrange(len(coins)): #모든 동전을 돌아가면서 for j in xrange(1, amount+1): #1원~만들고자하는 k원까지 if j >= coins[i]: #현재 동전으로 j원을 만들수있으면 dp[j] = min(dp[j], dp[j-coi..

271 https://leetcode.com/problems/encode-and-decode-strings/ 인코딩, 디코딩 함수를 구현하는 문제이다. 근데 그냥 인코딩후 디코딩이 제대로 되기만 하면 되니까 아주 간편하다. 원래는 base64같은거로 인코딩하고, 디코딩했을것같은데 여기서는 간편하게 절대 안나타날것같은 구분자인 ' '로 나누고 합쳐주는거로 했다.. class Codec: def encode(self, strs): if strs == []: return None return ' '.join(strs) def decode(self, s): if s is None: return [] return s.split(' ') 696 https://leetcode.com/problems/count-bin..

146 https://leetcode.com/problems/lru-cache/ lru 캐시를 구현하는 문제이다. python 의 ordereddict은 딕셔너리지만 넣은 순서가 보장된다. 이걸 이용한다. 아래처럼 구현하면 모든 연산이 O(1)이다. pop과 popitem이 O(1)연산인가? 궁금해서 찾아봤더니 맞다고 한다. from collections import OrderedDict class LRUCache(object): def __init__(self, capacity): self.cache = OrderedDict() self.c = capacity self.cur_len = 0 def get(self, key): if key not in self.cache: return -1 v = sel..

https://qkqhxla1.tistory.com/1061 에 이론을 정리해두고 아래는 응용 방법들을 정리해둠. 76. https://leetcode.com/problems/minimum-window-substring/S와 T가 있고, T의 모든 문자가 S에 포함되는 S의 가장 짧은 부분문자열의 길이를 구하여라. class Solution(object): def minWindow(self, s, t): if len(t) > len(s): return '' result = [] _dict = {} for tt in t: _dict[tt] = _dict.get(tt, 0) + 1 counter = len(_dict) begin = end = head = 0 _len = 999999999 while end ..

994 https://leetcode.com/problems/rotting-oranges/ 쉬어가는 bfs 비슷한문제. class Solution(object): def orangesRotting(self, grid): visited = set() def bfs(rotten_index_list): queue = rotten_index_list while queue: pop = queue.pop(0) for m in [[-1, 0], [0, 1], [0, -1], [1, 0]]: popx, popy = pop[0] + m[0], pop[1] + m[1] if popx len(grid)-1 or \ popy > len(grid[0])-1 or (popx, pop..

75 https://leetcode.com/problems/sort-colors/ 정렬을 구현하는 문제이다. 라이브러리 함수를 쓰면 안 되고, 되도록 constant한 공간만 사용하고 in-place로 입력으로 주어진 배열 자체를 바꾸라고 한다. counting sort로도 해보라고 한다. class Solution(object): def sortColors(self, n): n0,n1,n2 = 0,0,0 for nn in n: if nn == 0: n0 += 1 elif nn == 1: n1 += 1 else: n2 += 1 n[:n0] = [0]*n0 n[n0:n0+n1] = [1]*n1 n[n0+n1:n0+n1+n2] = [2]*n2 discussion에 있는 흥미로운 구현 방법들을 더 적어본다. ..

978 https://leetcode.com/problems/longest-turbulent-subarray/ 이거 푸는데 한참걸렸다.. turbulent는 내부의 값들이 올라갔다 내려가는 것들의 부분집합이다. 이후에는 길이가 2 이상인 것들만을 처리하기 위해 일단 맨 앞에서 길이가 1인것들과 2인것들을 미리 처리해준다. 그리고 [100, 100, 100]은 길이가 3 이상임에도 답은 1이 나와야하니 이런것들도 걸러준다. 최소 len(set(arr))으로 뽑았을때 두개 이상이 나와야 turbulent가 만들어진다. [1, 0, 1, 0, 1]같이 두개로도 만들어질수 있다. 그러니 예외케이스를 걸러주고.. 계산을 해야하는데 복잡하게 앞이 > i+1 i+2로 조건을 걸어놓으..