commit 558e36c9f9d0621987c3d3f94581c73f7234b0dc
parent 8337f9f03bc076414a6b3830dfd7d605e99a32a2
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Sat, 9 Sep 2023 21:52:53 +0200
5 Random Problems
Diffstat:
6 files changed, 154 insertions(+), 0 deletions(-)
diff --git a/Problems/0529.cpp b/Problems/0529.cpp
@@ -0,0 +1,41 @@
+class Solution {
+ public:
+ vector<vector<char>> updateBoard(vector<vector<char>> &board, const vector<int> &click) {
+ const int n = board.size(), m = board[0].size();
+
+ if (board[click[0]][click[1]] == 'M') {
+ board[click[0]][click[1]] = 'X';
+ return board;
+ }
+
+ if (board[click[0]][click[1]] != 'E') return board;
+
+ queue<pair<int, int>> q({{click[0], click[1]}});
+ while (!q.empty()) {
+ const auto [x, y] = q.front();
+ q.pop();
+ if (board[x][y] != 'E') continue;
+
+ int count = 0;
+ for (int i = max(x - 1, 0); i <= min(n - 1, x + 1); i++) {
+ for (int j = max(y - 1, 0); j <= min(m - 1, y + 1); j++) {
+ if (board[i][j] == 'M') count++;
+ }
+ }
+
+ if (count != 0) {
+ board[x][y] = '0' + count;
+ continue;
+ }
+
+ board[x][y] = 'B';
+ for (int i = max(x - 1, 0); i <= min(n - 1, x + 1); i++) {
+ for (int j = max(y - 1, 0); j <= min(m - 1, y + 1); j++) {
+ if (board[i][j] == 'E') q.push({i, j});
+ }
+ }
+ }
+
+ return board;
+ }
+};
diff --git a/Problems/0690.cpp b/Problems/0690.cpp
@@ -0,0 +1,32 @@
+/*
+// Definition for Employee.
+class Employee {
+public:
+ int id;
+ int importance;
+ vector<int> subordinates;
+};
+*/
+
+class Solution {
+ public:
+ int getImportance(const vector<Employee *> employees, int id) const {
+ static const Employee *um[2001];
+
+ memset(um, 0x00, sizeof(um));
+ for (const Employee *employee : employees)
+ um[employee->id] = employee;
+
+ int res = 0;
+ queue<int> q({id});
+ while (!q.empty()) {
+ int id = q.front();
+ q.pop();
+ res += um[id]->importance;
+ for (const int sub : um[id]->subordinates)
+ q.push(sub);
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/1190.cpp b/Problems/1190.cpp
@@ -0,0 +1,21 @@
+class Solution {
+ public:
+ string reverseParentheses(string s) const {
+ stack<int> st;
+ for (int i = 0; i < s.size(); i++) {
+ if (s[i] == '(')
+ st.push(i);
+ else if (s[i] == ')') {
+ reverse(begin(s) + st.top(), begin(s) + i);
+ st.pop();
+ }
+ }
+
+ int size = 0;
+ for (int i = 0; i < s.size(); i++)
+ if (s[i] != '(' && s[i] != ')') s[size++] = s[i];
+ s.resize(size);
+
+ return s;
+ }
+};
diff --git a/Problems/1861.cpp b/Problems/1861.cpp
@@ -0,0 +1,28 @@
+#pragma GCC optimize(fast);
+static auto _ = []() {
+ std::ios_base::sync_with_stdio(0);
+ std::cin.tie(0);
+ return 0;
+}();
+
+class Solution {
+ public:
+ vector<vector<char>> rotateTheBox(const vector<vector<char>> &box) const {
+ const int n = box.size(), m = box[0].size();
+ vector<vector<char>> res(m, vector(n, '.'));
+
+ for (int i = 0; i < n; i++) {
+ for (int j = m - 1, limit = m; j >= 0; j--) {
+ if (box[i][j] == '.') continue;
+ if (box[i][j] == '*') {
+ res[j][n - i - 1] = '*';
+ limit = j;
+ continue;
+ }
+ res[--limit][n - i - 1] = '#';
+ }
+ }
+
+ return res;
+ }
+};
diff --git a/Problems/2685.cpp b/Problems/2685.cpp
@@ -0,0 +1,27 @@
+class Solution {
+ public:
+ int countCompleteComponents(int n, const vector<vector<int>> &edges) {
+ static uint64_t con[50];
+
+ for (uint64_t i = 0; i < n; i++)
+ con[i] = 1ll << i;
+ for (const auto &edge : edges) {
+ con[edge[0]] |= 1ll << edge[1];
+ con[edge[1]] |= 1ll << edge[0];
+ }
+
+ int res = 0;
+ for (int i = 0; i < n; i++) {
+ if (!con[i]) continue;
+ for (uint64_t crnt = con[i] ^ (1ll << i), idx; crnt; crnt ^= 1ll << idx) {
+ idx = __builtin_ctzll(crnt);
+ if (con[idx] != con[i]) goto next;
+ con[idx] = 0;
+ }
+ res++;
+ next:;
+ }
+
+ return res;
+ }
+};
diff --git a/README.md b/README.md
@@ -311,6 +311,7 @@ for solving problems.
| 0516 | Medium | [Longest Palindromic Subsequence](Problems/0516.cpp) |
| 0518 | Medium | [Coin Change II](Problems/0518.cpp) |
| 0520 | Easy | [Detect Capital](Problems/0520.cpp) |
+| 0529 | Medium | [Minesweeper](Problems/0529.cpp) |
| 0530 | Easy | [Minimum Absolute Difference in BST](Problems/0530.cpp) |
| 0535 | Medium | [Encode and Decode TinyURL](Problems/0532.cpp) |
| 0535 | Medium | [K-diff Pairs in an Array](Problems/0532.cpp) |
@@ -351,6 +352,7 @@ for solving problems.
| 0673 | Medium | [Number of Longest Increasing Subsequence](Problems/0673.cpp) |
| 0684 | Medium | [Redundant Connection](Problems/0684.cpp) |
| 0688 | Medium | [Knight Probability in Chessboard](Problems/0688.cpp) |
+| 0690 | Medium | [Employee Importance](Problems/0690.cpp) |
| 0692 | Medium | [Top K Frequent Words](Problems/0692.cpp) |
| 0695 | Medium | [Max Area of Island](Problems/0695.cpp) |
| 0700 | Easy | [Search in a Binary Search Tree](Problems/0700.cpp) |
@@ -491,6 +493,7 @@ for solving problems.
| 1161 | Medium | [Maximum Level Sum of a Binary Tree](Problems/1161.cpp) |
| 1162 | Medium | [As Far from Land as Possible](Problems/1162.cpp) |
| 1187 | Hard | [Make Array Strictly Increasing](Problems/1187.cpp) |
+| 1190 | Medium | [Reverse Substrings Between Each Pair of Parentheses](Problems/1190.cpp) |
| 1202 | Medium | [Smallest String With Swaps](Problems/1202.cpp) |
| 1203 | Hard | [Sort Items by Groups Respecting Dependencies](Problems/1203.cpp) |
| 1209 | Medium | [Remove All Adjacent Duplicates in String II](Problems/1209.cpp) |
@@ -634,6 +637,7 @@ for solving problems.
| 1850 | Medium | [Minimum Adjacent Swaps to Reach the Kth Smallest Number](Problems/1850.cpp) |
| 1857 | Hard | [Largest Color Value in a Directed Graph](Problems/1857.cpp) |
| 1860 | Medium | [Incremental Memory Leak](Problems/1860.cpp) |
+| 1861 | Medium | [Rotating the Box](Problems/1861.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) |
@@ -758,6 +762,7 @@ 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) |
+| 2685 | Medium | [Count the Number of Complete Components](Problems/2685.cpp) |
| 2707 | Medium | [Extra Characters in a String](Problems/2707.cpp) |
| 2711 | Medium | [Difference of Number of Distinct Values on Diagonals](Problems/2711.cpp) |
| 2785 | Medium | [Sort Vowels in a String](Problems/2785.cpp) |
