commit e5acd3a1f703f9796029c62d754d875c27b92ae1
parent cb02c694ef6ee3085b85a51774b0cf95cc39504c
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Wed, 23 Aug 2023 15:53:56 +0200
Daily Problem and 5 Random Problems
Diffstat:
7 files changed, 151 insertions(+), 0 deletions(-)
diff --git a/Problems/0419.cpp b/Problems/0419.cpp
@@ -0,0 +1,15 @@
+class Solution {
+public:
+ int countBattleships(const vector<vector<char>> &board) {
+ int res = 0;
+ for (int i = 0; i < board.size(); i++) {
+ for (int j = 0; j < board[0].size(); j++) {
+ if (board[i][j] == '.') continue;
+ if (i > 0 && board[i - 1][j] == 'X') continue;
+ if (j > 0 && board[i][j - 1] == 'X') continue;
+ res++;
+ }
+ }
+ return res;
+ }
+};
diff --git a/Problems/0767.cpp b/Problems/0767.cpp
@@ -0,0 +1,32 @@
+class Solution {
+ typedef pair<int, char> pic;
+
+public:
+ string reorganizeString(const string &s) {
+ priority_queue<pic> pq;
+ int count[27] = {0};
+ string res;
+
+ for (char c : s) count[c & 0x1F]++;
+ for (int i = 1; i <= 26; i++)
+ if (count[i] > 0) pq.push({count[i], 'a' + i - 1});
+
+ while (!pq.empty()) {
+ const auto [cnt, c] = pq.top();
+ pq.pop();
+ if (pq.empty()) {
+ if (cnt == 1)
+ return res + c;
+ else
+ return "";
+ } else {
+ const auto [ocnt, oc] = pq.top();
+ pq.pop();
+ res += c, res += oc;
+ if (cnt - 1) pq.push({cnt - 1, c});
+ if (ocnt - 1) pq.push({ocnt - 1, oc});
+ }
+ }
+ return res;
+ }
+};
diff --git a/Problems/0861.cpp b/Problems/0861.cpp
@@ -0,0 +1,20 @@
+class Solution {
+public:
+ int matrixScore(const vector<vector<int>> &grid) {
+ int n = grid.size(), m = grid[0].size();
+ unordered_set<int> flipped;
+ for (int i = 0; i < n; i++) {
+ if (grid[i][0]) continue;
+ flipped.insert(i);
+ }
+
+ int res = n * (1 << m - 1);
+ for (int j = 1; j < m; j++) {
+ int count = 0;
+ for (int i = 0; i < n; i++)
+ count += flipped.count(i) ? !grid[i][j] : grid[i][j];
+ res += max(count, n - count) * (1 << m - j - 1);
+ }
+ return res;
+ }
+};
diff --git a/Problems/1277.cpp b/Problems/1277.cpp
@@ -0,0 +1,29 @@
+class Solution {
+public:
+ int countSquares(const vector<vector<int>> &matrix) {
+ int n = matrix.size(), m = matrix[0].size();
+ vector<vector<int>> count(n + 1, vector<int>(m + 1));
+
+ for (int i = 1; i <= n; i++) {
+ for (int j = 1; j <= m; j++) {
+ count[i][j] = matrix[i - 1][j - 1] + count[i - 1][j] + count[i][j - 1] -
+ count[i - 1][j - 1];
+ }
+ }
+
+ int res = 0;
+ for (int i = 1; i <= n; i++) {
+ for (int j = 1; j <= m; j++) {
+ int x = i, y = j;
+ for (int k = 1, x = i, y = j; x <= n && y <= m; x++, y++, k++) {
+ int sum = count[x][y] - count[i - 1][y] - count[x][j - 1] +
+ count[i - 1][j - 1];
+ if (sum != k * k) break;
+ res++;
+ }
+ }
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/2375.cpp b/Problems/2375.cpp
@@ -0,0 +1,35 @@
+class Solution {
+ string crnt = string(9, '#');
+
+ int rec(const string &pattern, uint mask = 0, uint idx = 0) {
+ if (idx == pattern.size() + 1) return 1;
+
+ int start, end;
+ if (!idx) {
+ start = 1;
+ end = 9;
+ } else {
+ if (pattern[idx - 1] == 'I') {
+ start = (crnt[idx - 1] & 0xF) + 1;
+ end = 9;
+ } else {
+ start = 1;
+ end = (crnt[idx - 1] & 0xF) - 1;
+ }
+ }
+
+ for (int i = start; i <= end; i++) {
+ if (mask & (1 << i)) continue;
+ crnt[idx] = '0' + i;
+ if (rec(pattern, mask | (1 << i), idx + 1)) return 1;
+ }
+ return 0;
+ }
+
+public:
+ string smallestNumber(const string &pattern) {
+ crnt.resize(pattern.size() + 1);
+ rec(pattern);
+ return crnt;
+ }
+};
diff --git a/Problems/2428.cpp b/Problems/2428.cpp
@@ -0,0 +1,14 @@
+class Solution {
+public:
+ int maxSum(const vector<vector<int>> &grid) {
+ int m = grid.size(), n = grid[0].size(), res = 0;
+ for (int i = 0; i < m - 2; ++i) {
+ for (int j = 0; j < n - 2; ++j)
+ res =
+ max(res, grid[i + 0][j] + grid[i + 0][j + 1] + grid[i + 0][j + 2] +
+ grid[i + 1][j + 1] + grid[i + 2][j] +
+ grid[i + 2][j + 1] + grid[i + 2][j + 2]);
+ }
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -273,6 +273,7 @@ for solving problems.
| 0415 | Easy | [Add Strings](Problems/0415.cpp) |
| 0416 | Medium | [Partition Equal Subset Sum](Problems/0416.cpp) |
| 0417 | Medium | [Pacific Atlantic Water Flow](Problems/0417.cpp) |
+| 0419 | Medium | [Battleships in a Board](Problems/0419.cpp) |
| 0424 | Medium | [Longest Repeating Character Replacement](Problems/0424.cpp) |
| 0427 | Medium | [Construct Quad Tree](Problems/0427.cpp) |
| 0429 | Medium | [N-ary Tree Level Order Traversal](Problems/0429.cpp) |
@@ -362,6 +363,7 @@ for solving problems.
| 0747 | Easy | [Largest Number At Least Twice of Others](Problems/0747.cpp) |
| 0752 | Medium | [Open the Lock](Problems/0752.cpp) |
| 0763 | Medium | [Partition Labels](Problems/0763.cpp) |
+| 0767 | Medium | [Reorganize String](Problems/0767.cpp) |
| 0783 | Easy | [Minimum Distance Between BST Nodes](Problems/0783.cpp) |
| 0784 | Medium | [Letter Case Permutation](Problems/0784.cpp) |
| 0785 | Medium | [Is Graph Bipartite?](Problems/0785.cpp) |
@@ -381,6 +383,7 @@ for solving problems.
| 0852 | Medium | [Peak Index in a Mountain Array](Problems/0852.cpp) |
| 0853 | Medium | [Car Fleet](Problems/0853.cpp) |
| 0859 | Easy | [Buddy Strings](Problems/0859.cpp) |
+| 0861 | Medium | [Score After Flipping Matrix](Problems/0861.cpp) |
| 0863 | Medium | [All Nodes Distance K in Binary Tree](Problems/0863.cpp) |
| 0864 | Hard | [Shortest Path to Get All Keys](Problems/0864.cpp) |
| 0872 | Easy | [Leaf-Similar Trees](Problems/0872.cpp) |
@@ -467,6 +470,7 @@ for solving problems.
| 1249 | Medium | [Minimum Remove to Make Valid Parentheses](Problems/1249.cpp) |
| 1254 | Medium | [Number of Closed Islands](Problems/1254.cpp) |
| 1261 | Medium | [Find Elements in a Contaminated Binary Tree](Problems/1261.cpp) |
+| 1277 | Medium | [Count Square Submatrices with All Ones](Problems/1277.cpp) |
| 1282 | Medium | [Group the People Given the Group Size They Belong To](Problems/1282.cpp) |
| 1290 | Easy | [Convert Binary Number in a Linked List to Integer](Problems/1290.cpp) |
| 1302 | Medium | [Deepest Leaves Sum](Problems/1302.cpp) |
@@ -633,12 +637,14 @@ for solving problems.
| 2368 | Medium | [Reachable Nodes With Restrictions](Problems/2368.cpp) |
| 2369 | Medium | [Check if There is a Valid Partition For The Array](Problems/2369.cpp) |
| 2374 | Medium | [Node With Highest Edge Score](Problems/2374.cpp) |
+| 2375 | Medium | [Construct Smallest Number From DI String](Problems/2375.cpp) |
| 2390 | Medium | [Removing Stars From a String](Problems/2390.cpp) |
| 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) |
| 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) |
| 2433 | Medium | [Find The Original Array of Prefix Xor](Problems/2433.cpp) |
| 2439 | Medium | [Minimize Maximum of Array](Problems/2439.cpp) |
| 2442 | Medium | [Count Number of Distinct Integers After Reverse Operations](Problems/2442.cpp) |
