commit eaca2c5a02e5c9c33ba3b5b7798d28604e2d85e1
parent cf76e2e190c536b18a29a970b7ee1bbf1d3eaa2b
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Thu, 24 Oct 2024 16:22:14 +0200
5 Random Problems
Diffstat:
6 files changed, 220 insertions(+), 0 deletions(-)
diff --git a/Problems/0307.cpp b/Problems/0307.cpp
@@ -0,0 +1,37 @@
+class SegmentTree {
+ const int n;
+ vector<int> t = vector<int>(2 * n);
+
+ public:
+ SegmentTree(const vector<int> nums) : n(size(nums)) {
+ for (int i = 0; i < n; i++)
+ t[n + i] = nums[i];
+ for (int i = n - 1; i > 0; i--)
+ t[i] = t[i * 2] + t[i * 2 + 1];
+ }
+
+ int sum(int l, int r) const {
+ int res = 0;
+
+ for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
+ if (l & 1) res += t[l++];
+ if (r & 1) res += t[--r];
+ }
+
+ return res;
+ }
+
+ void update(int p, int val) {
+ for (t[p += n] = val; p > 1; p /= 2)
+ t[p / 2] = t[p] + t[p ^ 1];
+ }
+};
+
+class NumArray {
+ SegmentTree seg;
+
+ public:
+ NumArray(const vector<int> &nums) : seg(nums) {}
+ void update(int index, int val) { seg.update(index, val); }
+ int sumRange(int left, int right) const { return seg.sum(left, right); }
+};
diff --git a/Problems/0315.cpp b/Problems/0315.cpp
@@ -0,0 +1,39 @@
+class SegmentTree {
+ const int n;
+ vector<int> t = vector<int>(2 * n);
+
+ public:
+ SegmentTree(int n) : n(n) {}
+
+ int sum(int l, int r) const {
+ int res = 0;
+
+ for (l += n, r += n; l < r; l /= 2, r /= 2) {
+ if (l & 1) res += t[l++];
+ if (r & 1) res += t[--r];
+ }
+
+ return res;
+ }
+
+ void update(int p) {
+ for (t[p += n]++; p > 1; p /= 2)
+ t[p / 2] = t[p] + t[p ^ 1];
+ }
+};
+
+class Solution {
+ public:
+ vector<int> countSmaller(const vector<int> &nums) const {
+ const int n = size(nums);
+ SegmentTree seg(20001);
+
+ vector<int> res(n);
+ for (int i = n - 1; i >= 0; i--) {
+ seg.update(nums[i] + 10000);
+ res[i] = seg.sum(0, nums[i] + 10000);
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/0493.cpp b/Problems/0493.cpp
@@ -0,0 +1,66 @@
+class SegmentTree {
+ const int n;
+ vector<int> t = vector<int>(2 * n);
+
+ public:
+ SegmentTree(const vector<int> nums) : n(size(nums)) {
+ for (int i = 0; i < n; i++)
+ t[n + i] = nums[i];
+ for (int i = n - 1; i > 0; i--)
+ t[i] = t[i * 2] + t[i * 2 + 1];
+ }
+
+ int sum(int l, int r) const {
+ int res = 0;
+
+ for (l += n, r += n; l < r; l /= 2, r /= 2) {
+ if (l & 1) res += t[l++];
+ if (r & 1) res += t[--r];
+ }
+
+ return res;
+ }
+
+ void update(int p) {
+ for (t[p += n]--; p > 1; p /= 2)
+ t[p / 2] = t[p] + t[p ^ 1];
+ }
+};
+
+class Solution {
+ public:
+ int reversePairs(const vector<int> &nums) const {
+ const int n = size(nums);
+
+ static int idxs[50001];
+ iota(idxs, idxs + n, 0);
+ sort(idxs, idxs + n, [&](int a, int b) { return nums[a] < nums[b]; });
+
+ vector<int> count; // count the number of each different value
+ map<long long, int> um; // map each number to its position in sorted unique array
+ int diff = 0, prev = nums[idxs[0]], cnt = 1;
+ for (int i = 1; i < n; i++, cnt++) {
+ const int crnt = nums[idxs[i]];
+ if (crnt == prev) continue;
+
+ um[prev] = size(count);
+ count.push_back(cnt);
+ prev = crnt;
+ cnt = 0;
+ }
+ um[prev] = size(count);
+ count.push_back(cnt);
+
+ int res = 0;
+ SegmentTree seg(count); // tree is indexed by position in sorted array
+ for (int i = n - 1; i >= 0; i--) {
+ // remove current element, and check for left pair in the rest
+ seg.update(um[nums[i]]);
+ const auto it = um.upper_bound(nums[i] * 2ll);
+ if (it == end(um)) continue;
+ res += seg.sum(it->second, size(count));
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/2080.cpp b/Problems/2080.cpp
@@ -0,0 +1,19 @@
+class RangeFreqQuery {
+ unordered_map<int, vector<int>> um;
+
+ public:
+ RangeFreqQuery(const vector<int> &arr) {
+ for (int i = 0; i < size(arr); i++) {
+ um[arr[i]].push_back(i);
+ };
+ }
+
+ int query(int left, int right, int value) const {
+ const auto it = um.find(value);
+
+ static const vector<int> dummy;
+ const auto &vec = it != end(um) ? it->second : dummy;
+
+ return distance(lower_bound(begin(vec), end(vec), left), upper_bound(begin(vec), end(vec), right));
+ }
+};
diff --git a/Problems/3291.cpp b/Problems/3291.cpp
@@ -0,0 +1,54 @@
+class Trie {
+ struct Node {
+ Node *children[26] = {0};
+ } root;
+
+ public:
+ void insert(const string &s) {
+ Node *crnt = &root;
+
+ for (const char c : s) {
+ const int idx = c - 'a';
+ if (!crnt->children[idx]) crnt->children[idx] = new Node();
+ crnt = crnt->children[idx];
+ }
+ }
+
+ int find(const string &s, int start) const {
+ const Node *crnt = &root;
+ int n = 0;
+
+ for (int i = start; i < size(s); i++, n++) {
+ const int idx = s[i] - 'a';
+ if (!crnt->children[idx]) break;
+ crnt = crnt->children[idx];
+ }
+
+ return n;
+ }
+};
+
+class Solution {
+ public:
+ int minValidStrings(const vector<string> &words, const string &target) const {
+ static unsigned dp[5001];
+ const int n = size(target);
+ Trie trie;
+
+ for (const auto &word : words)
+ trie.insert(word);
+
+ memset(dp, 0xFF, sizeof(dp));
+ dp[0] = 0;
+
+ for (int i = 0; i < n; i++) {
+ if (dp[i] == -1) continue;
+ const int limit = trie.find(target, i);
+ for (int len = 1; len <= limit; len++) {
+ dp[i + len] = min(dp[i + len], dp[i] + 1);
+ }
+ }
+
+ return dp[n];
+ }
+};
diff --git a/README.md b/README.md
@@ -284,8 +284,10 @@ for solving problems.
| 0303 | Easy | [Range Sum Query - Immutable](Problems/0303.cpp) |
| 0304 | Medium | [Range Sum Query 2D - Immutable](Problems/0304.cpp) |
| 0306 | Medium | [Additive Number](Problems/0306.cpp) |
+| 0307 | Medium | [Range Sum Query - Mutable](Problems/0307.cpp) |
| 0309 | Medium | [Best Time to Buy and Sell Stock with Cooldown](Problems/0309.cpp) |
| 0310 | Medium | [Minimum Height Trees](Problems/0310.cpp) |
+| 0315 | Hard | [Count of Smaller Numbers After Self](Problems/0315.cpp) |
| 0316 | Medium | [Remove Duplicate Letters](Problems/0316.cpp) |
| 0318 | Medium | [Maximum Product of Word Lengths](Problems/0318.cpp) |
| 0319 | Medium | [Bulb Switcher](Problems/0319.cpp) |
@@ -380,6 +382,7 @@ for solving problems.
| 0485 | Easy | [Max Consecutive Ones](Problems/0485.cpp) |
| 0486 | Medium | [Reachable Nodes With Restrictions](Problems/0486.cpp) |
| 0491 | Medium | [Non-decreasing Subsequences](Problems/0491.cpp) |
+| 0493 | Hard | [Reverse Pairs](Problems/0493.cpp) |
| 0494 | Medium | [Target Sum](Problems/0494.cpp) |
| 0496 | Medium | [Next Greater Element I](Problems/0496.cpp) |
| 0498 | Medium | [Diagonal Traverse](Problems/0498.cpp) |
@@ -1130,6 +1133,7 @@ for solving problems.
| 2074 | Medium | [Reverse Nodes in Even Length Groups](Problems/2074.cpp) |
| 2075 | Medium | [Decode the Slanted Ciphertext](Problems/2075.cpp) |
| 2079 | Medium | [Watering Plants](Problems/2079.cpp) |
+| 2080 | Medium | [Range Frequency Queries](Problems/2080.cpp) |
| 2085 | Easy | [Count Common Words With One Occurrence](Problems/2085.cpp) |
| 2087 | Medium | [Minimum Cost Homecoming of a Robot in a Grid](Problems/2087.cpp) |
| 2090 | Medium | [K Radius Subarray Averages](Problems/2090.cpp) |
@@ -1401,4 +1405,5 @@ for solving problems.
| 3239 | Medium | [Minimum Number of Flips to Make Binary Grid Palindromic I](Problems/3239.cpp) |
| 3249 | Medium | [Count the Number of Good Nodes](Problems/3249.cpp) |
| 3254 | Medium | [Find the Power of K-Size Subarrays I](Problems/3254.cpp) |
+| 3291 | Medium | [Minimum Number of Valid Strings to Form Target I](Problems/3291.cpp) |
| 3310 | Medium | [Remove Methods From Project](Problems/3310.cpp) |
