Website Summary Files Commits Branches @commit @diff @stats
path: root / Practicum / pract06
diff options
context:
space:
mode:
Commitca5b4c5d510c1d0c1251b2a750c659872c561de2 (patch)
Author
 Daniel Ghenov <47058577+Daniel-Ghenov@users.noreply.github.com>
2024-11-11 23:37:37 +0200
Committer
 GitHub <noreply@github.com>
2024-11-11 23:37:37 +0200
Files7f44e8cb9d75361f734c44abb71dcc6f5a54f16b /Practicum/pract06
Data-structures-and-algorithms-ca5b4c5d510c1d0c1251b2a750c659872c561de2.tar
Data-structures-and-algorithms-ca5b4c5d510c1d0c1251b2a750c659872c561de2.tar.gz
Data-structures-and-algorithms-ca5b4c5d510c1d0c1251b2a750c659872c561de2.zip
Parentb445b1b7522eb8862dffd027f391ee224e25b241 (diff)
Add files via upload
3 files changed, 94 insertions, 0 deletions
-rw-r--r--Practicum/pract06/readme.md11
-rw-r--r--Practicum/pract06/solutions/Task 01.cpp35
-rw-r--r--Practicum/pract06/solutions/Task 02.cpp48
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