From b56237c83f5b571d1c122f393b621a63a26e0d58 Mon Sep 17 00:00:00 2001 From: Desislava Shunina <115353472+desiish@users.noreply.github.com> Date: Tue, 5 Nov 2024 17:09:20 +0200 Subject: add pract05 --- Practicum/pract05/readme.md | 10 ++++++++++ 1 file changed, 10 insertions(+) create mode 100644 Practicum/pract05/readme.md (limited to 'Practicum') diff --git a/Practicum/pract05/readme.md b/Practicum/pract05/readme.md new file mode 100644 index 0000000..bc43383 --- /dev/null +++ b/Practicum/pract05/readme.md @@ -0,0 +1,10 @@ +# Практикум №5 по Структури от данни, спец. ИС + +## Основни задачи за свързани списъци, които ще решим заедно: +- [**Reverse a linked list**](https://www.hackerrank.com/challenges/reverse-a-linked-list/problem) +- [**Middle if linked list**](https://leetcode.com/problems/middle-of-the-linked-list/description/) +- [**Cycle Detection**](https://www.hackerrank.com/challenges/detect-whether-a-linked-list-contains-a-cycle/problem) +- [**Intersection of two linked lists**](https://leetcode.com/problems/intersection-of-two-linked-lists/description/) + +--- +[**Линк към задачите**](https://leetcode.com/problem-list/anqpylct/) -- cgit v1.3.1-23-gd82d From 8d143a1431e7fbc943524b3897afca0139a5f43b Mon Sep 17 00:00:00 2001 From: Desislava Shunina <115353472+desiish@users.noreply.github.com> Date: Tue, 5 Nov 2024 17:09:37 +0200 Subject: Update readme.md --- Practicum/pract05/readme.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'Practicum') diff --git a/Practicum/pract05/readme.md b/Practicum/pract05/readme.md index bc43383..e335dcd 100644 --- a/Practicum/pract05/readme.md +++ b/Practicum/pract05/readme.md @@ -2,7 +2,7 @@ ## Основни задачи за свързани списъци, които ще решим заедно: - [**Reverse a linked list**](https://www.hackerrank.com/challenges/reverse-a-linked-list/problem) -- [**Middle if linked list**](https://leetcode.com/problems/middle-of-the-linked-list/description/) +- [**Middle of linked list**](https://leetcode.com/problems/middle-of-the-linked-list/description/) - [**Cycle Detection**](https://www.hackerrank.com/challenges/detect-whether-a-linked-list-contains-a-cycle/problem) - [**Intersection of two linked lists**](https://leetcode.com/problems/intersection-of-two-linked-lists/description/) -- cgit v1.3.1-23-gd82d From f281f4124941da875a81df70b9b91b6eaf529434 Mon Sep 17 00:00:00 2001 From: Desislava Shunina <115353472+desiish@users.noreply.github.com> Date: Tue, 5 Nov 2024 17:12:04 +0200 Subject: Add tasks solutions --- Practicum/pract05/solutions/Task01.cpp | 17 +++++++++++ Practicum/pract05/solutions/Task03.cpp | 18 ++++++++++++ Practicum/pract05/solutions/Task04.cpp | 52 ++++++++++++++++++++++++++++++++++ 3 files changed, 87 insertions(+) create mode 100644 Practicum/pract05/solutions/Task01.cpp create mode 100644 Practicum/pract05/solutions/Task03.cpp create mode 100644 Practicum/pract05/solutions/Task04.cpp (limited to 'Practicum') diff --git a/Practicum/pract05/solutions/Task01.cpp b/Practicum/pract05/solutions/Task01.cpp new file mode 100644 index 0000000..1f9e7a9 --- /dev/null +++ b/Practicum/pract05/solutions/Task01.cpp @@ -0,0 +1,17 @@ +SinglyLinkedListNode* reverse(SinglyLinkedListNode* llist) { + if(!llist) + return nullptr; + + SinglyLinkedListNode* curr = llist; + SinglyLinkedListNode* prev = nullptr; + + while(curr) + { + SinglyLinkedListNode* next = curr->next; + curr->next = prev; + prev = curr; + curr = next; + } + + return prev; +} diff --git a/Practicum/pract05/solutions/Task03.cpp b/Practicum/pract05/solutions/Task03.cpp new file mode 100644 index 0000000..42282c6 --- /dev/null +++ b/Practicum/pract05/solutions/Task03.cpp @@ -0,0 +1,18 @@ +bool has_cycle(SinglyLinkedListNode* head) { + if(!head) + return false; + + SinglyLinkedListNode* slow = head; + SinglyLinkedListNode* fast = head; + + while(fast && fast->next) + { + slow = slow->next; + fast = fast->next->next; + + if(slow == fast) + return true; + } + + return false; +} diff --git a/Practicum/pract05/solutions/Task04.cpp b/Practicum/pract05/solutions/Task04.cpp new file mode 100644 index 0000000..3fc11a5 --- /dev/null +++ b/Practicum/pract05/solutions/Task04.cpp @@ -0,0 +1,52 @@ +/** + * Definition for singly-linked list. + * struct ListNode { + * int val; + * ListNode *next; + * ListNode(int x) : val(x), next(NULL) {} + * }; + */ +class Solution { +public: + size_t getLen(ListNode* head) + { + size_t cnt = 0; + while(head) + { + head = head->next; + cnt++; + } + + return cnt; + } + ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { + if(!headA || !headB) + return nullptr; + + size_t sizeA = getLen(headA); + size_t sizeB = getLen(headB); + + while(sizeA > sizeB) + { + headA = headA->next; + sizeA--; + } + + while(sizeB > sizeA) + { + headB = headB->next; + sizeB--; + } + + while(headA && headB) + { + if(headA == headB) + return headA; + + headA = headA->next; + headB = headB->next; + } + + return nullptr; + } +}; -- cgit v1.3.1-23-gd82d From b445b1b7522eb8862dffd027f391ee224e25b241 Mon Sep 17 00:00:00 2001 From: Desislava Shunina <115353472+desiish@users.noreply.github.com> Date: Tue, 5 Nov 2024 17:13:22 +0200 Subject: add second task solution --- Practicum/pract05/solutions/Task02.cpp | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) create mode 100644 Practicum/pract05/solutions/Task02.cpp (limited to 'Practicum') diff --git a/Practicum/pract05/solutions/Task02.cpp b/Practicum/pract05/solutions/Task02.cpp new file mode 100644 index 0000000..4905d58 --- /dev/null +++ b/Practicum/pract05/solutions/Task02.cpp @@ -0,0 +1,16 @@ +class Solution { +public: + ListNode* middleNode(ListNode* head) { + if(!head) + return nullptr; + + ListNode* middle = head; + ListNode* end = head; + + while(end != nullptr && end->next != nullptr) { + middle = middle->next; + end = end->next->next; + } + return middle; + } +}; -- cgit v1.3.1-23-gd82d From ca5b4c5d510c1d0c1251b2a750c659872c561de2 Mon Sep 17 00:00:00 2001 From: Daniel Ghenov <47058577+Daniel-Ghenov@users.noreply.github.com> Date: Mon, 11 Nov 2024 23:37:37 +0200 Subject: Add files via upload --- Practicum/pract06/readme.md | 11 ++++++++ Practicum/pract06/solutions/Task 01.cpp | 35 ++++++++++++++++++++++++ Practicum/pract06/solutions/Task 02.cpp | 48 +++++++++++++++++++++++++++++++++ 3 files changed, 94 insertions(+) create mode 100644 Practicum/pract06/readme.md create mode 100644 Practicum/pract06/solutions/Task 01.cpp create mode 100644 Practicum/pract06/solutions/Task 02.cpp (limited to 'Practicum') diff --git a/Practicum/pract06/readme.md b/Practicum/pract06/readme.md new file mode 100644 index 0000000..82957b3 --- /dev/null +++ b/Practicum/pract06/readme.md @@ -0,0 +1,11 @@ +# Практикум №5 по Структури от данни, спец. ИС + +--- + +[**Valid Parentheses**](https://leetcode.com/problems/valid-parentheses/description/) + +[**Asteroid Collision**](https://leetcode.com/problems/asteroid-collision/description/) + +--- + +[**Линк към задачите**](https://leetcode.com/problem-list/awthx4gv/) diff --git a/Practicum/pract06/solutions/Task 01.cpp b/Practicum/pract06/solutions/Task 01.cpp new file mode 100644 index 0000000..738b769 --- /dev/null +++ b/Practicum/pract06/solutions/Task 01.cpp @@ -0,0 +1,35 @@ +#include +#include + +class Solution +{ +public: + bool isValid(std::string s) + { + std::stack open; + + for (char ch : s) + { + if (ch == '(' || ch == '{' || ch == '[') + { + open.push(ch); + } + else + { + if (open.empty()) + return false; + + if ((open.top() == '(' && ch == ')') || + (open.top() == '{' && ch == '}') || + (open.top() == '[' && ch == ']')) + { + open.pop(); + continue; + } + return false; + } + } + + return open.empty(); + } +}; \ No newline at end of file diff --git a/Practicum/pract06/solutions/Task 02.cpp b/Practicum/pract06/solutions/Task 02.cpp new file mode 100644 index 0000000..6009d36 --- /dev/null +++ b/Practicum/pract06/solutions/Task 02.cpp @@ -0,0 +1,48 @@ +#include +#include +#include + +class Solution +{ +public: + std::vector asteroidCollision(std::vector &asteroids) + { + std::stack stack; + + for (int i = 0; i < asteroids.size(); ++i) + { + if (asteroids[i] > 0 || (stack.size() && stack.top() < 0)) + { + stack.push(asteroids[i]); + continue; + } + + bool addNeg = true; + while (stack.size() && stack.top() > 0 && stack.top() + asteroids[i] <= 0) + { + if (stack.top() + asteroids[i] == 0) + { + stack.pop(); + addNeg = false; + break; + } + stack.pop(); + } + + if (addNeg && (stack.empty() || stack.top() < 0)) + { + stack.push(asteroids[i]); + } + } + + int idx = stack.size(); + std::vector result(idx); + while (stack.size()) + { + result[--idx] = stack.top(); + stack.pop(); + } + + return result; + } +}; \ No newline at end of file -- cgit v1.3.1-23-gd82d From 6c086182cffc682a325e15fcdd068b07004c2742 Mon Sep 17 00:00:00 2001 From: Daniel Ghenov <47058577+Daniel-Ghenov@users.noreply.github.com> Date: Mon, 11 Nov 2024 23:38:10 +0200 Subject: Update readme.md --- Practicum/pract06/readme.md | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'Practicum') diff --git a/Practicum/pract06/readme.md b/Practicum/pract06/readme.md index 82957b3..c626846 100644 --- a/Practicum/pract06/readme.md +++ b/Practicum/pract06/readme.md @@ -1,4 +1,4 @@ -# Практикум №5 по Структури от данни, спец. ИС +# Практикум №6 по Структури от данни, спец. ИС --- -- cgit v1.3.1-23-gd82d From 33366f5c7a84093a3b794410bcfe5479536894b4 Mon Sep 17 00:00:00 2001 From: Daniel Ghenov <47058577+Daniel-Ghenov@users.noreply.github.com> Date: Mon, 11 Nov 2024 23:58:54 +0200 Subject: Update readme.md --- Practicum/pract06/readme.md | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'Practicum') diff --git a/Practicum/pract06/readme.md b/Practicum/pract06/readme.md index c626846..087c6d3 100644 --- a/Practicum/pract06/readme.md +++ b/Practicum/pract06/readme.md @@ -1,8 +1,8 @@ -# Практикум №6 по Структури от данни, спец. ИС +# Практикум №5 по Структури от данни, спец. ИС --- -[**Valid Parentheses**](https://leetcode.com/problems/valid-parentheses/description/) +[**Next Greatest Element**](https://leetcode.com/problems/next-greater-element-ii/description/) [**Asteroid Collision**](https://leetcode.com/problems/asteroid-collision/description/) -- cgit v1.3.1-23-gd82d From 4928246bfb99672c7f874a7b66cc3ef8cb02a3b2 Mon Sep 17 00:00:00 2001 From: Daniel Ghenov <47058577+Daniel-Ghenov@users.noreply.github.com> Date: Mon, 11 Nov 2024 23:59:13 +0200 Subject: Update Task 01.cpp --- Practicum/pract06/solutions/Task 01.cpp | 40 ++++++++++++++++----------------- 1 file changed, 19 insertions(+), 21 deletions(-) (limited to 'Practicum') diff --git a/Practicum/pract06/solutions/Task 01.cpp b/Practicum/pract06/solutions/Task 01.cpp index 738b769..9ddd5e8 100644 --- a/Practicum/pract06/solutions/Task 01.cpp +++ b/Practicum/pract06/solutions/Task 01.cpp @@ -1,35 +1,33 @@ -#include +#include #include class Solution { public: - bool isValid(std::string s) + std::vector nextGreaterElements(std::vector &nums) { - std::stack open; - - for (char ch : s) + std::stack> stack; + std::vector ans(nums.size(), -1); + for (int i = 0; i < nums.size(); ++i) { - if (ch == '(' || ch == '{' || ch == '[') + while (!stack.empty() && stack.top().first < nums[i]) { - open.push(ch); + ans[stack.top().second] = nums[i]; + stack.pop(); } - else - { - if (open.empty()) - return false; - if ((open.top() == '(' && ch == ')') || - (open.top() == '{' && ch == '}') || - (open.top() == '[' && ch == ']')) - { - open.pop(); - continue; - } - return false; + stack.emplace(nums[i], i); + } + + for (int i = 0; i < nums.size(); ++i) + { + while (!stack.empty() && stack.top().first < nums[i]) + { + ans[stack.top().second] = nums[i]; + stack.pop(); } } - return open.empty(); + return ans; } -}; \ No newline at end of file +}; -- cgit v1.3.1-23-gd82d