diff options
Add SI consultation
12 files changed, 455 insertions, 0 deletions
diff --git a/Additional/README.md b/Additional/Additional-2022-CS/README.md index 96b8018..96b8018 100644 --- a/Additional/README.md +++ b/Additional/Additional-2022-CS/README.md diff --git a/Additional/concatenate-queues.cpp b/Additional/Additional-2022-CS/concatenate-queues.cpp index c3f772e..c3f772e 100644 --- a/Additional/concatenate-queues.cpp +++ b/Additional/Additional-2022-CS/concatenate-queues.cpp diff --git a/Additional/equalize.cpp b/Additional/Additional-2022-CS/equalize.cpp index 263ccd2..263ccd2 100644 --- a/Additional/equalize.cpp +++ b/Additional/Additional-2022-CS/equalize.cpp diff --git a/Additional/merge-sorted.cpp b/Additional/Additional-2022-CS/merge-sorted.cpp index b801a72..b801a72 100644 --- a/Additional/merge-sorted.cpp +++ b/Additional/Additional-2022-CS/merge-sorted.cpp diff --git a/Additional/oddEvenList.cpp b/Additional/Additional-2022-CS/oddEvenList.cpp index 05a95ac..05a95ac 100644 --- a/Additional/oddEvenList.cpp +++ b/Additional/Additional-2022-CS/oddEvenList.cpp diff --git a/Additional/rearange.cpp b/Additional/Additional-2022-CS/rearange.cpp index 48dacff..48dacff 100644 --- a/Additional/rearange.cpp +++ b/Additional/Additional-2022-CS/rearange.cpp diff --git a/Additional/reverse-nodes-in-k-group.cpp b/Additional/Additional-2022-CS/reverse-nodes-in-k-group.cpp index 70b63fd..70b63fd 100644 --- a/Additional/reverse-nodes-in-k-group.cpp +++ b/Additional/Additional-2022-CS/reverse-nodes-in-k-group.cpp diff --git a/Additional/Additional-2023-SI/IntervalCollection.cpp b/Additional/Additional-2023-SI/IntervalCollection.cpp new file mode 100644 index 0000000..0ac2c76 --- /dev/null +++ b/Additional/Additional-2023-SI/IntervalCollection.cpp @@ -0,0 +1,103 @@ +#include <iostream> +#include <vector> +#include <algorithm> + +class IntervalCollection +{ + using Iterator = std::vector<std::pair<int, int>>::iterator; + using ConstIterator = std::vector<std::pair<int, int>>::const_iterator; + + Iterator getRightmostInterval(int x) + { + std::pair<int, int> searcher = { x, x }; + return std::lower_bound( + intervals.begin(), + intervals.end(), + searcher, + [](const std::pair<int, int>& first, const std::pair<int, int>& second) -> bool + { + return first.second < second.second; + } + ); + } + + ConstIterator getRightmostIntervalConst(int x) const + { + std::pair<int, int> searcher = { x, x }; + return std::lower_bound( + intervals.begin(), + intervals.end(), + searcher, + [](const std::pair<int, int>& first, const std::pair<int, int>& 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<std::pair<int, int>> 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 new file mode 100644 index 0000000..7d575aa --- /dev/null +++ b/Additional/Additional-2023-SI/MergeIntoList.cpp @@ -0,0 +1,117 @@ +#include <iostream> + +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 new file mode 100644 index 0000000..f27416a --- /dev/null +++ b/Additional/Additional-2023-SI/queue-insertion.cpp @@ -0,0 +1,109 @@ +#include <iostream> + +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 new file mode 100644 index 0000000..8bd0567 --- /dev/null +++ b/Additional/Additional-2023-SI/readme.md @@ -0,0 +1,14 @@ +## Разгледани структури от STL + +* std::vector +* std::list +* std::forward_list + +## Разгледани функции от STL +* std::sort() +* std::lower_bound() +* std::upper_bound() +* std::find() +* std::find_it() +* std::merge() +* 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 new file mode 100644 index 0000000..e5ad080 --- /dev/null +++ b/Additional/Additional-2023-SI/rearrange.cpp @@ -0,0 +1,112 @@ +#include <iostream> + +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 |
