commit 5eeea6409f84eaea17cc2e0f63a3955b29da7441
parent 45df212fd6301559bf6b382e0ef3c571de5bb783
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Mon, 11 Sep 2023 21:12:51 +0200
5 Random Problems
Diffstat:
6 files changed, 137 insertions(+), 0 deletions(-)
diff --git a/Problems/1029.cpp b/Problems/1029.cpp
@@ -0,0 +1,25 @@
+class Solution {
+ public:
+ int twoCitySchedCost(vector<vector<int>> &costs) {
+ sort(begin(costs), end(costs),
+ [](const auto &a, const auto &b) { return (a[0] - a[1]) < (b[0] - b[1]); });
+ int n = costs.size() / 2, res = 0;
+ for (int i = 0; i < n; i++)
+ res += costs[i][0] + costs[i + n][1];
+ return res;
+ }
+};
+
+// Little optimization
+class Solution {
+ public:
+ int twoCitySchedCost(vector<vector<int>> &costs) {
+ const int n = costs.size() / 2;
+ nth_element(begin(costs), begin(costs) + n, end(costs),
+ [](const auto &a, const auto &b) { return (a[0] - a[1]) < (b[0] - b[1]); });
+ int res = 0;
+ for (int i = 0; i < n; i++)
+ res += costs[i][0] + costs[i + n][1];
+ return res;
+ }
+};
diff --git a/Problems/1227.cpp b/Problems/1227.cpp
@@ -0,0 +1,4 @@
+class Solution {
+ public:
+ double nthPersonGetsNthSeat(int n) { return n == 1 ? 1 : 0.5; }
+};
diff --git a/Problems/1268.cpp b/Problems/1268.cpp
@@ -0,0 +1,53 @@
+
+// Original idea
+class Solution {
+ public:
+ vector<vector<string>> suggestedProducts(vector<string> &products, const string &searchWord) {
+ sort(begin(products), end(products));
+
+ vector<vector<string>> res(searchWord.size());
+ for (int i = 0; i < searchWord.size(); i++) {
+ const string search = searchWord.substr(0, i + 1);
+ vector<string> found;
+ for (const auto &product : products) {
+ if (product.size() > i && product[i] == searchWord[i])
+ found.push_back(product);
+ else if (found.size())
+ break;
+ }
+ for (int k = 0; k < min(3ul, found.size()); k++)
+ res[i].push_back(found[k]);
+ products = found;
+ }
+
+ return res;
+ }
+};
+
+// Optimized range based solution
+class Solution {
+ public:
+ vector<vector<string>> suggestedProducts(vector<string> &products, const string searchWord) {
+ sort(begin(products), end(products));
+ vector<vector<string>> res(searchWord.size());
+ int start = 0, end = products.size();
+ for (int i = 0; i < searchWord.size(); i++) {
+ const string search = searchWord.substr(0, i + 1);
+ bool found = false;
+ for (int j = start; j < end; j++) {
+ if (products[j].size() > i && products[j][i] == searchWord[i]) {
+ if (!found) start = j;
+ found = true;
+ } else if (found) {
+ end = j;
+ break;
+ }
+ }
+ if (!found || start >= end) break;
+ for (int j = 0; j < min(3, end - start); j++)
+ res[i].push_back(products[start + j]);
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/1625.cpp b/Problems/1625.cpp
@@ -0,0 +1,32 @@
+class Solution {
+ unordered_set<string> seen;
+ string res;
+
+ string rotate(string s, int b) {
+ reverse(s.begin(), s.end());
+ reverse(s.begin(), s.begin() + b);
+ reverse(s.begin() + b, s.end());
+ return s;
+ }
+
+ string add(string s, int x) {
+ for (int i = 1; i < s.size(); i += 2)
+ s[i] = '0' + ((s[i] & 0xF) + x) % 10;
+ return s;
+ }
+
+ public:
+ void dfs(const int a, const int b, const string &s) {
+ if (seen.count(s)) return;
+ res = min(res, s);
+ seen.insert(s);
+ dfs(a, b, rotate(s, b));
+ dfs(a, b, add(s, a));
+ }
+
+ string findLexSmallestString(const string &s, int a, int b) {
+ res = s;
+ dfs(a, b, s);
+ return res;
+ }
+};
diff --git a/Problems/2304.cpp b/Problems/2304.cpp
@@ -0,0 +1,18 @@
+class Solution {
+ public:
+ int minPathCost(vector<vector<int>> &grid, const vector<vector<int>> &moveCost) {
+ const int n = grid.size(), m = grid[0].size();
+
+ for (int i = n - 2; i >= 0; i--) {
+ for (int j = 0; j < m; j++) {
+ int res = INT_MAX;
+ for (int k = 0; k < m; k++) {
+ res = min(res, grid[i + 1][k] + moveCost[grid[i][j]][k]);
+ }
+ grid[i][j] += res;
+ }
+ }
+
+ return *min_element(begin(grid[0]), end(grid[0]));
+ }
+};
diff --git a/README.md b/README.md
@@ -465,6 +465,7 @@ for solving problems.
| 1022 | Easy | [Sum of Root To Leaf Binary Numbers](Problems/1022.cpp) |
| 1026 | Medium | [Maximum Difference Between Node and Ancestor](Problems/1026.cpp) |
| 1027 | Medium | [Longest Arithmetic Subsequence](Problems/1027.cpp) |
+| 1029 | Medium | [Two City Scheduling](Problems/1029.cpp) |
| 1035 | Medium | [Uncrossed Lines](Problems/1035.cpp) |
| 1038 | Medium | [Binary Search Tree to Greater Sum Tree](Problems/1038.cpp) |
| 1042 | Medium | [Flower Planting With No Adjacent](Problems/1042.cpp) |
@@ -499,11 +500,13 @@ for solving problems.
| 1209 | Medium | [Remove All Adjacent Duplicates in String II](Problems/1209.cpp) |
| 1218 | Medium | [Longest Arithmetic Subsequence of Given Difference](Problems/1218.cpp) |
| 1222 | Medium | [Queens That Can Attack the King](Problems/1222.cpp) |
+| 1227 | Medium | [Airplane Seat Assignment Probability](Problems/1227.cpp) |
| 1232 | Easy | [Check If It Is a Straight Line](Problems/1232.cpp) |
| 1237 | Medium | [Find Positive Integer Solution for a Given Equation](Problems/1237.cpp) |
| 1249 | Medium | [Minimum Remove to Make Valid Parentheses](Problems/1249.cpp) |
| 1254 | Medium | [Number of Closed Islands](Problems/1254.cpp) |
| 1261 | Medium | [Find Elements in a Contaminated Binary Tree](Problems/1261.cpp) |
+| 1268 | Medium | [Search Suggestions System](Problems/1268.cpp) |
| 1277 | Medium | [Count Square Submatrices with All Ones](Problems/1277.cpp) |
| 1282 | Medium | [Group the People Given the Group Size They Belong To](Problems/1282.cpp) |
| 1286 | Medium | [Iterator for Combination](Problems/1286.cpp) |
@@ -595,6 +598,7 @@ for solving problems.
| 1605 | Medium | [Find Valid Matrix Given Row and Column Sums](Problems/1605.cpp) |
| 1609 | Medium | [Even Odd Tree](Problems/1609.cpp) |
| 1615 | Medium | [Maximal Network Rank](Problems/1615.cpp) |
+| 1625 | Medium | [Lexicographically Smallest String After Applying Operations](Problems/1625.cpp) |
| 1626 | Medium | [Best Team With No Conflicts](Problems/1626.cpp) |
| 1630 | Medium | [Arithmetic Subarrays](Problems/1630.cpp) |
| 1637 | Medium | [Widest Vertical Area Between Two Points Containing No Points](Problems/1637.cpp) |
@@ -696,6 +700,7 @@ for solving problems.
| 2285 | Medium | [Maximum Total Importance of Roads](Problems/2285.cpp) |
| 2294 | Medium | [Partition Array Such That Maximum Difference Is K](Problems/2294.cpp) |
| 2300 | Medium | [Successful Pairs of Spells and Potions](Problems/2300.cpp) |
+| 2304 | Medium | [Minimum Path Cost in a Grid](Problems/2304.cpp) |
| 2305 | Medium | [Fair Distribution of Cookies](Problems/2305.cpp) |
| 2306 | Hard | [Naming a Company](Problems/2306.cpp) |
| 2316 | Medium | [Count Unreachable Pairs of Nodes in an Undirected Graph](Problems/2316.cpp) |
