Apes Together Strong.

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) { ..

https://leetcode.com/problems/reverse-linked-list/description/ 단일 linked list를 뒤집는 문제.마찬가지로 다른 문제들의 초석이 된다. 원리를 알면 간단하므로, 완전히 이해하자. 코드ListNode* reverseList(ListNode* head) { ListNode* node = head; ListNode* prev = nullptr; while (node != nullptr) { ListNode* next = node->next; node->next = prev; prev = node; node = next; } return prev;}  결과

https://leetcode.com/problems/search-in-rotated-sorted-array/description/ 회전된 정렬된 숫자배열이 주어질 때, target 값을 찾고 있다면 그 index를 반환하라. Binary search의 종합 선물세트 문제.  우선 회전된 rotated index를 찾는다.  이후 target 값을 검색하되, 실제 access해야 할 index는 (index+rotateIndex) % arraySize 이다.  코드 더보기int searchMinIdxBS(vector& nums, int left, int right){ if (left > right) return -1; // 1, 2, 3, 4, 5 // // 5, 1, 2, ..

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/ 주어진 정렬된 배열이 rotated 되어 있을 때, 최소 값 원소를 찾아라. 회전 가능성을 우선 나열한다. 1,2,3,4,55,1,2,3,44,5,1,2,33,4,5,1,22,3,4,5,1 left, mid, right 를 기준으로 크기 순서에 의해 3경우 분기가 가능하다. 1. left가 최소인 경우2. mid가 최소인 경우3. right 가 최소인 경우 left가 최소인 경우는 그냥 left 값이 답이다. mid가 최소인 경우는 mid가 최소이거나 left side에 답이 있다.right가 최소인 경우는 right가 최소이거나 right side에 답이 있다...

https://leetcode.com/problems/koko-eating-bananas/description/ 아래의 조건을 만족하는 divider를 찾아라. 해당 divider로 각 입력된 수를 나누되 나머지가 있으면 1을 더한다.(코코가 시간이 남아도 해당 pile만 시간내에 먹는다)그 나눈 최종 합이 hour 보다 같거나 작은(시간내에 먹어야 한다)최소의 divider값을 찾아라.   우선 koko가 바나나를 먹는다에 비유를 해서 문제를 제시 했으므로, 구문들을 로직 체계로 변환을 해야 한다.  그것이 위에 명기한 것이며, 결국 조건을 만족하는 최소의 divider값을 찾는 것이 문제가 원하는 답이다.  조건을 만족한다 => divider로 나눈 총합이 hour 보다 같거나 작아야 한다. 이 중 ..