commit 305d2784b18b027d3e98fea2c0c0a9d3b17b8daa
parent c8b9faa10b3c927f6e46964851629562d419fdda
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Fri, 22 Sep 2023 14:11:53 +0000
5 Random Problems
Diffstat:
6 files changed, 110 insertions(+), 0 deletions(-)
diff --git a/Problems/0648.cpp b/Problems/0648.cpp
@@ -0,0 +1,37 @@
+class Solution {
+ struct Node {
+ Node(){};
+ Node *children[27] = {nullptr};
+ bool &terminate = reinterpret_cast<bool &>(children[0]);
+ };
+
+ public:
+ string replaceWords(const vector<string> &dictionary, const string &sentence) {
+ Node *trie = new Node();
+ for (const string &s : dictionary) {
+ Node *crnt = trie;
+ for (const char c : s) {
+ const int idx = c & 0x1F;
+ if (!crnt->children[idx]) crnt->children[idx] = new Node();
+ crnt = crnt->children[idx];
+ }
+ crnt->terminate = true;
+ }
+
+ string res, word, tmp;
+ stringstream ss(sentence);
+ while (ss >> word) {
+ Node *crnt = trie;
+ for (const char c : word) {
+ const int idx = c & 0x1F;
+ if (!crnt->children[idx] || crnt->terminate) break;
+ crnt = crnt->children[idx];
+ tmp += c;
+ }
+ res += (crnt->terminate ? tmp : word) + ' ';
+ tmp.clear();
+ }
+ res.pop_back();
+ return res;
+ }
+};
diff --git a/Problems/0655.cpp b/Problems/0655.cpp
@@ -0,0 +1,25 @@
+class Solution {
+ int height(const TreeNode *root) {
+ if (!root) return 0;
+ return 1 + max(height(root->left), height(root->right));
+ }
+
+ typedef tuple<TreeNode *, int, int> record;
+
+ public:
+ vector<vector<string>> printTree(TreeNode *root) {
+ const int n = height(root), m = (1 << n) - 1;
+ vector<vector<string>> res(n, vector<string>(m));
+
+ queue<record> q;
+ q.push({root, 0, (m - 1) / 2});
+ while (!q.empty()) {
+ const auto [root, r, c] = q.front();
+ q.pop();
+ res[r][c] = to_string(root->val);
+ if (root->left) q.push({root->left, r + 1, c - (1 << (n - r - 2))});
+ if (root->right) q.push({root->right, r + 1, c + (1 << (n - r - 2))});
+ }
+ return res;
+ }
+};
diff --git a/Problems/1695.cpp b/Problems/1695.cpp
@@ -0,0 +1,12 @@
+class Solution {
+ public:
+ vector<int> getSumAbsoluteDifferences(vector<int> &nums) {
+ const int n = nums.size();
+ int left = 0, right = accumulate(begin(nums), end(nums), 0);
+ for (int i = 0; i < n; ++i) {
+ right -= nums[i], left += nums[i];
+ nums[i] = right - left + (2 * i - n + 2) * nums[i];
+ }
+ return nums;
+ }
+};
diff --git a/Problems/1701.cpp b/Problems/1701.cpp
@@ -0,0 +1,16 @@
+class Solution {
+ public:
+ double averageWaitingTime(const vector<vector<int>> &customers) {
+ const int n = customers.size();
+ double time = 0, res = 0;
+ for (int i = 0; i < n; i++) {
+ if (time < customers[i][0])
+ time = customers[i][0];
+ else
+ res += time - customers[i][0];
+ time += customers[i][1];
+ res += customers[i][1];
+ }
+ return res / n;
+ }
+};
diff --git a/Problems/1887.cpp b/Problems/1887.cpp
@@ -0,0 +1,15 @@
+class Solution {
+ public:
+ int reductionOperations(const vector<int> &nums) {
+ static int count[50001];
+ memset(count, 0x00, sizeof(count));
+
+ int res = 0, cnt = 0;
+ for (const int n : nums)
+ count[n]++;
+ for (int i = 50000; i >= 0; i--) {
+ if (count[i]) res += cnt += count[i];
+ }
+ return res - cnt;
+ }
+};
diff --git a/README.md b/README.md
@@ -347,10 +347,12 @@ for solving problems.
| 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) |
+| 0648 | Medium | [Replace Words](Problems/0648.cpp) |
| 0649 | Medium | [Dota2 Senate](Problems/0649.cpp) |
| 0652 | Medium | [Find Duplicate Subtrees](Problems/0652.cpp) |
| 0653 | Easy | [Two Sum IV - Input is a BST](Problems/0653.cpp) |
| 0654 | Medium | [Maximum Binary Tree](Problems/0654.cpp) |
+| 0655 | Medium | [Print Binary Tree](Problems/0655.cpp) |
| 0662 | Medium | [Maximum Width of Binary Tree](Problems/0662.cpp) |
| 0664 | Hard | [Strange Printer](Problems/0664.cpp) |
| 0669 | Medium | [Trim a Binary Search Tree](Problems/0669.cpp) |
@@ -647,10 +649,12 @@ for solving problems.
| 1672 | Easy | [Richest Customer Wealth](Problems/1672.cpp) |
| 1675 | Hard | [Minimize Deviation in Array](Problems/1675.cpp) |
| 1679 | Medium | [Max Number of K-Sum Pairs](Problems/1679.cpp) |
+| 1685 | Medium | [Sum of Absolute Differences in a Sorted Array](Problems/1685.cpp) |
| 1689 | Medium | [Partitioning Into Minimum Number Of Deci-Binary Numbers](Problems/1689.cpp) |
| 1696 | Medium | [Jump Game VI](Problems/1696.cpp) |
| 1697 | Hard | [Checking Existence of Edge Length Limited Paths](Problems/1697.cpp) |
| 1700 | Easy | [Number of Students Unable to Eat Lunch](Problems/1700.cpp) |
+| 1701 | Medium | [Average Waiting Time](Problems/1701.cpp) |
| 1704 | Easy | [Determine if String Halves Are Alike](Problems/1704.cpp) |
| 1706 | Medium | [Where Will the Ball Fall](Problems/1706.cpp) |
| 1721 | Medium | [Swapping Nodes in a Linked List](Problems/1721.cpp) |
@@ -685,6 +689,7 @@ for solving problems.
| 1870 | Medium | [Minimum Speed to Arrive on Time](Problems/1870.cpp) |
| 1877 | Medium | [Minimize Maximum Pair Sum in Array](Problems/1877.cpp) |
| 1884 | Medium | [Egg Drop With 2 Eggs and N Floors](Problems/1884.cpp) |
+| 1887 | Medium | [Reduction Operations to Make the Array Elements Equal](Problems/1887.cpp) |
| 1899 | Medium | [Merge Triplets to Form Target Triplet](Problems/1899.cpp) |
| 1905 | Medium | [Count Sub Islands](Problems/1905.cpp) |
| 1910 | Medium | [Remove All Occurrences of a Substring](Problems/1910.cpp) |
