commit 1572f4d687c5ee888458c3d1dbf643da4dd197c8
parent 5b66d3a36ebb5b96e69f6bf6047ca2706e4eb809
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Mon, 4 Nov 2024 15:23:33 +0100
Daily Problem, 2 Random
Diffstat:
4 files changed, 114 insertions(+), 0 deletions(-)
diff --git a/Problems/0385.cpp b/Problems/0385.cpp
@@ -0,0 +1,58 @@
+/**
+ * // This is the interface that allows for creating nested lists.
+ * // You should not implement it, or speculate about its implementation
+ * class NestedInteger {
+ * public:
+ * // Constructor initializes an empty nested list.
+ * NestedInteger();
+ *
+ * // Constructor initializes a single integer.
+ * NestedInteger(int value);
+ *
+ * // Return true if this NestedInteger holds a single integer, rather than a nested list.
+ * bool isInteger() const;
+ *
+ * // Return the single integer that this NestedInteger holds, if it holds a single integer
+ * // The result is undefined if this NestedInteger holds a nested list
+ * int getInteger() const;
+ *
+ * // Set this NestedInteger to hold a single integer.
+ * void setInteger(int value);
+ *
+ * // Set this NestedInteger to hold a nested list and adds a nested integer to it.
+ * void add(const NestedInteger &ni);
+ *
+ * // Return the nested list that this NestedInteger holds, if it holds a nested list
+ * // The result is undefined if this NestedInteger holds a single integer
+ * const vector<NestedInteger> &getList() const;
+ * };
+ */
+class Solution {
+ public:
+ NestedInteger deserialize(const string &s) const {
+ if (s[0] != '[') return NestedInteger(stoi(s));
+
+ stack<NestedInteger> st;
+ const int n = size(s);
+
+ for (int i = 0; i < n - 1; i++) {
+ if (s[i] == ',') continue;
+
+ if (s[i] == '[')
+ st.push({});
+ else if (s[i] == ']') {
+ const auto top = st.top();
+ st.pop();
+ st.top().add(top);
+ } else {
+ const int start = i;
+ while (i < n && s[i] != '[' && s[i] != ']' && s[i] != ',')
+ i++;
+ st.top().add(stoi(s.substr(start, i - start)));
+ i--;
+ }
+ }
+
+ return st.top();
+ }
+};
diff --git a/Problems/0388.cpp b/Problems/0388.cpp
@@ -0,0 +1,35 @@
+class Solution {
+ public:
+ int lengthLongestPath(const string &input) const {
+ const int n = size(input);
+ stack<pair<int, int>> st;
+ int res = 0;
+
+ st.emplace(0, 0);
+ for (int i = 0, dir_len = 0; i < n;) {
+ if (input[i] == '\n') {
+ int cnt = 0;
+ while (++i < n && input[i] == '\t')
+ cnt++;
+
+ while (cnt < st.top().first)
+ st.pop();
+ if (cnt > st.top().first) st.emplace(cnt, st.top().second + dir_len + 1);
+ } else {
+ int cnt = 0, is_file = 0;
+
+ while (i < n && input[i] != '\n') {
+ if (input[i] == '.') is_file = true;
+ i++, cnt++;
+ }
+
+ if (is_file)
+ res = max(res, st.top().second + cnt);
+ else
+ dir_len = cnt;
+ }
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/3163.cpp b/Problems/3163.cpp
@@ -0,0 +1,18 @@
+class Solution {
+ public:
+ string compressedString(const string &word) const {
+ const int n = size(word);
+ string res;
+
+ for (int i = 0; i < n;) {
+ const char c = word[i++];
+ int cnt = 1;
+
+ while (i < n && cnt < 9 && word[i] == c)
+ cnt++, i++;
+ res += to_string(cnt) + c;
+ }
+
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -336,8 +336,10 @@ reference and a base for solving problems.
| 0382 | Medium | [Linked List Random Node](Problems/0382.cpp) |
| 0383 | Easy | [Ransom Note](Problems/0383.cpp) |
| 0384 | Medium | [Shuffle an Array](Problems/0384.cpp) |
+| 0385 | Medium | [Mini Parser](Problems/0385.cpp) |
| 0386 | Medium | [Lexicographical Numbers](Problems/0386.cpp) |
| 0387 | Easy | [First Unique Character in a String](Problems/0387.cpp) |
+| 0388 | Medium | [Longest Absolute File Path](Problems/0388.cpp) |
| 0389 | Easy | [Find the Difference](Problems/0389.cpp) |
| 0392 | Easy | [Is Subsequence](Problems/0392.cpp) |
| 0394 | Medium | [Decode String](Problems/0394.cpp) |
@@ -1415,6 +1417,7 @@ reference and a base for solving problems.
| 3111 | Medium | [Minimum Rectangles to Cover Points](Problems/3111.cpp) |
| 3137 | Medium | [Minimum Number of Operations to Make Word K-Periodic](Problems/3137.cpp) |
| 3159 | Medium | [Find Occurrences of an Element in an Array](Problems/3159.cpp) |
+| 3163 | Medium | [String Compression III](Problems/3163.cpp) |
| 3190 | Easy | [Find Minimum Operations to Make All Elements Divisible by Three](Problems/3190.cpp) |
| 3191 | Medium | [Minimum Operations to Make Binary Array Elements Equal to One I](Problems/3191.cpp) |
| 3192 | Medium | [Minimum Operations to Make Binary Array Elements Equal to One II](Problems/3192.cpp) |
