leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE |
commitb3c2f19e8a0012b83880da750f75021cbf36bc3c
parent0370016abe1a5256cf42af36524c0c0ce2724aa9
authorDimitrije Dobrota <mail@dimitrijedobrota.com>
dateMon, 22 Jan 2024 18:19:47 +0000

Daily Problem and 5 Random Problems

Diffstat:
AProblems/0453.cpp|+++++++++
AProblems/0645.cpp|++++++++++++++
MProblems/0846.cpp|++++++++++++----------------------------------------------
AProblems/1283.cpp|++++++++++++++++
AProblems/1288.cpp|+++++++++++++++++
AProblems/1296.cpp|++++++++++++++++++
MREADME.md|++++++

7 files changed, 92 insertions(+), 46 deletions(-)

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

@@ -0,0 +1,9 @@

class Solution {
public:
int minMoves(const vector<int> &nums) const {
const int n = size(nums);
const int sum = accumulate(begin(nums), end(nums), 0);
const int mini = *min_element(begin(nums), end(nums));
return sum - mini * n;
}
};

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

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

class Solution {
public:
vector<int> findErrorNums(vector<int> &nums) const {
const int n = size(nums);
int dbl = 0, sum = 0;
for (int i = 0; i < n; i++) {
const int num = abs(nums[i]);
if (nums[num - 1] < 0) dbl = num;
nums[num - 1] = -nums[num - 1];
sum += num;
}
return {dbl, n * (n + 1) / 2 - (sum - dbl)};
}
};

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

@@ -1,52 +1,18 @@

class Solution {
typedef tuple<int, int, char> record;
int cantor(int a, int b) { return (a + b + 1) * (a + b) / 2 + b; }
int hash(const record &r) { return cantor(get<0>(r), cantor(get<1>(r), get<2>(r))); }
int n, m;
int valid(int x, int y) { return x >= 0 && y >= 0 && x < n && y < m; }
public:
int shortestPathAllKeys(const vector<string> &grid) {
static const int offset_x[] = {0, 0, 1, -1};
static const int offset_y[] = {1, -1, 0, 0};
n = grid.size(), m = grid[0].size();
int start_x = -1, start_y = -1, goal = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '@')
start_x = i, start_y = j;
else if (islower(grid[i][j]))
goal |= 1 << (grid[i][j] & 0xF);
bool isNStraightHand(const vector<int> &hand, const int groupSize) const {
map<int, int> um;
for (const int num : hand)
um[num]++;
for (auto start = begin(um); start != end(um); start++) {
const auto [crnt, step] = *start;
if (!step) continue;
for (int goal = crnt; goal < crnt + groupSize; goal++) {
auto it = um.find(goal);
if (it == end(um) || it->second < step) return false;
it->second -= step;
}
}
unordered_set<int> visited;
queue<record> q;
q.push({start_x, start_y, 0});
visited.insert(hash(q.front()));
for (int step = 0; !q.empty(); step++) {
for (int k = q.size(); k > 0; k--) {
auto [x, y, keys] = q.front();
q.pop();
if (keys == goal) return step;
for (int k = 0; k < 4; k++) {
int i = x + offset_x[k], j = y + offset_y[k], key = keys;
if (!valid(i, j) || grid[i][j] == '#') continue;
if (isupper(grid[i][j]) && !(key & (1 << (grid[i][j] & 0xF)))) continue;
if (islower(grid[i][j])) key |= 1 << (grid[i][j] & 0xF);
const record r = {i, j, key};
if (!visited.count(hash(r))) {
visited.insert(hash(r));
q.push(r);
}
}
}
}
return -1;
return true;
}
};

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

@@ -0,0 +1,16 @@

class Solution {
public:
int smallestDivisor(const vector<int> &nums, int threshold) const {
int left = 1, right = 1000000;
while (left < right) {
int mid = left + (right - left) / 2, sum = 0;
for (const int num : nums)
sum += (num + mid - 1) / mid;
if (sum > threshold)
left = mid + 1;
else
right = mid;
}
return left;
}
};

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

@@ -0,0 +1,17 @@

