본문 바로가기

Languages

(8)
TWO SUM in JAVA Given an array of integers, return the indicies of two numbers whose sum is equal to a given target. Example Given numsList = [1,3,5,7,9], target=10 The output should be [0,4] (i) Using nested loop, time complexity of O(N^2) private static int[] findTwoSum_BruteForce(int[] nums, int target) { for(int i=0; i
LeetCode 167. Two Sum II - Input Array Is Sorted Return index + 1 of the two numbers as a list [index1, index2] Input numbers = [2,7,11,15], target = 9 Output [1,2] # 2 + 7 = 9 Solutions (i) Dictionary time complexity O(N) / space complexity O(N) (ii) Brute Force time complexity O(N^2) / space complexity O(1) (iii) Binary Search time complexity O(NlogN) / space complexity O(1) (iv) Two pointer time complexity O(N) / space complexity O(1) def t..
Python List [:] 파이썬에서 괄호 안의 콜론(:)은 slicing에도 유용하게 쓰이지만, 콜론만 넣을 경우 shallow copy가 만들어진다. slice(start, end, step) myList = [0,1,2,3,4,5,6] print(myList[:]) # 전체 print(myList[4:]) # [4]부터 끝까지 print(myList[:3]) # 처음부터 [2]까지 (index 포함 X) print(myList[-1]) # 마지막 element print(myList[::-1]) # reverse string, -1은 move backward print(myList[3::-1]) # 3 2 1 0 shallow copy soft copy라고도 불리며 original list에 영향을 주지 않고 말그대로 con..
05.Two Pointers Problems LeetCode 977.Squares of a Sorted Array LeetCode 189.Rotate Array Two Pointers approach pointer initialization pointer movement stop condition 👉 optimizes the runtime by utilizing some order of the data (불필요한 sorting을 스킵) ex. Reverse Array start = 0 end = len(arr)-1 while start < end: arr[start], arr[end] = arr[end], arr[start] start += 1 end -= 1 start point: 0, end point: last element ..
04.Stack LeetCode 20.Valid Parentheses s = "[ [ ] ]" # valid s = "{ } [ ] ( )" # valid s = "{ [ ] ( )" # invalid closing shape가 나중 element이고 가장 recent한 opening shape과 매치되어야 하므로 stack 자료구조를 이용하여 문제 해결 Stack data structure - LIFO (Last In First Out) parentheses dictionary and stack def isValid(s): stack = [] closeToOpen = { ')' : '(', ']' : '[', '}' : '{' } ex. input = '( [ ] )' >>> stack = (, [, ], ) # fi..
03.Hash Table HackerRank Hash Tables: Ransom Note arr1(magazine)가 arr2(note)를 포함하면 True maganize = ["one", "two", "three] note = ["one", "two"] >>> True maganize = ["one", "two", "three] note = ["twp", "five"] >>> False collections.Counter from collections import Counter mList = ["a", "b", "c", "b"] mCounter = Counter(mList) mCounter >> Counter({'b': 2, 'a': 1, 'c': 1}) Counter() dict subclass for counting ha..
02.Binary Search Compare target(x) with the middle element if x matches with mid element, return mid (index) elif x is greater than mid element, change starting point to mid + 1 elif x is smaller than mid element, change end point to mid - 1 else x is not in array, return -1 (i) Iteration def binarySearch(nums, target): start = 0 end = len(nums) - 1 while start target: end = mid - 1 else: start = mid + 1 return ..
01.Intro 알고리즘 문제 풀이 website Leetcode, HackerRank language Python solve at least 3 problems everyday 새로운 concept들 위주로 정리하기 Time, space complexity, Big O notation 포함하기 Time Complexity 2022.04.27