leetcode

Solution to some Leetcode problems written in C++

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

commit	2f18129279bd6ce294c359c5bde7929d1ef77865
parent	202a36afa7f6d9bc8f16cf5151a8fff4763c773c
author	Dimitrije Dobrota <mail@dimitrijedobrota.com>
date	Fri, 26 Jan 2024 20:23:59 +0000

Daily Problem and 5 Random Problems

Diffstat:

A	Problems/0576.cpp	\|	++++++++++++++++++++++++++
A	Problems/0788.cpp	\|	++++++++++++++++++++++++
A	Problems/1040.cpp	\|	+++++++++++++++++++++
A	Problems/1094.cpp	\|	+++++++++++++++++++
A	Problems/1481.cpp	\|	+++++++++++++++++++++
A	Problems/1593.cpp	\|	+++++++++++++++++++
M	README.md	\|	++++++

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

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

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

class Solution {

static const int MOD = 1E9 + 7;

static int dp[51][51][51];

public:

Solution() { memset(dp, 0xFF, sizeof(dp)); }

int findPaths(const int m, const int n, const int moves, const int row, const int col) const {

if (!moves) return 0;

if (dp[moves][row][col] != -1) return dp[moves][row][col];

int res = 0;

static int offset[] = {-1, 0, 1, 0, -1};

for (int k = 0; k < 4; k++) {

const int x = row + offset[k];

const int y = col + offset[k + 1];

if (x < 0 || y < 0 || x >= m || y >= n)

res++;

else

res = (res + findPaths(m, n, moves - 1, x, y)) % MOD;

}

return dp[moves][row][col] = res;

}

};

int Solution::dp[51][51][51];

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

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

class Solution {

typedef array<int, 10001> record;

static constexpr const record cache = []() constexpr {

record res = {0};

int cnt = 0;

for (int i = 1; i < size(res); i++) {

int crnt = i, mirror = 1;

do {

const int digit = crnt % 10;

if (digit == 3 || digit == 4 || digit == 7) {

mirror = 1;

break;

}

if (digit != 0 && digit != 1 && digit != 8) mirror = 0;

} while ((crnt /= 10) > 0);

if (!mirror) cnt++;

res[i] = cnt;

}

return res;

}();

public:

constexpr int rotatedDigits(int n) const { return cache[n]; }

};

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

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

class Solution {

public:

vector<int> numMovesStonesII(vector<int> &stones) const {

const int n = size(stones);

vector<int> res(2, n);

sort(begin(stones), end(stones));

int i = 0;

for (int j = 0; j < n; j++) {

while (stones[j] - stones[i] >= n)

i++;

if (j - i + 1 == n - 1 && stones[j] - stones[i] == n - 2)

res[0] = min(res[0], 2);

else

res[0] = min(res[0], n - (j - i + 1));

}

res[1] = 2 + max(stones[n - 2] - stones[0], stones[n - 1] - stones[1]) - n;

return res;

}

};

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

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

class Solution {

public:

bool carPooling(const vector<vector<int>> &trips, int capacity) const {

static int count[1001];

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

for (const auto &trip : trips) {

count[trip[1]] += trip[0];

count[trip[2]] -= trip[0];

}

for (int i = 0; i < 1001; i++) {

capacity -= count[i];

if (capacity < 0) return false;

}

return true;

}

};

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

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

class Solution {

public:

int findLeastNumOfUniqueInts(const vector<int> &arr, int k) const {

unordered_map<int, int> um;

for (const int n : arr)

um[n]++;

static int count[100001];

size_t sz = 0;

for (const auto [_, cnt] : um)

count[sz++] = cnt;

sort(begin(count), begin(count) + sz);

for (int i = 0; i < sz; i++) {

k -= count[i];

if (k < 0) return sz - i;

}

return 0;

}

};

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

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

