diff options
Add additional tasks
8 files changed, 582 insertions, 0 deletions
diff --git a/Additional/Additional-2024-IS/README.md b/Additional/Additional-2024-IS/README.md new file mode 100644 index 0000000..6fab507 --- /dev/null +++ b/Additional/Additional-2024-IS/README.md @@ -0,0 +1,45 @@ +# Допълнително упражнение за контролно 1 за специалност информационни системи - 15.11.2024 + +## Задача първа - https://leetcode.com/problems/remove-nodes-from-linked-list/ +Да се напише функция `ListNode* removeNodes(ListNode* node)`, която премахва всеки възел на свързан списък, който има възел с по - голяма стойност вдясно от него, и връща началото на новия списък. + + + +Вход: глава = [5,2,13,3,8] + +Изход: [13,8] + +## Задача втора +Да се напише функция `node* level_sort(node* root)`, която приема двоично дърво, и връща ново двоично дърво, за което е вярно, че: +* Дървото е пълно - Пълно дърво наричаме дърво, в което всяко ниво (освен евентуално последното) е изцяло запълнено. +* Обхождайки последователно нивата на дървото отляво надясно ще получим елементите на дървото в сортиран вид. + +Решението да работи в O(nlog(n)) време и да използва O(n) памет. + +## Задача трета +Имаме низ състоящ се от малки латински букви, символа * и символа $. Всеки път, стигайки до символ *, изтриваме най - лявата буква в резултатния низ. Всеки път стигайки до симвой $ добавяме най - лявата буква в резултатния низ. +Да се напише функция `std::string parse(const std::string& str);` която приема низ от този вид и връща низ, който прилага всички символи * и $ върху низа. + +Пример: + +* abc\*\$\$\*d$a$$zz\* => abbddaaaz +* aaa*** => "" +* aaa$ => aaa + +--- +--- +--- + +## Задача четвърта +Да се напише функция, която приема сортиран масив, и строи балансирано двоично наредено дърво от него. + +## Задача пета +Да се напише функция, която като вход приема масив и връща дърво, в което лявото поддърво на корена съдържа чеслата по - малки от 0, а дясното поддърво тези по - големи от 0. Стойността на корена може да е произволно число от масива. + +## Задача шеста +Напишете функция, която получава като аргумент едносвързан списък с елементи цели числа. Функцията трябва да го сортира по следното правило - в началото на списъка трябва да останат четните елементи, подредени в нарастващ ред, след това нечетните елементи, подредени в намаляващ ред. + +Бонус: премахнете повтарящите се елементи. + +## Задача седма +Даден е масив от цели числа. Представяме си, че имаме прозорец с дължина *k* който се движи отляво надясно. Единственото което можем да видим са числата в прозореца. Да се изведе максимумът на всеки такъв прозорец.
\ No newline at end of file diff --git a/Additional/Additional-2024-IS/solutions/basic-parser.cpp b/Additional/Additional-2024-IS/solutions/basic-parser.cpp new file mode 100644 index 0000000..b3f8e49 --- /dev/null +++ b/Additional/Additional-2024-IS/solutions/basic-parser.cpp @@ -0,0 +1,32 @@ +#include <iostream> +#include <stack> +#include <string> + +std::string parse(const std::string& str) { + std::stack<char> result; + + for (char ch : str) { + if (ch >= 'a' && ch <= 'z') { + result.push(ch); + } else if (ch == '*' && !result.empty()) { + result.pop(); + } else if (ch == '$' && !result.empty()) { + result.push(result.top()); + } + } + + std::string finalResult; + while (!result.empty()) { + finalResult = result.top() + finalResult; + result.pop(); + } + + return finalResult; +} + +int main() { + std::string input = "abc*$$*d$a$$zz*"; + std::cout << "Result: " << parse(input) << std::endl; + + return 0; +} diff --git a/Additional/Additional-2024-IS/solutions/build_from_sorted.cpp b/Additional/Additional-2024-IS/solutions/build_from_sorted.cpp new file mode 100644 index 0000000..04c0d2c --- /dev/null +++ b/Additional/Additional-2024-IS/solutions/build_from_sorted.cpp @@ -0,0 +1,71 @@ +#include <iostream> +#include <vector> + +struct node +{ + int data; + node* left = nullptr; + node* right = nullptr; + + node(int d, node* l = nullptr, node* r = nullptr) + : data(d) + , left(l) + , right(r) + {} +}; + +using const_iterator = std::vector<int>::const_iterator; + +node* build_from_range(const_iterator begin, const_iterator end) +{ + // When end is before begin std::distance will return + // negative number by standard. + int distance = std::distance(begin, end); + + if(distance < 0) + return nullptr; + + if(distance == 0) + return new node(*begin); + + int mid = distance / 2; + + return new node( + *(begin + mid), + build_from_range(begin, begin + mid - 1), + build_from_range(begin + mid + 1, end) + ); +} + +node* build_from_sorted(const std::vector<int>& v) +{ + return build_from_range(v.begin(), v.end() - 1); +} + +void inorder(node* root) +{ + if(!root) return; + + inorder(root->left); + std::cout << root->data << " "; + inorder(root->right); +} + +void free_tree(node* tree) +{ + if(!tree) + return; + free_tree(tree->left); + free_tree(tree->right); + + delete tree; +} + +int main() +{ + std::vector<int> sorted = {1, 2, 4, 8, 16, 32, 64}; + node* result = build_from_sorted(sorted); + + inorder(result); + free_tree(result); +}
\ No newline at end of file diff --git a/Additional/Additional-2024-IS/solutions/odd-even-sort.cpp b/Additional/Additional-2024-IS/solutions/odd-even-sort.cpp new file mode 100644 index 0000000..c276254 --- /dev/null +++ b/Additional/Additional-2024-IS/solutions/odd-even-sort.cpp @@ -0,0 +1,112 @@ +#include <iostream> + +struct ListNode +{ + int val; + ListNode* next; + ListNode(int x, ListNode* next = nullptr) : val(x), next(next) {} +}; +template<class Comparator> +void insert_sorted(ListNode*& head, ListNode*& tail, ListNode* element, const Comparator& cmp) +{ + if(head == nullptr) + { + head = tail = element; + return; + } + + if(!cmp(head->val, element->val)) + { + element->next = head; + head = element; + return; + } + + ListNode* iter = head; + + while(iter->next) + { + if(!cmp(iter->next->val, element->val)) + break; + + iter = iter->next; + } + + if(iter->next == nullptr) + tail = element; + + element->next = iter->next; + iter->next = element; +} + +ListNode* odd_even_sort(ListNode* node) +{ + if(!node || !node->next) + return node; + + ListNode* even_head = nullptr; + ListNode* even_tail = nullptr; + + ListNode* odd_head = nullptr; + ListNode* odd_tail = nullptr; + + std::less<int> less; + std::greater<int> greater; + + while(node) + { + ListNode* to_insert = node; + node = node->next; + to_insert->next = nullptr; + + if(to_insert->val % 2 == 0) + { + insert_sorted(even_head, even_tail, to_insert, less); + } + else + { + insert_sorted(odd_head, odd_tail, to_insert, greater); + } + } + + if(odd_tail != nullptr) + odd_tail->next = nullptr; + + if(even_head == nullptr) + { + return odd_head; + } + + even_tail->next = odd_head; + return even_head; +} + + +void free_list(ListNode* list) +{ + while(list) + { + ListNode* to_delete = list; + list = list->next; + delete list; + } +} + +int main() +{ + ListNode* example = new ListNode( + 11, new ListNode(21, new ListNode(31, new ListNode(5, new ListNode(51)))) + ); + + ListNode* result = odd_even_sort(example); + + ListNode* iter = result; + + while(iter) + { + std::cout << iter->val << " "; + iter = iter->next; + } + + free_list(result); +}
\ No newline at end of file diff --git a/Additional/Additional-2024-IS/solutions/remove-nodes-recursion.cpp b/Additional/Additional-2024-IS/solutions/remove-nodes-recursion.cpp new file mode 100644 index 0000000..bff2191 --- /dev/null +++ b/Additional/Additional-2024-IS/solutions/remove-nodes-recursion.cpp @@ -0,0 +1,75 @@ +#include <climits> +#include <iostream> + +struct ListNode +{ + int val; + ListNode* next; + ListNode(int x, ListNode* next = nullptr) + : val(x) + , next(next) + {} +}; + +class Solution +{ + public: + ListNode* removeNodes(ListNode* head) + { + int maxVal = INT_MIN; + return removeNodesRecursive(head, maxVal); + } + + private: + ListNode* removeNodesRecursive(ListNode* node, int& maxVal) + { + if (node == nullptr) + { + return nullptr; + } + + ListNode* filteredNext = removeNodesRecursive(node->next, maxVal); + + if (node->val >= maxVal) + { + maxVal = node->val; + node->next = filteredNext; + return node; + } + else + { + delete node; + return filteredNext; + } + } +}; + +void printList(ListNode* node) +{ + while (node) + { + std::cout << node->val << " "; + node = node->next; + } + std::cout << std::endl; +} + +int main() +{ + Solution s; + + ListNode* result = + s.removeNodes(new ListNode(5, new ListNode(2, new ListNode(13, new ListNode(3, new ListNode(8)))))); + + printList(result); + + ListNode* current = result; + while (current) + { + ListNode* temp = current; + current = current->next; + delete temp; + } + + return 0; +} diff --git a/Additional/Additional-2024-IS/solutions/remove-nodes-stack.cpp b/Additional/Additional-2024-IS/solutions/remove-nodes-stack.cpp new file mode 100644 index 0000000..a43dcfc --- /dev/null +++ b/Additional/Additional-2024-IS/solutions/remove-nodes-stack.cpp @@ -0,0 +1,89 @@ +#include <climits> +#include <iostream> +#include <stack> + +struct ListNode +{ + int val; + ListNode* next; + ListNode() + : val(0) + , next(nullptr) + {} + ListNode(int x) + : val(x) + , next(nullptr) + {} + ListNode(int x, ListNode* next) + : val(x) + , next(next) + {} +}; + +class Solution +{ + public: + ListNode* removeNodes(ListNode* node) + { + if (!node || !node->next) + return node; + + std::stack<ListNode*> listNodes; + int maxValue = INT_MIN; + + ListNode* iter = nullptr; + + while (node) + { + listNodes.push(node); + node = node->next; + } + + while (!listNodes.empty()) + { + ListNode* currentNode = listNodes.top(); + listNodes.pop(); + + if (currentNode->val >= maxValue) + { + maxValue = currentNode->val; + currentNode->next = iter; + iter = currentNode; + } + else + { + delete currentNode; + } + } + + return iter; + } +}; + +void freeList(ListNode* node) +{ + while (node) + { + ListNode* temp = node; + node = node->next; + delete temp; + } +} + +int main() +{ + Solution s; + + ListNode* result = + s.removeNodes(new ListNode(5, new ListNode(2, new ListNode(13, new ListNode(3, new ListNode(8)))))); + + ListNode* toDelete = result; + + while (result) + { + std::cout << result->val << " "; + result = result->next; + } + + freeList(toDelete); +} diff --git a/Additional/Additional-2024-IS/solutions/sliding-window.maximum.cpp b/Additional/Additional-2024-IS/solutions/sliding-window.maximum.cpp new file mode 100644 index 0000000..242cd6a --- /dev/null +++ b/Additional/Additional-2024-IS/solutions/sliding-window.maximum.cpp @@ -0,0 +1,42 @@ +#include <iostream> +#include <deque> +#include <vector> + +std::vector<int> sliding_window_maximum(const std::vector<int> v, unsigned k) +{ + std::vector<int> result; + std::deque<int> window; + + for (size_t i = 0; i < k; i++) + { + while(!window.empty() && window.back() < v[i]) + { + window.pop_back(); + } + window.push_back(v[i]); + } + + result.push_back(window.front()); + + for (size_t i = k; i < v.size(); i++) + { + if(window.front() == v[i-k]) + window.pop_front(); + + while(!window.empty() && window.back() < v[i]) + { + window.pop_back(); + } + + window.push_back(v[i]); + + result.push_back(window.front()); + } + + return result; +} + +int main() +{ + +}
\ No newline at end of file diff --git a/Additional/Additional-2024-IS/solutions/sort-by-level-tree.cpp b/Additional/Additional-2024-IS/solutions/sort-by-level-tree.cpp new file mode 100644 index 0000000..4a4915d --- /dev/null +++ b/Additional/Additional-2024-IS/solutions/sort-by-level-tree.cpp @@ -0,0 +1,116 @@ +#include <algorithm> +#include <iostream> +#include <queue> + +struct node +{ + int data; + node* left = nullptr; + node* right = nullptr; + + node(int d, node* l = nullptr, node* r = nullptr) + : data(d) + , left(l) + , right(r) + {} +}; + +void fill(node* root, std::vector<int>& v) +{ + if (!root) + return; + + v.push_back(root->data); + fill(root->left, v); + fill(root->right, v); +} + +node* sort_by_level(node* tree) +{ + std::vector<int> v; + fill(tree, v); + + std::sort(v.begin(), v.end()); + + node* to_return = new node(v[0]); + int idx = 1; + + std::queue<node*> q; + q.push(to_return); + + while (idx < v.size()) + { + node* current = q.front(); + q.pop(); + + current->left = new node(v[idx++]); + if (idx >= v.size()) + break; + current->right = new node(v[idx++]); + + q.push(current->left); + q.push(current->right); + } + + return to_return; +} + +void free_tree(node* root) +{ + if (!root) + return; + free_tree(root->left); + free_tree(root->right); + delete root; +} + +// Print tree by levels. +// Not presented - used just for demo. +void print_levels(node* result) +{ + std::queue<node*> q; + q.push(result); + q.push(nullptr); + + while (q.size()) + { + node* current = q.front(); + q.pop(); + + if (current == nullptr) + { + if (!q.empty()) + { + q.push(nullptr); + std::cout << std::endl; + } + continue; + } + + std::cout << current->data << " "; + + if (current->left) + q.push(current->left); + if (current->right) + q.push(current->right); + } +} + +int main() +{ + node* tree = new node(5, + new node(3, + new node(4), + new node(0, + new node(1), + new node(2))), + new node(8, + new node(9), + new node(7, new node(10)))); + + node* result = sort_by_level(tree); + print_levels(result); + + free_tree(result); + free_tree(tree); +}
\ No newline at end of file |