archives

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..

https://leetcode.com/problems/next-permutation/discuss/13867/C%2B%2B-from-Wikipedia 의 댓글에 아주 잘 설명되어있다. 정리함. next permutation을 구하는 방법. 2,3,6,5,4,1로 알고리즘의 예를 듬. 1. 오른쪽에서 왼쪽으로 순회하면서 수가 증가하지 않는 부분을 찾는다. 2,3,6,5,4,1에서는 3 이다. 2-1. 수가 증가하지 않는 부분이 없으면 이 뜻은 permutation의 맨 마지막이라는 뜻이다. 이경우 맨 마지막의 다음은 맨 처음이므로 그냥 순서를 거꾸로 해주면 된다. 예로 6,5,4,3,2,1의 경우인데, 이 경우 그냥 거꾸로 순서를 해주면 맨 처음인1,2,3,4,5,6이다. 2-2. 수가 증가하지 않는 부분..

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..

es에 데이터를 넣으려고 하는데 u'error': {u'reason': u'blocked by: [FORBIDDEN/12/index read-only / allow delete (api)];', u'type': u'cluster_block_exception'} 요런 메시지가 뜨면서 데이터가 es로 들어가지 않는다. 구글링해보니 https://dev-yeon.tistory.com/12 에서 디스크가 거의 차서 발생하는 에러라고 한다. 디스크가 찼으면.. 인덱스를 좀 지워주면 되겠네? 하고 지우려했더니 read only라고 에러가 뜬다.저 블로그에서 나온것처럼 read only모드를 풀어주자. PUT _all/_settings { "index": { "blocks": { "read_only_allow_del..

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 ..