commit 095d05e82575e6b3345ab0819352b7d8576532de
parent 24eb038d748aff5c5e1b686a52d2e0841070841e
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Fri, 8 Nov 2024 19:58:22 +0100
5 Random Problems
Diffstat:
6 files changed, 153 insertions(+), 0 deletions(-)
diff --git a/Problems/0410.cpp b/Problems/0410.cpp
@@ -0,0 +1,38 @@
+class Solution {
+ int res = INT_MAX;
+
+ bool doable(const vector<int> &nums, int cuts, long long maxi) {
+ long long acc = 0;
+
+ for (const int num : nums) {
+ if (acc + num <= maxi)
+ acc += num;
+ else {
+ if (--cuts < 0) return false;
+ acc = num;
+ }
+ }
+
+ return true;
+ }
+
+ public:
+ int splitArray(const vector<int> &nums, int k) {
+ long long low = 0, high = 0;
+
+ for (const long long n : nums) {
+ low = max(low, n);
+ high += n;
+ }
+
+ while (low < high) {
+ const auto mid = low + (high - low) / 2;
+ if (doable(nums, k - 1, mid))
+ high = mid;
+ else
+ low = mid + 1;
+ }
+
+ return low;
+ }
+};
diff --git a/Problems/0468.cpp b/Problems/0468.cpp
@@ -0,0 +1,49 @@
+class Solution {
+ static string valid4(const string &s) {
+ stringstream ss(s);
+ string crnt;
+ int cnt = 0;
+
+ while (getline(ss, crnt, '.')) {
+ if (size(crnt) == 0 || size(crnt) > 3) break;
+ if (any_of(begin(crnt), end(crnt), [](char c) { return isalpha(c); })) break;
+ if (size(crnt) > 1 && crnt[0] == '0') break;
+ if (stoi(crnt) >= 256) break;
+ cnt++;
+ }
+
+ return cnt == 4 ? "IPv4" : "Neither";
+ }
+
+ static string valid6(const string &s) {
+ stringstream ss(s);
+ string crnt;
+ int cnt = 0;
+
+ while (getline(ss, crnt, ':')) {
+ if (size(crnt) == 0 || size(crnt) > 4) break;
+ cnt++;
+ }
+
+ return cnt == 8 ? "IPv6" : "Neither";
+ }
+
+ public:
+ string validIPAddress(const string &queryIP) const {
+ int dot = 0, col = 0;
+
+ for (const char c : queryIP) {
+ if (c == '.')
+ dot++;
+ else if (c == ':')
+ col++;
+ else if (!isxdigit(c))
+ return "Neither";
+ }
+
+ if (dot && col) return "Neither";
+ if (dot ? dot != 3 : col != 7) return "Neither";
+
+ return dot ? valid4(queryIP) : valid6(queryIP);
+ }
+};
diff --git a/Problems/0474.cpp b/Problems/0474.cpp
@@ -0,0 +1,19 @@
+class Solution {
+ public:
+ int findMaxForm(const vector<string> &strs, int m, int n) const {
+ static int dp[101][101];
+
+ memset(dp, 0x00, sizeof(dp));
+ for (const auto &s : strs) {
+ const int zero = count(begin(s), end(s), '0');
+ const int one = size(s) - zero;
+ for (int i = m; i >= zero; i--) {
+ for (int j = n; j >= one; j--) {
+ dp[i][j] = max(dp[i][j], 1 + dp[i - zero][j - one]);
+ }
+ }
+ }
+
+ return dp[m][n];
+ }
+};
diff --git a/Problems/0475.cpp b/Problems/0475.cpp
@@ -0,0 +1,24 @@
+class Solution {
+ public:
+ int findRadius(vector<int> &houses, vector<int> &heaters) const {
+ sort(begin(heaters), end(heaters));
+ sort(begin(houses), end(houses));
+
+ int res = 0, crnt;
+ const int n = size(houses);
+ const int m = size(heaters);
+ for (int i = 0, j = 0; i < n; i++) {
+ while (j < m && houses[i] >= heaters[j])
+ j++;
+
+ int crnt = INT_MAX;
+
+ if (j > 0) crnt = houses[i] - heaters[j - 1];
+ if (j != m) crnt = min(crnt, heaters[j] - houses[i]);
+
+ res = max(res, crnt);
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/0482.cpp b/Problems/0482.cpp
@@ -0,0 +1,18 @@
+class Solution {
+ public:
+ string licenseKeyFormatting(const string &s, int k) const {
+ const int n = std::count(begin(s), end(s), '-');
+ const int m = size(s) - n;
+
+ string res;
+ int goal = m % k ? m % k + 1 : k + 1;
+ for (const char c : s) {
+ if (c == '-') continue;
+ if (!--goal) res += '-', goal = k;
+
+ res += toupper(c);
+ }
+
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -357,6 +357,7 @@ reference and a base for solving problems.
| 0405 | Easy | [Convert a Number to Hexadecimal](Problems/0405.cpp) |
| 0406 | Medium | [Queue Reconstruction by Height](Problems/0406.cpp) |
| 0409 | Easy | [Longest Palindrome](Problems/0409.cpp) |
+| 0410 | Hard | [Split Array Largest Sum](Problems/0410.cpp) |
| 0412 | Easy | [Fizz Buzz](Problems/0412.cpp) |
| 0413 | Medium | [Arithmetic Slices](Problems/0413.cpp) |
| 0414 | Easy | [Third Maximum Number](Problems/0414.cpp) |
@@ -402,11 +403,15 @@ reference and a base for solving problems.
| 0463 | Easy | [Island Perimeter](Problems/0463.cpp) |
| 0464 | Medium | [Can I Win](Problems/0464.cpp) |
| 0467 | Medium | [Unique Substrings in Wraparound String](Problems/0467.cpp) |
+| 0468 | Medium | [Validate IP Address](Problems/0468.cpp) |
| 0472 | Hard | [Concatenated Words](Problems/0472.cpp) |
| 0473 | Medium | [Matchsticks to Square](Problems/0473.cpp) |
+| 0474 | Medium | [Ones and Zeroes](Problems/0474.cpp) |
+| 0475 | Medium | [Heaters](Problems/0475.cpp) |
| 0476 | Easy | [Number Complement](Problems/0476.cpp) |
| 0477 | Medium | [Total Hamming Distance](Problems/0477.cpp) |
| 0481 | Medium | [Magical String](Problems/0481.cpp) |
+| 0482 | Easy | [License Key Formatting](Problems/0482.cpp) |
| 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) |
