leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE |
commitdca51809e945f819aa539e654ff5998adab655aa
parentb3c2f19e8a0012b83880da750f75021cbf36bc3c
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateTue, 23 Jan 2024 18:21:10 +0000

Daily Problem and 2 Random Problems

Diffstat:
AProblems/0816.cpp|++++++++++++++++++++++++++++++++++++++++++
AProblems/1239.cpp|++++++++++++++++++++++++
AProblems/1461.cpp|++++++++++++++++++++++++
MREADME.md|+++

4 files changed, 93 insertions(+), 0 deletions(-)

diff --git a/Problems/0816.cpp b/Problems/0816.cpp

@@ -0,0 +1,42 @@

class Solution {
static bool valid(const string &s) {
const int n = size(s);
if (n == 1) return true;
if (s[0] == '0' && s[1] != '.') return false;
for (int i = 0; i < n; i++) {
if (s[i] == '.') return s[n - 1] != '0';
}
return true;
}
const vector<string> devide(const string &s) const {
const int n = size(s);
vector<string> res;
if (valid(s)) res.push_back(s);
string left(1, s[0]);
for (int i = 1; i < n; i++) {
const string crnt = left + '.' + s.substr(i, n - i);
if (valid(crnt)) res.push_back(crnt);
left += s[i];
}
return res;
}
public:
vector<string> ambiguousCoordinates(const string &s) const {
const int n = size(s) - 2;
vector<string> res;
string left;
for (int i = 1; i < n; i++) {
left += s[i];
for (const auto &a : devide(left)) {
for (const auto &b : devide(s.substr(i + 1, n - i))) {
res.push_back("(" + a + ", " + b + ")");
}
}
}
return res;
}
};

diff --git a/Problems/1239.cpp b/Problems/1239.cpp

@@ -0,0 +1,24 @@

class Solution {
public:
int maxLength(const vector<string> &arr) const {
typedef bitset<27> bs;
vector<bs> vec(1, 0);
int res = 0;
for (const auto &s : arr) {
const int n = size(s);
bs crnt;
for (const char c : s)
crnt.set(c & 0x1F);
if (crnt.count() != n) continue;
for (int i = size(vec) - 1; i >= 0; i--) {
const auto &prev = vec[i];
if ((prev & crnt).any()) continue;
res = max(res, (int)prev.count() + n);
vec.push_back(prev | crnt);
}
}
return res;
}
};

diff --git a/Problems/1461.cpp b/Problems/1461.cpp

@@ -0,0 +1,24 @@

class Solution {
public:
bool hasAllCodes(const string &s, const int k) const {
static int seen[1 << 20];
if (size(s) < (1 << k) + k - 1) return false;
int crnt = 0;
for (int i = 0; i < k; i++) {
crnt = (crnt << 1) | (s[i] & 1);
}
const int mask = (1 << k) - 1;
int res = 0;
memset(seen, 0x00, sizeof(seen));
for (int i = k; i < size(s); i++) {
if (!seen[crnt]) seen[crnt] = true, res++;
crnt = ((crnt << 1) | (s[i] & 1)) & mask;
}
if (!seen[crnt]) seen[crnt] = true, res++;
return res == (1 << k);
}
};

diff --git a/README.md b/README.md

@@ -473,6 +473,7 @@ for solving problems.

| 0811 | Medium | [Subdomain Visit Count](Problems/0811.cpp) |
| 0814 | Medium | [Binary Tree Pruning](Problems/0814.cpp) |
| 0815 | Hard | [Bus Routes](Problems/0815.cpp) |
| 0816 | Medium | [Ambiguous Coordinates](Problems/0816.cpp) |
| 0817 | Medium | [Linked List Components](Problems/0817.cpp) |
| 0820 | Medium | [Short Encoding of Words](Problems/0820.cpp) |
| 0823 | Medium | [Binary Trees With Factors](Problems/0823.cpp) |

@@ -646,6 +647,7 @@ for solving problems.

| 1235 | Hard | [Maximum Profit in Job Scheduling](Problems/1235.cpp) |
| 1237 | Medium | [Find Positive Integer Solution for a Given Equation](Problems/1237.cpp) |
| 1238 | Medium | [Circular Permutation in Binary Representation](Problems/1238.cpp) |
| 1239 | Medium | [Maximum Length of a Concatenated String with Unique Characters](Problems/1239.cpp) |
| 1247 | Medium | [Minimum Swaps to Make Strings Equal](Problems/1247.cpp) |
| 1248 | Medium | [Count Number of Nice Subarrays](Problems/1248.cpp) |
| 1249 | Medium | [Minimum Remove to Make Valid Parentheses](Problems/1249.cpp) |

@@ -747,6 +749,7 @@ for solving problems.

| 1456 | Medium | [Maximum Number of Vowels in a Substring of Given Length](Problems/1456.cpp) |
| 1457 | Medium | [Pseudo-Palindromic Paths in a Binary Tree](Problems/1457.cpp) |
| 1458 | Hard | [Max Dot Product of Two Subsequences](Problems/1458.cpp) |
| 1461 | Medium | [Check If a String Contains All Binary Codes of Size K](Problems/1461.cpp) |
| 1462 | Medium | [Course Schedule IV](Problems/1462.cpp) |
| 1464 | Easy | [Maximum Product of Two Elements in an Array](Problems/1464.cpp) |
| 1466 | Medium | [Reorder Routes to Make All Paths Lead to the City Zero](Problems/1466.cpp) |