목록leetcode (59)
one line of code at a time
정렬이 되어 있으면 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] [..
[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: ..
#트리 이진 트리에서 자식 노드의 좌, 우를 스왑하는 문제다. 재귀적으로 호출하면서 좌, 우를 바꿔주면 된다. # Definition for a binary tree node.# class TreeNode(object):# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution(object): def invertTree(self, root): """ :type root: TreeNode :rtype: TreeNode """ if ro..
undirected graph: 방향성이 없는 그래프. (goes both way) https://leetcode.com/problems/clone-graph/ class Node(object): def __init__(self, val = 0, neighbors = None): self.val = val self.neighbors = neighbors if neighbors is not None else []class Solution(object): def cloneGraph(self, node): """ :type node: Node :rtype: Node input: Node[] output: Node..
[leetcode] 200. Number of Islands 파이썬 코드
1은 land이고, 0은 water를 나타내는데 인접한 땅(1)은 하나의 섬이라고 생각할 때 섬의 개수가 총 몇 개인지 세는 문제이다.이 문제는 읽자마자 flood fill 알고리즘을 써야겠다는 생각이 들었다. 큐에 시작 정점을 넣어주고 방문 처리 한 다음에 사방 (four directions)을 탐색한다. 범위에도 포함되면서 (IndexError: list index out of range 를 내면 안 되니까 범위를 체크해줘야 한다) "1"이고 한 번도 방문한 적이 없다면, 큐에 넣어주고 방문처리 해준다. class Solution(object): def range_check(self, row, col): if 0 이렇게 하면 Runtime Error가 뜬다. - 클래스 내부에서 ..
[leetcode] 125. Valid Palindrome 파이썬 코드
#two-pointers https://leetcode.com/problems/valid-palindrome palindrome인지 테스트하는 문제였다. class Solution(object): def isPalindrome(self, s): s_lowered = s.lower() palindrome = ''.join([char for char in s_lowered if char.isalnum()]) # palindrome test string flag = True if len(palindrome) > 0: front = 0 # front pointer back = len(palindrome) - 1 # ..
[leetcode] 217. Contains Duplicate 파이썬 코드
#arrays #hashing 리스트가 주어지고, 이 리스트 안에 있는 정수들이 중복되면 True를, 중복이 없으면 False를 리턴하는 문제다. 파이썬 dictionary를 활용했는데 파이썬 딕셔너리는 해시테이블/해시 맵에 해당되는 자료구조다. def containsDuplicate(nums): val_dict = dict() for num in nums: if num in val_dict.keys(): return True else: val_dict[num] = 1 return Falseprint(containsDuplicate(nums)) 이렇게 하니까 시간 초과가 났다.val_dict.keys()를 하면, 가상의 v..