commit 66217fb7838be3c0bbb9dbfcd72d7c344e11807c
parent 305d2784b18b027d3e98fea2c0c0a9d3b17b8daa
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Sat, 23 Sep 2023 12:57:18 +0000
Daily Problem and 5 Random Problems
Diffstat:
7 files changed, 166 insertions(+), 0 deletions(-)
diff --git a/Problems/0341.cpp b/Problems/0341.cpp
@@ -0,0 +1,24 @@
+class NestedIterator {
+ stack<pair<vector<NestedInteger> *, int>> st;
+
+ public:
+ NestedIterator(vector<NestedInteger> &nestedList) { st.push({&nestedList, 0}); }
+ int next() {
+ if (!hasNext()) return -1;
+ auto &elem = st.top();
+ return (*elem.first)[elem.second++].getInteger();
+ }
+
+ bool hasNext() {
+ while (!st.empty()) {
+ auto &elem = st.top();
+ if (elem.second == elem.first->size()) {
+ st.pop();
+ continue;
+ }
+ if ((*elem.first)[elem.second].isInteger()) return true;
+ st.push({&(*elem.first)[elem.second++].getList(), 0});
+ }
+ return false;
+ }
+};
diff --git a/Problems/0386.cpp b/Problems/0386.cpp
@@ -0,0 +1,19 @@
+class Solution {
+ public:
+ vector<int> lexicalOrder(int n) {
+ vector<int> res(n);
+ int cur = 1;
+ for (int i = 0; i < n; i++) {
+ res[i] = cur;
+ if (cur * 10 <= n)
+ cur *= 10;
+ else {
+ if (cur >= n) cur /= 10;
+ cur += 1;
+ while (cur % 10 == 0)
+ cur /= 10;
+ }
+ }
+ return res;
+ }
+};
diff --git a/Problems/0398.cpp b/Problems/0398.cpp
@@ -0,0 +1,36 @@
+#pragma GCC optimize("fast")
+static auto _ = []() {
+ ios_base::sync_with_stdio(false);
+ cin.tie(NULL), cout.tie(NULL);
+ return 0;
+}();
+
+// O(n) pick, O(1) space
+class Solution {
+ const vector<int> &nums;
+
+ public:
+ Solution(const vector<int> &nums) : nums(nums) {}
+
+ int pick(int target) {
+ int n = 0, ans = -1;
+ for (int i = 0; i < nums.size(); i++) {
+ if (nums[i] != target) continue;
+ if (rand() % ++n == 0) ans = i;
+ }
+ return ans;
+ }
+};
+
+// O(1) pick, O(n) space
+class Solution {
+ unordered_map<int, vector<int>> um;
+
+ public:
+ Solution(const vector<int> &nums) {
+ for (int i = 0; i < nums.size(); i++)
+ um[nums[i]].push_back(i);
+ }
+
+ int pick(int target) { return um[target][rand() % um[target].size()]; }
+};
diff --git a/Problems/1048.cpp b/Problems/1048.cpp
@@ -0,0 +1,30 @@
+class Solution {
+ public:
+ int longestStrChain(vector<string> &words) {
+ sort(begin(words), end(words), [](const auto &a, const auto &b) { return a.size() < b.size(); });
+
+ static int dp[1001];
+ memset(dp, 0x00, sizeof(dp));
+
+ int res = 0;
+ for (int i = 0; i < words.size(); i++) {
+ for (int j = i + 1; j < words.size(); j++) {
+ if (words[j].size() == words[i].size()) continue;
+ if (words[j].size() - words[i].size() > 1) break;
+ int k = 0, l = 0, diff = 0;
+ while (k < words[i].size()) {
+ if (words[i][k] == words[j][l])
+ k++, l++;
+ else {
+ l++;
+ if (diff++) break;
+ }
+ }
+ if (diff == 2) continue;
+ res = max(res, dp[j] = max(dp[j], dp[i] + 1));
+ }
+ }
+
+ return res + 1;
+ }
+};
diff --git a/Problems/1324.cpp b/Problems/1324.cpp
@@ -0,0 +1,24 @@
+class Solution {
+ public:
+ vector<string> printVertically(const string &s) {
+ vector<string> vec, res;
+
+ string tmp, buf;
+ stringstream ss(s);
+ while (ss >> tmp)
+ vec.push_back(tmp);
+
+ for (int i = 0; true; i++) {
+ tmp.clear(), buf.clear();
+ for (const string &s : vec) {
+ if (s.size() <= i)
+ buf += " ";
+ else
+ tmp += buf + s[i], buf.clear();
+ }
+ if (!tmp.size()) break;
+ res.push_back(tmp);
+ }
+ return res;
+ }
+};
diff --git a/Problems/1400.cpp b/Problems/1400.cpp
@@ -0,0 +1,27 @@
+class Solution {
+ public:
+ bool canConstruct(const string &s, int k) {
+ if (s.size() < k) return false;
+
+ int count[27] = {0};
+ for (const char c : s)
+ count[c & 0x1F]++;
+
+ int singles = 0;
+ for (int i = 1; i <= 26; i++)
+ singles += count[i] & 1;
+ return singles <= k;
+ }
+};
+
+class Solution {
+ public:
+ bool canConstruct(const string &s, int k) {
+ if (s.size() < k) return false;
+
+ bitset<27> bs;
+ for (const char c : s)
+ bs.flip(c & 0x1F);
+ return bs.count() <= k;
+ }
+};
diff --git a/README.md b/README.md
@@ -249,6 +249,7 @@ for solving problems.
| 0332 | Hard | [Reconstruct Itinerary](Problems/0332.cpp) |
| 0334 | Medium | [Increasing Triplet Subsequence](Problems/0334.cpp) |
| 0338 | Easy | [Counting Bits](Problems/0338.cpp) |
+| 0341 | Medium | [Flatten Nested List Iterator](Problems/0341.cpp) |
| 0342 | Easy | [Power of Four](Problems/0342.cpp) |
| 0343 | Medium | [Integer Break](Problems/0343.cpp) |
| 0344 | Easy | [Reverse String](Problems/0344.cpp) |
@@ -265,9 +266,11 @@ 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) |
+| 0386 | Medium | [Lexicographical Numbers](Problems/0386.cpp) |
| 0387 | Easy | [First Unique Character in a String](Problems/0387.cpp) |
| 0392 | Easy | [Is Subsequence](Problems/0392.cpp) |
| 0394 | Medium | [Decode String](Problems/0394.cpp) |
+| 0398 | Medium | [Random Pick Index](Problems/0398.cpp) |
| 0399 | Medium | [Evaluate Division](Problems/0399.cpp) |
| 0402 | Medium | [Remove K Digits](Problems/0402.cpp) |
| 0403 | Hard | [Frog Jump](Problems/0403.cpp) |
@@ -487,6 +490,7 @@ for solving problems.
| 1043 | Medium | [Partition Array for Maximum Sum](Problems/1043.cpp) |
| 1046 | Easy | [Last Stone Weight](Problems/1046.cpp) |
| 1047 | Easy | [Remove All Adjacent Duplicates In String](Problems/1047.cpp) |
+| 1048 | Medium | [Longest String Chain](Problems/1048.cpp) |
| 1051 | Easy | [Height Checker](Problems/1051.cpp) |
| 1061 | Medium | [Lexicographically Smallest Equivalent String](Problems/1061.cpp) |
| 1071 | Easy | [Greatest Common Divisor of Strings](Problems/1071.cpp) |
@@ -543,6 +547,7 @@ for solving problems.
| 1318 | Medium | [Minimum Flips to Make a OR b Equal to c](Problems/1318.cpp) |
| 1319 | Medium | [Number of Operations to Make Network Connected](Problems/1319.cpp) |
| 1323 | Easy | [Maximum 69 Number](Problems/1323.cpp) |
+| 1324 | Medium | [Print Words Vertically](Problems/1324.cpp) |
| 1325 | Medium | [Delete Leaves With a Given Value](Problems/1325.cpp) |
| 1326 | Hard | [Minimum Number of Taps to Open to Water a Garden](Problems/1326.cpp) |
| 1329 | Medium | [Sort the Matrix Diagonally](Problems/1329.cpp) |
@@ -573,6 +578,7 @@ for solving problems.
| 1387 | Medium | [Sort Integers by The Power Value](Problems/1387.cpp) |
| 1395 | Medium | [Count Number of Teams](Problems/1395.cpp) |
| 1396 | Medium | [Design Underground System](Problems/1396.cpp) |
+| 1400 | Medium | [Construct K Palindrome Strings](Problems/1400.cpp) |
| 1402 | Hard | [Reducing Dishes](Problems/1402.cpp) |
| 1406 | Hard | [Stone Game III](Problems/1406.cpp) |
| 1409 | Medium | [Queries on a Permutation With Key](Problems/1409.cpp) |
