목록분류 전체보기 (76)
one line of code at a time
[leetcode] 417. Pacific Atlantic Water Flow 파이썬 코드
내가 좋아하는 그래프 문제. 왼쪽 위에는 태평양이 있고, 오른쪽 아래에는 대서양이 있다.이 둘을 건널 수 있는 좌표값들을 리스트에 반환하는 문제다. 태평양과 대서양을 건널 수 있는 좌표는 그 주변에 있는 섬들의 해수면 높이(sea level)보다 크거나 같아야 한다.즉, 이웃하는 셀들의 해수면 높이가 내가 위치한 셀의 해수면 높이보다 작거나 같아야 한다. 어떻게 해서 꾸역꾸역 푼 나의 코드는 다음과 같다. class Solution(object): def isPacific(self, r, c): if r == 0 and c == 0: return True elif r == 0 or c == 0: return True el..
[leetcode] 53. Maximum Subarray 파이썬 코드
배열이 주어졌을 때 이 배열의 subarray 중에서 가장 큰 합을 가지는 subarray의 합을 구하는 문제다. [8, -1, -1, -1, -1] 이런 배열도 있을 수 있겠고, 문제에서 예제로 주어진 건 3가지 배열이다. nums = [-2,1,-3,4,-1,2,1,-5,4]nums = [1]nums = [5,4,-1,7,8] 그래서 1개씩만 element를 볼 때, 2개, 3개, ..., len(nums)개를 한 꺼번에 볼 때 합을 구하도록 만들었다. maximum = nums[0]for k in range(1, len(nums)+1): # k = 1, 2, 3, 4, 5 for i in range(len(nums)+1-k): # 5 + 1 - 1 = 5 # i = 0, 1, 2, 3, 4 ..
[leetcode] 153. Find Minimum in Rotated Sorted Array 파이썬 코드
정렬된 배열에서 최솟값을 찾는 문제다. 그런데 완전히 정렬된 배열은 아니다. rotate되지 않았으면 가지런히 정렬된 배열이었겠지만, 한 번 rotated 되었기 때문에 정렬된 2개의 덩어리가 있다. 여기서 O(logn) 만에 최솟값을 찾아야 한다. 정렬과 주어진 시간 복잡도를 봤을 때 이진탐색을 써야 한다. 그런데 문제도 살짝 달라졌으니 이진 탐색 코드도 살짝 달라져야겠다. left pointer, right pointer, mid pointer를 둔다.mid pointer와 left pointer를 비교한다. 그래서 왼쪽이 가운데보다 작다면, (1) 이건 한 쪽이 정렬된 배열이니까 가장 왼쪽에 있는 값을 최솟값으로 두고, (2) left pointer를 mid+1로 옮겨서 오른쪽 배열을 봐야 한다. ..
[leetcode] 238. Product of Array Except Self 파이썬 코드
자신의 인덱스를 제외한 나머지 숫자들의 곱을 계산하는 문제이다.O(n)으로 작성해야 하며 나눗셈은 쓸 수 없다. 첫 번째 방법, prefix와 postfix 배열 사용하기 prefix = [0] * len(nums)postfix = [0] * len(nums)output = [0] * len(nums)for i in range(len(nums)): if i > 0: prefix[i] = prefix[i-1] * nums[i] else: prefix[i] = nums[i]for i in range(len(nums)-1, -1, -1): # i = 3, 2, 1, 0 if i len(nums)-1: output[i] = prefix[i-1] el..
[leetcode] 104. Maximum Depth of Binary Tree 파이썬 코드
트리의 최대 높이 구하는 문제이다.root에서 자식 노드까지 쭉 이어지는 노드를 카운트해서 가장 큰 것이 트리의 최대 높이가 된다. 첫 번째 방법: DFS (recursion)maximum height = 1 + max(dfs(왼쪽 서브트리) + dfs(오른쪽 서브트리)) class Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ if not root: # root is null -> return return 0 return 1 + max(self.maxDepth(root.left), s..
정렬이 되어 있으면 binary search를 쓰는 것이 좋다. # binary searchnums = [-1,0,3,5,9,12]target = 2def bsearch(nums): lp, rp = 0, len(nums) - 1 while lp
[leetcode] 49. Group Anagrams 파이썬 코드
https://leetcode.com/problems/group-anagrams/description/class Solution(object): def groupAnagrams(self, strs): """ :type strs: List[str] :rtype: List[List[str]] """ result = [[] for i in range(len(strs))] group_dict_pos = [] for i in range(len(strs)): vocab = strs[i] vocab_dict = dict() for alphabet in vocab: ..
[leetcode] 347. Top K Frequent Elements 파이썬 코드
이 문제는 제목에 그대로 나와있다. 숫자 배열이 주어지면 그 중에서 가장 빈번하게 (많이) 등장한 숫자를 반환하면 된다. 문제를 풀 때 숫자가 몇 번 나왔는지를 카운트하고 그것을 딕셔너리에 저장한 다음에 어떻게 해야 하는지 막혔다.그래서 다른 사람들의 풀이를 보았다. 첫 번째, bucket sort.숫자 배열이 주어지면 그 배열의 길이를 알 수 있다. 그리고 element가 아무리 많이 등장해도 (배열의 길이)번 만큼만 등장할 수 있다. 그러면 개수를 key로, 그만큼 등장한 숫자를 value에서 배열로 저장하는 방법이 있다. 1이 몇 개, 2가 몇 개... 이렇게 개수(count)를 value로 두었는데 개수(count)를 key로 가져간다는 게 새로웠다.count0123...K-2K-1K [3] [..
Heap- nearly complete binary tree- type: min heap, max heap- uses: heapsort, priority queues- height: lognimport heapqA = [-4, 3, 1, 0, 2, 5, 10, 8, 12, 9]heapq.heapify(A)print(A)heapq.heappush(A, 7)print(A)heapq.heappop(A)print(A) # Max HeapB = [-4, 3, 1, 0, 2, 5, 10, 8, 12, 9]for i in range(len(B)): B[i] = -B[i]heapq.heapify(B)print(B)largest = -heapq.heappop(B)print(largest) min-heap- valu..
[leetcode] 242. Valid Anagram 파이썬 코드
#hash table #string #sorting class Solution(object): def isAnagram(self, s, t): """ :type s: str :type t: str :rtype: bool """ s_hashmap = {} t_hashmap = {} for alphabet in s: if alphabet in s_hashmap: s_hashmap[alphabet] += 1 else: s_hashmap[alphabet] = 1 for alphabet in t: ..