highlightmoon 님의 블로그

링크 - https://leetcode.com/problems/dot-product-of-two-sparse-vectors/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days난이도 - MediumIntuitionSparse하기 때문에 효율적으로 필요한 계산만 할 필요가 있다. 여기에는 세가지 접근법이 있다.1) Non-efficient Array Approach그냥 무식하게 Sparse무시하고 푸는 방법이다. 효율성은 기대할 수 없을것이다.2) Hash Table0이 아닌 값들과 거기에 해당하는 인덱스들을 해시테이블에 저장해놓는 방법이다. 따라서 해시테이블 값이 적은 것을 기준으로 인덱스에 해당되는 값들만 곱해서 더하..

링크 - https://leetcode.com/problems/valid-palindrome-ii/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days난이도 - EasyIntuition두 개의 포인터를 사용해서 Greedy하게 풀어야 하는 문제이다. 만약에 주어진 String이 Palindrome하다면 우리는 그냥 캐릭터들을 비교하면서 맞음을 확인하고 True를 반환하면 된다.하지만 만약 중간에 틀린 글자가 있다면 우리는 선택을 해야한다. left에 있는 글자를 버릴건지, right에 있는 글자를 버릴건지.따라서 두개의 결과 중 하나라도 True가 있다면 True를 최종적으로 반환해야한다.Codeclass Solutio..

링크 - https://leetcode.com/problems/find-peak-element/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days난이도 - MediumIntuitionBinary Search를 통해 mid값을 비교하면서 답을 찾아갈 수 있는 문제이다. 여기서는 4가지의 케이스들을 비교해야 한다.case 1. 왼쪽으로 단조증가하는 경우5,4,3,2,1 같은 경우를 보자. 이 경우 mid는 3이다. 3의 이웃들을 살펴보면 4와2가 있다. 따라서 미드를 중심으로 왼쪽으로 단조증가 중이다. 따라서 우리는 오른쪽은 신경쓸 필요가 없다. 따라서 우리는 이때 right를 mid로 설정하면 된다.case2. 오른쪽으..

링크 - https://leetcode.com/problems/lru-cache/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days난이도 - MediumIntuitionLRU Cache문제는 Doubly-Linked List자료구조로 풀 수 있다. 예를 들어, A->B->C->D->E이렇게 캐쉬에 저장되어 있고 C가 호출이 되면 우리는 C를 꺼내서 맨 앞에 넣음으로써 C->A->B->D->E로 만들어서 Cache를 유지할 수 있다. 따라서 각 Node는 key, value, next node, prev node를 가지는 클래스로 만들어야 한다. 알고리즘은 다음과 같이 작동해야 한다.1. key-value pair를 저..

링크 - https://leetcode.com/problems/valid-palindrome/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days난이도 - EasyIntuition먼저 파이썬 내장함수를 몇가지 알아야 한다..isalnum(): character가 alphanumeric인지 확인하는 메서드이다. alphanumeric이면 True를 반환한다..lower(): character가 upper case letter이면 lower case letter로 변환해준다.두가지 방법으로 풀 수 있다.1) Compare with Reverse방법은 간단하다. 주어진 s를 alnum()를 통해 필터링하고 lower()해서 ..

링크 - https://leetcode.com/problems/merge-sorted-array/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days난이도 - EasyIntuition3가지 접근방식이 있다.1) Merge and Sort단순히 nums1에 nums2를 다 집어넣고 nums1을 sorting하는 것이다. 따라서 Time Complexity는 O((n+m)log(n+m))이 나오게 된다. 2) Three Pointers(Start From the Beginning)이미 nums1과 nums2가 Sorting이 되어있기 때문에, two pointers방식을 사용하여 O(n+m) time complexity로 ..

링크: https://leetcode.com/problems/simplify-path/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days난이도: MediumIntuitionString에 대한 파이썬 내장함수를 알아두면 도움이 된다.path.split("/") # split string with "/". # e.g. # "/home/" -> ['', 'home', '']# "/home//foo/" -> ['', 'home', '', 'foo', '']# "/home/user/Documents/../Pictures" -> ['', 'home', 'user', 'Documents', '..', 'Pictures']"/".join(stack)# ..

링크 - https://leetcode.com/problems/diameter-of-binary-tree/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days난이도 - EasyIntuition가장 긴 길을 찾기 위해서는 일단 임의의 두 노드들을 찍어보자. 거기서 더 긴 길을 찾으려면 각 노드의 child노드들을 찾아가야 한다. 따라서 가장 긴 길은 Leaf node 두 개를 연결하는 것이다. 더 나아가 우리는 트리에서 각각의 노드들은 하나의 부모 노드와 최대 2개의 자식 노드들을 가지고 있다는 것을 알고 있다. 그래서 가장 긴 길은 한 노드를 중심으로 가장 긴 왼쪽 브랜치와 가장 긴 오른쪽 브랜치를 가질 것이다. 따라..