commit cf76e2e190c536b18a29a970b7ee1bbf1d3eaa2b
parent f62b544a342a9931356afc695891df152b86bebb
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Wed, 23 Oct 2024 14:34:40 +0200
4 Random Problems
Diffstat:
5 files changed, 123 insertions(+), 0 deletions(-)
diff --git a/Problems/0233.cpp b/Problems/0233.cpp
@@ -0,0 +1,13 @@
+class Solution {
+ public:
+ int countDigitOne(int n) const {
+ int res = 0;
+
+ for (long long m = 1; m <= n; m *= 10) {
+ const int a = n / m, b = n % m;
+ res += (a + 8) / 10 * m + (a % 10 == 1) * (b + 1);
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/0275.cpp b/Problems/0275.cpp
@@ -0,0 +1,18 @@
+class Solution {
+ public:
+ int hIndex(const vector<int> &citations) const {
+ const int n = size(citations);
+ int low = 0, high = n - 1;
+
+ while (low <= high) {
+ const int mid = low + (high - low) / 2;
+ if (citations[mid] == n - mid) return citations[mid];
+ if (citations[mid] > n - mid)
+ high = mid - 1;
+ else
+ low = mid + 1;
+ }
+
+ return n - high - 1;
+ }
+};
diff --git a/Problems/0282.cpp b/Problems/0282.cpp
@@ -0,0 +1,52 @@
+class Solution {
+ vector<string> res;
+
+ vector<long long> operan;
+ vector<char> operat;
+
+ void rec(long long target, const string &num, int start, long long total, long long prev) {
+ if (start == size(num)) {
+ if (total != target) return;
+
+ res.push_back(to_string(operan[0]));
+ for (int i = 0; i < size(operat); i++) {
+ res.back() += operat[i] + to_string(operan[i + 1]);
+ }
+
+ return;
+ }
+
+ operan.push_back(-1);
+ operat.push_back('_');
+ for (long long i = start, crnt = 0; i < size(num); i++) {
+ operan.back() = crnt = crnt * 10 + num[i] - '0';
+
+ operat.back() = '+';
+ rec(target, num, i + 1, total + crnt, crnt);
+
+ operat.back() = '-';
+ rec(target, num, i + 1, total - crnt, -crnt);
+
+ operat.back() = '*';
+ rec(target, num, i + 1, total + prev * (crnt - 1), prev * crnt);
+
+ if (num[start] == '0') break;
+ }
+ operan.pop_back();
+ operat.pop_back();
+ }
+
+ public:
+ vector<string> addOperators(const string &num, int target) {
+
+ operan.push_back(-1);
+ for (long long i = 0, crnt = 0; i < size(num); i++) {
+ operan.back() = crnt = crnt * 10 + num[i] - '0';
+ rec(target, num, i + 1, crnt, crnt);
+
+ if (num[0] == '0') break;
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/0301.cpp b/Problems/0301.cpp
@@ -0,0 +1,36 @@
+class Solution {
+ unordered_set<string> st;
+ int maxi = 0;
+
+ void rec(const string &s, int idx, const string &crnt, int open, int close) {
+ if (idx == size(s)) {
+ if (open != 0) return;
+
+ if (size(crnt) > maxi) {
+ maxi = size(crnt);
+ st.clear();
+ }
+
+ if (size(crnt) == maxi && !st.count(crnt)) {
+ st.insert(crnt);
+ }
+
+ return;
+ }
+
+ if (s[idx] == '(') {
+ if (open + 1 <= close) rec(s, idx + 1, crnt + '(', open + 1, close);
+ rec(s, idx + 1, crnt, open, close);
+ } else if (s[idx] == ')') {
+ if (open > 0) rec(s, idx + 1, crnt + ')', open - 1, close - 1);
+ rec(s, idx + 1, crnt, open, close);
+ } else
+ rec(s, idx + 1, crnt + s[idx], open, close);
+ }
+
+ public:
+ vector<string> removeInvalidParentheses(const string &s) {
+ rec(s, 0, "", 0, count(begin(s), end(s), ')'));
+ return vector(begin(st), end(st));
+ }
+};
diff --git a/README.md b/README.md
@@ -247,6 +247,7 @@ for solving problems.
| 0229 | Medium | [Majority Element II](Problems/0229.cpp) |
| 0231 | Easy | [Power of Two](Problems/0231.cpp) |
| 0232 | Easy | [Implement Queue using Stacks](Problems/0232.cpp) |
+| 0233 | Hard | [Number of Digit One](Problems/0233.cpp) |
| 0234 | Easy | [Palindrome Linked List](Problems/0234.cpp) |
| 0235 | Medium | [Lowest Common Ancestor of a Binary Search Tree](Problems/0235.cpp) |
| 0236 | Medium | [Lowest Common Ancestor of a Binary Tree](Problems/0236.cpp) |
@@ -265,8 +266,10 @@ for solving problems.
| 0268 | Easy | [Missing Number](Problems/0268.cpp) |
| 0273 | Hard | [Integer to English Words](Problems/0273.cpp) |
| 0274 | Medium | [H-Index](Problems/0274.cpp) |
+| 0275 | Medium | [H-Index II](Problems/0275.cpp) |
| 0278 | Easy | [First Bad Version](Problems/0278.cpp) |
| 0279 | Medium | [Perfect Squares](Problems/0279.cpp) |
+| 0282 | Hard | [Expression Add Operators](Problems/0282.cpp) |
| 0283 | Easy | [Move Zeroes](Problems/0283.cpp) |
| 0284 | Medium | [Peeking Iterator](Problems/0284.cpp) |
| 0287 | Medium | [Find the Duplicate Number](Problems/0287.cpp) |
@@ -277,6 +280,7 @@ for solving problems.
| 0297 | Hard | [Serialize and Deserialize Binary Tree](Problems/0297.cpp) |
| 0299 | Medium | [Bulls and Cows](Problems/0299.cpp) |
| 0300 | Medium | [Longest Increasing Subsequence](Problems/0300.cpp) |
+| 0301 | Hard | [Remove Invalid Parentheses](Problems/0301.cpp) |
| 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) |
