Apes Together Strong.

https://leetcode.com/problems/invert-binary-tree/description/ 주어진 binary tree를 그림과 같이 역전시켜라. 쉬워 보이지만, 접근을 잘 해야 하는 문제.  제일 하단 leaf 노드부터 뒤집으면 그 위로 차례로 뒤집으면 해결됨을 파악해야 한다. 각 depth 별로 노드를 얻어 하려고 하면 복잡해 지고, DFS방식으로 접근해서 하단부터 값을 얻고 위로 올라오면서 적용한다.  코드 TreeNode* invertTree(TreeNode* node){ if (node == nullptr) return nullptr; auto left = invertTree(node->left); auto right = invertTree(nod..

https://leetcode.com/problems/merge-k-sorted-lists/description/ 다수의 정렬된 list가 주어질 때, 모든 정렬을 유지하면서 이 list를 하나로 merge 하라. 정렬이 되어 있으므로, 각 list의 제일 앞 node를 비교하며 제일 작은 순서대로 새 노드에 연결하면 될 것이다.  매번 모든 앞 노드를 비교하면서 최소 값을 가진 노드를 찾을 수 있고, 이것은 시간이 많이 걸릴 것이다. 혹은 추가되는 노드만 더하면서 정렬할 수도 있겠다. map 이나 priority queue를 사용하면 될 것 같다.  코드 더보기void pushNode(map>& mNodes, ListNode* target){ if (mNodes.find(target->val) =..

https://leetcode.com/problems/lru-cache/description/ LRU Cache를 구현하라. LRU Cache 구현의 핵심은, list를 이용하여, 가장 최근에 사용한 데이터를 list의 제일 앞쪽에 위치시키고, 따라서 capacity가 꽉 차면 가장 마지막에 data를 삭제하는 것이다. 이때 데이터 접근에 따라 list에서 해당 데이터를 찾고 앞쪽에 위치시켜야 하는데, 이 검색시간을 O(1)로 하는게 문제 풀이의 핵심이라 할 수 있다.  결국 list의 iterator를 이용해 한번에 지워야 한다.  코드 더보기class LRUCache { int _capacity; list> _listData; // value, key. unor..

https://leetcode.com/problems/find-the-duplicate-number/description/ 아래와 같은 정수 배열이 주어질 때 단 하나의 중복 값이 존재한다. 이 값을 찾아라.  입력 배열을 수정하지 말고, 추가 메모리를 사용하지 말라. 이 문제가 linked list category인 이유가 있다. 따라서 해석이 중요한 문제다.  각 원소가 다음 원소의 index의 위치라고 한다면, 중복되는 값은 cycle의 시작 지점을 의미한다.  우선, cycle이 존재하는 지 판단하고, 그 지점을 찾는다.찾고 cycle의 시작점을 찾는다.  그러면 답이 찾아진다. 코드더보기int findDuplicate(vector& nums) { int idxFast = 0; int ..

https://leetcode.com/problems/linked-list-cycle/description/ 주어진 list에서 cycle이 있는지 판단하라. 검색법은 간단하다. fast와 slow pointer가 출발 이후 만난다면, cycle이 있다고 판단할 수 있다. code 더보기bool hasCycle(ListNode *head) { ListNode* slow = head; ListNode *fast = head; bool start = false; while (fast != nullptr && fast->next != nullptr) { // cout val next->val next->next; slow = slow->next; ..

Add Two Numbers - LeetCode 두개의 리스트가 주어질 때, 하나의 노드가 한 자리수의 숫자를 의미한다.더 리스트의 수를 더하라. carry에 주의해서 더하고 new list를 만든다. 코드 더보기ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* newHead = nullptr; ListNode* node = nullptr; ListNode* node1 = l1; ListNode* node2 = l2; ListNode* prev = nullptr; int carry = 0; while (node1 != nullptr || node2 != nullptr || carry > 0) { ..

Copy List with Random Pointer - LeetCode list가 주어지고 random 포인터가 랜덤하게 다른 노드를 가리키고 있을 때, 이 list을 deep copy 하라. 약간 난해한 문제. 우선 직관적으로 해 보면, 먼저 메모리를 할당해서 기본 list를 copy를 한다.다음으로 random 포인터의 위치를 index를 파악한다. 그리고 이 data를 이용해 새로 만든 리스트에서 random의 대상이 되는 노드를 찾아 연결한다.  시간 효율이 좋지 않을 것이 자명하다.  일단 코드 ..더보기Node* copyRandomList(Node* head) { Node* newHead = nullptr; Node* prev = nullptr; Node* node = hea..

Remove Nth Node From End of List - LeetCode 리스트가 주어질 때, 뒤에서 n 번째에 해당하는 노드를 삭제 하라.  먼저 뒤에서 n 번째의 노드를 찾는다. slow, fast 포인터를 이용하면 찾을 수 있다. 이 후, head 처리에 유의하며 해당 노드를 삭제 한다. 더보기ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* fast = head; ListNode* slow = head; ListNode* prev = nullptr; int cnt = 0; while (fast != nullptr) { if (cnt >= n) { prev ..

Reorder List - LeetCode  리스트가 주어질 때, 리스트를 앞에서 하나, 뒤에서 하나 이런식으로 재정렬 하라. 우선 가운데 부분을 찾는다. 이후 중간부터 버퍼에 넣고 뒤집는다. 혹은 바로 list를 뒤집는다. 이후에 하나씩 head에 넣으면서 순서를 바꾼다.  더보기void reorderList(ListNode* head) { // Find the center. ListNode* fast = head; ListNode* slow = head; ListNode* prev = nullptr; while (fast != nullptr && fast->next != nullptr) { prev = slow; slow = slow->nex..

https://leetcode.com/problems/merge-two-sorted-lists/description/  두 개의 정렬된 list가 두어질 때 이 두 리스트를 merge 하라.  딱히 어려운 부분이 없다.직관대로 한다. 코드 .ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* head = nullptr; ListNode* node1 = list1; ListNode* node2 = list2; ListNode* node = nullptr; ListNode* prev = nullptr; while (node1 != nullptr || node2 != nullptr) { ..