diff options
Merge branch 'main' of https://github.com/stoychoX/Data-structures-and-algorithms
3 files changed, 92 insertions, 0 deletions
| -rw-r--r-- | Practicum/pract06/readme.md | 11 | ||||
| -rw-r--r-- | Practicum/pract06/solutions/Task 01.cpp | 33 | ||||
| -rw-r--r-- | Practicum/pract06/solutions/Task 02.cpp | 48 |
diff --git a/Practicum/pract06/readme.md b/Practicum/pract06/readme.md new file mode 100644 index 0000000..087c6d3 --- /dev/null +++ b/Practicum/pract06/readme.md @@ -0,0 +1,11 @@ +# Практикум №5 по Структури от данни, спец. ИС
+
+---
+
+[**Next Greatest Element**](https://leetcode.com/problems/next-greater-element-ii/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..9ddd5e8 --- /dev/null +++ b/Practicum/pract06/solutions/Task 01.cpp @@ -0,0 +1,33 @@ +#include <vector>
+#include <stack>
+
+class Solution
+{
+public:
+ std::vector<int> nextGreaterElements(std::vector<int> &nums)
+ {
+ std::stack<std::pair<int, int>> stack;
+ std::vector<int> ans(nums.size(), -1);
+ for (int i = 0; i < nums.size(); ++i)
+ {
+ while (!stack.empty() && stack.top().first < nums[i])
+ {
+ ans[stack.top().second] = nums[i];
+ stack.pop();
+ }
+
+ 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 ans;
+ }
+};
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 <string>
+#include <stack>
+#include <vector>
+
+class Solution
+{
+public:
+ std::vector<int> asteroidCollision(std::vector<int> &asteroids)
+ {
+ std::stack<int> 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<int> result(idx);
+ while (stack.size())
+ {
+ result[--idx] = stack.top();
+ stack.pop();
+ }
+
+ return result;
+ }
+};
\ No newline at end of file |