leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

commit	83959563e1f1525d34518c7624f3caa174db4d15
parent	26ce085c68cca11fcf52797756a1e2bbf48a98b6
author	Dimitrije Dobrota <mail@dimitrijedobrota.com>
date	Tue, 26 Sep 2023 18:28:38 +0000

Daily Problem and 5 Random Problems

Diffstat:

A	Problems/0316.cpp	\|	+++++++++++++++++++
A	Problems/1081.cpp	\|	+++++++++++++++++++
A	Problems/1090.cpp	\|	+++++++++++++++++++++
A	Problems/1530.cpp	\|	+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A	Problems/1947.cpp	\|	+++++++++++++++++++++++++++
A	Problems/2410.cpp	\|	++++++++++++
M	README.md	\|	++++++

7 files changed, 169 insertions(+), 0 deletions(-)

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

@@ -0,0 +1,19 @@

class Solution {

public:

string removeDuplicateLetters(string s) {

uint16_t last[128] = {0}, seen[128] = {0};

string res = "";

for (int i = 0; i < s.size(); i++)

last[s[i]] = i;

for (int i = 0; i < s.size(); i++) {

if (seen[s[i]]++) continue;

while (!res.empty() && res.back() > s[i] && i < last[res.back()]) {

seen[res.back()] = 0;

res.pop_back();

}

res.push_back(s[i]);

}

return res;

}

};

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

@@ -0,0 +1,19 @@

class Solution {

public:

string smallestSubsequence(const string &s) {

uint16_t last[128] = {0}, seen[128] = {0};

string res = "";

for (int i = 0; i < s.size(); i++)

last[s[i]] = i;

for (int i = 0; i < s.size(); i++) {

if (seen[s[i]]++) continue;

while (!res.empty() && res.back() > s[i] && i < last[res.back()]) {

seen[res.back()] = 0;

res.pop_back();

}

res.push_back(s[i]);

}

return res;

}

};

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

@@ -0,0 +1,21 @@

class Solution {

public:

int largestValsFromLabels(const vector<int> &values, const vector<int> &labels, int numWanted,

int useLimit) {

static int count[20001], idx[20001];

memset(count, 0x00, sizeof(count));

const int n = values.size();

iota(begin(idx), begin(idx) + n, 0);

sort(begin(idx), begin(idx) + n, [&](int a, int b) { return values[a] > values[b]; });

int res = 0;

for (const int i : idx) {

if (count[labels[i]] >= useLimit) continue;

res += values[i];

if (!--numWanted) break;

count[labels[i]]++;

}

return res;

}

};

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

@@ -0,0 +1,65 @@

// Recursive

