diff options
Add files via upload
3 files changed, 94 insertions, 0 deletions
| -rw-r--r-- | Practicum/pract06/readme.md | 11 | ||||
| -rw-r--r-- | Practicum/pract06/solutions/Task 01.cpp | 35 | ||||
| -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..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 <string>
+#include <stack>
+
+class Solution
+{
+public:
+ bool isValid(std::string s)
+ {
+ std::stack<char> 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 <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 |