class Solution {

unordered_set<string> seen;

public:

int maxUniqueSplit(const string &s, int idx = 0) {

if (idx == size(s)) return size(seen);

int res = 0;

string crnt;

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

auto it = seen.emplace(crnt += s[i]);

if (!it.second) continue;

res = max(res, maxUniqueSplit(s, i + 1));

seen.erase(it.first);

}

return res;

}

};

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

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

| 0567 | Medium | [Permutation in String](Problems/0567.cpp) |

| 0570 | Medium | [Managers with at Least 5 Direct Reports](Problems/0570.cpp) |

| 0572 | Easy | [Subtree of Another Tree](Problems/0572.cpp) |

| 0576 | Medium | [Out of Boundary Paths](Problems/0576.cpp) |

| 0577 | Easy | [Employee Bonus](Problems/0577.cpp) |

| 0583 | Medium | [Delete Operation for Two Strings](Problems/0583.cpp) |

| 0584 | Easy | [Find Customer Referee](Problems/0584.cpp) |

@@ -463,6 +464,7 @@ for solving problems.

| 0784 | Medium | [Letter Case Permutation](Problems/0784.cpp) |

| 0785 | Medium | [Is Graph Bipartite?](Problems/0785.cpp) |

| 0787 | Medium | [Cheapest Flights Within K Stops](Problems/0787.cpp) |

| 0788 | Medium | [Rotated Digits](Problems/0788.cpp) |

| 0789 | Medium | [Escape The Ghosts](Problems/0789.cpp) |

| 0790 | Medium | [Domino and Tromino Tiling](Problems/0790.cpp) |

| 0791 | Medium | [Custom Sort String](Problems/0791.cpp) |

@@ -582,6 +584,7 @@ for solving problems.

| 1035 | Medium | [Uncrossed Lines](Problems/1035.cpp) |

| 1038 | Medium | [Binary Search Tree to Greater Sum Tree](Problems/1038.cpp) |

| 1039 | Medium | [Minimum Score Triangulation of Polygon](Problems/1039.cpp) |

| 1040 | Medium | [Moving Stones Until Consecutive II](Problems/1040.cpp) |

| 1042 | Medium | [Flower Planting With No Adjacent](Problems/1042.cpp) |

| 1043 | Medium | [Partition Array for Maximum Sum](Problems/1043.cpp) |

| 1045 | Medium | [Customers Who Bought All Products](Problems/1045.cpp) |

@@ -603,6 +606,7 @@ for solving problems.

| 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) |

| 1094 | Medium | [Car Pooling](Problems/1094.cpp) |

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

| 1095 | Hard | [Find in Mountain Array](Problems/1095.cpp) |

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

@@ -760,6 +764,7 @@ for solving problems.

| 1472 | Medium | [Design Browser History ](Problems/1472.cpp) |

| 1476 | Medium | [Subrectangle Queries](Problems/1476.cpp) |

| 1480 | Easy | [Running Sum of 1d Array](Problems/1480.cpp) |

| 1481 | Medium | [Least Number of Unique Integers after K Removals](Problems/1481.cpp) |

| 1484 | Easy | [Group Sold Products By The Date](Problems/1484.cpp) |

| 1489 | Hard | [Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree](Problems/1489.cpp) |

| 1491 | Easy | [Average Salary Excluding the Minimum and Maximum Salary](Problems/1491.cpp) |

@@ -802,6 +807,7 @@ for solving problems.

| 1583 | Medium | [Count Unhappy Friends](Problems/1583.cpp) |

| 1584 | Medium | [Min Cost to Connect All Points](Problems/1584.cpp) |

| 1587 | Easy | [Bank Account Summary II](Problems/1587.cpp) |

| 1593 | Medium | [Split a String Into the Max Number of Unique Substrings](Problems/1593.cpp) |

| 1600 | Medium | [Throne Inheritance](Problems/1600.cpp) |

| 1601 | Hard | [Maximum Number of Achievable Transfer Requests](Problems/1601.cpp) |

| 1603 | Easy | [Design Parking System](Problems/1603.cpp) |