class Solution {
public:
int removeCoveredIntervals(vector<vector<int>> &intervals) const {
const int n = size(intervals);
sort(begin(intervals), end(intervals),
[](const auto &a, const auto &b) { return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1]; });
int res = 0, right = 0;
for (int i = 0; i < n; i++) {
if (intervals[i][1] <= right) continue;
right = intervals[i][1];
res++;
}
return res;
}
};

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

@@ -0,0 +1,18 @@

class Solution {
public:
bool isPossibleDivide(const vector<int> &nums, const int k) const {
map<int, int> um;
for (const int num : nums)
um[num]++;
for (auto start = begin(um); start != end(um); start++) {
const auto [crnt, step] = *start;
if (!step) continue;
for (int goal = crnt; goal < crnt + k; goal++) {
auto it = um.find(goal);
if (it == end(um) || it->second < step) return false;
it->second -= step;
}
}
return true;
}
};

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

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

| 0450 | Medium | [Delete Node in a BST](Problems/0450.cpp) |
| 0451 | Medium | [Sort Characters By Frequency](Problems/0451.cpp) |
| 0452 | Medium | [Minimum Number of Arrows to Burst Balloons](Problems/0452.cpp) |
| 0453 | Medium | [Minimum Moves to Equal Array Elements](Problems/0453.cpp) |
| 0454 | Medium | [4Sum II](Problems/0454.cpp) |
| 0455 | Easy | [Assign Cookies](Problems/0455.cpp) |
| 0456 | Medium | [132 Pattern](Problems/0456.cpp) |

@@ -408,6 +409,7 @@ for solving problems.

| 0637 | Easy | [Average of Levels in Binary Tree](Problems/0637.cpp) |
| 0641 | Medium | [Design Circular Deque](Problems/0641.cpp) |
| 0643 | Easy | [Maximum Average Subarray I](Problems/0643.cpp) |
| 0645 | Easy | [Set Mismatch](Problems/0645.cpp) |
| 0646 | Medium | [Maximum Length of Pair Chain](Problems/0646.cpp) |
| 0647 | Medium | [Palindromic Substrings](Problems/0647.cpp) |
| 0648 | Medium | [Replace Words](Problems/0648.cpp) |

@@ -481,6 +483,7 @@ for solving problems.

| 0839 | Hard | [Similar String Groups](Problems/0839.cpp) |
| 0841 | Medium | [Keys and Rooms](Problems/0841.cpp) |
| 0844 | Easy | [Backspace String Compare](Problems/0844.cpp) |
| 0846 | Medium | [Hand of Straights](Problems/0846.cpp) |
| 0847 | Hard | [Shortest Path Visiting All Nodes](Problems/0847.cpp) |
| 0851 | Medium | [Loud and Rich](Problems/0851.cpp) |
| 0852 | Medium | [Peak Index in a Mountain Array](Problems/0852.cpp) |

@@ -656,10 +659,13 @@ for solving problems.

| 1277 | Medium | [Count Square Submatrices with All Ones](Problems/1277.cpp) |
| 1280 | Easy | [Students and Examinations](Problems/1280.cpp) |
| 1282 | Medium | [Group the People Given the Group Size They Belong To](Problems/1282.cpp) |
| 1283 | Medium | [Find the Smallest Divisor Given a Threshold](Problems/1283.cpp) |
| 1286 | Medium | [Iterator for Combination](Problems/1286.cpp) |
| 1287 | Easy | [Element Appearing More Than 25% In Sorted Array](Problems/1287.cpp) |
| 1288 | Medium | [Remove Covered Intervals](Problems/1288.cpp) |
| 1290 | Easy | [Convert Binary Number in a Linked List to Integer](Problems/1290.cpp) |
| 1291 | Medium | [Sequential Digits](Problems/1291.cpp) |
| 1296 | Medium | [Divide Array in Sets of K Consecutive Numbers](Problems/1296.cpp) |
| 1302 | Medium | [Deepest Leaves Sum](Problems/1302.cpp) |
| 1305 | Medium | [All Elements in Two Binary Search Trees](Problems/1305.cpp) |
| 1306 | Medium | [Jump Game III](Problems/1306.cpp) |