leetcode

Solution to some Leetcode problems written in C++

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

commit	9fe29dc153950a30adae9baca066f11ac2bac0b4
parent	94271d7e360bf8d7acb91178c5096d79b67b6a9f
author	Dimitrije Dobrota <mail@dimitrijedobrota.com>
date	Mon, 18 Sep 2023 10:58:52 +0000

5 Random Problems

Diffstat:

A	Problems/0835.cpp	\|	+++++++++++++++++++++++
A	Problems/1219.cpp	\|	++++++++++++++++++++++++++++++
A	Problems/1451.cpp	\|	+++++++++++++++++++++++++++++
A	Problems/1558.cpp	\|	+++++++++++++
A	Problems/2155.cpp	\|	+++++++++++++++++++
M	README.md	\|	+++++

6 files changed, 119 insertions(+), 0 deletions(-)

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

@@ -0,0 +1,23 @@

class Solution {

public:

int largestOverlap(const vector<vector<int>> &img1, const vector<vector<int>> &img2) {

const int n = img1.size();

vector<int> one, two;

unordered_map<int, int> count;

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

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

if (img1[i][j]) one.push_back(i * 100 + j);

if (img2[i][j]) two.push_back(i * 100 + j);

}

for (int i : one)

for (int j : two)

count[i - j]++;

int res = 0;

for (auto it : count)

res = max(res, it.second);

return res;

}

};

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

@@ -0,0 +1,30 @@

class Solution {

int n, m;

bool valid(const int x, const int y) { return x >= 0 && x < n && y >= 0 && y < m; }

int dfs(vector<vector<int>> &grid, const int x, const int y) {

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

int res = 0;

grid[x][y] = -grid[x][y];

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

const int i = x + dir[k + 1];

const int j = y + dir[k];

if (!valid(i, j) || grid[i][j] <= 0) continue;

res = max(res, dfs(grid, i, j));

}

grid[x][y] = -grid[x][y];

return grid[x][y] + res;

}

public:

int getMaximumGold(vector<vector<int>> &grid) {

n = grid.size(), m = grid[0].size();

int res = 0;

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

for (int j = 0; j < m; j++)

res = max(res, dfs(grid, i, j));

}

return res;

}

};

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

@@ -0,0 +1,29 @@

#pragma GCC optimize("fast")

static auto _ = []() {

ios_base::sync_with_stdio(false);

cin.tie(nullptr);

cout.tie(nullptr);

return 0;

}();

class Solution {

public:

string arrangeWords(string &text) {

map<int, vector<string>> um;

string word, res;

text[0] = tolower(text[0]);

stringstream ss(text);

while (ss >> word)

um[word.size()].push_back(word);

res.reserve(text.size());

for (const auto &[_, v] : um) {

for (const auto &w : v)

res += w + " ";

}

res[0] = toupper(res[0]);

res.pop_back();

return res;

}

};

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

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

class Solution {

static constexpr const int size = sizeof(int) * 8 - 1;

public:

int minOperations(const vector<int> &nums) {

int mini = INT_MAX, res = 0;

for (const int n : nums) {

if (n) mini = min(mini, __builtin_clz(n));

res += __builtin_popcount(n);

}

return max(0, res + size - mini);

}

};

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

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

class Solution {

public:

vector<int> maxScoreIndices(const vector<int> &nums) {

int score = accumulate(begin(nums), end(nums), 0);

vector<int> res = {0};

for (int i = 0, maxi = score; i < nums.size(); i++) {

score += (nums[i] == 0) ? 1 : -1;

if (score < maxi) continue;

if (score > maxi) {

res.clear();

maxi = score;

}

res.push_back(i + 1);

}

return res;

}

};

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

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

| 0814 | Medium | [Binary Tree Pruning](Problems/0814.cpp) |

| 0815 | Hard | [Bus Routes](Problems/0815.cpp) |

| 0830 | Medium | [Kth Smallest Element in a BST](Problems/0230.cpp) |

| 0835 | Medium | [Image Overlap](Problems/0835.cpp) |

| 0837 | Medium | [New 21 Game](Problems/0837.cpp) |

| 0839 | Hard | [Similar String Groups](Problems/0839.cpp) |

| 0841 | Medium | [Keys and Rooms](Problems/0841.cpp) |

@@ -507,6 +508,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) |

| 1219 | Medium | [Path with Maximum Gold](Problems/1219.cpp) |

| 1222 | Medium | [Queens That Can Attack the King](Problems/1222.cpp) |

| 1227 | Medium | [Airplane Seat Assignment Probability](Problems/1227.cpp) |

| 1232 | Easy | [Check If It Is a Straight Line](Problems/1232.cpp) |

@@ -578,6 +580,7 @@ for solving problems.

| 1444 | Hard | [Number of Ways of Cutting a Pizza](Problems/1444.cpp) |

| 1447 | Medium | [Simplified Fractions](Problems/1447.cpp) |

| 1448 | Medium | [Count Good Nodes in Binary Tree](Problems/1448.cpp) |

| 1451 | Medium | [Rearrange Words in a Sentence](Problems/1451.cpp) |

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

| 1462 | Medium | [Course Schedule IV](Problems/1462.cpp) |

@@ -602,6 +605,7 @@ for solving problems.

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

| 1551 | Medium | [Minimum Operations to Make Array Equal](Problems/1551.cpp) |

| 1557 | Medium | [Minimum Number of Vertices to Reach All Nodes](Problems/1557.cpp) |

| 1558 | Medium | [Minimum Numbers of Function Calls to Make Target Array](Problems/1558.cpp) |

| 1561 | Medium | [Maximum Number of Coins You Can Get](Problems/1561.cpp) |

| 1567 | Medium | [Maximum Length of Subarray With Positive Product](Problems/1567.cpp) |

| 1569 | Hard | [Number of Ways to Reorder Array to Get Same BST](Problems/1569.cpp) |

@@ -697,6 +701,7 @@ for solving problems.

| 2140 | Medium | [Solving Questions With Brainpower](Problems/2140.cpp) |

| 2141 | Hard | [Maximum Running Time of N Computers](Problems/2141.cpp) |

| 2149 | Medium | [Rearrange Array Elements by Sign](Problems/2149.cpp) |

| 2155 | Medium | [All Divisions With the Highest Score of a Binary Array](Problems/2155.cpp) |

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