commit 4a4aabf9af32c9c11e623dd56367ef38ba55c08e
parent 913dfac86f8993bcf569db309ab5563e76c6d0e9
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Sun, 1 Jan 2023 19:27:06 +0100
Some daily problems
Diffstat:
4 files changed, 109 insertions(+), 22 deletions(-)
diff --git a/Problems/0290.cpp b/Problems/0290.cpp
@@ -0,0 +1,22 @@
+class Solution {
+public:
+ bool wordPattern(string pattern, string s) {
+ vector<string> done(26, "");
+ unordered_set<string> st;
+
+ int c = 0;
+ istringstream in(s);
+ for (string crnt; in >> crnt; ++c) {
+ if (c >= pattern.size()) return false;
+ int index = pattern[c] - 'a';
+ if (done[index].empty()) {
+ if (st.count(crnt)) return false;
+ st.insert(done[index] = crnt);
+ } else if (done[index] != crnt)
+ return false;
+ }
+ if (pattern.size() > c) return false;
+
+ return true;
+ }
+};
diff --git a/Problems/0494.cpp b/Problems/0494.cpp
@@ -1,30 +1,37 @@
+// Initial solution
class Solution {
public:
int findTargetSumWays(vector<int> &nums, int target) {
- queue<int> st;
- st.push(0);
-
- int zc = 0;
- for (int i = 0; i != nums.size(); ++i) {
- if (!nums[i]) {
- zc++;
- continue;
- }
-
- for (int j = st.size(); j > 0; --j) {
- int n = st.front();
- st.pop();
- st.push(n - nums[i]);
- st.push(n + nums[i]);
+ unordered_map<int, int> crnt;
+ crnt[0] = 1;
+ for (int i = 0; i < nums.size(); i++) {
+ unordered_map<int, int> next;
+ for (auto &p : crnt) {
+ next[p.first + nums[i]] += p.second;
+ next[p.first - nums[i]] += p.second;
}
+ crnt = next;
}
+ return crnt[target];
+ }
+};
- int count = 0;
- while (!st.empty()) {
- if (st.front() == target) count++;
- st.pop();
+// Optimized using array;
+class Solution {
+public:
+ int findTargetSumWays(vector<int> &nums, int target) {
+ int total = accumulate(nums.begin(), nums.end(), 0);
+ vector<int> dp(2 * total + 1);
+ dp[total] = 1;
+ for (int i = 0; i < nums.size(); i++) {
+ vector<int> next(2 * total + 1);
+ for (int j = 0; j < dp.size(); j++) {
+ if (!dp[j]) continue;
+ next[j + nums[i]] += dp[j];
+ next[j - nums[i]] += dp[j];
+ }
+ dp = next;
}
-
- return count * exp2(zc);
+ return abs(target) > total ? 0 : dp[target + total];
}
};
diff --git a/Problems/0980.cpp b/Problems/0980.cpp
@@ -0,0 +1,56 @@
+class Solution {
+ vector<pair<int, int>> offset = {
+ { 0, 1},
+ { 0, -1},
+ { 1, 0},
+ {-1, 0}
+ };
+ int m, n;
+
+ bool valid(int x, int y) { return x >= 0 && x < m && y >= 0 && y < n; }
+
+ int find(vector<vector<int>> &grid, int x, int y, int obs) {
+ stack<pair<int, int>> st;
+ st.push({x, y});
+
+ int count = 0, goal = m * n - obs - 1, crnt = 0;
+ while (!st.empty()) {
+ auto p = st.top();
+
+ if (grid[p.first][p.second] == 3) {
+ st.pop();
+ grid[p.first][p.second] = 0;
+ crnt--;
+ continue;
+ }
+
+ grid[p.first][p.second] = 3;
+ crnt++;
+ for (auto &o : offset) {
+ int x = p.first + o.first;
+ int y = p.second + o.second;
+ if (!valid(x, y) || grid[x][y] == 3 || grid[x][y] == -1) continue;
+ if (grid[x][y] == 2)
+ count += crnt == goal;
+ else
+ st.push({x, y});
+ }
+ }
+ return count;
+ }
+
+public:
+ int uniquePathsIII(vector<vector<int>> &grid) {
+ m = grid.size(), n = grid[0].size();
+
+ int x, y, count = 0;
+ for (int i = 0; i < m; i++)
+ for (int j = 0; j < n; j++)
+ if (grid[i][j] == 1)
+ x = i, y = j;
+ else if (grid[i][j] == -1)
+ count++;
+
+ return find(grid, x, y, count);
+ }
+};
diff --git a/README.md b/README.md
@@ -93,6 +93,7 @@ if you have any questions.
| 0279 | Medium | [Perfect Squares](Problems/0279.cpp) |
| 0283 | Easy | [Move Zeroes](Problems/0283.cpp) |
| 0287 | Medium | [Find the Duplicate Number](Problems/0287.cpp) |
+| 0290 | Easy | [Word Pattern](Problems/0290.cpp) |
| 0328 | Medium | [Odd Even Linked List](Problems/0328.cpp) |
| 0338 | Easy | [Counting Bits](Problems/0338.cpp) |
| 0344 | Easy | [Reverse String](Problems/0344.cpp) |
@@ -114,6 +115,7 @@ if you have any questions.
| 0448 | Easy | [Find All Numbers Disappeared in an Array](Problems/0448.cpp) |
| 0450 | Medium | [Delete Node in a BST](Problems/0450.cpp) |
| 0485 | Easy | [Max Consecutive Ones](Problems/0485.cpp) |
+| 0494 | Medium | [Target Sum](Problems/0494.cpp) |
| 0496 | Medium | [Next Greater Element I](Problems/0496.cpp) |
| 0498 | Medium | [Diagonal Traverse](Problems/0498.cpp) |
| 0501 | Easy | [Find Mode in Binary Search Tree](Problems/0501.cpp) |
@@ -167,6 +169,7 @@ if you have any questions.
| 0959 | Medium | [Regions Cut By Slashes](Problems/0959.cpp) |
| 0965 | Easy | [Univalued Binary Tree](Problems/0965.cpp) |
| 0977 | Easy | [Squares of a Sorted Array](Problems/0977.cpp) |
+| 0980 | Hard | [Unique Paths III](Problems/0980.cpp) |
| 0989 | Easy | [Add to Array-Form of Integer](Problems/0989.cpp) |
| 0993 | Easy | [Cousins in Binary Tree](Problems/0993.cpp) |
| 0997 | Easy | [Find the Town Judge](Problems/0997.cpp) |
@@ -237,7 +240,6 @@ if you have any questions.
| Number | Difficulty | Solution |
|:------:|:----------:|-------------------------------------------------------------------------------------------------|
-| 0494 | Medium | [Target Sum](Problems/0494.cpp) |
| 0402 | Medium | [Remove K Digits](Problems/0402.cpp) |
| 0129 | Medium | [Sum Root to Leaf Numbers](Problems/0129.cpp) |
| 0542 | Medium | [01 Matrix](Problems/0542.cpp) |
