목록분류 전체보기 (76)
one line of code at a time
#트리 이진 트리에서 자식 노드의 좌, 우를 스왑하는 문제다. 재귀적으로 호출하면서 좌, 우를 바꿔주면 된다. # 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 # ..
Given an array of sorted integers, find two numbers such that they add up to a target number.Questions to ask:- What does my input look like?- Will the sum cause integer overflow? [0, 1, 2, 3, 4, 5]- O(n^2) for loop 2개 쓰는 것 ➡️ Brue-Force approach- O(N log N) 알고리즘: Sort and Scan, Scan through array and use binary search- 만약에 array가 정렬되어 있다면, 항상 binary search를 쓸 수 있는지 체크해보기.- O(N): array sorted 되어..
[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..