class Solution {

public:

int countPairs(TreeNode *root, int distance) {

unordered_map<TreeNode *, vector<int>> um;

stack<TreeNode *> st;

int res = 0;

st.push(root);

while (!st.empty()) {

TreeNode *root = st.top();

if (root) {

st.push(nullptr);

if (!root->left && !root->right)

um[root].push_back(1);

else {

if (root->left) st.push(root->left);

if (root->right) st.push(root->right);

}

continue;

}

st.pop();

root = st.top();

st.pop();

for (const int n : um[root->right])

um[root].push_back(n + 1);

for (const int a : um[root->left]) {

um[root].push_back(a + 1);

for (const int b : um[root->right])

if (a + b <= distance) res++;

}

return res;

}

};

// Iterative

class Solution {

int res = 0;

vector<int> rec(TreeNode *root, int distance) {

if (!root->left && !root->right) return {1};

vector<int> left, right, sum;

if (root->left) left = rec(root->left, distance);

if (root->right) right = rec(root->right, distance);

sum.reserve(left.size() + right.size());

for (const int b : right)

sum.push_back(b + 1);

for (const int a : left) {

sum.push_back(a + 1);

for (const int b : right) {

res += (a + b <= distance);

}

return sum;

}

public:

int countPairs(TreeNode *root, int distance) {

rec(root, distance);

return res;

}

};

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

@@ -0,0 +1,27 @@

class Solution {

public:

int maxCompatibilitySum(vector<vector<int>> &students, vector<vector<int>> &mentors) {

const int n = students.size(), m = students[0].size();

uint16_t student[9] = {0}, mentor[9] = {0};

for (uint8_t i = 0; i < n; i++) {

for (const int n : students[i])

student[i] = (student[i] | n) << 1;

for (const int n : mentors[i])

mentor[i] = (mentor[i] | n) << 1;

}

uint8_t res = 0;

vector<uint8_t> idx(n);

iota(begin(idx), end(idx), 0);

do {

uint8_t count = 0;

for (uint8_t i = 0; i < n; i++) {

count += m - __builtin_popcount(student[i] ^ mentor[idx[i]]);

}

res = max(res, count);

} while (next_permutation(begin(idx), end(idx)));

return res;

}

};

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

@@ -0,0 +1,12 @@

class Solution {

public:

int matchPlayersAndTrainers(vector<int> &players, vector<int> &trainers) {

sort(begin(players), end(players));

sort(begin(trainers), end(trainers));

int res = 0;

for (int i = 0; res < players.size() && i < trainers.size(); i++)

res += trainers[i] >= players[res];

return res;

}

};

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

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

| 0306 | Medium | [Additive Number](Problems/0306.cpp) |

| 0309 | Medium | [Best Time to Buy and Sell Stock with Cooldown](Problems/0309.cpp) |

| 0310 | Medium | [Minimum Height Trees](Problems/0310.cpp) |

| 0316 | Medium | [Remove Duplicate Letters](Problems/0316.cpp) |

| 0319 | Medium | [Bulb Switcher](Problems/0319.cpp) |

| 0322 | Medium | [Coin Change](Problems/0322.cpp) |

| 0326 | Easy | [Power of Three](Problems/0326.cpp) |

@@ -502,7 +503,9 @@ for solving problems.

| 1071 | Easy | [Greatest Common Divisor of Strings](Problems/1071.cpp) |

| 1072 | Medium | [Flip Columns For Maximum Number of Equal Rows](Problems/1072.cpp) |

| 1079 | Medium | [Letter Tile Possibilities](Problems/1079.cpp) |

| 1081 | Medium | [Smallest Subsequence of Distinct Characters](Problems/1081.cpp) |

| 1089 | Easy | [Duplicate Zeros](Problems/1089.cpp) |

| 1090 | Medium | [Largest Values From Labels](Problems/1090.cpp) |

| 1091 | Medium | [Shortest Path in Binary Matrix](Problems/1091.cpp) |

| 1095 | Easy | [Find Numbers with Even Number of Digits](Problems/1095.cpp) |

| 1099 | Easy | [Replace Elements with Greatest Element on Right Side](Problems/1099.cpp) |

@@ -625,6 +628,7 @@ for solving problems.

| 1523 | Easy | [Count Odd Numbers in an Interval Range](Problems/1523.cpp) |

| 1525 | Medium | [Number of Good Ways to Split a String](Problems/1525.cpp) |

| 1529 | Medium | [Minimum Suffix Flips](Problems/1529.cpp) |

| 1530 | Medium | [Number of Good Leaf Nodes Pairs](Problems/1530.cpp) |

| 1539 | Easy | [Kth Missing Positive Number](Problems/1539.cpp) |

| 1544 | Easy | [Make The String Great](Problems/1544.cpp) |

| 1547 | Hard | [Minimum Cost to Cut a Stick](Problems/1547.cpp) |

@@ -709,6 +713,7 @@ for solving problems.

| 1905 | Medium | [Count Sub Islands](Problems/1905.cpp) |

| 1910 | Medium | [Remove All Occurrences of a Substring](Problems/1910.cpp) |

| 1926 | Medium | [Nearest Exit from Entrance in Maze](Problems/1926.cpp) |

| 1947 | Medium | [Maximum Compatibility Score Sum](Problems/1947.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) |

@@ -786,6 +791,7 @@ for solving problems.

| 2391 | Medium | [Minimum Amount of Time to Collect Garbage](Problems/2391.cpp) |

| 2396 | Medium | [Strictly Palindromic Number](Problems/2396.cpp) |

| 2405 | Medium | [Optimal Partition of String](Problems/2405.cpp) |

| 2410 | Medium | [Maximum Matching of Players With Trainers](Problems/2410.cpp) |

| 2415 | Medium | [Reverse Odd Levels of Binary Tree](Problems/2415.cpp) |

| 2421 | Medium | [Number of Good Paths](Problems/2421.cpp) |

| 2428 | Medium | [Maximum Sum of an Hourglass](Problems/2428.cpp) |