leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE |

commit728ba868cb3c59350689f3a9c5b48b62de44c1e2
parent3931c0cafe32664d0a12f032bf85812739bfa962
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateTue, 29 Aug 2023 10:16:53 +0200

Daily Problem and 5 Random Problems

Diffstat:
AProblems/1222.cpp|++++++++++++++++++++++++++
AProblems/1860.cpp|++++++++++++++
AProblems/1884.cpp|++++++++++++
AProblems/2186.cpp|+++++++++++++
AProblems/2483.cpp|+++++++++++++++
AProblems/2711.cpp|++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
MREADME.md|++++++

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


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

@@ -0,0 +1,26 @@

class Solution {
public:
vector<vector<int>> queensAttacktheKing(vector<vector<int>> &queens, vector<int> &king) {
static constexpr const int offset_x[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
static constexpr const int offset_y[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int hit[64] = {0};
vector<vector<int>> res;
for (const auto &queen : queens)
hit[queen[0] * 8 + queen[1]] = true;
for (int i = 0; i < 8; i++) {
int x = king[0] + offset_x[i], y = king[1] + offset_y[i];
while (x >= 0 && x < 8 && y >= 0 && y < 8) {
if (hit[x * 8 + y]) {
res.push_back({x, y});
break;
}
x += offset_x[i], y += offset_y[i];
}
}
return res;
}
};

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

@@ -0,0 +1,14 @@

class Solution {
public:
vector<int> memLeak(int memory1, int memory2) {
int time = 1;
while (time <= memory1 || time <= memory2) {
if (memory1 < memory2)
memory2 -= time;
else
memory1 -= time;
time++;
}
return {time, memory1, memory2};
}
};

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

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

class Solution {
int dp[1001] = {0};
public:
int twoEggDrop(int n) {
if (dp[n]) return dp[n];
int res = n;
for (int i = 1; i <= n; i++)
res = min(res, 1 + max(i - 1, twoEggDrop(n - i)));
return dp[n] = res;
}
};

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

@@ -0,0 +1,13 @@

class Solution {
public:
int minSteps(const string &s, const string &t) {
int count[27] = {0}, res = 0;
for (const char c : s)
count[c & 0x1F]++;
for (const char c : t)
count[c & 0x1F]--;
for (int i = 1; i <= 26; i++)
res += abs(count[i]);
return res;
}
};

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

@@ -0,0 +1,15 @@

class Solution {
public:
int bestClosingTime(string customers) {
int mini = 0, crnt = 0, res = 0;
for (int i = 0; i < customers.size(); i++) {
crnt += (customers[i] == 'Y') ? -1 : +1;
if (crnt >= mini) continue;
res = i + 1;
mini = crnt;
}
return res;
}
};

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

@@ -0,0 +1,64 @@

// Solution idea
class Solution {
public:
vector<vector<int>> differenceOfDistinctValues(vector<vector<int>> &grid) {
const int n = grid.size(), m = grid[0].size(), l = n - 1;
vector<unordered_set<int>> vus(m + n - 1);
vector<vector<int>> res(n, vector(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
res[i][j] = vus[j - i + l].size();
vus[j - i + l].insert(grid[i][j]);
}
}
for (int i = 0; i < m + n - 1; i++)
vus[i].clear();
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
res[i][j] = abs((int)(res[i][j] - vus[j - i + l].size()));
vus[j - i + l].insert(grid[i][j]);
}
}
return res;
}
};
// Optimized solution
class Solution {
public:
vector<vector<int>> differenceOfDistinctValues(vector<vector<int>> &grid) {
int vus[101][51] = {0}, count[101] = {0};
const int n = grid.size(), m = grid[0].size(), l = n - 1;
vector<vector<int>> res(n, vector(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
res[i][j] = count[j - i + l];
if (vus[j - i + l][grid[i][j]] != 1) {
vus[j - i + l][grid[i][j]] = 1;
count[j - i + l]++;
}
}
}
for (int i = 0; i < m + n - 1; i++)
count[i] = 0;
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
res[i][j] = abs(res[i][j] - count[j - i + l]);
if (vus[j - i + l][grid[i][j]] != 2) {
vus[j - i + l][grid[i][j]] = 2;
count[j - i + l]++;
}
}
}
return res;
}
};

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

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

| 1203 | Hard | [Sort Items by Groups Respecting Dependencies](Problems/1203.cpp) |
| 1209 | Medium | [Remove All Adjacent Duplicates in String II](Problems/1209.cpp) |
| 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) |
| 1249 | Medium | [Minimum Remove to Make Valid Parentheses](Problems/1249.cpp) |
| 1254 | Medium | [Number of Closed Islands](Problems/1254.cpp) |

@@ -595,8 +596,10 @@ for solving problems.

| 1833 | Medium | [Maximum Ice Cream Bars](Problems/1833.cpp) |
| 1834 | Medium | [Single-Threaded CPU](Problems/1834.cpp) |
| 1857 | Hard | [Largest Color Value in a Directed Graph](Problems/1857.cpp) |
| 1860 | Medium | [Incremental Memory Leak](Problems/1860.cpp) |
| 1870 | Medium | [Minimum Speed to Arrive on Time](Problems/1870.cpp) |
| 1877 | Medium | [Minimize Maximum Pair Sum in Array](Problems/1877.cpp) |
| 1884 | Medium | [Egg Drop With 2 Eggs and N Floors](Problems/1884.cpp) |
| 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) |

@@ -626,6 +629,7 @@ for solving problems.

| 2161 | Medium | [Partition Array According to Given Pivot](Problems/2161.cpp) |
| 2177 | Medium | [Find Three Consecutive Integers That Sum to a Given Number](Problems/2177.cpp) |
| 2181 | Medium | [Merge Nodes in Between Zeros](Problems/2181.cpp) |
| 2186 | Medium | [Minimum Number of Steps to Make Two Strings Anagram II](Problems/2186.cpp) |
| 2187 | Medium | [Minimum Time to Complete Trips](Problems/2187.cpp) |
| 2192 | Medium | [All Ancestors of a Node in a Directed Acyclic Graph](Problems/2192.cpp) |
| 2196 | Medium | [Create Binary Tree From Descriptions](Problems/2196.cpp) |

@@ -680,6 +684,7 @@ for solving problems.

| 2467 | Medium | [Most Profitable Path in a Tree](Problems/2467.cpp) |
| 2477 | Medium | [Minimum Fuel Cost to Report to the Capital](Problems/2477.cpp) |
| 2482 | Medium | [Difference Between Ones and Zeros in Row and Column](Problems/2482.cpp) |
| 2483 | Medium | [Minimum Penalty for a Shop](Problems/2483.cpp) |
| 2492 | Medium | [Minimum Score of a Path Between Two Cities](Problems/2492.cpp) |
| 2497 | Medium | [Maximum Star Sum of a Graph](Problems/2497.cpp) |
| 2542 | Medium | [Maximum Subsequence Score](Problems/2542.cpp) |

@@ -704,5 +709,6 @@ for solving problems.

| 2666 | Easy | [Allow One Function Call](Problems/2666.js) |
| 2667 | Easy | [Create Hello World Function](Problems/2667.js) |
| 2676 | Medium | [Throttle](Problems/2676.js) |
| 2711 | Medium | [Difference of Number of Distinct Values on Diagonals](Problems/2711.cpp) |
| 2785 | Medium | [Sort Vowels in a String](Problems/2785.cpp) |
| 2807 | Medium | [Insert Greatest Common Divisors in Linked List](Problems/2807.cpp) |