soicem's note

문제: https://leetcode.com/problems/matrix-block-sum/ Matrix Block Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 2d vector에서 특정 구간의 합을 구하는 문제다. k값이 주어지고, 2d vector 안의 (y,x) 포인트에서 i - k = lenX ? lenX - 1 : j + k; mat[i][j] = pSums[moreI + 1][moreJ + 1] + pSums[lessI][lessJ] - ..

링크: https://leetcode.com/problems/minimum-domino-rotations-for-equal-row/ Minimum Domino Rotations For Equal Row - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 2개의 도미노들 중 위아래 하나의 라인에서 같은 숫자가 이어지게끔 만드는 swap 개수 중 작은 값을 리턴하는 문제 class Solution { public: int minDominoRotations(vector..

링크: https://leetcode.com/problems/duplicate-zeros/ Duplicate Zeros - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com arr에 0이 있으면 2개로 늘리는데, inplace가 제한조건이다. class Solution { public: void duplicateZeros(vector& arr) { int zeroCnt = 0; int right = arr.size() - 1; for(int i = 0; i < ar..

링크: https://leetcode.com/problems/add-bold-tag-in-string/ 동일한 문제: https://leetcode.com/problems/bold-words-in-string/ Account Login - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com Input: s = "abcxyz123" dict = ["abc","123"] Output: "abcxyz123" dict에 존재하는 문자열이 s에 존재한다면 ", "로 감싸서 r..

문제: leetcode.com/problems/print-immutable-linked-list-in-reverse/ Account Login - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. Recursion class Solution { public: void printLinkedListInReverse(ImmutableListNode* head) { if(!head){ return; } printLinkedListInReverse(head->getNe..

문제: leetcode.com/problems/guess-number-higher-or-lower-ii/ Guess Number Higher or Lower II - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com MINMAX 알고리즘을 사용하는 문제. 어떤 수를 선택하던 상관없이 무조건 이길 수 있는 최소의 돈의 양을 return 해야한다. from i to j에서 사이의 값인 k를 택했을 때 i ~ k -1과 k + 1 ~ j 중에서 최악의 경우의 수를 찾으면..

booking 문제. My Calendar 1: leetcode.com/problems/my-calendar-i/ My Calendar I - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com class MyCalendar { public: vector reserves; MyCalendar() { } bool book(int start, int end) { for(auto reserve : reserves){ int oldStart = reserve[0]; int ..

문제: leetcode.com/problems/find-root-of-n-ary-tree/ mock interview를 수행하다가 막혀서... 문제 자체를 제대로 이해못했다. 조건이 findRoot는 A arbitrary order 속성을 가진 array에서 root를 찾는 문제이며 findRoot는 drive code다. 즉, serialized input data -> a arbitrary order array -> find root -> make a serialized date by using a root node 이런 흐름이다. root는 parent가 없으므로 parent가 없는 Node를 arbitrary한 order를 가진 array에서 찾으면 된다. set이나 visited array를 두..

문제: leetcode.com/problems/longest-increasing-subsequence/ Longest Increasing Subsequence - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com LIS 문제인데 O(nlogn) 해답이 재밌다. 처음에는 각 요소별로 재귀 진입해서 LIS를 하되 cache로 memoization을 해주는 O(N^2) 정도가 직관적으로 떠오른다. 더 최적화하면 LIS를 additional space에 만들고 해당 spa..

문제: leetcode.com/problems/candy/ Candy - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 적어도 1명의 아이는 1개의 캔디를 가져야하고 자기 옆에있는 친구보다 낮은 rating을 가졌으면 반드시 적은 캔디를 가져야한다. 반대로 rating이 높으면 많은 캔디를 가져야 한다. 기본적으로 V자일 때 두 선분이 만나는 점에서 상대적 rating을 확인하는 작업이 들어간다. 4가지 정도 cases가 있는데 중요한 점은 V자 일때 아래의 점..