commit b9380b2758109dc635a18825071caebfcaba6d5f
parent 588fe94ef913e9ca4cd59527c6da461b4ee96bb7
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Fri, 1 Sep 2023 12:49:43 +0200
5 Random Problems
Diffstat:
6 files changed, 101 insertions(+), 0 deletions(-)
diff --git a/Problems/1237.cpp b/Problems/1237.cpp
@@ -0,0 +1,12 @@
+class Solution {
+ public:
+ vector<vector<int>> findSolution(CustomFunction &customfunction, int z) const {
+ vector<vector<int>> res;
+ for (int x = 1, y = 1000; x <= 1000; ++x) {
+ while (y > 1 && customfunction.f(x, y) > z)
+ y--;
+ if (customfunction.f(x, y) == z) res.push_back({x, y});
+ }
+ return res;
+ }
+};
diff --git a/Problems/1357.cpp b/Problems/1357.cpp
@@ -0,0 +1,25 @@
+class Cashier {
+ uint16_t price[201];
+ uint16_t n, crnt = 0;
+ double discount;
+
+ public:
+ Cashier(int n, int discount, const vector<int> &products, const vector<int> &prices)
+ : n(n), discount((double)(100 - discount) / 100.0) {
+ for (int i = 0; i < products.size(); i++)
+ this->price[products[i]] = prices[i];
+ }
+
+ double getBill(const vector<int> &product, const vector<int> &amount) {
+ uint32_t total = 0;
+ for (uint8_t i = 0; i < product.size(); i++)
+ total += price[product[i]] * amount[i];
+
+ if (++crnt == n) {
+ crnt = 0;
+ return total * discount;
+ }
+
+ return total;
+ }
+};
diff --git a/Problems/1387.cpp b/Problems/1387.cpp
@@ -0,0 +1,26 @@
+class Solution {
+ static inline constexpr const array<int, 1001> dp = []() constexpr -> array<int, 1001> {
+ array<int, 1001> dp;
+ dp[0] = 0;
+ for (int i = 1; i <= 1000; i++) {
+ int res = 0, n = i;
+ while (n != 1) {
+ n = (n % 2) ? 3 * n + 1 : n / 2;
+ res++;
+ }
+ dp[i] = res;
+ }
+ return dp;
+ }();
+
+ public:
+ int getKth(int lo, int hi, int k) {
+ vector<int> vec(hi - lo + 1);
+
+ iota(begin(vec), end(vec), lo);
+ nth_element(begin(vec), begin(vec) + k - 1, end(vec),
+ [](const int a, const int b) { return dp[a] == dp[b] ? a < b : dp[a] < dp[b]; });
+
+ return vec[k - 1];
+ }
+};
diff --git a/Problems/1433.cpp b/Problems/1433.cpp
@@ -0,0 +1,20 @@
+class Solution {
+ public:
+ bool checkIfCanBreak(const string &s1, const string &s2) const {
+ int vec[27] = {0};
+
+ for (int i = 0; i < s1.size(); i++) {
+ vec[s1[i] & 0x1F]++;
+ vec[s2[i] & 0x1F]--;
+ }
+
+ bool b1 = false, b2 = false;
+ for (int i = 1, total = 0; i <= 26; i++) {
+ total += vec[i];
+ if (total > 0) b1 = true;
+ if (total < 0) b2 = true;
+ if (b1 && b2) return false;
+ }
+ return true;
+ }
+};
diff --git a/Problems/1963.cpp b/Problems/1963.cpp
@@ -0,0 +1,13 @@
+class Solution {
+ public:
+ int minSwaps(const string &s) {
+ int size = 0;
+ for (const char c : s) {
+ if (c == '[')
+ size++;
+ else if (size > 0)
+ size--;
+ }
+ return (size + 1) / 2;
+ }
+};
diff --git a/README.md b/README.md
@@ -485,6 +485,7 @@ for solving problems.
| 1218 | Medium | [Longest Arithmetic Subsequence of Given Difference](Problems/1218.cpp) |
| 1222 | Medium | [Queens That Can Attack the King](Problems/1222.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) |
@@ -513,6 +514,7 @@ for solving problems.
| 1346 | Easy | [Check if N and Its Double Exist](Problems/1346.cpp) |
| 1347 | Medium | [Minimum Number of Steps to Make Two Strings Anagram](Problems/1347.cpp) |
| 1351 | Easy | [Count Negative Numbers in a Sorted Matrix](Problems/1351.cpp) |
+| 1357 | Medium | [Apply Discount Every n Orders](Problems/1357.cpp) |
| 1361 | Medium | [Validate Binary Tree Nodes](Problems/1361.cpp) |
| 1367 | Medium | [Linked List in Binary Tree ](Problems/1367.cpp) |
| 1372 | Medium | [Longest ZigZag Path in a Binary Tree](Problems/1372.cpp) |
@@ -521,6 +523,7 @@ for solving problems.
| 1379 | Easy | [Find a Corresponding Node of a Binary Tree in a Clone of That Tree](Problems/1379.cpp) |
| 1381 | Medium | [Design a Stack With Increment Operation](Problems/1381.cpp) |
| 1382 | Medium | [Balance a Binary Search Tree](Problems/1382.cpp) |
+| 1387 | Medium | [Sort Integers by The Power Value](Problems/1387.cpp) |
| 1396 | Medium | [Design Underground System](Problems/1396.cpp) |
| 1402 | Hard | [Reducing Dishes](Problems/1402.cpp) |
| 1406 | Hard | [Stone Game III](Problems/1406.cpp) |
@@ -530,6 +533,7 @@ for solving problems.
| 1418 | Medium | [Display Table of Food Orders in a Restaurant](Problems/1418.cpp) |
| 1425 | Hard | [Constrained Subsequence Sum](Problems/1425.cpp) |
| 1431 | Easy | [Kids With the Greatest Number of Candies](Problems/1431.cpp) |
+| 1433 | Medium | [Check If a String Can Break Another String](Problems/1433.cpp) |
| 1436 | Easy | [Destination City](Problems/1436.cpp) |
| 1438 | Medium | [Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit](Problems/1438.cpp) |
| 1441 | Medium | [Build an Array With Stack Operations](Problems/1441.cpp) |
@@ -613,6 +617,7 @@ for solving problems.
| 1910 | Medium | [Remove All Occurrences of a Substring](Problems/1910.cpp) |
| 1926 | Medium | [Nearest Exit from Entrance in Maze](Problems/1926.cpp) |
| 1962 | Medium | [Remove Stones to Minimize the Total](Problems/1962.cpp) |
+| 1963 | Medium | [Minimum Number of Swaps to Make the String Balanced](Problems/1963.cpp) |
| 1964 | Hard | [Find the Longest Valid Obstacle Course at Each Position](Problems/1964.cpp) |
| 1970 | Hard | [Last Day Where You Can Still Cross](Problems/1970.cpp) |
| 1971 | Easy | [Find if Path Exists in Graph](Problems/1971.cpp) |
