commit 4262d450c26845dfa95cf1bae83b5eb1f8810b17
parent cbaca96c3832ccca2b0d11cc061a5812fb7fffe2
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Sat, 20 Jan 2024 20:28:08 +0000
5 Random Problems
Diffstat:
6 files changed, 202 insertions(+), 0 deletions(-)
diff --git a/Problems/0454.cpp b/Problems/0454.cpp
@@ -0,0 +1,23 @@
+class Solution {
+ public:
+ int fourSumCount(const vector<int> &nums1, const vector<int> &nums2, const vector<int> &nums3,
+ const vector<int> &nums4) const {
+ const int n = size(nums1);
+ unordered_map<int, int> um;
+ int res = 0;
+
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < n; j++) {
+ um[nums1[i] + nums2[j]]++;
+ }
+ }
+
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < n; j++) {
+ res += um[-(nums3[i] + nums4[j])];
+ }
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/0641.cpp b/Problems/0641.cpp
@@ -0,0 +1,45 @@
+class MyCircularDeque {
+ const int n;
+ vector<int> q;
+
+ int size = 0;
+ int head = 0, tail = 0;
+
+ public:
+ MyCircularDeque(int k) : n(k), q(k) {}
+
+ bool insertFront(int value) {
+ if (size == n) return false;
+ q[head] = value;
+ head = (head + 1) % n;
+ size++;
+ return true;
+ }
+
+ bool insertLast(int value) {
+ if (size == n) return false;
+ tail = (tail - 1 + n) % n;
+ q[tail] = value;
+ size++;
+ return true;
+ }
+
+ bool deleteFront() {
+ if (!size) return false;
+ head = (head - 1 + n) % n;
+ size--;
+ return true;
+ }
+
+ bool deleteLast() {
+ if (!size) return false;
+ tail = (tail + 1) % n;
+ size--;
+ return true;
+ }
+
+ int getFront() const { return size ? q[(head - 1 + n) % n] : -1; }
+ int getRear() const { return size ? q[tail] : -1; }
+ bool isEmpty() const { return size == 0; }
+ bool isFull() const { return size == n; }
+};
diff --git a/Problems/0677.cpp b/Problems/0677.cpp
@@ -0,0 +1,82 @@
+// Only Trie
+class MapSum {
+ struct Node {
+ Node(){};
+ Node *children[27] = {nullptr};
+ int &value = reinterpret_cast<int &>(children[0]);
+ int trail = 0;
+ };
+
+ Node *trie = new Node();
+
+ public:
+ void insert(const string &key, int val) {
+ Node *prev = trie;
+ for (const char c : key) {
+ const int idx = c & 0x1F;
+ if (!prev->children[idx]) {
+ prev = nullptr;
+ break;
+ };
+ prev = prev->children[idx];
+ }
+
+ const int diff = prev ? val - prev->value : val;
+
+ Node *crnt = trie;
+ for (const char c : key) {
+ const int idx = c & 0x1F;
+ crnt->trail += diff;
+ if (!crnt->children[idx]) crnt->children[idx] = new Node();
+ crnt = crnt->children[idx];
+ }
+ crnt->value = val;
+ }
+
+ int sum(const string &prefix) const {
+ const Node *crnt = trie;
+ for (const char c : prefix) {
+ const int idx = c & 0x1F;
+ if (!crnt->children[idx]) return 0;
+ crnt = crnt->children[idx];
+ }
+ return crnt->value + crnt->trail;
+ }
+};
+
+// Trie + hash map
+class MapSum {
+ struct Node {
+ Node(){};
+ Node *children[27] = {nullptr};
+ int &value = reinterpret_cast<int &>(children[0]);
+ };
+
+ Node *trie = new Node();
+ unordered_map<string, int> um;
+
+ public:
+ void insert(const string &key, int val) {
+ const int diff = val - um[key];
+
+ Node *crnt = trie;
+ for (const char c : key) {
+ const int idx = c & 0x1F;
+ crnt->value += diff;
+ if (!crnt->children[idx]) crnt->children[idx] = new Node();
+ crnt = crnt->children[idx];
+ }
+ crnt->value += diff;
+ um[key] = val;
+ }
+
+ int sum(const string &prefix) const {
+ const Node *crnt = trie;
+ for (const char c : prefix) {
+ const int idx = c & 0x1F;
+ if (!crnt->children[idx]) return 0;
+ crnt = crnt->children[idx];
+ }
+ return crnt->value;
+ }
+};
diff --git a/Problems/1690.cpp b/Problems/1690.cpp
@@ -0,0 +1,22 @@
+class Solution {
+ static int dp[1001][1001];
+
+ static int solve(const vector<int> &stones, int i, int j, int sum) {
+ if (i > j) return 0;
+ if (dp[i][j] != -1) return dp[i][j];
+
+ const int a = sum - stones[i] - solve(stones, i + 1, j, sum - stones[i]);
+ const int b = sum - stones[j] - solve(stones, i, j - 1, sum - stones[j]);
+
+ return dp[i][j] = max(a, b);
+ }
+
+ public:
+ Solution() { memset(dp, 0xFF, sizeof(dp)); }
+ int stoneGameVII(const vector<int> &stones) const {
+ const int sum = accumulate(begin(stones), end(stones), 0);
+ return solve(stones, 0, size(stones) - 1, sum);
+ }
+};
+
+int Solution::dp[1001][1001];
diff --git a/Problems/2596.cpp b/Problems/2596.cpp
@@ -0,0 +1,25 @@
+class Solution {
+ public:
+ bool checkValidGrid(const vector<vector<int>> &grid) const {
+ static const int offset_x[] = {-2, -2, -1, -1, 1, 1, 2, 2};
+ static const int offset_y[] = {-1, 1, -2, 2, -2, 2, -1, 1};
+ const int n = size(grid), m = size(grid[0]);
+
+ int x = 0, y = 0;
+ if (grid[0][0] != 0) return false;
+ for (int cnt = 1; cnt < n * m; cnt++) {
+ for (int k = 0; k < 8; k++) {
+ const int a = x + offset_x[k];
+ const int b = y + offset_y[k];
+ if (a < 0 || b < 0 || a >= n || b >= m) continue;
+ if (grid[a][b] == cnt) {
+ x = a, y = b;
+ goto next;
+ }
+ }
+ return false;
+ next:;
+ }
+ return true;
+ }
+};
diff --git a/README.md b/README.md
@@ -330,6 +330,7 @@ for solving problems.
| 0450 | Medium | [Delete Node in a BST](Problems/0450.cpp) |
| 0451 | Medium | [Sort Characters By Frequency](Problems/0451.cpp) |
| 0452 | Medium | [Minimum Number of Arrows to Burst Balloons](Problems/0452.cpp) |
+| 0454 | Medium | [4Sum II](Problems/0454.cpp) |
| 0455 | Easy | [Assign Cookies](Problems/0455.cpp) |
| 0456 | Medium | [132 Pattern](Problems/0456.cpp) |
| 0458 | Hard | [Poor Pigs](Problems/0458.cpp) |
@@ -403,6 +404,7 @@ for solving problems.
| 0627 | Easy | [Swap Salary](Problems/0627.cpp) |
| 0636 | Medium | [Exclusive Time of Functions](Problems/0636.cpp) |
| 0637 | Easy | [Average of Levels in Binary Tree](Problems/0637.cpp) |
+| 0641 | Medium | [Design Circular Deque](Problems/0641.cpp) |
| 0643 | Easy | [Maximum Average Subarray I](Problems/0643.cpp) |
| 0646 | Medium | [Maximum Length of Pair Chain](Problems/0646.cpp) |
| 0647 | Medium | [Palindromic Substrings](Problems/0647.cpp) |
@@ -420,6 +422,7 @@ for solving problems.
| 0671 | Easy | [Second Minimum Node In a Binary Tree](Problems/0671.cpp) |
| 0673 | Medium | [Number of Longest Increasing Subsequence](Problems/0673.cpp) |
| 0676 | Medium | [Implement Magic Dictionary](Problems/0676.cpp) |
+| 0677 | Medium | [Map Sum Pairs](Problems/0677.cpp) |
| 0684 | Medium | [Redundant Connection](Problems/0684.cpp) |
| 0688 | Medium | [Knight Probability in Chessboard](Problems/0688.cpp) |
| 0690 | Medium | [Employee Importance](Problems/0690.cpp) |
@@ -819,6 +822,7 @@ for solving problems.
| 1685 | Medium | [Sum of Absolute Differences in a Sorted Array](Problems/1685.cpp) |
| 1688 | Easy | [Count of Matches in Tournament](Problems/1688.cpp) |
| 1689 | Medium | [Partitioning Into Minimum Number Of Deci-Binary Numbers](Problems/1689.cpp) |
+| 1690 | Medium | [Stone Game VII](Problems/1690.cpp) |
| 1693 | Easy | [Daily Leads and Partners](Problems/1693.cpp) |
| 1695 | Medium | [Maximum Erasure Value](Problems/1695.cpp) |
| 1696 | Medium | [Jump Game VI](Problems/1696.cpp) |
@@ -1030,6 +1034,7 @@ for solving problems.
| 2568 | Medium | [Minimum Impossible OR](Problems/2568.cpp) |
| 2579 | Medium | [Count Total Number of Colored Cells](Problems/2579.cpp) |
| 2592 | Medium | [Maximize Greatness of an Array](Problems/2592.cpp) |
+| 2596 | Medium | [Check Knight Tour Configuration](Problems/2596.cpp) |
| 2610 | Medium | [Convert an Array Into a 2D Array With Conditions](Problems/2610.cpp) |
| 2616 | Medium | [Minimize the Maximum Difference of Pairs](Problems/2616.cpp) |
| 2620 | Easy | [Counter](Problems/2620.js) |
