From 7eee5a78005a9a569186d2c8b4b645a818ab9bf1 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Sun, 6 Oct 2024 07:04:44 -0400 Subject: Cleanup --- Additional/Additional-2022-CS/README.md | 68 ------------ .../Additional-2022-CS/concatenate-queues.cpp | 70 ------------ Additional/Additional-2022-CS/equalize.cpp | 60 ----------- Additional/Additional-2022-CS/merge-sorted.cpp | 51 --------- Additional/Additional-2022-CS/oddEvenList.cpp | 55 ---------- Additional/Additional-2022-CS/rearange.cpp | 55 ---------- .../reverse-nodes-in-k-group.cpp | 54 ---------- .../Additional-2023-SI/IntervalCollection.cpp | 103 ------------------ Additional/Additional-2023-SI/MergeIntoList.cpp | 117 --------------------- Additional/Additional-2023-SI/queue-insertion.cpp | 109 ------------------- Additional/Additional-2023-SI/readme.md | 13 --- Additional/Additional-2023-SI/rearrange.cpp | 112 -------------------- 12 files changed, 867 deletions(-) delete mode 100644 Additional/Additional-2022-CS/README.md delete mode 100644 Additional/Additional-2022-CS/concatenate-queues.cpp delete mode 100644 Additional/Additional-2022-CS/equalize.cpp delete mode 100644 Additional/Additional-2022-CS/merge-sorted.cpp delete mode 100644 Additional/Additional-2022-CS/oddEvenList.cpp delete mode 100644 Additional/Additional-2022-CS/rearange.cpp delete mode 100644 Additional/Additional-2022-CS/reverse-nodes-in-k-group.cpp delete mode 100644 Additional/Additional-2023-SI/IntervalCollection.cpp delete mode 100644 Additional/Additional-2023-SI/MergeIntoList.cpp delete mode 100644 Additional/Additional-2023-SI/queue-insertion.cpp delete mode 100644 Additional/Additional-2023-SI/readme.md delete mode 100644 Additional/Additional-2023-SI/rearrange.cpp (limited to 'Additional') diff --git a/Additional/Additional-2022-CS/README.md b/Additional/Additional-2022-CS/README.md deleted file mode 100644 index 96b8018..0000000 --- a/Additional/Additional-2022-CS/README.md +++ /dev/null @@ -1,68 +0,0 @@ -# Задачи за допълнително упражнение 22.11.2022 - -## Задача първа - Merge linked lists -Да се напише функция, която получава два сортирани списъка с елементи цели числа, обединява ги в един сортиран списък и връща резултата. - -**Пример:** - -Вход: -* l1 = [1, 2, 4, 8, 16] -* l2 = [1, 2, 3, 5, 7, 9, 11] - -Изход: - -* [1, 1, 2, 2, 3, 4, 5, 7, 8, 9, 11, 16] - -## Задача втора -Даден е едносвъран списък, чийто елементи са числа. Напишете функция rearange, която пренарежда елементите, така че първо да бъдат четните числа, после нечетните. Относителната наредба между числата трябва да се запази. Решението ви трябва да работи за O(n) време и O(1) памет. - -Пример: - -Вход: - -* 3 -> 5 -> 2 -> 9 -> 4 - -Изход: - -* 2 -> 4 -> 3 -> 5 -> 9 - -## Задача трета -Даден е свързан списък, чиито елементи са числа. Напишете функция oddEvenList, която пренарежда списъка така, че в първо да бъдат възлите на нечетни **позиции** а след това тези на четни. Решението ви трябва да работи в O(n) време и O(1) памет. Считаме първата позиция за нечетна. - -Пример: - -Вход: -* 1 -> 2 -> 3 -> 4 -> 5 - -Изход: -* 1 -> 3 -> 5 -> 2 -> 4 - -Вход: -* 2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7 - -Изход: -* 2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4 - -## Задача четвърта - Reverse nodes in K-group -Да се напише функция, която приема едносвързан списък и естествено число k. За k знаем, че е по - голямо от 0, но по - малко от дължината на списъка. K група наричаме възлите на индекси [0..k-1], [k..2k-1] и тн. Да се обърнат всички K групи. - -Пример: - -Вход: [1, 2, 3, 4, 5], k = 2 - -Тук K групите са (1, 2), (3, 4). В резултата те са обърнати. - -Изход: [2, 1, 4, 3, 5] - -Вход: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17], k = 4 - -Тук K групите са (1, 2, 3, 4), (5, 6, 7, 8), (9, 10, 11, 12), (13, 14, 15, 16). В резултата те са обърнати. - -Изход: [4, 3, 2, 1, 8, 7, 6, 5, 12, 11, 10, 9, 16, 15, 14, 13, 17] - -## Задача пета -Нека е даден списък L с елементи стекове. Възлите на L са от тип Node. Да се дефинира подходящо параметризирана функция equalize(L), която размества елементите на стековете така, че да няма два стека в L с разлика в броя на елементите, по-голяма от 1. - -## Задача шеста -Даден е свързан списък с една връзка L, чийто елементи са опашки. -Да се напише функция, което конкатенира всички последователни опашки, чиито елементи отговарят на даден предикат p. \ No newline at end of file diff --git a/Additional/Additional-2022-CS/concatenate-queues.cpp b/Additional/Additional-2022-CS/concatenate-queues.cpp deleted file mode 100644 index c3f772e..0000000 --- a/Additional/Additional-2022-CS/concatenate-queues.cpp +++ /dev/null @@ -1,70 +0,0 @@ -#include"../Seminar04/linked-list-utils.h" -#include -#include - -using ListNode = LinkedListNode>; - -void concatenate(std::queue& to, std::queue& from) { - while(!from.empty()) { - to.push(from.front()); - from.pop(); - } -} - -bool all(std::queue q, bool (*pred)(int)) { - while(!q.empty()) { - if(!pred(q.front())) { - return false; - } - q.pop(); - } - - return true; -} - -void concatenateSimilarQueues(ListNode* ll, bool (*pred)(int)) { - if(!ll || !ll->next) - return; - - ListNode* iter = ll; - - while(iter && iter->next) { - if(all(iter->data, pred)) { - while(iter->next && all(iter->next->data, pred)) { - ListNode* toDelete = iter->next; - iter->next = iter->next->next; - concatenate(iter->data, toDelete->data); - - delete toDelete; - } - } - iter = iter->next; - } -} - -void printQueue(std::queue q) { - std::cout << "[ "; - while(!q.empty()) { - std::cout << q.front() << " "; - q.pop(); - } - std::cout << " ]" << std::endl; -} - -int main() { - ListNode* ll = fromList({ - std::queue({1, 2, 3}), - std::queue({4, 5, 6, 7, 8, 8, 9}), - std::queue({12, 14, 16}), - std::queue({101, 102}), - std::queue({103, 104, 105}) - }); - - concatenateSimilarQueues( - ll, - [](int x) -> bool { return x < 10 || x > 100; } - ); - - printLinkedList(ll, printQueue); - freeList(ll); -} \ No newline at end of file diff --git a/Additional/Additional-2022-CS/equalize.cpp b/Additional/Additional-2022-CS/equalize.cpp deleted file mode 100644 index 263ccd2..0000000 --- a/Additional/Additional-2022-CS/equalize.cpp +++ /dev/null @@ -1,60 +0,0 @@ -#include -#include"../Seminar04/linked-list-utils.h" -#include - -using ListNode = LinkedListNode>; - -// O(k*n) памет, където n е дължината на списъка а k размера на най - големия стек -// O(k*n) време -void equalize(ListNode* ll) { - std::stack temp; - ListNode* iter = ll; - - while(iter) { - while(!iter->data.empty()) { - temp.push(iter->data.top()); - iter->data.pop(); - } - iter = iter->next; - } - - iter = ll; - - while(!temp.empty()) { - if(iter == nullptr) { - iter = ll; - } - iter->data.push(temp.top()); - temp.pop(); - iter = iter->next; - } -} - -void printStack(std::stack s) { - int size = s.size(); - - std::cout << "["; - - while (!s.empty()) { - std::cout << s.top() << " "; - s.pop(); - } - - std::cout << "] -> " << size << std::endl; -} - -int main() { - ListNode* ll = fromList( - { - std::stack({1, 4}), - std::stack({6, 7, 8, 9, 5}), - std::stack({10, 11, 12}), - std::stack({1, 41}), - std::stack({6, 7, 8, 9, 5, 7, 9, 0, 10, 20, 30}) - } - ); - - equalize(ll); - printLinkedList(ll, printStack); - freeList(ll); -} \ No newline at end of file diff --git a/Additional/Additional-2022-CS/merge-sorted.cpp b/Additional/Additional-2022-CS/merge-sorted.cpp deleted file mode 100644 index b801a72..0000000 --- a/Additional/Additional-2022-CS/merge-sorted.cpp +++ /dev/null @@ -1,51 +0,0 @@ -#include -#include"../Seminar04/linked-list-utils.h" - -using ListNode = LinkedListNode; - -ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { - if(list1 == nullptr) - return list2; - - if(list2 == nullptr) - return list1; - - ListNode* start = nullptr; - ListNode* iter = nullptr; - - while(list1 != nullptr && list2 != nullptr) { - ListNode*& toInsert = (list1->data > list2->data) ? list2 : list1; - - if(iter == nullptr) { - start = toInsert; - iter = toInsert; - } - else { - iter->next = toInsert; - iter = iter->next; - } - - toInsert = toInsert->next; - } - - ListNode* rest = (list1 == nullptr) ? list2 : list1; - - while(rest != nullptr) { - iter->next = rest; - iter = iter->next; - rest = rest->next; - } - - iter->next = nullptr; - return start; -} - -int main() { - ListNode* l1 = new ListNode(1, new ListNode(2, new ListNode(4))); - ListNode* l2 = new ListNode(1, new ListNode(3, new ListNode(4))); - - ListNode* r = mergeTwoLists(l1, l2); - - printLinkedList(r); - freeList(r); -} \ No newline at end of file diff --git a/Additional/Additional-2022-CS/oddEvenList.cpp b/Additional/Additional-2022-CS/oddEvenList.cpp deleted file mode 100644 index 05a95ac..0000000 --- a/Additional/Additional-2022-CS/oddEvenList.cpp +++ /dev/null @@ -1,55 +0,0 @@ -#include"../Seminar04/linked-list-utils.h" - -using ListNode = LinkedListNode; - -ListNode* oddEvenList(ListNode* head) { - if(head == nullptr || head->next == nullptr) - return head; - - ListNode* oddStart = nullptr; - ListNode* oddIter = nullptr; - - ListNode* evenStart = nullptr; - ListNode* evenIter = nullptr; - - bool odd = true; - - while(head) { - ListNode*& curr = odd ? oddIter : evenIter; - - if(curr == nullptr) { - curr = head; - if(odd) - oddStart = head; - else - evenStart = head; - } - else { - curr->next = head; - curr = curr->next; - } - - head = head->next; - odd = !odd; - } - - oddIter->next = evenStart; - - if(evenIter != nullptr) - evenIter->next = nullptr; - - return oddStart; -} - -int main() { - ListNode* l = fromList({1, 2, 3, 4, 5}); - - ListNode* result = oddEvenList(l); - printLinkedList(result); - freeList(result); - - ListNode* ls = fromList({2, 1, 3, 5, 6, 4, 7}); - result = oddEvenList(ls); - printLinkedList(result); - freeList(result); -} \ No newline at end of file diff --git a/Additional/Additional-2022-CS/rearange.cpp b/Additional/Additional-2022-CS/rearange.cpp deleted file mode 100644 index 48dacff..0000000 --- a/Additional/Additional-2022-CS/rearange.cpp +++ /dev/null @@ -1,55 +0,0 @@ -#include -#include"../Seminar04/linked-list-utils.h" - -using ListNode = LinkedListNode; - -ListNode* rearange(ListNode* head) { - ListNode* oddStart = nullptr; - ListNode* oddIter = nullptr; - - ListNode* evenStart = nullptr; - ListNode* evenIter = nullptr; - - while(head != nullptr) { - if(head->data % 2 == 1) { - if(oddIter == nullptr) { - oddStart = head; - oddIter = head; - } - else { - oddIter->next = head; - oddIter = oddIter->next; - } - } - else { - if(evenIter == nullptr) { - evenStart = head; - evenIter = head; - } - else { - evenIter->next = head; - evenIter = evenIter->next; - } - } - - head = head->next; - } - - if(evenStart == nullptr) - return oddStart; - - evenIter->next = oddStart; - - if(oddIter != nullptr) - oddIter->next = nullptr; - - return evenStart; -} - -int main() { - ListNode* ll = new ListNode(3, new ListNode(5, new ListNode(2, new ListNode(9, new ListNode(4))))); - ListNode* res = rearange(ll); - - printLinkedList(res); - freeList(res); -} \ No newline at end of file diff --git a/Additional/Additional-2022-CS/reverse-nodes-in-k-group.cpp b/Additional/Additional-2022-CS/reverse-nodes-in-k-group.cpp deleted file mode 100644 index 70b63fd..0000000 --- a/Additional/Additional-2022-CS/reverse-nodes-in-k-group.cpp +++ /dev/null @@ -1,54 +0,0 @@ -#include -#include"../Seminar04/linked-list-utils.h" - -using ListNode = LinkedListNode; - -ListNode* getNext(ListNode* head, int k) { - while(k && head) { - head = head->next; - --k; - } - - return head; -} - -ListNode* reverse(ListNode*& head) { - ListNode* next = nullptr; - ListNode* prev = nullptr; - ListNode* it = head; - ListNode* tmp = head; - - while(it) { - next = it->next; - it->next = prev; - prev = it; - it = next; - } - - head = prev; - return tmp; -} - -ListNode* reverseKGroup(ListNode* head, int k) { - ListNode* end = getNext(head, k - 1); - - if(end == nullptr) - return head; - - ListNode* next = end->next; - - end->next = nullptr; - - ListNode* last = reverse(head); - ListNode* res = reverseKGroup(next, k); - - last->next = res; - return head; -} - -int main() { - ListNode* ll = fromList({1, 2, 3, 4, 5, 6, 7,8 ,9,10, 11, 12, 13, 14, 15, 16, 17}); - ll = reverseKGroup(ll, 4); - printLinkedList(ll); - freeList(ll); -} \ No newline at end of file diff --git a/Additional/Additional-2023-SI/IntervalCollection.cpp b/Additional/Additional-2023-SI/IntervalCollection.cpp deleted file mode 100644 index 0ac2c76..0000000 --- a/Additional/Additional-2023-SI/IntervalCollection.cpp +++ /dev/null @@ -1,103 +0,0 @@ -#include -#include -#include - -class IntervalCollection -{ - using Iterator = std::vector>::iterator; - using ConstIterator = std::vector>::const_iterator; - - Iterator getRightmostInterval(int x) - { - std::pair searcher = { x, x }; - return std::lower_bound( - intervals.begin(), - intervals.end(), - searcher, - [](const std::pair& first, const std::pair& second) -> bool - { - return first.second < second.second; - } - ); - } - - ConstIterator getRightmostIntervalConst(int x) const - { - std::pair searcher = { x, x }; - return std::lower_bound( - intervals.begin(), - intervals.end(), - searcher, - [](const std::pair& first, const std::pair& second) -> bool - { - return first.second < second.second; - } - ); - } - -public: - void insert(int x) - { - Iterator right = getRightmostInterval(x); - bool begin = (right == intervals.begin()); - - Iterator left = begin ? intervals.end() : right - 1; - - bool needLeftMerge = !begin && (x - 1 == left->second); - bool needRightMerge = (right != intervals.end()) && (x + 1 == right->first); - - if (right != intervals.end() && x >= right->first && x <= right->second) - { - return; - } - - if (needLeftMerge && needRightMerge) - { - left->second = right->second; - intervals.erase(right); - } - else if (needLeftMerge) - { - left->second = x; - } - else if (needRightMerge) - { - right->first = x; - } - else - { - intervals.insert(right, { x, x }); - } - } - - bool contains(int x) const - { - ConstIterator right = getRightmostIntervalConst(x); - return (right != intervals.end() && x >= right->first && x <= right->second); - } - - void print() const - { - for (const auto& x : intervals) - { - std::cout << x.first << " " << x.second << std::endl; - } - } -private: - std::vector> intervals; -}; - -int main() -{ - IntervalCollection ic; - - ic.insert(1); - ic.insert(3); - ic.insert(2); - ic.insert(5); - ic.insert(7); - ic.insert(4); - ic.insert(6); - - std::cout << ic.contains(1) << " " << ic.contains(10); -} \ No newline at end of file diff --git a/Additional/Additional-2023-SI/MergeIntoList.cpp b/Additional/Additional-2023-SI/MergeIntoList.cpp deleted file mode 100644 index 7d575aa..0000000 --- a/Additional/Additional-2023-SI/MergeIntoList.cpp +++ /dev/null @@ -1,117 +0,0 @@ -#include - -struct ListNode -{ - int val; - ListNode *next; - ListNode(int x, ListNode *n = nullptr) : val(x), next(n) {} -}; - -ListNode *advance(ListNode *from, size_t index) -{ - while (index) - { - if (from == nullptr) - { - return nullptr; - } - - from = from->next; - --index; - } - - return from; -} - -ListNode *getTail(ListNode *list) -{ - if (!list || !list->next) - { - return list; - } - - while (list->next) - { - list = list->next; - } - return list; -} - -void freeRagne(ListNode *from, ListNode *to) -{ - while (from != to) - { - ListNode *node = from; - from = from->next; - delete node; - } -} - -void free(ListNode *ll) -{ - while (ll) - { - ListNode *toDelete = ll; - ll = ll->next; - delete toDelete; - } -} - -ListNode *addFront(ListNode *destination, ListNode *target, size_t to) -{ - ListNode *tail = getTail(target); - ListNode *end = advance(destination, to + 1); - tail->next = end; - freeRagne(destination, end); - return target; -} - -ListNode *mergeInBetween(ListNode *destination, ListNode *target, size_t from, size_t to) -{ - if (from == 0) - { - return addFront(destination, target, to); - } - - ListNode *predBegin = advance(destination, from - 1); - if (!predBegin) - { - return nullptr; - } - - ListNode *postEnd = advance(predBegin, to - from + 2); - ListNode *toDeleteHolder = predBegin->next; - ListNode *targetTail = getTail(target); - - predBegin->next = target; - targetTail->next = postEnd; - - freeRagne(toDeleteHolder, postEnd); - - return destination; -} - -int main() -{ - ListNode *fst = new ListNode(1, - new ListNode(2, - new ListNode(3, - new ListNode(4, - new ListNode(6))))); - - ListNode *snd = new ListNode(3, - new ListNode(4, - new ListNode(5))); - - ListNode *ans = mergeInBetween(fst, snd, 1, 3); - - ListNode *it = ans; - - while(it) - { - std::cout << it->val << " "; - it = it->next; - } - - free(ans); -} \ No newline at end of file diff --git a/Additional/Additional-2023-SI/queue-insertion.cpp b/Additional/Additional-2023-SI/queue-insertion.cpp deleted file mode 100644 index f27416a..0000000 --- a/Additional/Additional-2023-SI/queue-insertion.cpp +++ /dev/null @@ -1,109 +0,0 @@ -#include - -struct Node -{ - Node* next = nullptr; - int data = 0; - Node(int data, Node* next = nullptr) : data(data), next(next){} -}; - -struct Queue -{ - Node* head = nullptr; - Node* tail = nullptr; -}; - -void push(Queue& q, int el) -{ - if (q.head == nullptr) - q.head = q.tail = new Node(el); - else - { - Node* newNode = new Node(el); - q.tail->next = newNode; - - q.tail = newNode; - } -} -void pop(Queue& q) -{ - if (!q.head) - return; - Node* toDelete = q.head; - q.head = q.head->next; - delete toDelete; -} - -void insert(Queue& q, int el) -{ - Node* iter = q.head; - - while (iter) - { - if (iter->data % 10 == el % 10) - { - break; - } - iter = iter->next; - } - - if (iter) - { - Node* newNode = new Node(el); - newNode->next = iter->next; - iter->next = newNode; - } - else - { - if (!q.head) - { - Node* newNode = new Node(el); - q.head = q.tail = newNode; - } - else - { - Node* newNode = new Node(el); - q.tail->next = newNode; - q.tail = newNode; - } - } -} - -void print(const Queue& q) -{ - const Node* it = q.head; - - while(it) - { - std::cout << it->data << " "; - - it = it->next; - } -} -void free(Queue& q) -{ - while (q.head) - { - Node* toDelete = q.head; - q.head = q.head->next; - - delete toDelete; - } - -} -int main() -{ - Queue q; - - push(q, 1); - push(q, 2); - push(q, 4); - push(q, 8); - push(q, 16); - - insert(q, 12); - - print(q); - - free(q); -} \ No newline at end of file diff --git a/Additional/Additional-2023-SI/readme.md b/Additional/Additional-2023-SI/readme.md deleted file mode 100644 index 8ffe953..0000000 --- a/Additional/Additional-2023-SI/readme.md +++ /dev/null @@ -1,13 +0,0 @@ -## Разгледани структури от STL - -* std::vector -* std::list -* std::forward_list - -## Разгледани функции от STL -* std::sort() -* std::lower_bound() -* std::upper_bound() -* std::find() -* std::find_if() -* std::list::splice \ No newline at end of file diff --git a/Additional/Additional-2023-SI/rearrange.cpp b/Additional/Additional-2023-SI/rearrange.cpp deleted file mode 100644 index e5ad080..0000000 --- a/Additional/Additional-2023-SI/rearrange.cpp +++ /dev/null @@ -1,112 +0,0 @@ -#include - -struct Node -{ - Node* next = nullptr; - Node* prev = nullptr; - int data = 0; - Node(int data, Node* next = nullptr, Node* prev = nullptr) : data(data), next(next), prev(prev) {} -}; - -Node* rearange(Node* head) -{ - Node* evensBegin = nullptr; - Node* evensEnd = nullptr; - Node* oddsBegin = nullptr; - Node* oddsEnd = nullptr; - - Node* iter = head; - - while (iter) - { - if (iter->data % 2 == 0) - { - if (!evensBegin) - { - evensBegin = evensEnd = iter; - iter->prev = nullptr; - } - else - { - evensEnd->next = iter; - iter->prev = evensEnd; - evensEnd = iter; - } - } - else - { - if (!oddsBegin) - { - oddsBegin = oddsEnd = iter; - iter->prev = nullptr; - } - else - { - oddsEnd->next = iter; - iter->prev = oddsEnd; - oddsEnd = iter; - } - } - iter = iter->next; - } - if(evensEnd) - evensEnd->next = nullptr; - if(oddsEnd) - oddsEnd->next = nullptr; - - // concat - if (!evensBegin) - return oddsBegin; - if (!oddsBegin) - return evensBegin; - - evensEnd->next = oddsBegin; - oddsBegin->prev = evensEnd; - return evensBegin; -} - -Node* push_front(Node* list, int elem) -{ - if(!list) - { - return new Node(elem); - } - - Node* toReturn = new Node(elem, list); - list->prev = toReturn; - return toReturn; -} - -void free(Node* l) -{ - Node* it = l; - - while(it) - { - Node* toDelete = it; - it = it->next; - delete toDelete; - } -} - -int main() -{ - Node* l = nullptr; - - for (size_t i = 0; i < 50; i++) - { - l = push_front(l, 50 - i); - } - - l = rearange(l); - - Node* it = l; - - while(it) - { - std::cout << it->data << " "; - it = it->next; - } - - free(l); -} \ No newline at end of file -- cgit v1.3.1-26-gb76a