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