14#include <unordered_set>
20 if(this->
left !=
nullptr && node.
left ==
nullptr) {
23 if(this->
left ==
nullptr && node.
left !=
nullptr) {
26 if(this->
right !=
nullptr && node.
right ==
nullptr) {
29 if(this->
right ==
nullptr && node.
right !=
nullptr) {
32 if(this->
left !=
nullptr && node.
left !=
nullptr && *this->
left != *node.
left) {
38 return this->
val == node.
val;
43 namespace concatenated_words {
45 sort(words.begin(), words.end(), [&](
const string &a,
const string &b) { return a.size() < b.size(); });
46 auto ans = vector<string>();
48 for(
const string &word: words) {
49 if(word.length() == 0) {
52 if(node.dfs(&node, word, 0,
false)) {
67 auto *node = this->
nexts[str[0] -
'a'];
70 this->
nexts[str[0] -
'a'] = node;
72 if(str.length() == 1) {
76 return node->insert(str.substr(1));
82 const auto *
const node = this->
nexts[str[start] -
'a'];
86 return node->
dfs(
root, str, start, flag);
91 if(start == str.length() - 1) {
94 const auto res =
root->dfs(
root, str, start + 1,
true);
100 if(str[start + 1] -
'a' >= 0) {
101 node = this->
nexts[str[start + 1] -
'a'];
103 return node !=
nullptr && node->
dfs(
root, str, start + 1, flag);
107 namespace excel_sheet_column_number {
110 int length =
static_cast<int>(columnTitle.length());
111 for(
const char c: columnTitle) {
112 sum +=
static_cast<int>(
static_cast<double>(c -
'A' + 1) * pow(26, length-- - 1));
118 namespace excel_sheet_column_title {
122 while(columnNumber != 0) {
125 ch =
static_cast<char>(columnNumber % 26 + 63);
128 ch =
static_cast<char>(columnNumber % 26 + 64);
130 if(ch ==
'@' && columnNumber >= 26) {
133 }
else if(ch ==
'?' && columnNumber >= 26) {
137 if(
'A' <= ch && ch <=
'Z') {
138 ans.insert(0, 1, ch);
146 namespace majority_element {
153 if(
m[i] > nums.size() / 2) {
164 namespace count_special_quadruplets {
167 for(
int i = 3; i < nums.size(); i++) {
168 for(
int j = 0; j < i - 2; j++) {
172 for(
int k = j + 1; k < i - 1; k++) {
176 for(
int l = k + 1; l < i; l++) {
180 if(nums[k] + nums[j] + nums[l] == nums[i]) {
191 namespace hand_of_straights {
193 if(hand.size() % groupSize != 0) {
199 sort(hand.begin(), hand.end());
200 const auto len = hand.size() / groupSize;
201 for(
int i = 0; i < len; i++) {
202 int current = *hand.begin();
203 hand.erase(hand.begin());
204 for(
int j = 1; j < groupSize; j++) {
205 auto next =
find(hand.begin(), hand.end(), current + 1);
206 if(next == hand.end()) {
217 namespace perfect_number {
221 for(
int i = 1; i < max; i++) {
234 namespace convert_bst_to_greater_tree {
236 if(
root ==
nullptr) {
248 if(node->
left !=
nullptr) {
251 if(node->
right !=
nullptr) {
258 if(node->
left !=
nullptr) {
262 if(node->
right !=
nullptr) {
269 if(sum_node->
right !=
nullptr) {
274 if(sum_node->
left !=
nullptr) {
283 namespace convert_1d_array_into_2d_array {
285 if(original.size() !=
static_cast<unsigned long long>(m) *
static_cast<unsigned long long>(n)) {
288 auto ans = vector<vector<int>>();
290 for(
int i = 0; i < m; i++) {
291 auto row = vector<int>();
292 for(
int j = 0; j < n; j++) {
293 row.push_back(original[count++]);
301 namespace elimination_game {
307 while(num_amount != 1) {
309 if(num_amount % 2 == 1) {
312 }
else if(num_amount % 2 == 0) {
314 const bool left_to_right = loop_cnt % 2 == 0;
329 namespace check_if_all_as_appears_before_all_bs {
332 for(
const char ch: s) {
337 }
else if(ch ==
'b') {
345 namespace number_of_laser_beams_in_a_bank {
347 if(bank.size() == 1) {
354 while(i < j && i < bank.size() && j < bank.size()) {
360 count += count_i * count_j;
370 for(
const char c: str) {
379 namespace destroying_asteroids {
382 sort(asteroids.begin(), asteroids.end());
383 for(
const int i: asteroids) {
474 namespace day_of_the_week {
476 const string output[] = {
"Sunday",
"Monday",
"Tuesday",
"Wednesday",
"Thursday",
"Friday",
"Saturday"};
477 const int dayofmonths[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
479 count += (year - 1971) * 365;
480 count += (year - 1) / 4 - 1970 / 4;
481 for(
int m = 0; m < month - 1; m++) {
482 count += dayofmonths[m];
484 if(month > 2 && year % 4 == 0 && year % 100 != 0) {
489 return output[count];
493 namespace cat_and_mouse {
497 memset(
dp, -1,
sizeof dp);
505 if(
dp[mouse][cat][turns] < 0) {
508 }
else if(cat == mouse) {
514 return dp[mouse][cat][turns];
518 const int curMove = turns % 2 == 0 ? mouse : cat;
520 int result = defaultResult;
521 for(
int next:
graph[curMove]) {
522 if(curMove == cat && next == 0) {
525 const int nextMouse = curMove == mouse ? next : mouse;
526 const int nextCat = curMove == cat ? next : cat;
527 const int nextResult =
getResult(nextMouse, nextCat, turns + 1);
528 if(nextResult != defaultResult) {
535 dp[mouse][cat][turns] = result;
539 namespace replace_all_s_to_avoid_consecutive_repeating_characters {
541 for(
int i = 0; i < s.size(); i++) {
543 for(
char ch =
'a'; ch <
'z' + 1; ch++) {
544 if(0 <= i - 1 && s[i - 1] == ch) {
547 if(i + 1 < s.size() && s[i + 1] == ch) {
559 namespace simplify_path {
561 auto *
const str_cpy =
new char[path.size() + 1];
562 memcpy(str_cpy, path.c_str(), path.size() + 1);
563 auto *next = strtok(str_cpy,
"/");
564 auto stck = deque<string>();
565 while(next !=
nullptr) {
566 auto nextstr = string(next);
567 if(nextstr ==
"..") {
571 next = strtok(
nullptr,
"/");
575 next = strtok(
nullptr,
"/");
578 stck.emplace_back(next);
579 next = strtok(
nullptr,
"/");
581 auto oss = ostringstream();
585 while(!stck.empty()) {
586 auto pname = stck.front();
596 namespace maximum_nesting_depth_of_the_parentheses {
600 for(
const char ch: s) {
603 }
else if(ch ==
')') {
614 namespace gray_code {
616 vector<int> ret(1 << n);
617 for(
int i = 0; i < ret.size(); i++) {
624 namespace check_if_every_row_and_column_contains_all_numbers {
626 const unsigned int n = matrix.size();
627 for(
int i = 0; i < n; i++) {
628 auto *
const row =
new bool[n + 1];
629 memset(row, 1, (n + 1) *
sizeof(
bool));
630 for(
int j = 0; j < n; j++) {
631 if(!row[matrix[i][j]]) {
635 row[matrix[i][j]] =
false;
640 for(
int j = 0; j < n; j++) {
641 auto *
const column =
new bool[n + 1];
642 memset(column, 1, (n + 1) *
sizeof(
bool));
643 for(
int i = 0; i < n; i++) {
644 if(!column[matrix[i][j]]) {
648 column[matrix[i][j]] =
false;
656 namespace minimum_swaps_to_group_all_1s_together_ii {
659 for(
const int num: nums) {
669 for(
int i = 0; i < onecount; i++) {
676 for(
int i = 0; i < nums.size(); i++) {
680 if(nums[(onecount + i) % nums.size()] == 0) {
683 if(zerocount < min) {
691 namespace count_words_obtained_after_adding_a_letter {
693 vector<string> &targetWords) {
695 auto start = unordered_set<unsigned int>();
696 for(
const string &word: startWords) {
700 for(
const string &word: targetWords) {
701 const auto bin =
str2bin(word);
702 for(
int i = 0; i < 26; i++) {
703 if((bin & 1 << i) != 0 && start.contains(bin - (1 << i))) {
714 unsigned int ret = 0;
715 for(
const char ch: str) {
716 ret |= 1 << ch -
'a';
722 namespace slowest_key {
724 int max = releaseTimes[0];
726 for(
int i = 1; i < releaseTimes.size(); i++) {
727 const int time = releaseTimes[i] - releaseTimes[i - 1];
731 }
else if(max == time) {
732 if(keysPressed[i] > keysPressed[maxi]) {
737 return keysPressed[maxi];
741 namespace additive_number {
743 if(num.length() < 3) {
746 auto *
const nums =
new char[num.length()];
747 for(
int i = 0; i < num.length(); i++) {
750 for(
int i = 1; i <= num.length() - i; i++) {
751 const auto n1 =
str2ui(nums, 0, i);
752 for(
int j = i + 1; j - i <= num.length() - j; j++) {
753 const auto n2 =
str2ui(nums, i, j - i);
754 if(
dfs(n1, n2, nums, num.length(), j)) {
769 bool Solution::dfs(
unsigned long long n1,
unsigned long long n2,
const char *nums,
unsigned short length,
unsigned short current) {
770 const auto sum = to_string(n1 + n2);
771 if(sum.length() > length - current) {
775 if(!
equal(sum, nums, current, length)) {
779 if(current + sum.length() == length) {
783 const auto n3 =
str2ui(nums, current, sum.length());
784 return dfs(n2, n3, nums, length, current + sum.length());
787 unsigned long long Solution::str2ui(
const char *str,
unsigned short start,
unsigned short length) {
788 unsigned long long ans = 0;
789 for(
int i = start; i < start + length; i++) {
796 bool Solution::equal(
string sum,
const char *nums,
unsigned short start,
unsigned short length) {
798 for(
int i = start; j < sum.length() && i < length; i++, j++) {
799 if(sum[j] != nums[i]) {
803 return j == sum.length();
807 namespace decode_the_slanted_ciphertext {
809 if(encodedText.empty()) {
812 const int columns = encodedText.length() / rows;
813 auto *
const table =
new char *[rows];
814 for(
int i = 0; i < rows; i++) {
815 table[i] =
new char[columns - rows + 2];
816 for(
int j = i; j - i < columns - rows + 2; j++) {
817 if(i * columns + j < encodedText.length()) {
818 table[i][j - i] = encodedText[i * columns + j];
820 table[i][j - i] =
' ';
824 auto oss = ostringstream();
825 for(
int j = 0; j < columns - rows + 2; j++) {
826 for(
int i = 0; i < rows; i++) {
830 string ans = oss.str();
831 for(
int i = 0; i < rows; i++) {
839 for(
int i = s.length() - 1; i >= 0; i--) {
841 string ans = s.substr(0, i + 1);
849 namespace escape_a_large_maze {
851 const int limit = blocked.size() * (blocked.size() - 1) / 2;
852 if(blocked.empty()) {
855 auto *p_source =
new point(source[0], source[1], 0,
nullptr);
856 auto *p_target =
new point(target[0], target[1], 0,
nullptr);
857 auto blocked_set_source = unordered_set<point, point_hash>();
858 auto blocked_set_target = unordered_set<point, point_hash>();
859 for(
auto block: blocked) {
860 blocked_set_source.insert(
point(block[0], block[1], 0,
nullptr));
861 blocked_set_target.insert(
point(block[0], block[1], 0,
nullptr));
863 const unsigned int source_status =
search(blocked_set_source, p_source, p_target, limit);
864 if(source_status == 0) {
867 if(source_status == 1) {
870 const unsigned int target_status =
search(blocked_set_target, p_target, p_source, limit);
873 return target_status != 0;
877 auto pq = priority_queue<point>();
878 pq.push(
point(source->
x, source->
y, 0, target));
881 if(count > limit || pq.size() > limit) {
885 const auto p = pq.top();
887 point nexts[] = {
point(p.x + 1, p.y, p.distance + 1, target),
point(p.x - 1, p.y, p.distance + 1, target),
point(p.x, p.y + 1, p.distance + 1, target),
point(p.x, p.y - 1, p.distance + 1, target)};
888 for(
auto next: nexts) {
889 if(0 <= next.x && next.x < 1000000 && 0 <= next.y && next.y < 1000000 && !block_set.contains(next)) {
890 if(next.x == target->
x && next.y == target->
y) {
894 block_set.insert(next);
907 namespace increasing_triplet_subsequence {
909 if(nums.size() < 3) {
912 auto *min =
new int[nums.size()];
913 auto *max =
new int[nums.size()];
915 max[nums.size() - 1] = nums[nums.size() - 1];
916 for(
int i = 1, j = nums.size() - 2; i < nums.size() && j >= 0; i++, j--) {
917 if(min[i - 1] > nums[i]) {
923 if(max[j + 1] < nums[j]) {
929 for(
int i = 0; i < nums.size(); i++) {
930 if(nums[i] > min[i] && nums[i] < max[i]) {
942 namespace largest_number_at_least_twice_of_others {
944 if(nums.size() < 2) {
950 if(nums[0] < nums[1]) {
959 for(
int i = 2; i < nums.size(); i++) {
964 }
else if(nums[i] > second) {
968 if(max >= 2 * second) {
975 namespace find_k_pairs_with_smallest_sums {
977 auto ans = vector<vector<int>>();
978 auto pq = priority_queue<pair>();
979 for(
int i = 0; i < k && i < nums1.size(); i++) {
980 for(
int j = 0; j < k && j < nums2.size(); j++) {
981 pq.push(
pair(nums1[i], nums2[j]));
984 for(
int i = 0; i < k && i < nums1.size() * nums2.size(); i++) {
985 const pair p = pq.top();
987 auto to_add = vector<int>();
991 ans.push_back(to_add);
999 namespace permutations {
1001 auto ans = vector<vector<int>>();
1002 if(nums.size() == 1) {
1003 auto next_ans = vector<int>();
1004 next_ans.push_back(nums[0]);
1005 ans.push_back(next_ans);
1008 for(
auto num: nums) {
1009 auto next = vector(nums);
1010 next.erase(
find(next.begin(), next.end(), num));
1011 auto next_permutations =
permute(next);
1012 auto new_ans = vector<int>();
1013 new_ans.push_back(num);
1014 for(
auto next_permutation: next_permutations) {
1015 auto next_ans = vector(new_ans);
1016 next_ans.insert(next_ans.end(), next_permutation.begin(), next_permutation.end());
1017 ans.push_back(next_ans);
1024 namespace calculate_money_in_leetcode_bank {
1026 int sum = n / 7 * (28 + 7 * (n / 7 + 3)) / 2;
1027 for(
int i = 0; i < n % 7; i++) {
1028 sum += n / 7 + 1 + i;
1034 namespace linked_list_random_node {
1038 for(
const auto *node =
head; node !=
nullptr; node = node->
next, i++) {
1039 if(rand() % i == 0) {
1048 namespace divide_a_string_into_groups_of_size_k {
1050 auto ans = vector<string>();
1052 for(; i * k + k < s.length(); i++) {
1053 ans.push_back(s.substr(i * k, k));
1055 if(i * k != s.length()) {
1056 string last = s.substr(i * k);
1057 for(
int j = last.length(); j < k; j++) {
1060 ans.push_back(last);
1066 namespace minimum_moves_to_reach_target_score {
1069 while(target != 1) {
1070 if(maxDoubles == 0) {
1071 return count + target - 1;
1073 if(target % 2 == 0 && maxDoubles != 0) {
1085 namespace solving_questions_with_brainpower {
1087 vector<long long> f(questions.size() + 1);
1088 for(
int i = questions.size() - 1; i >= 0; --i) {
1089 auto &q = questions[i];
1090 const int j = i + q[1] + 1;
1091 f[i] = max(f[i + 1], q[0] + (j < questions.size() ? f[j] : 0));
1097 namespace maximum_running_time_of_n_computers {
1099 auto check = [&](
long long t) {
1101 for(
const int i: batteries) {
1102 sum += min(t,
static_cast<long long>(i));
1104 return sum / t >= n;
1110 const long long m = (l + r) / 2;
1121 namespace coun_vowels_permutation {
1124 unsigned long long end[5] = {1, 1, 1, 1, 1};
1125 for(
int _i = 1; _i < n; _i++) {
1126 const unsigned long long a = (end[1] + end[2] + end[4]) % 1000000007;
1127 const unsigned long long e = (end[0] + end[2]) % 1000000007;
1128 const unsigned long long i = (end[1] + end[3]) % 1000000007;
1129 const unsigned long long o = end[2] % 1000000007;
1130 const unsigned long long u = (end[2] + end[3]) % 1000000007;
1137 return (end[0] + end[1] + end[2] + end[3] + end[4]) % 1000000007;
1141 namespace minimum_time_difference {
1143 auto vec = vector<int>();
1144 for(
string timePoint: timePoints) {
1145 vec.push_back(((timePoint[0] -
'0') * 10 + (timePoint[1] -
'0')) * 60 + (timePoint[3] -
'0') * 10 + (timePoint[4] -
'0'));
1147 sort(
vec.begin(),
vec.end());
1148 int minimum = INT_MAX;
1149 for(
int i = 0; i + 1 <
vec.size(); i++) {
1150 minimum = min(minimum,
vec[i + 1] -
vec[i]);
1152 minimum = min(minimum,
vec[0] + 24 * 60 -
vec[
vec.size() - 1]);
1157 namespace contains_duplicate_ii {
1159 auto um = unordered_map<int, vector<int>>();
1160 for(
int i = 0; i < nums.size(); i++) {
1161 if(!um.contains(nums[i])) {
1162 um.insert(pair(nums[i], vector<int>()));
1164 auto pos = lower_bound(um[nums[i]].begin(), um[nums[i]].end(), i);
1165 if(pos != um[nums[i]].end() && abs(*pos - i) <= k || pos != um[nums[i]].begin() && abs(*(pos - 1) - i) <= k) {
1168 um[nums[i]].insert(pos, i);
1171 sort(i.second.begin(), i.second.end());
1177 namespace stone_game_ix {
1180 unsigned int counts[3] = {0, 0, 0};
1181 for(
auto stone: stones) {
1185 if(stones.size() == 1) {
1188 if(counts[1] + counts[2] == 2) {
1189 if(counts[1] == 2 || counts[2] == 2) {
1193 if(counts[1] == 0 && counts[2] == 0) {
1196 if(abs(
static_cast<int>(counts[1]) -
static_cast<int>(counts[2])) <= 2) {
1197 return counts[0] % 2 == 0;
1203 namespace jump_game_iv {
1205 if(arr.size() == 1) {
1208 auto pq = queue<pair<int, int>>();
1209 auto *flag =
new bool[arr.size()];
1210 memset(flag, 0, arr.size() *
sizeof(
bool));
1211 auto um = unordered_map<int, vector<int>>();
1212 for(
int i = 0; i < arr.size(); i++) {
1213 if(!um.contains(arr[i])) {
1214 auto vec = vector<int>();
1216 um.insert(pair(arr[i],
vec));
1218 um[arr[i]].push_back(i);
1221 pq.push(pair(0, 0));
1223 while(!pq.empty()) {
1224 auto [current_i, current_count] = pq.front();
1226 if(current_i == arr.size() - 1) {
1227 return current_count;
1229 if(um.contains(arr[current_i])) {
1230 for(
auto i: um[arr[current_i]]) {
1231 if(i != current_i && !flag[i]) {
1232 pq.push(pair(i, current_count + 1));
1237 um.erase(arr[current_i]);
1238 if(current_i - 1 >= 0 && !flag[current_i - 1]) {
1239 pq.push(pair(current_i - 1, current_count + 1));
1240 flag[current_i - 1] =
true;
1242 if(current_i + 1 < arr.size() && !flag[current_i + 1]) {
1243 pq.push(pair(current_i + 1, current_count + 1));
1244 flag[current_i + 1] =
true;
1252 namespace remove_palindromic_subsequences {
1254 for(
int i = 0, j = s.length() - 1; i < j; i++, j--) {
1265 auto oss = ostringstream();
1266 auto *
const nstr =
new char[sentence.length() + 1];
1268 for(
const auto &
root: dictionary) {
1271 strcpy(nstr, sentence.c_str());
1272 char *word = strtok(nstr,
" ");
1273 while(word !=
nullptr) {
1274 oss << tn.get_prefix(
"",
string(word)) <<
" ";
1275 word = strtok(
nullptr,
" ");
1277 const string ans = oss.str();
1279 return ans.substr(0, ans.length() - 1);
1287 if(this->
next[str[0] -
'a'] ==
nullptr) {
1290 this->
next[str[0] -
'a']->
insert(str.substr(1));
1294 if(this->
endroot || str.empty()) {
1297 if(this->
next[str[0] -
'a'] ==
nullptr) {
1304 namespace minimum_cost_of_buying_candies_with_discount {
1306 if(cost.size() == 1) {
1309 if(cost.size() == 2) {
1310 return cost[0] + cost[1];
1313 sort(cost.rbegin(), cost.rend());
1314 for(
int i = 0; i < cost.size(); i++) {
1323 namespace count_the_hidden_sequences {
1325 long long current = 0;
1326 long long maximum = 0;
1327 long long minimum = 0;
1328 for(
const auto difference: differences) {
1329 current += difference;
1330 maximum = max(maximum, current);
1331 minimum = min(minimum, current);
1333 return max(
static_cast<long long>(0), upper - lower - (maximum - minimum) + 1);
1337 namespace k_highest_ranked_items_within_a_price_range {
1339 const auto m = grid.size();
1340 const auto n = grid[0].size();
1341 auto ans = vector<vector<int>>();
1342 const auto low = pricing[0];
1343 const auto high = pricing[1];
1344 const auto row = start[0];
1345 const auto col = start[1];
1346 auto pq = priority_queue<item>();
1347 pq.push(
item(0, grid[row][col], row, col));
1349 while(pq.empty() && k != 0) {
1350 auto current = pq.top();
1352 if(current.price != 1 && current.price >= low && current.price <= high) {
1354 auto vec = vector<int>();
1355 vec.push_back(current.row);
1356 vec.push_back(current.col);
1359 pair<int, int> nexts[4] = {pair(current.row + 1, current.col),
1360 pair(current.row - 1, current.col),
1361 pair(current.row, current.col + 1),
1362 pair(current.row, current.col - 1)};
1363 for(
const pair<int, int> next: nexts) {
1364 if(0 <= next.first && next.first < m && 0 <= next.second && next.second < n && grid[next.first][next.second] != 0) {
1365 pq.push(
item(current.distance + 1, grid[next.first][next.second], next.first, next.second));
1366 grid[next.first][next.second] = 0;
1381 return this->
row > i.
row;
1383 return this->
col > i.
col;
1387 namespace number_of_ways_to_divide_a_long_corridor {
1389 unsigned int s_count = 0;
1390 auto p = vector<unsigned int>();
1391 for(
const char ch: corridor) {
1396 if(s_count == 0 || s_count % 2 != 0) {
1402 unsigned int start = 0;
1403 unsigned int end = corridor.length() - 1;
1404 for(; start < end; start++) {
1405 if(corridor[start] ==
'S') {
1409 for(; end > start; end--) {
1410 if(corridor[end] ==
'S') {
1415 unsigned int p_count = 0;
1417 for(
unsigned int i = start + 1; i <= end; i++) {
1418 if(corridor[i] ==
'S') {
1428 }
else if(s_count == 1) {
1430 p.push_back(p_count + 1);
1436 unsigned long long ans = 1;
1437 for(
const auto i: p) {
1445 namespace count_elements_with_strictly_smaller_and_greater_elements {
1447 int maximum = nums[0];
1448 int minimum = nums[0];
1449 for(
auto num: nums) {
1450 maximum = max(maximum, num);
1451 minimum = min(minimum, num);
1453 unsigned int count = 0;
1454 for(
const auto num: nums) {
1455 if(maximum != num && minimum != num) {
1463 namespace rearrange_array_elements_by_sign {
1465 const auto size = nums.size();
1466 auto ans = vector<int>();
1467 auto positive = vector<int>();
1468 auto negative = vector<int>();
1469 for(
auto num: nums) {
1471 positive.push_back(num);
1473 negative.push_back(num);
1476 for(
int i = 0; i < size / 2; i++) {
1477 ans.push_back(positive[i]);
1478 ans.push_back(negative[i]);
1484 namespace find_all_lonely_numbers_in_the_array {
1486 if(nums.size() == 1) {
1489 sort(nums.begin(), nums.end());
1490 auto ans = vector<int>();
1491 if(nums[1] - nums[0] > 1) {
1492 ans.push_back(nums[0]);
1494 if(nums[nums.size() - 1] - nums[nums.size() - 2] > 1) {
1495 ans.push_back(nums[nums.size() - 1]);
1497 for(
int i = 1; i < nums.size() - 1; i++) {
1498 if(nums[i] - nums[i - 1] > 1 && nums[i + 1] - nums[i] > 1) {
1499 ans.push_back(nums[i]);
1506 namespace maximum_good_people_based_on_statements {
1509 auto dup = unordered_map<int, bool>();
1510 for(
int i = 0; i < statements.size(); i++) {
1514 const auto um = unordered_map<int, bool>();
1515 auto que = queue<msg>();
1516 que.push(
msg(i,
true));
1517 auto ans =
dfs(statements, um, que);
1518 maximum = max(maximum, ans.first);
1519 for(
auto it: ans.second) {
1528 pair<int, unordered_map<int, bool>>
Solution::dfs(vector<vector<int>> &statements, unordered_map<int, bool> um, queue<msg> que) {
1530 bool contradict =
false;
1531 while(!que.empty()) {
1532 auto current = que.front();
1534 if(um.contains(current.person)) {
1536 if(um[current.person] != current.good) {
1538 return pair<int, unordered_map<int, bool>>(0, {});
1541 um.insert(pair(current.person, current.good));
1545 for(
int j = 0; j < statements.size(); j++) {
1546 if(statements[current.person][j] != 2 && j != current.person) {
1547 auto nmsg =
msg(j, statements[current.person][j] == 1);
1548 if(um.contains(nmsg.person)) {
1550 if(um[nmsg.person] != nmsg.good) {
1553 return pair<int, unordered_map<int, bool>>(0, {});
1565 auto dup = unordered_map<int, bool>();
1566 for(
int i = 0; i < statements.size(); i++) {
1570 if(!um.contains(i)) {
1572 for(
auto v: statements[i]) {
1578 um.insert(pair(i,
true));
1581 auto nque = queue<msg>();
1582 nque.push(
msg(i,
true));
1583 auto ans =
dfs(statements, um, nque);
1584 maximum = max(maximum, ans.first);
1585 for(
auto it: ans.second) {
1599 maximum = max(maximum, good_count);
1601 return pair(maximum, um);
1605 namespace stock_price_fluctuation {
1607 ms = multiset<int>();
1608 m = map<int, int>();
1612 if(!
m.contains(timestamp)) {
1613 m.insert(pair(timestamp, price));
1615 ms.erase(
ms.find(
m[timestamp]));
1616 m[timestamp] = price;
1628 namespace second_minimum_time_to_reach_destination {
1630 auto record = unordered_map<int, vector<int>>();
1631 for(
int i = 1; i <= n; i++) {
1632 record.insert(pair(i, vector<int>()));
1634 auto um = unordered_map<int, unordered_set<int>>();
1635 for(
auto edge: edges) {
1636 if(!um.contains(edge[0])) {
1637 auto us = unordered_set<int>();
1639 um.insert(pair(edge[0], us));
1641 um[edge[0]].insert(edge[1]);
1643 if(!um.contains(edge[1])) {
1644 auto us = unordered_set<int>();
1646 um.insert(pair(edge[1], us));
1648 um[edge[1]].insert(edge[0]);
1651 auto pq = priority_queue<status>();
1655 while(!pq.empty()) {
1656 status current = pq.top();
1661 prev = current.
time;
1663 if(current.
time != prev) {
1664 return current.
time;
1676 for(
int next: um[current.
position]) {
1678 if(current.
time / change % 2 == 1) {
1680 next_time = (current.
time / change + 1) * change + time;
1682 next_time = current.
time + time;
1684 auto next_status =
status(next, next_time);
1685 if(record[next_status.position].empty() || record[next_status.position].size() == 1 && next_status.time != *record[next_status.position].rbegin()) {
1687 pq.push(next_status);
1697 namespace count_of_matches_in_tournament {
1701 namespace detect_squares {
1709 if(p.first != point[0] && p.second != point[1] && abs(p.first - point[0]) == abs(p.second - point[1])) {
1710 count +=
ms.count(pair(p.first, point[1])) *
ms.count(pair(point[0], p.second));
1717 namespace number_of_valid_words_in_a_sentence {
1719 auto *str =
new char[sentence.length() + 1];
1720 strcpy(str, sentence.c_str());
1722 for(
const char *token = strtok(str,
" "); token !=
nullptr; token = strtok(
nullptr,
" ")) {
1724 bool hyphen =
false;
1725 for(
int i = 0; token[i] !=
'\0'; i++) {
1726 const char ch = token[i];
1735 if(i == 0 || token[i + 1] ==
'\0') {
1740 if(isalpha(token[i - 1]) == 0 || isalpha(token[i + 1]) == 0) {
1745 }
else if(token[i + 1] !=
'\0' && isalpha(ch) == 0) {
1749 }
else if(isdigit(ch) != 0) {
1764 namespace the_number_of_weak_characters_in_the_game {
1767 sort(properties.begin(), properties.end(), [](
const vector<int> &a,
const vector<int> &b) { return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0]; });
1771 for(
const auto &p: properties) {
1782 namespace pattern_matching_lcci {
1786 for(
const char ch: pattern) {
1793 if(a_count == 0 || b_count == 0) {
1797 if(value.length() % a_count != 0) {
1800 size = value.length() / a_count;
1803 if(value.length() % b_count != 0) {
1806 size = value.length() / b_count;
1809 const string str = value.substr(0, size);
1810 for(
int i = 0; i < count; i++) {
1811 auto s = value.substr(i * size, size);
1818 for(
int a_size = 0; a_size <= value.length() / a_count; a_size++) {
1821 if((value.length() - a_size * a_count) % b_count == 0) {
1822 const int b_size = (value.length() - a_size * a_count) / b_count;
1823 string value_local = value;
1824 for(
const char ch: pattern) {
1826 string a_local = value_local.substr(0, a_size);
1829 }
else if(a_local != a) {
1832 value_local = value_local.substr(a_size);
1834 string b_local = value_local.substr(0, b_size);
1837 }
else if(b_local != b) {
1840 value_local = value_local.substr(b_size);
1854 namespace map_of_highest_peak {
1856 const int m = isWater.size();
1857 const int n = isWater[0].size();
1858 auto *occupied =
new bool *[m];
1859 for(
int i = 0; i < m; i++) {
1860 occupied[i] =
new bool[n];
1861 memset(occupied[i], 0, n *
sizeof(
bool));
1863 auto que = queue<pair<int, int>>();
1864 for(
int i = 0; i < m; i++) {
1865 for(
int j = 0; j < n; j++) {
1866 if(isWater[i][j] == 1) {
1867 que.push(pair(i, j));
1869 occupied[i][j] =
true;
1875 while(!que.empty()) {
1876 pair<int, int> current = que.front();
1878 pair<int, int> nexts[4] = {pair(current.first + 1, current.second),
1879 pair(current.first - 1, current.second),
1880 pair(current.first, current.second + 1),
1881 pair(current.first, current.second - 1)};
1882 for(
auto next: nexts) {
1883 if(0 <= next.first && next.first < m && 0 <= next.second && next.second < n && !occupied[next.first][next.second]) {
1884 isWater[next.first][next.second] = isWater[current.first][current.second] + 1;
1885 occupied[next.first][next.second] =
true;
1895 namespace uncommon_words_from_two_sentences {
1897 auto ans = vector<string>();
1898 auto um = unordered_map<string, unsigned int>();
1899 auto *
const s1_str =
new char[s1.length() + 1];
1900 auto *
const s2_str =
new char[s2.length() + 1];
1901 strcpy(s1_str, s1.c_str());
1902 strcpy(s2_str, s2.c_str());
1903 for(
char *word = strtok(s1_str,
" "); word !=
nullptr; word = strtok(
nullptr,
" ")) {
1904 auto word_str = string(word);
1905 if(!um.contains(word_str)) {
1906 um.insert(pair(word_str, 1));
1911 for(
char *word = strtok(s2_str,
" "); word !=
nullptr; word = strtok(
nullptr,
" ")) {
1912 auto word_str = string(word);
1913 if(!um.contains(word_str)) {
1914 um.insert(pair(word_str, 1));
1919 for(
const auto &p: um) {
1921 ans.push_back(p.first);
1930 namespace keep_multiplying_found_values_by_two {
1933 for(
const auto num: nums) {
1934 if(num == original) {
1943 namespace all_divisions_with_the_highest_score_of_a_binary_array {
1945 const auto n = nums.size();
1946 auto left_0_count = vector<int>();
1947 auto right_1_count = vector<int>();
1948 left_0_count.push_back(0);
1949 right_1_count.push_back(0);
1951 for(
int i = 0; i < n; i++) {
1955 left_0_count.push_back(count);
1958 for(
int i = n - 1; i >= 0; i--) {
1962 right_1_count.push_back(count);
1964 right_1_count = vector(right_1_count.rbegin(), right_1_count.rend());
1966 for(
int i = 0; i <= n; i++) {
1967 maximum = max(maximum, left_0_count[i] + right_1_count[i]);
1969 auto ans = vector<int>();
1970 for(
int i = 0; i <= n; i++) {
1971 if(maximum == left_0_count[i] + right_1_count[i]) {
1979 namespace find_substring_with_given_hash_value {
1982 auto *
const pn =
new int[k];
1984 for(
int i = 1; i < k; i++) {
1985 pn[i] =
static_cast<unsigned long long>(pn[i - 1]) *
static_cast<unsigned long long>(power) % modulo;
1988 for(
int i = 0; i < s.length(); i++) {
1989 unsigned long long hash = 0;
1990 for(
int j = 0; j < k; j++) {
1991 hash +=
static_cast<unsigned long long>((s[i + j] -
'a' + 1) % modulo) * pn[j];
1994 if(hash == hashValue) {
1995 return s.substr(i, k);
2003 namespace groups_of_strings {
2005 auto ans = vector<int>();
2006 auto nums = vector<unsigned int>();
2007 for(
const auto &word: words) {
2009 nums.push_back(num);
2012 for(
const auto num: nums) {
2013 for(
int i = 0; i < 26; i++) {
2014 auto next = num ^ 1 << i;
2015 if(
parent.contains(next)) {
2018 if((num >> i & 1) == 1) {
2020 for(
int j = 0; j < 26; j++) {
2021 if((num >> j & 1) == 0) {
2023 auto next = num ^ 1 << i | 1 << j;
2024 if(
parent.contains(next)) {
2025 to_union(num, num ^ 1 << i | 1 << j);
2038 unsigned int ans = 0;
2039 for(
const char ch: word) {
2040 ans |= 1 << ch -
'a';
2046 parent.insert(pair(num, num));
2047 rank.insert(pair(num, 0));
2048 if(!
size.contains(num)) {
2049 size.insert(pair(num, 1));
2060 const int f1 =
find(x1);
2061 const int f2 =
find(x2);
2081 namespace number_of_steps_to_reduce_a_number_to_zero {
2088 if((num & 1) == 0) {
2099 namespace longest_nice_substring {
2101 auto [max_start, max_len] =
dfs(s, 0, s.length() - 1);
2105 return s.substr(max_start, max_len);
2116 for(
int i = start; i <= end; i++) {
2117 const char ch = s[i];
2118 if(islower(ch) != 0) {
2119 lower |= 1 << ch -
'a';
2122 upper |= 1 << ch -
'A';
2125 if(lower == upper) {
2127 return {start, end - start + 1};
2130 const int not_nice = lower ^ upper;
2133 if((not_nice >> tolower(s[i]) -
'a' & 1) == 1) {
2139 while(j <= end && (not_nice >> tolower(s[j]) -
'a' & 1) != 1) {
2142 auto [next_start, next_len] =
dfs(s, i, j - 1);
2143 if(max_len < next_len) {
2145 max_start = next_start;
2149 return {max_start, max_len};
2153 namespace reverse_prefix_of_word {
2156 for(; i < word.length(); i++) {
2161 if(i == word.length()) {
2164 string prefix = word.substr(0, i + 1);
2165 const string suffix = word.substr(i + 1);
2166 const auto xiferp = string(prefix.rbegin(), prefix.rend());
2167 return xiferp + suffix;
2171 namespace find_the_minimum_number_of_fibonacci_numbers_whose_sum_is_k {
2173 auto fibb = set<int, greater<>>();
2179 const int prev_2 = prev_1;
2181 next = prev_1 + prev_2;
2183 return find_min(fibb, k, fibb.begin());
2187 const auto i = lower_bound(begin, fibb.end(), k, greater<int>());
2191 return 1 +
find_min(fibb, k - *i, i);
2195 namespace number_of_rectangles_that_can_form_the_largest_square {
2197 auto m = map<int, int>();
2198 for(
auto rectangle: rectangles) {
2199 int k = min(rectangle[0], rectangle[1]);
2202 return (*m.rbegin()).second;
2206 namespace path_with_maximum_gold {
2208 const int m = grid.size();
2209 const int n = grid[0].size();
2211 for(
int i = 0; i < m; i++) {
2212 for(
int j = 0; j < n; j++) {
2213 if(grid[i][j] != 0) {
2214 auto *occupied =
new bool *[m];
2215 for(
int k = 0; k < m; k++) {
2216 occupied[k] =
new bool[n];
2217 memset(occupied[k], 0, n *
sizeof(
bool));
2219 occupied[i][j] =
true;
2220 ans = max(ans,
get_sum(grid[i][j], i, j, m, n, grid, occupied));
2221 for(
int k = 0; k < m; k++) {
2222 delete[] occupied[k];
2231 int Solution::get_sum(
int current,
int x,
int y,
int m,
int n, vector<vector<int>> &grid,
bool **occupied) {
2232 pair<int, int> nexts[] = {make_pair(x + 1, y), make_pair(x - 1, y), make_pair(x, y + 1), make_pair(x, y - 1)};
2233 int maximum = current;
2234 for(
auto [next_x, next_y]: nexts) {
2235 if(0 <= next_x && next_x < m && 0 <= next_y && next_y < n && grid[next_x][next_y] != 0 && !occupied[next_x][next_y]) {
2236 auto *occupied_cpy =
new bool *[m];
2237 for(
int i = 0; i < m; i++) {
2238 occupied_cpy[i] =
new bool[n];
2239 memcpy(occupied_cpy[i], occupied[i], n *
sizeof(
bool));
2241 occupied_cpy[next_x][next_y] =
true;
2242 maximum = max(maximum,
get_sum(current + grid[next_x][next_y], next_x, next_y, m, n, grid, occupied_cpy));
2243 for(
int i = 0; i < m; i++) {
2244 delete[] occupied_cpy[i];
2246 delete[] occupied_cpy;
2253 namespace minimum_sum_of_four_digit_number_after_splitting_digits {
2255 auto oss = ostringstream();
2257 const string str = oss.str();
2259 for(
int i = 0; i < 4; i++) {
2260 nums[i] = str[i] -
'0';
2262 sort(nums, nums + 4);
2263 return nums[0] * 10 + nums[1] * 10 + nums[2] + nums[3];
2267 namespace partition_array_according_to_given_pivot {
2269 auto less = vector<int>();
2270 auto equal = vector<int>();
2271 auto greater = vector<int>();
2272 for(
auto num: nums) {
2274 less.push_back(num);
2275 }
else if(num == pivot) {
2276 equal.push_back(num);
2278 greater.push_back(num);
2281 less.insert(less.end(),
equal.begin(),
equal.end());
2282 less.insert(less.end(), greater.begin(), greater.end());
2287 namespace minimum_cost_to_set_cooking_time {
2289 int ans = (moveCost + pushCost) * 4;
2290 int minute = targetSeconds / 60;
2291 int second = targetSeconds % 60;
2292 while(minute > 99) {
2296 const int num[4] = {minute / 10, minute % 10, second / 10, second % 10};
2297 ans = min(ans,
get_cost(startAt, moveCost, pushCost, num));
2298 if(second + 60 < 100 && minute - 1 >= 0) {
2301 const int num[4] = {minute / 10, minute % 10, second / 10, second % 10};
2302 ans = min(ans,
get_cost(startAt, moveCost, pushCost, num));
2309 int current = startAt;
2311 for(
int i = 0; i < 4; i++) {
2312 if(num[i] == 0 && flag) {
2316 if(num[i] != current) {
2326 namespace minimum_difference_in_sums_after_removal_of_elements {
2328 const int n = nums.size() / 3;
2329 auto *left_sum =
new long long[n];
2330 auto *right_sum =
new long long[n];
2331 long long left_min = 0;
2332 long long right_max = 0;
2333 auto left_n = priority_queue<int>();
2334 auto right_n = priority_queue<int, vector<int>, greater<>>();
2335 for(
int i = 0; i < n; i++) {
2336 left_n.push(nums[i]);
2337 left_min += nums[i];
2339 for(
int i = 3 * n - 1; i >= 2 * n; i--) {
2340 right_n.push(nums[i]);
2341 right_max += nums[i];
2343 const long long left_min_preserve = left_min;
2344 const long long right_max_preserve = right_max;
2345 left_sum[0] = left_min;
2346 right_sum[n - 1] = right_max;
2347 for(
int i = n; i < 2 * n; i++) {
2348 if(nums[i] < left_n.top()) {
2349 left_min += nums[i] - left_n.top();
2351 left_n.push(nums[i]);
2353 left_sum[i - n] = left_min;
2355 for(
int i = 2 * n - 1; i >= n; i--) {
2356 if(nums[i] > right_n.top()) {
2357 right_max += nums[i] - right_n.top();
2359 right_n.push(nums[i]);
2361 right_sum[i - n] = right_max;
2363 long long ans = left_min_preserve - right_sum[0];
2364 for(
int i = 0; i < n - 1; i++) {
2365 ans = min(ans, left_sum[i] - right_sum[i + 1]);
2367 ans = min(ans, left_sum[n - 1] - right_max_preserve);
2374 namespace sum_of_unique_elements {
2376 auto um = unordered_map<int, int>();
2377 for(
auto num: nums) {
2381 for(
auto [k, v]: um) {
2390 namespace sort_even_and_odd_indices_independently {
2395 for(
int i = 0; i < nums.size(); i++) {
2397 even.push_back(nums[i]);
2399 odd.push_back(nums[i]);
2402 sort(even.begin(), even.end());
2403 sort(odd.begin(), odd.end(), greater<int>());
2404 for(
int i = 0; i < odd.size(); i++) {
2405 ans.push_back(even[i]);
2406 ans.push_back(odd[i]);
2408 if(even.size() > odd.size()) {
2409 ans.push_back(even.back());
2415 namespace smallest_value_of_the_rearranged_number {
2417 bool positive = num > 0;
2418 auto oss = ostringstream();
2422 for(
char ch: oss.str()) {
2423 n.push_back(ch -
'0');
2425 sort(n.begin(), n.end());
2435 ans.insert(ans.begin() + 1, i);
2439 for(
int i = n.size() - 1; i >= 0; i--) {
2440 ans.push_back(n[i]);
2443 oss = ostringstream();
2450 auto iss = istringstream(oss.str());
2457 namespace design_bitset {
2460 one1 =
new set<unsigned int>();
2461 zero0 =
new set<unsigned int>();
2462 for(
int i = 0; i <
size; i++) {
2478 auto *
const tmp =
one1;
2490 auto oss = ostringstream();
2491 auto c1 =
one1->begin();
2492 auto c0 =
zero0->begin();
2493 for(
int i = 0; i <
size; i++) {
2494 if(c1 !=
one1->end() && *c1 == i) {
2497 }
else if(c0 !=
zero0->end() && *c0 == i) {
2506 namespace longest_happy_string {
2508 auto oss = ostringstream();
2513 while(a != 0 || b != 0 || c != 0) {
2514 if(!(count == 2 && prev == ch[2] && *
get_p(ch[2], &a, &b, &c) > 0)) {
2516 (*
get_p(ch[2], &a, &b, &c))--;
2523 }
else if(!(count == 2 && prev == ch[1]) && *
get_p(ch[1], &a, &b, &c) > 0) {
2525 (*
get_p(ch[1], &a, &b, &c))--;
2532 }
else if(!(count == 2 && prev == ch[0]) && *
get_p(ch[0], &a, &b, &c) > 0) {
2534 (*
get_p(ch[0], &a, &b, &c))--;
2570 ch[1] =
'a' +
'b' +
'c' - ch[0] - ch[2];
2578 default:
return nullptr;
2583 namespace grid_illumination {
2585 auto ls = unordered_set<pair<int, int>,
pair_hash>();
2586 auto row = unordered_map<int, int>();
2587 auto col = unordered_map<int, int>();
2588 auto diag_down = unordered_map<int, int>();
2589 auto diag_up = unordered_map<int, int>();
2590 for(
auto lamp: lamps) {
2593 auto p = make_pair(x, y);
2594 if(!ls.contains(p)) {
2598 diag_down[n - x + y]++;
2602 auto ans = vector<int>();
2603 for(
auto query: queries) {
2604 int query_x = query[0];
2605 int query_y = query[1];
2606 if(row[query_x] > 0 || col[query_y] > 0 || diag_down[n - query_x + query_y] > 0 || diag_up[query_x + query_y] > 0) {
2611 pair<int, int> adjacents[9] = {make_pair(query_x + 1, query_y + 1), make_pair(query_x + 1, query_y), make_pair(query_x + 1, query_y - 1),
2612 make_pair(query_x, query_y + 1), make_pair(query_x, query_y), make_pair(query_x, query_y - 1),
2613 make_pair(query_x - 1, query_y + 1), make_pair(query_x - 1, query_y), make_pair(query_x - 1, query_y - 1)};
2614 for(
auto adjacent: adjacents) {
2615 if(ls.contains(adjacent)) {
2617 auto [x, y] = adjacent;
2620 diag_down[n - x + y]--;
2628 unsigned long long pair_hash::operator()(
const pair<int, int> &p)
const {
return static_cast<unsigned long long>(p.first) * 1000000000 + p.second; }
2631 namespace count_number_of_pairs_with_absolute_difference_k {
2634 for(
int i = 0; i < nums.size(); i++) {
2635 for(
int j = i + 1; j < nums.size(); j++) {
2636 if(abs(nums[i] - nums[j]) == k) {
2645 namespace simplified_fractions {
2647 auto ans = vector<string>();
2648 for(
int denominator = 2; denominator <= n; denominator++) {
2649 for(
int numerator = 1; numerator < denominator; numerator++) {
2650 if(
gcd(denominator, numerator) != 1) {
2653 auto oss = ostringstream();
2654 oss << numerator <<
"/" << denominator;
2655 ans.push_back(oss.str());
2664 namespace minimum_difference_between_highest_and_lowest_of_k_scores {
2667 sort(nums.begin(), nums.end());
2668 for(
int i = 0; i + k - 1 < nums.size(); i++) {
2669 ans = min(ans, nums[i + k - 1] - nums[i]);
2675 namespace number_of_enclaves {
2678 const int m = grid.size();
2679 const int n = grid[0].size();
2680 auto que = queue<pair<int, int>>();
2681 for(
int i = 0; i < m; i++) {
2682 for(
int j = 0; j < n; j++) {
2683 if(grid[i][j] == 1) {
2685 if(i == 0 || i == m - 1 || j == 0 || j == n - 1) {
2686 que.push(make_pair(i, j));
2692 while(!que.empty()) {
2693 auto [x, y] = que.front();
2696 pair<int, int> nexts[4] = {make_pair(x + 1, y), make_pair(x - 1, y), make_pair(x, y + 1), make_pair(x, y - 1)};
2697 for(
auto next: nexts) {
2698 auto [next_x, next_y] = next;
2699 if(0 <= next_x && next_x < m && 0 <= next_y && next_y < n && grid[next_x][next_y] != 0) {
2701 grid[next_x][next_y] = 0;
2709 namespace maximum_number_of_balloons {
2716 for(
const char ch: text) {
2746 namespace swap_adjacent_in_lr_string {
2748 auto oss_start = ostringstream();
2749 auto oss_end = ostringstream();
2750 auto i_start = vector<int>();
2751 auto i_end = vector<int>();
2752 for(
int i = 0; i < start.size(); i++) {
2754 if(ch ==
'R' || ch ==
'L') {
2756 i_start.push_back(i);
2759 for(
int i = 0; i < end.size(); i++) {
2761 if(ch ==
'R' || ch ==
'L') {
2766 string str_start = oss_start.str();
2767 string str_end = oss_end.str();
2768 if(str_start != str_end) {
2771 for(
int i = 0; i < i_start.size(); i++) {
2772 if(str_start[i] ==
'R') {
2773 if(i_start[i] > i_end[i]) {
2778 if(i_start[i] < i_end[i]) {
2787 namespace count_operations_to_obtain_zero {
2790 while(num1 != 0 && num2 != 0) {
2792 count += num1 / num2;
2795 count += num2 / num1;
2803 namespace minimum_operations_to_make_the_array_alternating {
2807 auto a = unordered_map<int, int>();
2808 auto b = unordered_map<int, int>();
2809 for(
int i = 0; i < nums.size(); i++) {
2821 for(
const auto i: a) {
2822 if(maximum < i.second) {
2827 ans1 += a_sum - maximum;
2829 for(
const auto i: b) {
2830 if(i.first != max_num && maximum < i.second) {
2834 ans1 += b_sum - maximum;
2839 for(
const auto i: b) {
2840 if(maximum < i.second) {
2845 ans2 += b_sum - maximum;
2847 for(
const auto i: a) {
2848 if(i.first != max_num && maximum < i.second) {
2852 ans2 += a_sum - maximum;
2853 return min(ans1, ans2);
2857 namespace removing_minimum_number_of_magic_beans {
2859 sort(beans.begin(), beans.end());
2861 long long maximum = 0;
2862 for(
int i = 0; i < beans.size(); i++) {
2864 maximum = max(maximum,
static_cast<long long>(beans[i] * (beans.size() - i)));
2866 return sum - maximum;
2870 namespace maximum_and_sum_of_array {
2873 vector<int> max_and_sum_of_status(1 << numSlots * 2);
2874 for(
unsigned int status = 0; status < max_and_sum_of_status.size(); ++status) {
2876 const int one_count = popcount(status);
2877 if(one_count >= nums.size()) {
2880 for(
int next_slot = 0; next_slot < numSlots * 2; ++next_slot) {
2881 if((status & 1 << next_slot) == 0) {
2883 const int next_status = status | 1 << next_slot;
2884 const auto slot_num = next_slot / 2 + 1;
2885 max_and_sum_of_status[next_status] = max(max_and_sum_of_status[next_status], max_and_sum_of_status[status] + (slot_num & nums[one_count]));
2886 ans = max(ans, max_and_sum_of_status[next_status]);
2894 namespace single_element_in_a_sorted_array {
2897 int r = nums.size() - 1;
2903 if(r == nums.size() - 1) {
2906 if(nums[l - 1] == nums[l]) {
2911 const int m = (l + r) / 2;
2913 if(nums[m + 1] == nums[m]) {
2928 namespace lucky_numbers_in_a_matrix {
2930 auto ans = vector<int>();
2931 const auto m = matrix.size();
2932 const auto n = matrix[0].size();
2933 auto *minimum =
new int[m];
2934 memset(minimum, 50, m *
sizeof(
int));
2935 auto *maximum =
new int[n];
2936 memset(maximum, 0, n *
sizeof(
int));
2937 for(
int i = 0; i < m; i++) {
2938 for(
int j = 0; j < n; j++) {
2939 minimum[i] = min(minimum[i], matrix[i][j]);
2940 maximum[j] = max(maximum[j], matrix[i][j]);
2943 for(
int i = 0; i < m; i++) {
2944 for(
int j = 0; j < n; j++) {
2945 if(matrix[i][j] == minimum[i] && matrix[i][j] == maximum[j]) {
2946 ans.push_back(matrix[i][j]);
2956 namespace number_of_ways_to_reconstruct_a_tree {
2958 unordered_map<int, unordered_set<int>> adj;
2959 for(
auto &p: pairs) {
2960 adj[p[0]].emplace(p[1]);
2961 adj[p[1]].emplace(p[0]);
2965 for(
auto &[node, neighbours]: adj) {
2966 if(neighbours.size() == adj.size() - 1) {
2976 for(
auto &[node, neighbours]: adj) {
2980 const int currDegree = neighbours.size();
2982 int parentDegree = INT_MAX;
2985 for(
const auto &neighbour: neighbours) {
2986 if(adj[neighbour].size() < parentDegree && adj[neighbour].size() >= currDegree) {
2988 parentDegree = adj[neighbour].size();
2996 for(
const auto &neighbour: neighbours) {
2997 if(neighbour == parent) {
3000 if(
static_cast<unsigned int>(adj[parent].contains(neighbour)) == 0U) {
3004 if(parentDegree == currDegree) {
3012 namespace find_center_of_star_graph {
3014 auto um = unordered_map<int, int>();
3015 for(
auto edge: edges) {
3018 if(um[edge[0]] > 1) {
3021 if(um[edge[1]] > 1) {
3029 namespace knight_probability_in_chessboard {
3034 const auto s =
status(k, row, column);
3035 if(
um.count(s) == 1) {
3039 pair<int, int> nexts[8] = {make_pair(row - 2, column - 1),
3040 make_pair(row - 2, column + 1),
3041 make_pair(row + 2, column - 1),
3042 make_pair(row + 2, column + 1),
3043 make_pair(row - 1, column - 2),
3044 make_pair(row - 1, column + 2),
3045 make_pair(row + 1, column - 2),
3046 make_pair(row + 1, column + 2)};
3048 for(
auto [next_x, next_y]: nexts) {
3049 if(0 <= next_x && next_x < n && 0 <= next_y && next_y < n) {
3053 const double ans = sum / 8;
3063 namespace pancake_sorting {
3065 auto ans = vector<int>();
3066 const int n = arr.size();
3067 auto *current =
new int[n];
3068 auto *sorted =
new int[n];
3069 for(
int i = 0; i < n; i++) {
3070 current[i] = arr[i];
3073 sort(sorted, sorted + n);
3075 for(
int i = n - 1; i >= 0; i--) {
3076 if(current[i] != sorted[i]) {
3077 const int target = sorted[i];
3079 for(
int j = 0; j <= i; j++) {
3080 if(current[j] == target) {
3088 ans.push_back(target_i);
3089 for(
int j = 0; j < target_i / 2; j++) {
3090 swap(current[j], current[target_i - j - 1]);
3101 namespace count_equal_and_divisible_pairs_in_an_array {
3104 for(
int i = 0; i + 1 < nums.size(); i++) {
3105 for(
int j = i + 1; j < nums.size(); j++) {
3106 if(nums[i] == nums[j] && i * j % k == 0) {
3115 namespace find_three_consecutive_integers_that_sum_to_a_given_number {
3118 const long long mid = num / 3;
3119 vector ans = {mid - 1, mid, mid + 1};
3126 namespace maximum_split_of_positive_even_integers {
3128 if(finalSum % 2 != 0) {
3134 auto ans = vector<long long int>();
3137 for(
long long i = 4; i <= finalSum; i += 2) {
3138 const long long int next = finalSum - i;
3143 ans.push_back(finalSum);
3151 namespace count_good_triplets_in_an_array {
3153 const int n = nums1.size();
3155 unordered_map<int, int> pos;
3156 for(
int i = 0; i < n; ++i) {
3157 pos[nums2[i]] = i + 1;
3160 for(
int i = 0; i < n; ++i) {
3161 const int idx = pos[nums1[i]];
3172 namespace count_integers_with_even_digit_sum {
3175 for(
int i = 1; i <= num; i++) {
3191 namespace merge_nodes_in_between_zeros {
3193 while(head !=
nullptr && head->
val == 0) {
3197 while(head !=
nullptr && head->
next !=
nullptr) {
3210 namespace construct_string_with_repeat_limit {
3213 for(
const char c: s) {
3216 auto oss = ostringstream();
3217 for(
int i = 25; i >= 0; i--) {
3220 oss << static_cast<char>(i +
'a');
3223 if(repeat == repeatLimit && ch[i] != 0) {
3224 for(
int j = i - 1; j >= 0; j--) {
3226 oss << static_cast<char>(j +
'a');
3242 namespace count_array_pairs_divisible_by_k {
3246 auto count = unordered_map<int, int>();
3247 for(
const auto num: nums) {
3250 const int maximum = *max_element(nums.begin(), nums.end());
3252 for(
int i = 1; i <= maximum; i++) {
3253 for(
int j = i * 2; j <= maximum; j += i) {
3254 count[i] += count[j];
3257 for(
const auto num: nums) {
3259 ans += count[k / gcd(k, num)];
3260 if(
static_cast<long long>(num) * num % k == 0) {
3269 namespace leetcode717_1_bit_and_2_bit_characters {
3271 for(
int i = 0; i < bits.size();) {
3278 if(next >= bits.size()) {
3279 return i == bits.size() - 1;
3287 namespace longest_mountain_in_array {
3289 if(arr.size() < 3) {
3292 auto up_down = vector<int>(arr.size() - 1);
3293 for(
int i = 0; i + 1 < arr.size(); i++) {
3294 if(arr[i] < arr[i + 1]) {
3296 }
else if(arr[i] > arr[i + 1]) {
3302 auto sector_size = vector<pair<int, int>>();
3303 int prev = up_down[0];
3305 for(
int i = 1; i < up_down.size(); i++) {
3306 if(up_down[i] != prev) {
3307 sector_size.emplace_back(prev, count);
3314 sector_size.emplace_back(prev, count);
3315 if(sector_size.size() < 2) {
3319 for(
int i = 0; i + 1 < sector_size.size(); i++) {
3320 if(sector_size[i].first == 1 && sector_size[i + 1].first == 0) {
3321 maximum = max(maximum, sector_size[i].second + sector_size[i + 1].second + 1);
3328 namespace push_dominoes {
3330 const int n = dominoes.length();
3331 auto *left_to_r =
new int[n];
3332 auto *right_to_l =
new int[n];
3333 auto *left_is =
new char[n];
3334 auto *right_is =
new char[n];
3338 for(
int i = 0; i < n; i++) {
3339 if(dominoes[i] !=
'.') {
3345 for(
int i = n - 1; i >= 0; i--) {
3346 if(dominoes[i] !=
'.') {
3351 for(
int i = 0; i < n; i++) {
3352 if(dominoes[i] ==
'R') {
3359 for(
int i = n - 1; i >= 0; i--) {
3360 if(dominoes[i] ==
'L') {
3365 right_to_l[i] = r2l;
3367 for(
int i = 0; i < n; i++) {
3368 if(dominoes[i] ==
'.') {
3369 if(left_is[i] ==
'R' && right_is[i] ==
'L') {
3370 if(right_to_l[i] > left_to_r[i]) {
3372 }
else if(left_to_r[i] > right_to_l[i]) {
3375 }
else if(right_is[i] ==
'L') {
3377 }
else if(left_is[i] ==
'R') {
3383 delete[] right_to_l;
3390 namespace the_number_of_good_subsets {
3392 vector<int> freq(
num_max + 1);
3393 for(
const int num: nums) {
3399 for(
int i = 0; i < freq[1]; ++i) {
3400 f[0] = f[0] * 2 %
mod;
3403 for(
int i = 2; i <=
num_max; ++i) {
3412 for(
int j = 0; j <
primes.size(); j++) {
3413 const int prime =
primes[j];
3414 if(x % (prime * prime) == 0) {
3418 if(x % prime == 0) {
3427 for(
int mask =
mask_max - 1; mask > 0; mask--) {
3428 if((mask & subset) == subset) {
3429 f[mask] = (f[mask] +
static_cast<long long>(f[mask ^ subset]) * freq[i]) %
mod;
3434 for(
int mask = 1; mask <
mask_max; mask++) {
3435 ans = (ans + f[mask]) %
mod;
3441 namespace reverse_only_letters {
3443 for(
int i = 0, j = s.length() - 1; i < j && i < s.length() && j >= 0;) {
3444 if(isalpha(s[i]) != 0 && isalpha(s[j]) != 0) {
3445 const char temp = s[i];
3451 while(i < s.length() && isalpha(s[i]) == 0) {
3454 while(j >= 0 && isalpha(s[j]) == 0) {
3463 namespace where_will_the_ball_fall {
3465 const int m = grid.size();
3466 const int n = grid[0].size();
3468 for(
int i = 0; i < n; i++) {
3473 if(current_x == m) {
3477 if(current_x < 0 || current_y < 0 || current_y >= n) {
3483 if(grid[current_x][current_y] == 1) {
3488 }
else if(dir == 1) {
3490 if(grid[current_x][current_y] == 1) {
3497 if(grid[current_x][current_y] == 1) {
3507 }
else if(dir == 1) {
3520 namespace complex_number_multiplication {
3522 auto ss = stringstream();
3535 const int r = r1 * r2 - i1 * i2;
3536 const int i = r1 * i2 + r2 * i1;
3537 ss = stringstream();
3538 ss << r <<
'+' << i <<
'i';
3543 namespace maximum_difference_between_increasing_elements {
3547 for(
int i = 1; i < nums.size(); i++) {
3548 if(nums[i] > minn) {
3549 max_diff = max(max_diff, nums[i] - minn);
3551 minn = min(minn, nums[i]);
3557 namespace optimal_division {
3559 auto oss = ostringstream();
3560 if(nums.size() == 1) {
3562 }
else if(nums.size() == 2) {
3563 oss << nums[0] <<
'/' << nums[1];
3565 oss << nums[0] <<
"/(";
3566 for(
int i = 1; i < nums.size() - 1; i++) {
3567 oss << nums[i] <<
'/';
3569 oss << nums[nums.size() - 1] <<
')';
3575 namespace counting_words_with_a_given_prefix {
3578 for(
auto word: words) {
3580 for(
int i = 0; i < pref.length(); i++) {
3581 if(pref[i] != word[i]) {
3594 namespace minimum_number_of_steps_to_make_two_strings_anagram_ii {
3599 for(
const char ch: s) {
3602 for(
const char ch: t) {
3605 for(
int i = 0; i < 26; i++) {
3606 ans += abs(s_num[i] - t_num[i]);
3612 namespace minimum_time_to_complete_trips {
3617 max_t = max(max_t, t);
3618 min_t = min(min_t, t);
3620 long long l =
static_cast<long long>(totalTrips) / max_t / time.size();
3621 long long r =
static_cast<long long>(totalTrips) * max_t;
3623 const long long m = (l + r) / 2;
3625 for(
const auto t: time) {
3628 if(l == r || l + 1 == r) {
3631 if(sum >= totalTrips) {
3633 }
else if(sum < totalTrips) {
3641 namespace minimum_time_to_finish_the_race {
3644 vector<long long> min_times(20, 1e9);
3645 for(
auto &v: tires) {
3646 const long long f = v[0];
3647 const long long r = v[1];
3648 const long long cost = f + changeTime;
3649 long long current = f;
3650 long long sum = cost;
3651 for(
int i = 1; i <= 19; i++) {
3652 min_times[i] = min(min_times[i], sum);
3654 if(current > cost) {
3663 vector<long long> dp(numLaps + 1, 1e9);
3665 for(
int i = 1; i <= numLaps; i++) {
3666 for(
int j = 1; j <= min(19, i); j++) {
3667 dp[i] = min(dp[i], dp[i - j] + min_times[j]);
3671 return dp[numLaps] - changeTime;
3675 namespace maximum_number_of_achievable_transfer_requests {
3678 for(
unsigned int i = 0; i < 1 << requests.size(); i++) {
3679 auto *in =
new int[n];
3680 auto *out =
new int[n];
3681 memset(in, 0, n *
sizeof(
int));
3682 memset(out, 0, n *
sizeof(
int));
3683 for(
unsigned int j = 0; j < requests.size(); j++) {
3684 if((i & 1 << j) != 0) {
3685 out[requests[j][0]]++;
3686 in[requests[j][1]]++;
3690 for(
int j = 0; j < n; j++) {
3691 if(out[j] != in[j]) {
3697 ans = max(ans, popcount(i));
3706 namespace zigzag_conversion {
3711 auto oss = ostringstream();
3712 auto *m =
new char *[numRows];
3713 for(
int i = 0; i < numRows; i++) {
3714 m[i] =
new char[s.length()];
3715 memset(m[i],
' ', s.length() *
sizeof(
char));
3720 for(
const char ch: s) {
3721 m[current_x][current_y] = ch;
3722 if(dir && current_x == numRows - 1 || !dir && current_x == 0) {
3732 for(
int i = 0; i < numRows; i++) {
3733 for(
int j = 0; j <= min(current_y, static_cast<int>(s.length() - 1)); j++) {
3734 if(m[i][j] !=
' ') {
3739 for(
int i = 0; i < numRows; i++) {
3747 namespace find_the_closest_palindrome {
3749 const long long num = stoll(n);
3750 if(num == 10 || num == 11) {
3754 return to_string(num - 1);
3756 int len = n.length();
3757 const bool even = n.length() % 2 == 0;
3758 string prefix = n.substr(0, n.length() / 2 + (even ? 0 : 1));
3759 string option_str[3];
3760 auto rev = string(prefix.rbegin() + (even ? 0 : 1), prefix.rend());
3761 option_str[2] = prefix + rev;
3762 const long long prefix_int[2] = {stoll(prefix) - 1, stoll(prefix) + 1};
3763 string prefix_str[2] = {to_string(prefix_int[0]), to_string(prefix_int[1])};
3764 for(
int i = 0; i < 2; i++) {
3765 if(prefix_str[i].length() == prefix.length()) {
3766 rev = string(prefix_str[i].rbegin() + (even ? 0 : 1), prefix_str[i].rend());
3767 option_str[i] = prefix_str[i] + rev;
3768 }
else if(prefix_str[i].length() > prefix.length()) {
3769 rev = string(prefix_str[i].rbegin() + (even ? 1 : 2), prefix_str[i].rend());
3770 option_str[i] = prefix_str[i] + rev;
3771 }
else if(prefix_str[i].length() < prefix.length()) {
3772 rev = string(prefix_str[i].rbegin(), prefix_str[i].rend());
3773 option_str[i] = prefix_str[i] + (even ?
"9" :
"") + rev;
3776 long long option_int[3] = {stoll(option_str[0]), stoll(option_str[1]), stoll(option_str[2])};
3777 sort(option_int, option_int + 3);
3778 long long minimum = option_int[0];
3779 for(
int i = 1; i < 3; i++) {
3780 if(abs(option_int[i] - num) < abs(minimum - num) && option_int[i] != num) {
3781 minimum = option_int[i];
3784 return to_string(minimum);
3788 namespace add_digits {
3792 namespace sum_of_subarray_ranges {
3795 for(
int i = 0; i + 1 < nums.size(); i++) {
3796 int minimum = nums[i];
3797 int maximum = nums[i];
3798 for(
int j = i + 1; j < nums.size(); j++) {
3799 minimum = min(minimum, nums[j]);
3800 maximum = max(maximum, nums[j]);
3801 ans += maximum - minimum;
3808 namespace longest_uncommon_subsequence_i {
3810 if(a.length() != b.length() || b.find(a) == string::npos && a.find(b) == string::npos) {
3811 return max(a.length(), b.length());
3817 namespace most_frequent_number_following_key_in_an_array {
3819 unordered_map<int, int> um;
3820 for(
int i = 0; i + 1 < nums.size(); i++) {
3821 if(nums[i] == key) {
3827 for(
auto [k, v]: um) {
3837 namespace sort_the_jumbled_numbers {
3839 vector<tuple<int, int, int>>
vec;
3840 for(
int i = 0; i < nums.size(); i++) {
3841 string str = to_string(nums[i]);
3843 for(
const char ch: str) {
3844 oss << mapping[ch -
'0'];
3846 vec.emplace_back(i, nums[i], stoi(oss.str()));
3850 ans.reserve(
vec.size());
3851 for(
auto [i, num, rev]:
vec) {
3858 namespace all_ancestors_of_a_node_in_a_directed_acyclic_graph {
3860 for(
int i = 0; i < n; i++) {
3861 nexts[i] = unordered_set<int>();
3864 for(
auto edge: edges) {
3865 nexts[edge[0]].insert(edge[1]);
3867 for(
int i = 0; i < n; i++) {
3868 for(
const auto next:
nexts[i]) {
3869 auto *dfsd =
new bool[n];
3870 memset(dfsd, 0, n *
sizeof(
bool));
3875 vector<vector<int>> ans;
3876 for(
int i = 0; i < n; i++) {
3889 for(
const auto next:
nexts[i]) {
3897 namespace minimum_number_of_moves_to_make_palindrome {
3903 if(s[
left] == s[i]) {
3906 for(; i <
right; i++) {
3907 swap(s[i], s[i + 1]);
3916 ans += s.size() / 2 -
left;
3923 namespace cells_in_a_range_on_an_excel_sheet {
3926 istringstream ss(s);
3934 for(
char col = col1; col <= col2; col++) {
3935 for(
int row = row1; row <= row2; row++) {
3938 ans.push_back(oss.str());
3945 namespace append_k_integers_with_minimal_sum {
3949 for(
auto num: nums) {
3952 long long limit = k;
3953 for(
auto i = s.begin(); i != s.end() && *i <= limit; ++i) {
3956 ans += limit + limit * (limit - 1) / 2;
3957 for(
auto i = s.begin(); i != s.end() && *i < limit; ++i) {
3964 namespace create_binary_tree_from_descriptions {
3966 unordered_map<int, TreeNode *> um;
3967 unordered_set<int> nodes;
3968 unordered_set<int> childs;
3969 for(
auto description: descriptions) {
3970 nodes.insert(description[0]);
3971 nodes.insert(description[1]);
3972 childs.insert(description[1]);
3974 for(
auto node: nodes) {
3977 for(
auto description: descriptions) {
3978 if(description[2] == 1) {
3980 um[description[0]]->left = um[description[1]];
3983 um[description[0]]->right = um[description[1]];
3986 for(
auto node: nodes) {
3987 if(!childs.contains(node)) {
3995 namespace replace_non_coprime_numbers_in_array {
3998 for(
int i = 0; i < nums.size(); i++) {
4000 while(!ans.empty() && gcd(num, ans.back()) > 1) {
4001 num = num / gcd(num, ans.back()) * ans.back();
4010 namespace find_good_days_to_rob_the_bank {
4012 if(security.size() < 2 * time + 1) {
4017 for(
int i = 0; i < security.size(); i++) {
4022 vector non_increasing(security.size(), 0);
4023 vector non_decreasing(security.size(), 0);
4024 for(
int i = 1; i < security.size(); i++) {
4025 if(security[i] >= security[i - 1]) {
4026 non_decreasing[i] = non_decreasing[i - 1] + 1;
4028 non_decreasing[i] = 0;
4030 if(security[i] <= security[i - 1]) {
4031 non_increasing[i] = non_increasing[i - 1] + 1;
4033 non_increasing[i] = 0;
4036 for(
int i = time; i + time < security.size(); i++) {
4037 if(non_decreasing[i + time] >= time && non_increasing[i] >= time) {
4057 deq.push_front(num % 7);
4064 for(
const int n: deq) {
4071 namespace plates_between_candles {
4074 vector<int> plate_count(s.length());
4075 vector<int> candle_pos;
4080 candle_pos.push_back(0);
4082 for(
int i = 1; i < s.length(); i++) {
4083 plate_count[i] = plate_count[i - 1];
4087 candle_pos.push_back(i);
4090 for(
auto query: queries) {
4091 int left = query[0];
4092 int right = query[1];
4093 auto li = lower_bound(candle_pos.begin(), candle_pos.end(),
left);
4094 if(li == candle_pos.end() || *li >
right) {
4098 auto ri = lower_bound(candle_pos.rbegin(), candle_pos.rend(),
right, greater<int>());
4099 if(ri == candle_pos.rend() || *ri <
left) {
4103 ans.push_back(plate_count[*ri] - plate_count[*li]);
4109 namespace smallest_rotation_with_highest_score {
4111 const int n = nums.size();
4112 vector k_score_diff(n + 1, 0);
4113 for(
int i = 0; i < n; i++) {
4114 const int low = (i + 1) % n;
4115 const int high = (i - nums[i] + n) % n;
4116 k_score_diff[low]++;
4117 k_score_diff[high + 1]--;
4126 for(
int i = 0; i < n; i++) {
4127 score += k_score_diff[i];
4128 if(score > max_score) {
4137 namespace n_ary_tree_preorder_traversal {
4139 if(
root ==
nullptr) {
4143 ans.push_back(
root->val);
4144 for(
auto *child:
root->children) {
4145 auto preorder_child =
preorder(child);
4146 ans.insert(ans.end(), preorder_child.begin(), preorder_child.end());
4152 namespace count_nodes_with_the_highest_score {
4155 auto nodes = vector<TreeNode *>(parents.size(),
nullptr);
4156 auto edges = vector(parents.size(), vector<int>());
4157 auto scores = vector<unsigned long long>(parents.size(), 0);
4158 for(
int i = 0; i < parents.size(); i++) {
4160 if(parents[i] != -1) {
4161 edges[i].push_back(parents[i]);
4162 edges[parents[i]].push_back(i);
4166 for(
int i = 0; i < parents.size(); i++) {
4167 if(parents[i] != -1) {
4168 nodes[parents[i]]->add_child(nodes[i]);
4174 unsigned long long max_score = 0;
4175 for(
int i = 0; i < parents.size(); i++) {
4176 unsigned long long score = 1;
4177 const auto *node = nodes[i];
4178 for(
const auto *child: node->get_children()) {
4179 score *= child->get_count();
4181 if(node->get_parent() !=
nullptr) {
4182 score *=
root->get_count() - node->get_count();
4184 max_score = max(max_score, score);
4187 return count(scores.begin(), scores.end(), max_score);
4198 ans += child->dfs();
4211 namespace n_ary_tree_postorder_traversal {
4213 if(
root ==
nullptr) {
4217 for(
auto *child:
root->children) {
4219 ans.insert(ans.end(), res.begin(), res.end());
4221 ans.push_back(
root->val);
4226 namespace max_area_of_island {
4228 const int m = grid.size();
4229 const int n = grid[0].size();
4232 for(
int i = 0; i < m; i++) {
4233 for(
int j = 0; j < n; j++) {
4234 if(grid[i][j] == 1) {
4235 const pair<int, int> p = make_pair(i, j);
4236 ans = max(ans, uf.get_size(p));
4237 pair<int, int> siblings[4] = {
4238 make_pair(i + 1, j),
4239 make_pair(i - 1, j),
4240 make_pair(i, j + 1),
4241 make_pair(i, j - 1),
4243 for(
const auto sibling: siblings) {
4244 if(uf.contains(sibling) && grid[sibling.first][sibling.second] == 1 && !uf.same(p, sibling)) {
4245 uf.merge(p, sibling);
4246 ans = max(ans, uf.get_size(p));
4257 parent = unordered_map<pair<int, int>,
4259 function<
unsigned int(
const pair<int, int> &)>>(
4261 [](
const pair<int, int> &p) {
return static_cast<unsigned int>(p.first * 50 + p.second); });
4262 size = unordered_map<pair<int, int>,
4264 function<
unsigned int(
const pair<int, int> &)>>(
4266 [](
const pair<int, int> &p) {
return static_cast<unsigned int>(p.first * 50 + p.second); });
4267 rank = unordered_map<pair<int, int>,
4269 function<
unsigned int(
const pair<int, int> &)>>(
4271 [](
const pair<int, int> &p) {
return static_cast<unsigned int>(p.first * 50 + p.second); });
4272 for(
int i = 0; i <
m; i++) {
4273 for(
int j = 0; j <
n; j++) {
4274 pair<int, int> p = make_pair(i, j);
4290 const auto pa =
find(a);
4291 const auto pb =
find(b);
4293 const int sum =
size[pa] +
size[pb];
4314 namespace find_all_k_distant_indices_in_an_array {
4318 for(
int i = 0; i < nums.size(); i++) {
4319 if(nums[i] == key) {
4323 for(
const auto ks: key_set) {
4324 for(
int i = ks - k; i <= ks + k; i++) {
4325 if(0 <= i && i < nums.size()) {
4330 return vector(ans_set.begin(), ans_set.end());
4334 namespace count_artifacts_that_can_be_extracted {
4336 auto *grid =
new bool *[n];
4337 for(
int i = 0; i < n; i++) {
4338 grid[i] =
new bool[n];
4339 memset(grid[i], 0, n *
sizeof(
bool));
4342 grid[i[0]][i[1]] =
true;
4345 for(
auto artifact: artifacts) {
4347 for(
int i = artifact[0]; i <= artifact[2]; i++) {
4348 for(
int j = artifact[1]; j <= artifact[3]; j++) {
4362 for(
int i = 0; i < n; i++) {
4370 namespace maximize_the_topmost_element_after_k_moves {
4372 if(nums.size() == 1 && k % 2 == 1) {
4375 if(k > nums.size()) {
4377 for(
auto num: nums) {
4378 ans = max(ans, num);
4382 unordered_map<int, int> element_count;
4383 set<int> poped_elements;
4384 for(
auto num: nums) {
4385 element_count[num]++;
4387 for(
int i = 0; i < nums.size() && i < k - 1; i++) {
4388 poped_elements.insert(nums[i]);
4389 element_count[nums[i]]--;
4392 if(k < nums.size()) {
4396 for(
const auto i = poped_elements.rbegin(); i != poped_elements.rend();) {
4400 return max(ans, maximum);
4404 namespace minimum_weighted_subgraph_with_the_required_paths {
4406 auto *graph =
new vector<pair<int, int>>[n];
4407 auto *graph_rev =
new vector<pair<int, int>>[n];
4408 for(
int i = 0; i < n; i++) {
4409 graph[i] = vector<pair<int, int>>();
4410 graph_rev[i] = vector<pair<int, int>>();
4412 for(
auto &edge: edges) {
4413 auto from = edge[0];
4415 auto weight = edge[2];
4416 graph[from].emplace_back(to, weight);
4417 graph_rev[to].emplace_back(from, weight);
4420 long long a = LLONG_MAX;
4421 vector dist_src1(n, LLONG_MAX);
4422 vector dist_src2(n, LLONG_MAX);
4423 vector dist_dest(n, LLONG_MAX);
4429 long long ans = LLONG_MAX;
4431 for(
int i = 0; i < n; ++i) {
4432 if(dist_src1[i] != LLONG_MAX && dist_src2[i] != LLONG_MAX && dist_dest[i] != LLONG_MAX) {
4433 ans = min(ans, dist_src1[i] + dist_src2[i] + dist_dest[i]);
4436 if(ans == LLONG_MAX) {
4445 priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
4448 while(!pq.empty()) {
4449 auto [weight, node] = pq.top();
4451 if(weight > dist[node]) {
4454 for(
auto [next_node, next_weight]: graph[node]) {
4455 if(weight + next_weight < dist[next_node]) {
4456 dist[next_node] = weight + next_weight;
4457 pq.emplace(weight + next_weight, next_node);
4464 namespace utf_8_validation {
4467 for(
const auto num: data) {
4471 }
else if(num >> 3 == 30) {
4474 }
else if(num >> 4 == 14) {
4477 }
else if(num >> 5 == 6) {
4480 }
else if(num >> 6 == 2) {
4488 for(
int i = 0; i < len.size(); i++) {
4505 namespace minimum_index_sum_of_two_lists {
4507 unordered_map<string, int> restaurants;
4508 unordered_map<string, int> index1;
4509 unordered_map<string, int> index2;
4510 for(
int i = 0; i < list1.size(); i++) {
4511 restaurants[list1[i]]++;
4512 index1[list1[i]] = i;
4514 for(
int i = 0; i < list2.size(); i++) {
4515 restaurants[list2[i]]++;
4516 index2[list2[i]] = i;
4518 unordered_set<string> optional_restaurants;
4519 for(
auto [restaurant, count]: restaurants) {
4521 optional_restaurants.insert(restaurant);
4524 int min_index_sum = INT_MAX;
4525 for(
const auto &optional_restaurant: optional_restaurants) {
4526 int index_sum = index1[optional_restaurant] + index2[optional_restaurant];
4527 min_index_sum = min(min_index_sum, index_sum);
4530 for(
const auto &optional_restaurant: optional_restaurants) {
4531 int index_sum = index1[optional_restaurant] + index2[optional_restaurant];
4532 if(index_sum == min_index_sum) {
4533 ans.push_back(optional_restaurant);
4540 namespace count_number_of_maximum_bitwise_or_subsets {
4543 for(
const auto num: nums) {
4546 return dfs(0, max, nums);
4550 if((current | target) == current) {
4551 return 1 << nums.size();
4554 vector nums_cpy = nums;
4555 for(
int i = 0; i < nums.size(); i++) {
4556 nums_cpy.erase(nums_cpy.begin());
4557 sum +=
dfs(current | nums[i], target, nums_cpy);
4563 namespace all_oone_data_structure {
4565 str_count = unordered_map<string, int>();
4566 count_str = map<int, unordered_set<string>>();
4621 namespace longest_word_in_dictionary {
4624 for(
const auto &word: words) {
4632 for(
auto *next: node->
nexts) {
4633 if(next !=
nullptr && next->end_of_word) {
4634 string ret =
dfs(str + next->ch, next);
4635 if(ans.length() < ret.length()) {
4644 namespace simple_bank_system {
4646 accounts = unordered_map<int, long long>(balance.size());
4647 for(
int i = 0; i < balance.size(); i++) {
4684 namespace construct_string_from_binary_tree {
4688 if(
root->left !=
nullptr) {
4690 }
else if(
root->right !=
nullptr) {
4693 if(
root->right !=
nullptr) {
4700 namespace maximize_number_of_subsequences_in_a_string {
4703 long long count = 0;
4704 vector<long long> p1count(text.length());
4705 long long p0count = 0;
4707 p1count[text.length() - 1] = 0;
4708 for(
int i = text.length() - 1; i >= 0; i--) {
4709 if(text[i] == pattern[1]) {
4711 }
else if(text[i] == pattern[0]) {
4715 p1count[i - 1] = count;
4718 for(
int i = 0; i < text.length(); i++) {
4719 if(text[i] == pattern[0]) {
4723 ans += max(p0count, count);
4728 namespace minimum_operations_to_halve_array_sum {
4730 long double sum = 0;
4732 priority_queue<long double> pq;
4733 for(
const auto num: nums) {
4737 const long double target = sum / 2;
4738 while(sum > target) {
4739 auto num = pq.top();
4750 namespace minimum_white_tiles_after_covering_with_carpets {
4752 const int n = floor.length();
4753 vector f(numCarpets + 1, vector<int>(n));
4754 f[0][0] = floor[0] % 2;
4755 for(
int i = 1; i < n; ++i) {
4756 f[0][i] = f[0][i - 1] + floor[i] % 2;
4758 for(
int i = 1; i <= numCarpets; ++i) {
4760 for(
int j = carpetLen; j < n; ++j) {
4761 f[i][j] = min(f[i][j - 1] + floor[j] % 2, f[i - 1][j - carpetLen]);
4764 return f[numCarpets][n - 1];
4768 namespace count_hills_and_valleys_in_an_array {
4771 const auto u = unique(nums.begin(), nums.end());
4772 nums.erase(u, nums.end());
4773 for(
int i = 1; i + 1 < nums.size(); i++) {
4774 if(nums[i] > nums[i - 1] && nums[i] > nums[i + 1] || nums[i] < nums[i - 1] && nums[i] < nums[i + 1]) {
4782 namespace count_collisions_on_a_road {
4785 vector<char> status;
4788 for(
char ch: directions) {
4789 if(status.empty()) {
4790 status.push_back(ch);
4793 if(status.back() == ch) {
4796 status.push_back(ch);
4797 count.push_back(current);
4802 count.push_back(current);
4803 for(
int i = 0; i + 1 < status.size(); i++) {
4804 if(status[i] ==
'R' && status[i + 1] ==
'L') {
4805 ans += count[i] + count[i + 1];
4806 }
else if(status[i] ==
'R' && status[i + 1] ==
'S') {
4808 }
else if(status[i] ==
'S' && status[i + 1] ==
'L') {
4809 ans += count[i + 1];
4816 namespace maximum_points_in_an_archery_competition {
4820 for(
unsigned int n = 1; n < 1 << 11; n++) {
4821 int rest = numArrows;
4823 for(
int i = 0; i <= 10; i++) {
4824 if((n & 1 << i) != 0) {
4826 rest -= aliceArrows[11 - i] + 1;
4832 if(maximum < score) {
4838 vector ans(aliceArrows.size(), 0);
4839 for(
int i = 0; i <= 10; i++) {
4840 if((max_n & 1 << i) != 0) {
4841 numArrows -= aliceArrows[11 - i] + 1;
4842 ans[11 - i] = aliceArrows[11 - i] + 1;
4845 ans[0] += numArrows;
4850 namespace the_time_when_the_network_becomes_idle {
4852 unordered_map<int, Node *> um;
4853 unordered_set<int> nodes;
4854 for(
int i = 0; i < patience.size(); i++) {
4855 um[i] =
new Node(i, patience[i]);
4858 for(
auto edge: edges) {
4859 um[edge[0]]->linked.insert(edge[1]);
4860 um[edge[1]]->linked.insert(edge[0]);
4862 auto comp = [](
const pair<int, int> &s1,
const pair<int, int> &s2) ->
bool {
return s1.second > s2.second; };
4863 priority_queue<pair<int, int>, vector<pair<int, int>>,
decltype(comp)> pq;
4864 pq.push(make_pair(0, 0));
4865 while(!nodes.empty()) {
4866 auto [num, len] = pq.top();
4868 if(nodes.contains(num)) {
4870 Node *node = um[num];
4872 for(
auto next: node->
linked) {
4873 if(nodes.contains(next)) {
4874 pq.push(make_pair(next, len + 1));
4880 for(
auto [num, node]: um) {
4882 int resent_num = node->time * 2 / node->patience;
4883 if(node->time * 2 % node->patience == 0) {
4886 ans = max(ans, resent_num * node->patience + 2 * node->time + 1);
4893 namespace two_sum_iv_input_is_a_bst {
4896 unordered_map<int, int> count;
4897 queue<TreeNode *> que;
4899 while(!que.empty()) {
4900 const auto *node = que.front();
4902 s.insert(node->val);
4904 if(node->left !=
nullptr) {
4905 que.push(node->left);
4907 if(node->right !=
nullptr) {
4908 que.push(node->right);
4912 for(
auto it = s.begin(); it != s.end(); ++it) {
4913 int other = k - *it;
4915 if(count[other] > 1) {
4919 }
else if(s.contains(other)) {
4928 namespace remove_colored_pieces_if_both_neighbors_are_the_same_color {
4932 vector
vec(colors.length(),
true);
4934 vec[colors.length() - 1] =
false;
4935 for(
int i = 0; i + 1 < colors.length(); i++) {
4936 if(colors[i] != colors[i + 1]) {
4941 for(
int i = 0; i + 1 < colors.length(); i++) {
4943 if(colors[i] ==
'A') {
4950 return a_count > b_count;
4954 namespace k_th_smallest_in_lexicographical_order {
4959 const int steps =
getSteps(curr, n);
4976 steps += min(last, n) - first + 1;
4978 last = last * 10 + 9;
4984 namespace image_smoother {
4986 const int m = img.size();
4987 const int n = img[0].size();
4988 auto ans = vector(m, vector<int>(n));
4989 for(
int i = 0; i < m; i++) {
4990 for(
int j = 0; j < n; j++) {
4991 pair<int, int> cells[9] = {make_pair(i - 1, j - 1), make_pair(i - 1, j), make_pair(i - 1, j + 1),
4992 make_pair(i, j - 1), make_pair(i, j), make_pair(i, j + 1),
4993 make_pair(i + 1, j - 1), make_pair(i + 1, j), make_pair(i + 1, j + 1)};
4996 for(
int k = 0; k < 9; k++) {
4997 auto [x, y] = cells[k];
4998 if(0 <= x && x < m && 0 <= y && y < n) {
5003 ans[i][j] = sum / count;
5010 namespace factorial_trailing_zeroes {
5012 unsigned int pow5 = 5;
5013 unsigned int pow2 = 2;
5014 unsigned int count5 = 0;
5015 unsigned int count2 = 0;
5016 while(n / pow5 != 0) {
5020 while(n / pow2 != 0) {
5024 return min(count2, count5);
5028 namespace baseball_game {
5031 for(
const string &op: ops) {
5033 const int score1 = stk.back();
5034 const int score2 = *(stk.rbegin() + 1);
5035 stk.push_back(score1 + score2);
5036 }
else if(op ==
"D") {
5037 stk.push_back(2 * stk.back());
5038 }
else if(op ==
"C") {
5045 stk.push_back(score);
5049 for(
const auto score: stk) {
5056 namespace minimum_deletions_to_make_array_beautiful {
5058 vector<int> indexes;
5059 for(
int i = 0; i + 1 < nums.size(); i++) {
5060 if(nums[i] == nums[i + 1]) {
5061 indexes.push_back(i);
5066 for(
const auto index: indexes) {
5067 if(even && index % 2 == 0 || !even && index % 2 != 0) {
5072 if((nums.size() - ans) % 2 != 0) {
5079 namespace find_palindrome_with_fixed_length {
5080 unsigned long long qmi(
unsigned long long m,
unsigned long long k) {
5081 unsigned long long res = 1;
5082 unsigned long long t = m;
5094 vector<long long> ans;
5095 if(intLength == 1) {
5096 for(
auto query: queries) {
5098 ans.push_back(query);
5105 if(intLength == 2) {
5106 for(
auto query: queries) {
5108 ans.push_back(query * 10 + query);
5115 int n = (intLength + 1) / 2;
5116 vector<unsigned long long> q10(n + 1);
5117 for(
int i = 1; i <= n; i++) {
5118 q10[i] =
qmi(10, n - i);
5120 for(
auto query: queries) {
5121 vector<unsigned long long> num;
5122 int n1 = query / q10[1] + 1;
5123 if(n1 == 10 && query % q10[1] == 0) {
5125 for(
int i = 0; i < intLength; i++) {
5137 if(n1 < 10 && query % q10[1] == 0) {
5139 query = (query - 1) % q10[1] + 1;
5144 for(
int i = 2; i <= n; i++) {
5145 int digit = query / q10[i];
5148 }
else if(query != q10[i] && query % q10[i] == 0) {
5150 }
else if(query == q10[i]) {
5154 num.push_back((digit + 10) % 10);
5157 for(
int digit: num) {
5160 int i = num.size() - 1;
5161 if(intLength % 2 != 0) {
5176 namespace find_missing_observations {
5178 const int m = rolls.size();
5179 int sum = (m + n) * mean;
5180 for(
const auto roll: rolls) {
5183 if(sum < n || sum > 6 * n) {
5186 vector ans(n, sum / n);
5188 for(
int i = 0; i < sum; i++) {
5195 namespace binary_number_with_alternating_bits {
5204 for(
int i = 0; i + 1 < str.length(); i++) {
5205 if(str[i] == str[i + 1]) {
5213 namespace maximize_the_confusion_of_an_exam {
5215 if(answerKey.length() == 1) {
5218 vector<int> t_count(answerKey.length());
5219 vector<int> f_count(answerKey.length());
5222 for(
int i = 0; i < t_count.size(); i++) {
5223 if(answerKey[i] ==
'T') {
5228 t_count[i] = t_current;
5229 f_count[i] = f_current;
5232 int r = answerKey.size();
5233 auto check = [&answerKey, &t_count, &f_count, &k](
int len) ->
bool {
5234 for(
int i = 0; i + len <= answerKey.length(); i++) {
5235 int tc = t_count[i + len - 1] - (i - 1 >= 0 ? t_count[i - 1] : 0);
5236 int fc = f_count[i + len - 1] - (i - 1 >= 0 ? f_count[i - 1] : 0);
5237 if(min(tc, fc) <= k) {
5250 const int mid = (l + r) / 2;
5261 namespace find_servers_that_handled_most_number_of_requests {
5266 for(
int i = 0; i < k; i++) {
5267 available.insert(i);
5269 priority_queue<event> events;
5270 for(
int i = 0; i < arrival.size(); i++) {
5271 event e = {arrival[i],
true, i};
5274 while(!events.empty()) {
5275 event e = events.top();
5278 if(!available.empty()) {
5279 auto it = available.lower_bound(e.index % k);
5280 if(it == available.end()) {
5281 it = available.begin();
5283 event next = {e.time + load[e.index],
false, e.index, *it};
5285 available.erase(it);
5289 available.insert(e.server_index);
5290 count[e.server_index]++;
5293 const int maximum = *max_element(count.begin(), count.end());
5294 for(
int i = 0; i < k; i++) {
5295 if(count[i] == maximum) {
5310 namespace self_dividing_numbers {
5319 const int num = ch -
'0';
5337 namespace array_of_doubled_pairs {
5339 multiset<int> positive;
5340 multiset<int, greater<>> negative;
5341 for(
auto num: arr) {
5343 positive.insert(num);
5345 negative.insert(num);
5348 while(!positive.empty()) {
5349 const int num = *positive.begin();
5350 positive.erase(positive.begin());
5351 auto it = positive.find(num * 2);
5352 if(it == positive.end()) {
5357 while(!negative.empty()) {
5358 const int num = *negative.begin();
5359 negative.erase(negative.begin());
5360 auto it = negative.find(num * 2);
5361 if(it == negative.end()) {
5372 namespace strong_password_checker {
5374 const int n = password.length();
5375 bool has_lower =
false;
5376 bool has_upper =
false;
5377 bool has_digit =
false;
5378 for(
const char ch: password) {
5379 if(islower(ch) != 0) {
5381 }
else if(isupper(ch) != 0) {
5383 }
else if(isdigit(ch) != 0) {
5387 const int categories =
static_cast<int>(has_lower) +
static_cast<int>(has_upper) +
static_cast<int>(has_digit);
5390 return max(6 - n, 3 - categories);
5397 for(
const char ch: password) {
5401 replace += count / 3;
5406 replace += count / 3;
5407 return max(replace, 3 - categories);
5417 for(
const char ch: password) {
5421 if(
remove > 0 && count >= 3) {
5422 if(count % 3 == 0) {
5426 }
else if(count % 3 == 1) {
5432 replace += count / 3;
5437 if(
remove > 0 && count >= 3) {
5438 if(count % 3 == 0) {
5441 }
else if(count % 3 == 1) {
5445 replace += count / 3;
5448 const int use2 = min({replace, rm2,
remove / 2});
5452 const int use3 = min(replace,
remove / 3);
5455 return n - 20 + max(replace, 3 - categories);
5459 namespace number_of_ways_to_select_buildings {
5461 const unsigned int n = s.length();
5462 vector<unsigned int> prev0(n, 0);
5463 vector<unsigned int> prev1(n, 0);
5464 vector<unsigned int> post0(n, 0);
5465 vector<unsigned int> post1(n, 0);
5466 unsigned current0 = 0;
5467 unsigned current1 = 0;
5468 for(
int i = 0; i < n; i++) {
5469 prev0[i] = current0;
5470 prev1[i] = current1;
5479 for(
int i = n - 1; i >= 0; i--) {
5480 post0[i] = current0;
5481 post1[i] = current1;
5489 for(
unsigned i = 0; i < n; i++) {
5491 ans +=
static_cast<long long>(prev1[i]) * post1[i];
5493 ans +=
static_cast<long long>(prev0[i]) * post0[i];
5500 namespace sum_of_scores_of_built_strings {
5502 const int n = s.length();
5507 for(
int i = 1; i < n; ++i) {
5508 if(i <= r && z[i - l] < r - i + 1) {
5511 z[i] = max(0, r - i + 1);
5512 while(i + z[i] < n && s[z[i]] == s[i + z[i]]) {
5516 if(i + z[i] - 1 > r) {
5529 namespace minimum_number_of_operations_to_convert_time {
5531 const int current_h = (current[0] -
'0') * 10 + (current[1] -
'0');
5532 const int current_m = (current[3] -
'0') * 10 + (current[4] -
'0');
5533 const int correct_h = (correct[0] -
'0') * 10 + (correct[1] -
'0');
5534 const int correct_m = (correct[3] -
'0') * 10 + (correct[4] -
'0');
5535 int diff = correct_h * 60 + correct_m - (current_h * 60 + current_m);
5554 namespace find_players_with_zero_or_one_losses {
5556 map<unsigned, unsigned> lose;
5557 for(
auto match: matches) {
5558 lose[match[0]] += 0;
5559 lose[match[1]] += 1;
5561 vector<vector<int>> ans(2);
5564 for(
auto [player, count]: lose) {
5566 ans1.push_back(player);
5567 }
else if(count == 1) {
5568 ans2.push_back(player);
5580 namespace maximum_candies_allocated_to_k_children {
5582 sort(candies.begin(), candies.end());
5584 for(
const auto candy: candies) {
5594 unsigned long long count = 0;
5595 for(
auto it = candies.rbegin(); it != candies.rend() && *it >= r; ++it) {
5606 const int m = (l + r) / 2;
5607 unsigned long long count = 0;
5608 for(
auto it = candies.rbegin(); it != candies.rend() && *it >= m; ++it) {
5616 }
else if(count < k) {
5624 namespace encrypt_and_decrypt_strings {
5626 for(
int i = 0; i < keys.size(); ++i) {
5627 mp[keys[i] -
'a'] = values[i];
5629 for(
const auto &s: dictionary) {
5636 for(
const char ch: word1) {
5637 const auto &s =
mp[ch -
'a'];
5647 if(
count.contains(word2)) {
5649 return count[word2];
5656 namespace range_sum_query_mutable {
5659 const int n =
nums.size();
5662 for(
int i = 0; i < n; i++) {
5679 return accumulate(
nums.begin() + b1 *
size + i1,
nums.begin() + b1 *
size + i2 + 1, 0);
5681 const int sum1 = accumulate(
nums.begin() + b1 *
size + i1,
nums.begin() + b1 *
size +
size, 0);
5682 const int sum2 = accumulate(
nums.begin() + b2 *
size,
nums.begin() + b2 *
size + i2 + 1, 0);
5683 const int sum3 = accumulate(
sum.begin() + b1 + 1,
sum.begin() + b2, 0);
5684 return sum1 + sum2 + sum3;
5688 namespace process_restricted_friend_requests {
5691 vector<bool> ans(requests.size());
5692 auto check = [&uf, &restrictions](
int x,
int y) ->
bool {
5698 for(
auto &restriction: restrictions) {
5699 int i = uf.
find(restriction[0]);
5700 int j = uf.
find(restriction[1]);
5704 if(i == x && j == y) {
5710 for(
int i = 0; i < requests.size(); i++) {
5711 if(check(requests[i][0], requests[i][1])) {
5712 uf.
unite(requests[i][0], requests[i][1]);
5722 namespace prime_number_of_set_bits_in_binary_representation {
5725 const unordered_set primes{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61};
5726 for(
unsigned i =
left; i <=
right; i++) {
5727 if(primes.contains(popcount(i))) {
5735 namespace minimum_height_trees {
5740 vector<vector<int>> adj(n);
5741 for(
auto &edge: edges) {
5742 adj[edge[0]].emplace_back(edge[1]);
5743 adj[edge[1]].emplace_back(edge[0]);
5746 vector parent(n, -1);
5755 path.emplace_back(y);
5758 const int m = path.size();
5760 return {path[m / 2 - 1], path[m / 2]};
5762 return {path[m / 2]};
5766 const int n = adj.size();
5768 vector<bool> visit(n);
5773 while(!qu.empty()) {
5774 const int curr = qu.front();
5777 for(
auto &v: adj[curr]) {
5789 namespace rotate_string {
5791 if(s.length() != goal.length()) {
5795 return s.find(goal) != string::npos;
5799 namespace n_ary_tree_level_order_traversal {
5801 queue<pair<int, Node *>> q;
5802 vector<vector<int>> ans;
5803 if(
root ==
nullptr) {
5806 q.push(make_pair(0,
root));
5808 auto [level, node] = q.front();
5809 if(ans.size() == level) {
5812 ans[level].push_back(node->val);
5814 for(
auto *next: node->children) {
5815 q.push(make_pair(level + 1, next));
5822 namespace reaching_points {
5824 while(tx > sx && ty > sy && tx != ty) {
5831 if(tx == sx && ty == sy) {
5835 return ty > sy && (ty - sy) % tx == 0;
5838 return tx > sx && (tx - sx) % ty == 0;
5844 namespace maximum_product_after_k_increments {
5846 priority_queue<int, vector<int>, greater<int>> pq;
5847 for(
auto num: nums) {
5851 const int num = pq.top();
5856 while(!pq.empty()) {
5857 const int num = pq.top();
5866 namespace maximum_total_beauty_of_the_gardens {
5868 const int n = flowers.size();
5869 sort(flowers.begin(), flowers.end());
5870 for(
int i = 0; i < n; i++) {
5871 flowers[i] = min(flowers[i], target);
5874 vector<long long> sum(n + 1, 0);
5875 for(
int i = 0; i < n; i++) {
5876 sum[i + 1] = sum[i] + flowers[i];
5878 for(
int i = 0, j = 0; i <= n; i++) {
5879 const long long rest = newFlowers - (
static_cast<long long>(target) * (n - i) - (sum[n] - sum[i]));
5881 while(j < i && rest >=
static_cast<long long>(flowers[j]) * j - sum[j]) {
5885 ans = max(ans,
static_cast<long long>(full) * (n - i) + (j == 0 ? 0 :
static_cast<long long>(partial) * min(
static_cast<long long>(target - 1), (rest + sum[j]) / j)));
5887 if(i < n && flowers[i] == target) {
5895 namespace count_numbers_with_unique_digits {
5900 vector<int> dp(n + 1);
5902 for(
int i = 2; i <= n; ++i) {
5903 dp[i] = dp[i - 1] * (10 - (i - 1));
5906 for(
int i = 1; i <= n; ++i) {
5913 namespace number_of_lines_to_write_string {
5917 for(
int i = 0; i < s.length(); i++) {
5918 if(current + widths[s[i] -
'a'] > 100) {
5922 current += widths[s[i] -
'a'];
5924 return {lines, current};
5928 namespace permutation_in_string {
5930 if(s1.length() > s2.length()) {
5933 unordered_map<char, int> um1;
5934 unordered_map<char, int> um2;
5938 for(
int i = 0; i < s1.length(); i++) {
5944 for(
int i = 0; i + s1.length() < s2.length(); i++) {
5946 um2[s2[i + s1.length()]]++;
5947 if(um2[s2[i]] == 0) {
5958 namespace insert_delete_getrandom_o1 {
5960 generator = default_random_engine(time(
nullptr));
5965 if(
static_cast<unsigned int>(
map.contains(val)) != 0U) {
5968 nums.push_back(val);
5974 if(
static_cast<unsigned int>(
map.contains(val)) == 0U) {
5977 const int index =
map[val];
5978 const int last =
nums.back();
5989 namespace projection_area_of_3d_shapes {
5991 const int n = grid.size();
5995 auto grid_xz = vector(51, vector(51, 0));
5996 auto grid_yz = vector(51, vector(51, 0));
5997 for(
int i = 0; i < n; i++) {
5998 for(
int j = 0; j < n; j++) {
5999 if(grid[i][j] != 0) {
6002 for(
int k = 0; k < grid[i][j]; k++) {
6008 for(
int i = 0; i < 51; i++) {
6009 for(
int j = 0; j < 51; j++) {
6010 if(grid_xz[i][j] != 0) {
6013 if(grid_yz[i][j] != 0) {
6018 return xy + yz + xz;
6022 namespace design_parking_system {
6024 : big(big), medium(medium), small(small) {}
6049 default:
return false;
6054 namespace range_sum_query_immutable {
6056 pref_sum = vector<int>(nums.size());
6058 for(
int i = 1; i < nums.size(); i++) {
6066 namespace house_robber {
6068 if(nums.size() == 1) {
6071 vector<int> dp(nums.size());
6073 dp[1] = max(nums[0], nums[1]);
6074 for(
int i = 2; i < nums.size(); i++) {
6075 dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
6077 return dp[nums.size() - 1];
6081 namespace triangle {
6083 vector<vector<int>> dp = triangle;
6084 for(
int i = 1; i < triangle.size(); i++) {
6085 for(
int j = 0; j < triangle[i].size(); j++) {
6087 dp[i][j] = dp[i - 1][j] + triangle[i][j];
6088 }
else if(j == triangle[i].size() - 1) {
6089 dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
6091 dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
6095 int ans = dp.back()[0];
6096 for(
int i = 0; i < dp.back().size(); i++) {
6097 ans = min(ans, dp.back()[i]);
6103 namespace lowest_common_ancestor_of_a_binary_search_tree {
6110 while(current !=
nullptr) {
6112 current = current->
parent;
6115 while(current !=
nullptr) {
6119 current = current->
parent;
6126 if(tn->
val == low) {
6128 }
else if(tn->
val == high) {
6131 if(tn->
left !=
nullptr) {
6136 if(tn->
right !=
nullptr) {
6144 namespace shuffle_an_array {
6149 vector<int> cpy =
nums;
6150 while(!cpy.empty()) {
6151 const int idx = rand() % cpy.size();
6152 ans.emplace_back(cpy[idx]);
6153 cpy.erase(cpy.begin() + idx);
6159 : nums(nums) { srand(time(
nullptr)); }
6162 namespace find_all_anagrams_in_a_string {
6165 unordered_map<char, int> um_p;
6169 unordered_map<char, int> um_s;
6170 for(
int i = 0; i < p.length(); i++) {
6174 ans.emplace_back(0);
6176 for(
int i = p.length(); i < s.length(); i++) {
6178 um_s[s[i - p.length()]]--;
6179 if(um_s[s[i - p.length()]] == 0) {
6180 um_s.erase(s[i - p.length()]);
6183 ans.emplace_back(i - p.length() + 1);
6190 namespace subarray_product_less_than_k {
6195 for(
int j = 0; j < nums.size(); j++) {
6197 while(i <= j && prod >= k) {
6207 namespace minimum_size_subarray_sum {
6209 int r = nums.size() - 1;
6213 while(l >= 0 && l <= r) {
6214 if(nums[l] >= target) {
6217 while(l - 1 >= 0 && sum + nums[l - 1] < target) {
6226 ans = min(ans, r - l + 1);
6234 ans = min(ans, r - l + 1);
6236 }
while(sum >= target && r >= l);
6242 namespace populating_next_right_pointers_in_each_node_ii {
6244 if(
root ==
nullptr) {
6249 queue<pair<int, Node *>> q;
6250 if(
root->left !=
nullptr) {
6251 q.emplace(1,
root->left);
6253 if(
root->right !=
nullptr) {
6254 q.emplace(1,
root->right);
6257 auto [level, node] = q.front();
6259 if(level == prev_level) {
6260 prev_node->
next = node;
6264 if(node->left !=
nullptr) {
6265 q.emplace(level + 1, node->left);
6267 if(node->right !=
nullptr) {
6268 q.emplace(level + 1, node->right);
6275 namespace subtree_of_another_tree {
6277 if(
root ==
nullptr) {
6280 queue<TreeNode *> q;
6283 auto *
const node = q.front();
6285 if(
equal(node, subRoot)) {
6288 if(node->left !=
nullptr) {
6291 if(node->right !=
nullptr) {
6292 q.push(node->right);
6299 if(
static_cast<int>(tn1 ==
nullptr) +
static_cast<int>(tn2 ==
nullptr) == 1) {
6302 if(tn1 ==
nullptr && tn2 ==
nullptr) {
6305 if(tn1->
val != tn2->
val) {
6308 if(
static_cast<int>(tn1->
left ==
nullptr) +
static_cast<int>(tn2->
left ==
nullptr) == 1) {
6311 if(
static_cast<int>(tn1->
right ==
nullptr) +
static_cast<int>(tn2->
right ==
nullptr) == 1) {
6318 namespace shortest_path_in_binary_matrix {
6320 int n = grid.size();
6321 auto levels = vector(n, vector(n, -1));
6322 auto cmp = [&n](
const tuple<int, int, int> &t1,
const tuple<int, int, int> &t2) {
6323 const auto &[level1, x1, y1] = t1;
6324 const auto &[level2, x2, y2] = t2;
6325 const int dx1 = abs(n - 1 - x1);
6326 const int dy1 = abs(n - 1 - y1);
6327 const int dx2 = abs(n - 1 - x2);
6328 const int dy2 = abs(n - 1 - y2);
6329 return level1 + dx1 + dy1 - min(dx1, dy1) > level2 + dx2 + dy2 - min(dx2, dy2);
6331 priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>,
decltype(
cmp)> pq(
cmp);
6332 if(grid[0][0] == 0 && grid[n - 1][n - 1] == 0) {
6333 pq.push(make_tuple(1, 0, 0));
6337 while(!pq.empty()) {
6338 auto [level, x, y] = pq.top();
6339 if(x == n - 1 && y == n - 1) {
6343 if(levels[x][y] == -1 || levels[x][y] > level) {
6344 levels[x][y] = level;
6348 pair<int, int> nexts[8] = {make_pair(x - 1, y - 1), make_pair(x - 1, y), make_pair(x - 1, y + 1),
6349 make_pair(x, y - 1), make_pair(x, y + 1),
6350 make_pair(x + 1, y - 1), make_pair(x + 1, y), make_pair(x + 1, y + 1)};
6351 for(
auto [next_x, next_y]: nexts) {
6352 if(next_x >= 0 && next_x < n && next_y >= 0 && next_y < n && grid[next_x][next_y] == 0 && (levels[next_x][next_y] == -1 || levels[next_x][next_y] > level + 1)) {
6353 pq.push(make_tuple(level + 1, next_x, next_y));
6361 namespace surrounded_regions {
6363 const int m = board.size();
6364 const int n = board[0].size();
6365 for(
int i = 0; i < n; i++) {
6366 if(board[0][i] ==
'O') {
6369 if(board[m - 1][i] ==
'O') {
6370 dfs(board, m - 1, i);
6373 for(
int j = 0; j < m; j++) {
6374 if(board[j][0] ==
'O') {
6377 if(board[j][n - 1] ==
'O') {
6378 dfs(board, j, n - 1);
6381 for(
int i = 0; i < m; i++) {
6382 for(
int j = 0; j < n; j++) {
6383 if(board[i][j] ==
'O') {
6386 if(board[i][j] ==
'D') {
6395 const int m = board.size();
6396 const int n = board[0].size();
6397 pair<int, int> nexts[4] = {{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}};
6398 for(
auto [next_x, next_y]: nexts) {
6399 if(next_x >= 0 && next_x < m && next_y >= 0 && next_y < n && board[next_x][next_y] ==
'O') {
6400 dfs(board, next_x, next_y);
6406 namespace all_paths_from_source_to_target {
6408 vector<vector<int>> ans;
6410 for(
auto &path: ans) {
6412 path = vector(path.rbegin(), path.rend());
6417 int Solution::dfs(vector<vector<int>> &graph, vector<vector<int>> &ans,
int cur) {
6419 if(cur == graph.size() - 1) {
6420 ans.emplace_back(vector(1, cur));
6423 for(
const auto next: graph[cur]) {
6424 const int n =
dfs(graph, ans, next);
6426 for(
int i = ans.size() - 1, j = 0; j < n; i--, j++) {
6427 ans[i].emplace_back(cur);
6434 namespace permutations_ii {
6436 vector<vector<int>> ans;
6438 dfs(s, vector<int>(), nums);
6439 ans.reserve(s.size());
6440 for(
const auto &
vec: s) {
6441 ans.emplace_back(
vec);
6446 void Solution::dfs(set<vector<int>> &s,
const vector<int> ¤t, vector<int> rest) {
6451 for(
auto it = rest.begin(); it != rest.end(); ++it) {
6452 vector<int> next_current = current;
6453 vector<int> next_rest = rest;
6454 next_current.push_back(*it);
6455 next_rest.erase(next_rest.begin() + (it - rest.begin()));
6456 dfs(s, next_current, next_rest);
6461 namespace combination_sum {
6463 sort(candidates.begin(), candidates.end());
6464 return recurse(candidates, target, 0);
6468 vector<vector<int>> ans;
6469 for(
int i = index; i < candidates.size(); i++) {
6470 auto &candidate = candidates[i];
6471 if(candidate == target) {
6472 ans.emplace_back(vector(1, candidate));
6473 }
else if(target - candidate >= 1) {
6474 auto res =
recurse(candidates, target - candidate, i);
6475 for(
auto &
vec: res) {
6476 vec.push_back(candidate);
6485 namespace combination_sum_ii {
6487 sort(candidates.begin(), candidates.end());
6488 const auto ret =
recurse(candidates, target, -10);
6489 vector<vector<int>> ans(ret.size());
6490 for(
int i = 0; i < ret.size(); i++) {
6491 ans[i] = vector<int>(ret[i].size());
6492 for(
int j = 0; j < ret[i].size(); j++) {
6493 ans[i][j] = candidates[ret[i][j]];
6500 vector<vector<int>> ans;
6501 for(
int i = max(0, index + 1); i < candidates.size(); i++) {
6502 if(!(i > 0 && candidates[i] == candidates[i - 1] && index != i - 1)) {
6503 const auto &candidate = candidates[i];
6504 if(candidate == target) {
6505 ans.emplace_back(vector(1, i));
6506 }
else if(target - candidate >= 1) {
6507 auto res =
recurse(candidates, target - candidate, i);
6508 for(
auto &
vec: res) {
6519 namespace house_robber_ii {
6521 if(nums.size() == 1) {
6524 auto vec1 = vector(nums.begin(), nums.end() - 1);
6525 auto vec2 = vector(nums.begin() + 1, nums.end());
6530 namespace jump_game {
6532 vector can(nums.size(),
false);
6535 for(
int i = 0; i < nums.size(); i++) {
6536 if(can[i] && min(i + nums[i],
static_cast<int>(nums.size() - 1)) > last) {
6537 for(
int j = last + 1; j <= i + nums[i] && j < nums.size(); j++) {
6540 last = min(i + nums[i],
static_cast<int>(nums.size() - 1));
6547 namespace jump_game_ii {
6549 const int n = nums.size();
6553 for(
int i = 0; i < n; i++) {
6554 if(i + nums[i] >= last) {
6565 namespace unique_paths {
6567 vector dp(m, vector(n, 0));
6568 dp[m - 1][n - 1] = 1;
6569 for(
int i = m - 1; i >= 0; i--) {
6570 for(
int j = n - 1; j >= 0; j--) {
6572 dp[i][j] += dp[i + 1][j];
6575 dp[i][j] += dp[i][j + 1];
6583 namespace longest_palindromic_substring {
6585 const int n = s.size();
6593 vector dp(n, vector<int>(n));
6595 for(
int i = 0; i < n; i++) {
6600 for(
int L = 2; L <= n; L++) {
6602 for(
int i = 0; i < n; i++) {
6604 const int j = L + i - 1;
6616 dp[i][j] = dp[i + 1][j - 1];
6621 if(dp[i][j] != 0 && j - i + 1 > maxLen) {
6627 return s.substr(begin, maxLen);
6631 namespace arithmetic_slices {
6633 const int n = nums.size();
6634 vector<int> diff(n - 1);
6635 for(
int i = 0; i < n - 1; i++) {
6636 diff[i] = nums[i + 1] - nums[i];
6638 vector<int> consecutive;
6641 for(
int i = 0; i < n - 1; i++) {
6642 if(diff[i] == diff[prev]) {
6645 consecutive.emplace_back(cnt);
6650 consecutive.emplace_back(cnt);
6652 for(
const auto num: consecutive) {
6654 ans += (num - 1) * num / 2;
6661 namespace decode_ways {
6663 vector dp(s.length(), 0);
6664 for(
int i = 0; i < dp.size(); i++) {
6666 if(
'1' <= s[i] && s[i] <=
'9') {
6667 dp[i] += i - 1 >= 0 ? dp[i - 1] : 1;
6670 if(i - 1 >= 0 && (s[i - 1] ==
'1' &&
'0' <= s[i] && s[i] <=
'9' || s[i - 1] ==
'2' &&
'0' <= s[i] && s[i] <=
'6')) {
6671 dp[i] += i - 2 >= 0 ? dp[i - 2] : 1;
6682 namespace word_break {
6684 vector end(s.length(),
false);
6686 for(
const auto &word: wordDict) {
6690 for(
int i = 1; i < s.length(); i++) {
6703 for(; i < s.length(); i++) {
6704 node = node->
nexts[s[i] -
'a'];
6705 if(node ==
nullptr) {
6715 namespace longest_increasing_subsequence {
6717 const int n = nums.size();
6720 for(
int i = 0; i < n; i++) {
6721 for(
int j = i + 1; j < n; j++) {
6722 if(nums[j] > nums[i]) {
6723 dp[j] = max(dp[j], dp[i] + 1);
6726 ans = max(ans, dp[i]);
6732 namespace number_of_longest_increasing_subsequence {
6734 const int n = nums.size();
6735 vector dp(n, map<unsigned, unsigned>());
6736 for(
int i = 0; i < n; i++) {
6739 unsigned max_len = 1;
6740 for(
int i = 0; i < n; i++) {
6741 for(
int j = i + 1; j < n; j++) {
6742 auto &[len, cnt] = *dp[i].rbegin();
6743 if(nums[j] > nums[i]) {
6744 dp[j][len + 1] += cnt;
6745 max_len = max(max_len, len + 1);
6750 for(
int i = 0; i < n; i++) {
6751 ans += dp[i][max_len];
6757 namespace longest_common_subsequence {
6759 vector dp(text1.length(), vector(text2.length(), 0));
6760 for(
int i = 0; i < text1.length(); i++) {
6761 for(
int j = 0; j < text2.length(); j++) {
6762 if(text1[i] == text2[j]) {
6763 dp[i][j] = (i - 1 < 0 || j - 1 < 0 ? 0 : dp[i - 1][j - 1]) + 1;
6765 dp[i][j] = max(i - 1 >= 0 ? dp[i - 1][j] : 0, j - 1 >= 0 ? dp[i][j - 1] : 0);
6769 return dp.back().back();
6773 namespace delete_operation_for_two_strings {
6776 return word1.length() + word2.length() - 2 * lcs;
6780 namespace edit_distance {
6783 vector dp(word1.length() + 1, vector<int>(word2.length() + 1));
6785 for(
int j = 0; j <= word2.length(); j++) {
6788 for(
int i = 0; i <= word1.length(); i++) {
6791 for(
int i = 1; i <= word1.length(); i++) {
6792 for(
int j = 1; j <= word2.length(); j++) {
6793 if(word1[i - 1] == word2[j - 1]) {
6794 dp[i][j] = dp[i - 1][j - 1];
6796 dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
6800 return dp.back().back();
6804 namespace coin_change {
6806 vector dp(amount + 1, -1);
6808 for(
const auto &coin: coins) {
6809 if(coin <= amount) {
6813 for(
unsigned i = 0; i <= amount; i++) {
6815 for(
const auto &coin: coins) {
6816 if(i + coin <=
static_cast<unsigned>(amount)) {
6817 if(dp[i + coin] == -1) {
6818 dp[i + coin] = dp[i] + 1;
6820 dp[i + coin] = min(dp[i + coin], dp[i] + 1);
6830 namespace integer_break {
6833 vector<int> dp(n + 1);
6837 for(
int i = 3; i <= n; i++) {
6838 for(
int j = 1; j < i; j++) {
6839 dp[i] = max(dp[i], dp[j] * dp[i - j]);
6840 dp[i] = max(dp[i], j * dp[i - j]);
6841 dp[i] = max(dp[i], dp[j] * (i - j));
6842 dp[i] = max(dp[i], j * (i - j));
6849 namespace max_points_on_a_line {
6852 for(
auto &p1: points) {
6853 unordered_map<long double, int> us;
6855 for(
auto &p2: points) {
6856 if(p2[0] != p1[0]) {
6857 us[
static_cast<long double>(p2[1] - p1[1]) /
static_cast<long double>(p2[0] - p1[0])]++;
6862 for(
auto &[k, v]: us) {
6863 cnt = max(cnt, v + 1);
6865 ans = max(ans, cnt);
6871 namespace group_anagrams {
6873 vector<string> strs_sorted = strs;
6874 unordered_map<string, vector<string>> um;
6875 for(
auto &str: strs_sorted) {
6876 sort(str.begin(), str.end());
6877 if(!um.contains(str)) {
6878 um[str] = vector<string>();
6881 for(
int i = 0; i < strs.size(); i++) {
6882 um[strs_sorted[i]].emplace_back(strs[i]);
6884 vector<vector<string>> ans;
6885 ans.reserve(um.size());
6886 for(
auto &[k, v]: um) {
6887 ans.emplace_back(v);
6893 namespace sort_colors {
6902 const int pivot = nums[(l + r) / 2];
6904 while(nums[++lp] < pivot) {}
6905 while(nums[--rp] > pivot) {}
6907 swap(nums[lp], nums[rp]);
6911 qsort(nums, rp + 1, r);
6915 namespace top_k_frequent_elements {
6917 unordered_map<int, int> um;
6918 for(
auto num: nums) {
6921 vector<int>
vec(um.size());
6923 for(
auto &[_, v]: um) {
6926 sort(
vec.rbegin(),
vec.rend());
6927 unordered_set<int> us;
6928 for(i = 0; i < k; i++) {
6932 for(
auto [num, v]: um) {
6933 if(us.contains(v)) {
6934 ans.emplace_back(num);
6941 namespace kth_largest_element_in_an_array {
6943 sort(nums.rbegin(), nums.rend());
6948 namespace merge_intervals {
6950 vector<vector<int>> ans;
6951 auto comp = [](
const vector<int> &a,
const vector<int> &b) {
return a[0] < b[0]; };
6952 sort(intervals.begin(), intervals.end(), comp);
6953 int start = intervals[0][0];
6954 int end = intervals[0][1];
6955 for(
int i = 1; i < intervals.size(); i++) {
6956 if(intervals[i][0] <= end) {
6957 end = max(end, intervals[i][1]);
6959 ans.emplace_back(vector{start, end});
6960 start = intervals[i][0];
6961 end = intervals[i][1];
6964 ans.emplace_back(vector{start, end});
6969 namespace search_a_2d_matrix_ii {
6972 bool Solution::search(
const vector<vector<int>> &matrix,
int target,
int x_start,
int x_end,
int y_start,
int y_end) {
6973 const int minimum = min(x_end - x_start, y_end - y_start);
6974 vector<int> diag1(minimum + 1);
6975 for(
int i = 0; i <= minimum; i++) {
6976 diag1[i] = matrix[x_start + i][y_start + i];
6978 const auto it = lower_bound(diag1.begin(), diag1.end(), target);
6979 const int x = x_start + it - diag1.begin();
6980 const int y = y_start + it - diag1.begin();
6981 if(it != diag1.end()) {
6985 if(it == diag1.begin()) {
6988 if(
search(matrix, target, x_start, x - 1, y, y_end)) {
6991 if(
search(matrix, target, x, x_end, y_start, y - 1)) {
6994 if(
search(matrix, target, x, x_end, y, y_end)) {
6998 if(x > x_end && y > y_end) {
7001 if(x > x_end &&
search(matrix, target, x_start, x_end, y, y_end)) {
7004 if(y > y_end &&
search(matrix, target, x, x_end, y_start, y_end)) {
7012 namespace serialize_and_deserialize_binary_tree {
7014 if(
root ==
nullptr) {
7020 queue<TreeNode *> q;
7025 if(node ==
nullptr) {
7026 vec.emplace_back(
"null");
7029 vec.emplace_back(to_string(node->
val));
7031 q.push(node->
right);
7033 int end =
vec.size() - 1;
7034 while(
vec[end] ==
"null" && end > 0) {
7038 for(
int i = 1; i <= end; i++) {
7039 oss <<
',' <<
vec[i];
7050 data = data.substr(1, data.size() - 2);
7051 auto *
const str =
static_cast<char *
>(malloc((data.length() + 1) *
sizeof(
char)));
7052 memcpy(str, data.c_str(), (data.length() + 1) *
sizeof(
char));
7053 for(
const char *item = strtok(str,
","); item !=
nullptr; item = strtok(
nullptr,
",")) {
7054 vec.emplace_back(
string(item));
7056 queue<TreeNode **> q;
7059 for(
const auto &str:
vec) {
7060 auto *
const node = q.front();
7066 q.push(&(*node)->left);
7067 q.push(&(*node)->right);
7074 namespace task_scheduler {
7077 return tasks.size();
7081 unordered_map<char, int> task_cnt;
7082 unordered_map<char, int> processing;
7083 for(
char task: tasks) {
7087 bool finished =
true;
7089 for(
const auto &[task, cnt]: task_cnt) {
7093 if(processing[task] <= 0) {
7094 maximum = max(maximum, cnt);
7100 for(
auto &[task, rest]: processing) {
7103 for(
auto &[task, cnt]: task_cnt) {
7104 if(maximum == cnt && processing[task] <= 0) {
7106 processing[task] = n;
7115 namespace design_hashmap {
7117 arr = array<list<pair<int, int>>,
SZ>();
7118 for(
unsigned i = 0; i <
SZ; i++) {
7119 arr[i] = list<pair<int, int>>();
7124 const unsigned slot =
static_cast<unsigned>(key) %
SZ;
7125 for(
auto &[k, v]:
arr[slot]) {
7131 arr[slot].emplace_back(key, value);
7135 const unsigned slot =
static_cast<unsigned>(key) %
SZ;
7136 for(
auto &[k, v]:
arr[slot]) {
7145 const unsigned slot =
static_cast<unsigned>(key) %
SZ;
7146 for(
auto it =
arr[slot].begin(); it !=
arr[slot].end(); ++it) {
7147 if(it->first == key) {
7148 arr[slot].erase(it);
7155 namespace spiral_matrix_ii {
7157 vector ans(n, vector(n, 0));
7162 for(
int i = 0; i < n * n; i++) {
7182 if(flag && (nx < 0 || nx >= n || ny < 0 || ny >= n || ans[nx][ny] != 0)) {
7195 namespace non_overlapping_intervals {
7197 if(intervals.empty()) {
7201 sort(intervals.begin(), intervals.end(), [](
const auto &u,
const auto &v) { return u[1] < v[1]; });
7203 const int n = intervals.size();
7204 int right = intervals[0][1];
7206 for(
int i = 1; i < n; ++i) {
7207 if(intervals[i][0] >=
right) {
7209 right = intervals[i][1];
7216 namespace product_of_array_except_self {
7218 vector<int>
left(nums.size());
7219 vector<int>
right(nums.size());
7221 for(
int i = 0; i <
left.size(); i++) {
7226 for(
int i =
left.size() - 1; i >= 0; i--) {
7230 vector<int> ans(nums.size());
7231 for(
int i = 0; i < nums.size(); i++) {
7238 namespace subarray_sum_equals_k {
7240 unordered_map<int, int> um;
7244 for(
const auto &num: nums) {
7246 count += um[ps - k];
7253 namespace partition_labels {
7255 unordered_map<char, unsigned> last;
7257 for(
int i = 0; i < s.length(); i++) {
7260 for(
int i = 0; i < s.length();) {
7261 unsigned last_pos = i;
7263 for(
int j = i; j <= last_pos; j++) {
7264 last_pos = max(last_pos, last[s[j]]);
7266 ans.emplace_back(last_pos - i + 1);
7273 namespace repeated_dna_sequences {
7275 vector<unsigned short>
vec(s.length());
7276 for(
int i = 0; i < s.length(); i++) {
7293 if(s.length() < 10) {
7296 unordered_map<unsigned, string> um;
7297 unordered_map<unsigned, unsigned> cnt;
7298 for(
int i = 0; i < 10; i++) {
7302 um[hsv] = s.substr(0, 10);
7304 const unsigned f = 262144;
7305 for(
int i = 10; i < s.length(); i++) {
7306 hsv -=
vec[i - 10] * f;
7309 um[hsv] = s.substr(i - 9, 10);
7313 for(
auto &[k, v]: um) {
7315 ans.emplace_back(v);
7322 namespace design_linked_list {
7334 for(
int i = 0; i < index && current !=
nullptr; i++) {
7335 current = current->
next;
7337 return current ==
nullptr ? -1 : current->
val;
7341 auto *
const node =
new ListNode(val);
7350 auto *
const node =
new ListNode(val);
7360 auto *
const node =
new ListNode(val);
7362 for(
int i = 0; i < index - 1 && current !=
nullptr; i++) {
7363 current = current->
next;
7365 if(current ==
nullptr) {
7370 current->
next = node;
7371 if(current ==
tail) {
7382 for(
int i = 0; i < index - 1 && current !=
nullptr; i++) {
7383 current = current->
next;
7385 if(current ==
nullptr) {
7388 const auto *
const p = current->
next;
7399 namespace delete_node_in_a_bst {
7402 while(current->
right !=
nullptr) {
7404 current = current->
right;
7411 while(current->
left !=
nullptr) {
7413 current = current->
left;
7419 if(node->
right !=
nullptr) {
7426 if(node->
left !=
nullptr) {
7433 if(
prev !=
nullptr) {
7446 if(
root ==
nullptr) {
7450 while(current !=
nullptr && current->
val != key) {
7451 if(current->
val == key) {
7455 if(current->
val < key) {
7456 current = current->
right;
7458 current = current->
left;
7461 if(current ==
nullptr) {
7464 if(
root->left ==
nullptr &&
root->right ==
nullptr) {
7472 namespace missing_element_in_sorted_array {
7474 unordered_set<int> us;
7475 for(
auto num: nums) {
7478 if(
missing(nums, nums.size() - 1) < k) {
7479 return nums[0] + k + nums.size() - 1;
7482 int r = nums.size() - 1;
7485 return nums[l] + k -
missing(nums, l);
7487 const int m = (l + r) / 2;
7490 }
else if(
missing(nums, m) >= k) {
7500 namespace find_a_peak_element_ii {
7502 const int mid = (l + r) / 2;
7506 for(
int i = 0; i < mat.size(); i++) {
7507 for(
int j = mid - 1; j <= mid + 1; j++) {
7508 if(maximum <
get(mat, i, j)) {
7509 maximum =
get(mat, i, j);
7515 if(max_col == mid || l + 1 == r) {
7516 return {max_row, max_col};
7518 if(max_col == mid + 1) {
7527 if(i >= 0 && i < mat.size() && j >= 0 && j < mat[0].size()) {
7534 namespace divide_chocolate {
7536 int l = sweetness[0];
7538 for(
auto s: sweetness) {
7544 return count(sweetness, r) == k + 1 ? r : l;
7546 const int m = (l + r) / 2;
7547 const int c =
count(sweetness, m);
7560 for(
const auto s: sweetness) {
7571 namespace shortest_distance_to_target_color {
7574 unordered_map<int, vector<int>> um;
7575 for(
int i = 0; i < colors.size(); i++) {
7576 um[colors[i]].emplace_back(i);
7578 for(
auto &[k,
vec]: um) {
7579 sort(
vec.begin(),
vec.end());
7581 for(
auto &query: queries) {
7584 vector<int> &
vec = um[c];
7585 auto g = lower_bound(
vec.begin(),
vec.end(), i, less());
7586 auto l = lower_bound(
vec.rbegin(),
vec.rend(), i, greater());
7587 if(g ==
vec.end() && l ==
vec.rend()) {
7588 ans.emplace_back(-1);
7589 }
else if(g ==
vec.end()) {
7590 ans.emplace_back(abs(*l - i));
7591 }
else if(l ==
vec.rend()) {
7592 ans.emplace_back(abs(*g - i));
7594 ans.emplace_back(min(abs(*l - i), abs(*g - i)));
7601 namespace meeting_scheduler {
7604 auto cmp = [](
const vector<int> &vec1,
const vector<int> &vec2) ->
bool {
7605 if(vec1[1] != vec2[1]) {
7606 return vec1[1] < vec2[1];
7608 return vec1[0] < vec2[0];
7610 sort(slots1.begin(), slots1.end(),
cmp);
7611 sort(slots2.begin(), slots2.end(),
cmp);
7612 for(
auto it1 = slots1.begin(), it2 = slots2.begin(); it1 != slots1.end() && it2 != slots2.end();) {
7613 pair<int, int> p =
merge(*it1, *it2);
7614 if(p.second - p.first >= duration) {
7615 return {p.first, p.first + duration};
7617 if(
cmp(*it1, *it2)) {
7626 pair<int, int>
Solution::merge(
const vector<int> &vec1,
const vector<int> &vec2) {
return {max(vec1[0], vec2[0]), min(vec1[1], vec2[1])}; }
7629 namespace find_the_duplicate_number {
7631 int maximum = nums[0];
7632 int minimum = nums[0];
7633 for(
const auto &num: nums) {
7634 maximum = max(maximum, num);
7635 minimum = min(minimum, num);
7640 const int m = (l + r) / 2;
7642 if(c == m - l + 1) {
7644 }
else if(c > m - l + 1) {
7655 for(
const auto &num: nums) {
7656 if(l <= num && num <= r) {
7664 namespace trapping_rain_water {
7666 vector
lmax(height.size(), 0);
7667 vector rmax(height.size(), 0);
7668 int maximum = height[0];
7669 for(
int i = 0; i < height.size(); i++) {
7670 maximum = max(maximum, height[i]);
7673 maximum = height.back();
7674 for(
int i = height.size() - 1; i >= 0; i--) {
7675 maximum = max(maximum, height[i]);
7679 for(
int i = 0; i < height.size(); i++) {
7680 ans += min(
lmax[i], rmax[i]) - height[i];
7686 namespace product_of_two_run_length_encoded_arrays {
7688 vector<vector<int>> ans;
7691 for(
int i1 = 0, i2 = 0; i1 < encoded1.size() && i2 < encoded2.size();) {
7692 const int len = min(encoded1[i1][1] - p1, encoded2[i2][1] - p2);
7693 const int v = encoded1[i1][0] * encoded2[i2][0];
7694 if(!ans.empty() && ans.back()[0] == v) {
7695 ans.back()[1] += len;
7697 vector
vec = {v, len};
7698 ans.emplace_back(
vec);
7702 if(p1 >= encoded1[i1][1]) {
7706 if(p2 >= encoded2[i2][1]) {
7715 namespace longest_substring_with_at_most_two_distinct_characters {
7717 unordered_map<char, int> um;
7718 for(
int i = 0; i < len; i++) {
7721 size_t ans = um.size();
7722 for(
int i = 0, j = len; j < s.length(); i++, j++) {
7728 ans = min(ans, um.size());
7737 const int mid = (l + r) / 2 + 1;
7749 namespace longest_substring_with_at_most_k_distinct_characters {
7757 const int mid = (l + r) / 2 + 1;
7769 namespace max_consecutive_ones_iii {
7772 int r = nums.size();
7774 const int mid = (l + r) / 2 + 1;
7790 for(
int i = 0; i < len; i++) {
7796 for(
int i = 0, j = len; j < nums.size(); i++, j++) {
7803 ans = min(ans, current);
7809 namespace sliding_window_maximum {
7812 for(
int i = 0; i < k; i++) {
7816 for(
int i = 0, j = k; j < nums.size(); i++, j++) {
7817 ans.emplace_back(*
ms.rbegin());
7818 ms.erase(
ms.lower_bound(nums[i]));
7821 ans.emplace_back(*
ms.rbegin());
7826 namespace minimum_window_substring {
7831 unordered_map<char, int> umt;
7832 unordered_map<char, int> ums;
7838 while(l <= r && r < s.length() && l < s.length()) {
7839 while(!
valid(ums, umt) && r + 1 < s.length()) {
7842 while(
valid(ums, umt) && l < s.length()) {
7844 if(r - l + 1 < ans.length()) {
7845 ans = s.substr(l, r - l + 1);
7852 if(r == s.length() - 1) {
7859 bool Solution::valid(unordered_map<char, int> &ums,
const unordered_map<char, int> &umt) {
7860 for(
const auto &[k, v]: umt) {
7861 if(!ums.contains(k) || ums[k] < v) {
7869 namespace walls_and_gates {
7871 const int m = rooms.size();
7872 const int n = rooms[0].size();
7873 queue<tuple<int, int, int>> q;
7874 for(
int i = 0; i < m; i++) {
7875 for(
int j = 0; j < n; j++) {
7876 if(rooms[i][j] == 0) {
7882 auto [d, x, y] = q.front();
7884 pair<int, int> nexts[4] = {{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}};
7885 for(
auto &[next_x, next_y]: nexts) {
7886 if(next_x >= 0 && next_y >= 0 && next_x < m && next_y < n && rooms[next_x][next_y] != -1 && rooms[next_x][next_y] != 0 && (rooms[next_x][next_y] == INT_MAX || rooms[next_x][next_y] > d + 1)) {
7887 rooms[next_x][next_y] = d + 1;
7888 q.push({d + 1, next_x, next_y});
7895 namespace pacific_atlantic_waterflow {
7897 const int m = heights.size();
7898 const int n = heights[0].size();
7899 unordered_set<pair<int, int>,
myhash,
myeq> pacific;
7900 unordered_set<pair<int, int>,
myhash,
myeq> atlantic;
7901 queue<pair<int, int>> q;
7902 vector<vector<int>> ans;
7904 for(
int i = 0; i < m; i++) {
7906 pacific.insert({i, 0});
7908 for(
int i = 1; i < n; i++) {
7910 pacific.insert({0, i});
7913 auto [x, y] = q.front();
7915 pair<int, int> nexts[4] = {{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}};
7916 for(
auto &[next_x, next_y]: nexts) {
7917 if(next_x >= 0 && next_y >= 0 && next_x < m && next_y < n && heights[next_x][next_y] >= heights[x][y] && !pacific.contains({next_x, next_y})) {
7918 pacific.insert({next_x, next_y});
7919 q.push({next_x, next_y});
7924 for(
int i = 0; i < m; i++) {
7926 atlantic.insert({i, n - 1});
7928 for(
int i = 0; i < n - 1; i++) {
7930 atlantic.insert({m - 1, i});
7933 auto [x, y] = q.front();
7935 pair<int, int> nexts[4] = {{x + 1, y}, {x - 1, y}, {x, y + 1}, {x, y - 1}};
7936 for(
auto &[next_x, next_y]: nexts) {
7937 if(next_x >= 0 && next_y >= 0 && next_x < m && next_y < n && heights[next_x][next_y] >= heights[x][y] && !atlantic.contains({next_x, next_y})) {
7938 atlantic.insert({next_x, next_y});
7939 q.push({next_x, next_y});
7944 for(
const auto &p: atlantic) {
7945 if(pacific.contains(p)) {
7946 vector
vec = {p.first, p.second};
7947 ans.emplace_back(
vec);
7950 sort(ans.begin(), ans.end());
7954 bool myeq::operator()(
const pair<int, int> &p1,
const pair<int, int> &p2)
const {
return p1 == p2; }
7959 namespace find_all_the_lonely_nodes {
7962 queue<TreeNode *> q;
7967 if(node->
left ==
nullptr && node->
right !=
nullptr) {
7968 ans.emplace_back(node->
right->
val);
7969 }
else if(node->
right ==
nullptr && node->
left !=
nullptr) {
7970 ans.emplace_back(node->
left->
val);
7972 if(node->
left !=
nullptr) {
7975 if(node->
right !=
nullptr) {
7976 q.push(node->
right);
7983 namespace kill_process {
7985 unordered_map<int, Node *> um;
7986 for(
const auto &v: pid) {
7987 um[v] =
new Node(v);
7989 for(
int i = 0; i < pid.size(); i++) {
7991 um[ppid[i]]->children.insert(um[pid[i]]);
7998 Node *node = q.front();
8000 ans.emplace_back(node->
val);
8009 namespace all_nodes_distance_k_in_binary_tree {
8012 return {target->
val};
8014 unordered_map<TreeNode *, Node *> um;
8016 queue<TreeNode *> q1;
8019 while(!q1.empty()) {
8022 if(tn->
left !=
nullptr) {
8025 um[tn->
left]->siblings.insert(um[tn]);
8026 um[tn]->siblings.insert(um[tn->left]);
8028 if(tn->
right !=
nullptr) {
8031 um[tn->
right]->siblings.insert(um[tn]);
8032 um[tn]->siblings.insert(um[tn->right]);
8035 Node *node = um[target];
8036 unordered_set<Node *> vis;
8037 queue<pair<int, Node *>> q2;
8039 while(!q2.empty()) {
8040 auto [d, nd] = q2.front();
8043 for(
auto *sibling: nd->siblings) {
8044 if(!vis.contains(sibling)) {
8045 vis.insert(sibling);
8047 ans.emplace_back(sibling->val);
8049 q2.push({d + 1, sibling});
8058 namespace open_the_lock {
8060 unordered_set<string> deads;
8061 unordered_set<string> vis;
8062 for(
auto &deadend: deadends) {
8063 deads.insert(deadend);
8065 auto get_nexts = [](
const string &code) {
8066 vector ans(8, code);
8067 ans[0][0] = (ans[0][0] -
'0' + 10 + 1) % 10 +
'0';
8068 ans[1][0] = (ans[1][0] -
'0' + 10 - 1) % 10 +
'0';
8069 ans[2][1] = (ans[2][1] -
'0' + 10 + 1) % 10 +
'0';
8070 ans[3][1] = (ans[3][1] -
'0' + 10 - 1) % 10 +
'0';
8071 ans[4][2] = (ans[4][2] -
'0' + 10 + 1) % 10 +
'0';
8072 ans[5][2] = (ans[5][2] -
'0' + 10 - 1) % 10 +
'0';
8073 ans[6][3] = (ans[6][3] -
'0' + 10 + 1) % 10 +
'0';
8074 ans[7][3] = (ans[7][3] -
'0' + 10 - 1) % 10 +
'0';
8077 queue<pair<int, string>> q;
8078 q.push({0,
"0000"});
8080 auto [step, code] = q.front();
8081 if(code == target) {
8086 if(deads.contains(code)) {
8089 auto nexts = get_nexts(code);
8090 for(
auto &next: nexts) {
8091 if(!vis.contains(next)) {
8093 if(next == target) {
8096 q.push({step + 1, next});
8104 namespace number_of_operations_to_make_network_connected {
8106 vector<unordered_set<int>> g(n);
8107 for(
auto &connection: connections) {
8108 g[connection[0]].insert(connection[1]);
8109 g[connection[1]].insert(connection[0]);
8112 int free_edges_cnt = 0;
8113 unordered_set<int> vis;
8114 for(
int i = 0; i < n; i++) {
8115 if(!vis.contains(i)) {
8118 dfs(edge_cnt, node_cnt, vis, i, g);
8120 free_edges_cnt += edge_cnt / 2 - node_cnt + 1;
8123 if(free_edges_cnt < group_cnt - 1) {
8126 return group_cnt - 1;
8129 void Solution::dfs(
int &edge_cnt,
int &node_cnt, unordered_set<int> &vis,
int node, vector<unordered_set<int>> &g) {
8131 edge_cnt += g[node].size();
8133 for(
auto next: g[node]) {
8134 if(!vis.contains(next)) {
8135 dfs(edge_cnt, node_cnt, vis, next, g);
8141 namespace minimum_cost_to_make_at_least_one_valid_path_in_a_grid {
8143 const int m = grid.size();
8144 const int n = grid[0].size();
8145 vector g(m, vector<Node *>(n,
nullptr));
8146 for(
int i = 0; i < m; i++) {
8147 for(
int j = 0; j < n; j++) {
8148 g[i][j] =
new Node(i, j);
8151 for(
int i = 0; i < m; i++) {
8152 for(
int j = 0; j < n; j++) {
8153 pair<int, int> nexts[4] = {{i + 1, j}, {i - 1, j}, {i, j + 1}, {i, j - 1}};
8154 for(
auto [x, y]: nexts) {
8155 if(x >= 0 && x < m && y >= 0 && y < n) {
8156 g[i][j]->siblings.insert(make_pair(g[x][y], 1));
8161 switch(grid[i][j]) {
8175 if(x >= 0 && x < m && y >= 0 && y < n) {
8176 g[i][j]->siblings[g[x][y]] = 0;
8180 priority_queue<pair<int, Node *>, vector<pair<int, Node *>>,
mycmp> pq;
8181 unordered_set<Node *> vis;
8182 pq.push({0, g[0][0]});
8183 while(!pq.empty()) {
8184 auto [cost, node] = pq.top();
8186 if(vis.contains(node)) {
8190 if(node->x == m - 1 && node->y == n - 1) {
8193 for(
auto [sibling, c]: node->siblings) {
8194 if(!vis.contains(sibling)) {
8195 pq.push({cost + c, sibling});
8203 if(p1.first != p2.first) {
8204 return p1.first > p2.first;
8206 return p1.second->x + p1.second->y < p2.second->x + p2.second->y;
8210 namespace critical_connections_in_a_network {
8212 vector<unordered_set<int>> g(n);
8213 for(
auto &conn: connections) {
8214 g[conn[0]].insert(conn[1]);
8215 g[conn[1]].insert(conn[0]);
8217 vector<vector<int>> ans;
8220 unordered_set<int> vis;
8222 for(
int i = 0; i < n; i++) {
8225 tarjan(-1, step, dfn, i, g, low, ans);
8231 void Solution::tarjan(
int prev,
int &step, vector<int> &dfn,
int node, vector<unordered_set<int>> &g, vector<int> &low, vector<vector<int>> &ans) {
8234 for(
const auto &next: g[node]) {
8235 if(dfn[next] == -1) {
8236 tarjan(node, ++step, dfn, next, g, low, ans);
8239 low[node] = min(low[node], low[next]);
8241 if(dfn[node] < low[next]) {
8242 ans.push_back({node, next});
8248 namespace factor_combinations {
8250 vector<vector<int>> ans;
8251 for(
int i = minimum; i <= sqrt(n); i++) {
8253 ans.push_back({i, n / i});
8255 for(
auto &
vec: res) {
8257 ans.back().insert(ans.back().end(),
vec.begin(),
vec.end());
8267 namespace decode_string {
8271 vector<string> strs;
8272 while(i < s.length()) {
8273 if(isalpha(s[i]) != 0) {
8274 cnt.emplace_back(1);
8275 strs.emplace_back(
string(1, s[i]));
8277 }
else if(isdigit(s[i]) != 0) {
8279 while(j < s.length() && isdigit(s[j]) != 0) {
8282 cnt.emplace_back(stoi(s.substr(i, j - i)));
8289 }
else if(s[j] ==
']') {
8293 strs.emplace_back(
decodeString(s.substr(i + 1, j - i - 1)));
8298 for(i = 0; i < cnt.size(); i++) {
8299 for(
int j = 0; j < cnt[i]; j++) {
8307 namespace n_queens {
8309 vector<vector<string>> ans;
8310 const vector board(n, vector(n,
false));
8311 dfs(board, 0, n, ans);
8315 void Solution::dfs(
const vector<vector<bool>> &board,
int line,
int n, vector<vector<string>> &ans) {
8320 for(
int i = 0; i < n; i++) {
8321 if(
valid(board, n, line, i)) {
8322 vector<vector<bool>> next = board;
8323 next[line][i] =
true;
8324 dfs(next, line + 1, n, ans);
8330 for(
int i = 0; i < x; i++) {
8335 for(
int i = x, j = y; i >= 0 && i < n && j >= 0 && j < n; i--, j--) {
8340 for(
int i = x, j = y; i >= 0 && i < n && j >= 0 && j < n; i--, j++) {
8349 vector<string> ans(board.size());
8350 for(
int i = 0; i < board.size(); i++) {
8352 for(
int j = 0; j < board[i].size(); j++) {
8353 oss << (board[i][j] ?
'Q' :
'.');
8361 namespace sudoku_solver {
8364 bool Solution::dfs(
const vector<vector<char>> &board, vector<vector<char>> &ans) {
8365 for(
int i = 0; i < 9; i++) {
8366 for(
int j = 0; j < 9; j++) {
8367 if(board[i][j] ==
'.') {
8368 for(
char c =
'1'; c <=
'9'; c++) {
8369 if(
valid(board, i, j, c)) {
8370 bool haveValid =
true;
8371 vector<vector<char>> next = board;
8373 if(
dfs(next, ans)) {
8387 for(
int i = 0; i < 9; i++) {
8388 if(board[i][y] == num) {
8392 for(
int j = 0; j < 9; j++) {
8393 if(board[x][j] == num) {
8397 for(
int i = 0; i < 3; i++) {
8398 for(
int j = 0; j < 3; j++) {
8399 if(board[x / 3 * 3 + i][y / 3 * 3 + j] == num) {
8408 namespace regular_expression_matching {
8412 if(pi == p.length() && si == s.length()) {
8415 if(pi == p.length()) {
8418 const char c = p[pi++];
8419 bool multiple =
false;
8420 if(pi < p.length() && p[pi] ==
'*') {
8425 if(si == s.length()) {
8428 if(c ==
'.' || s[si] == c) {
8429 return dfs(s, p, si + 1, pi);
8434 for(
int i = si; i <= s.length(); i++) {
8435 if(
dfs(s, p, i, pi)) {
8443 if(
dfs(s, p, ++i, pi)) {
8447 return dfs(s, p, si, pi);
8451 namespace different_ways_to_add_parentheses {
8454 bool allDigit =
true;
8455 for(
int i = start; i <= end; i++) {
8456 if(!isdigit(expr[i])) {
8458 vector
left =
eval(expr, start, i - 1);
8460 for(
const auto &l:
left) {
8461 for(
const auto &r:
right) {
8464 ans.emplace_back(l + r);
8467 ans.emplace_back(l - r);
8470 ans.emplace_back(l * r);
8479 for(
int i = start; i <= end; i++) {
8481 val += expr[i] -
'0';
8483 ans.emplace_back(val);
8489 vector ans =
eval(expression, 0, expression.length() - 1);
8490 sort(ans.begin(), ans.end());
8495 namespace remove_invalid_parentheses {
8498 unordered_set<string> currSet;
8502 for(
auto &str: currSet) {
8504 ans.emplace_back(str);
8507 sort(ans.begin(), ans.end());
8510 unordered_set<string> nextSet;
8511 for(
auto &str: currSet) {
8512 for(
int i = 0; i < str.size(); i++) {
8513 if(i > 0 && str[i] == str[i - 1]) {
8516 if(str[i] ==
'(' || str[i] ==
')') {
8517 nextSet.insert(str.substr(0, i) + str.substr(i + 1, str.size()));
8528 for(
const char c: str) {
8531 }
else if(c ==
')') {
8543 namespace median_of_two_sorted_arrays {
8545 if(nums1.size() > nums2.size()) {
8549 const int m = nums1.size();
8550 const int n = nums2.size();
8554 int median1 = 0, median2 = 0;
8560 const int j = (m + n + 1) / 2 - i;
8563 int nums_im1 = i == 0 ? INT_MIN : nums1[i - 1];
8564 int nums_i = i == m ? INT_MAX : nums1[i];
8565 int nums_jm1 = j == 0 ? INT_MIN : nums2[j - 1];
8566 int nums_j = j == n ? INT_MAX : nums2[j];
8568 if(nums_im1 <= nums_j) {
8569 median1 = max(nums_im1, nums_jm1);
8570 median2 = min(nums_i, nums_j);
8577 return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
8581 namespace count_of_smaller_numbers_after_self {
8583 vector<int> resultList;
8587 Init(nums.size() + 5);
8589 for(
int i =
static_cast<int>(nums.size()) - 1; i >= 0; --i) {
8590 const int id =
getId(nums[i]);
8591 resultList.push_back(
Query(
id - 1));
8595 reverse(resultList.begin(), resultList.end());
8605 while(pos <
c.size()) {
8623 a.assign(nums.begin(), nums.end());
8624 sort(
a.begin(),
a.end());
8625 a.erase(unique(
a.begin(),
a.end()),
a.end());
8631 namespace best_time_to_buy_and_sell_stock_with_cooldown {
8633 if(prices.empty()) {
8637 const int n = prices.size();
8638 int f0 = -prices[0];
8641 for(
int i = 1; i < n; ++i) {
8642 tie(f0, f1, f2) = make_tuple(max(f0, f2 - prices[i]), f0 + prices[i], max(f1, f2));
8649 namespace best_time_to_buy_and_sell_stock_with_transaction_fee {
8651 const int n = prices.size();
8652 vector<int> holding(n);
8653 vector<int> not_holding(n);
8655 holding[0] = -prices[0];
8656 for(
int i = 1; i < n; i++) {
8657 not_holding[i] = max(not_holding[i - 1], holding[i - 1] + prices[i] - fee);
8658 holding[i] = max(holding[i - 1], not_holding[i - 1] - prices[i]);
8660 return max(not_holding.back(), holding.back());
8664 namespace split_array_largest_sum {
8668 for(
auto num: nums) {
8673 const int mid = (l + r) / 2;
8674 const int cnt =
get_m(nums, mid);
8677 }
else if(cnt > m) {
8679 }
else if(cnt < m) {
8689 for(
const auto num: nums) {
8690 if(c + num > msum) {
8703 namespace house_robber_iii {
8710 if(
um.contains({node, steal})) {
8711 return um[{node, steal}];
8713 int ans = steal ? node->
val : 0;
8714 if(node->
left !=
nullptr) {
8715 const int ns =
dfs(!steal, node->
left);
8716 const int s = !steal ?
dfs(steal, node->
left) : 0;
8719 if(node->
right !=
nullptr) {
8720 const int ns =
dfs(!steal, node->
right);
8721 const int s = !steal ?
dfs(steal, node->
right) : 0;
8724 um[{node, steal}] = ans;
8728 size_t myhash::operator()(
const pair<TreeNode *, bool> &p)
const {
return (uint64_t) p.first * 2 + (p.second ? 1 : 0); }
8730 bool myeq::operator()(
const pair<TreeNode *, bool> &p1,
const pair<TreeNode *, bool> &p2)
const {
return p1.first == p2.first && p1.second == p2.second; }
8733 namespace maximal_square {
8735 const int m = matrix.size();
8736 const int n = matrix[0].size();
8737 vector horizontal_next_1s(m, vector(n, 0));
8738 vector vertical_next_1s(m, vector(n, 0));
8739 vector dp(m + 1, vector(n + 1, 0));
8740 for(
int i = 0; i < m; i++) {
8742 for(
int j = n - 1; j >= 0; j--) {
8743 if(matrix[i][j] ==
'1') {
8748 horizontal_next_1s[i][j] = cnt;
8751 for(
int j = 0; j < n; j++) {
8753 for(
int i = m - 1; i >= 0; i--) {
8754 if(matrix[i][j] ==
'1') {
8759 vertical_next_1s[i][j] = cnt;
8763 for(
int i = m - 1; i >= 0; i--) {
8764 for(
int j = n - 1; j >= 0; j--) {
8765 if(matrix[i][j] ==
'1') {
8766 dp[i][j] = min(min(vertical_next_1s[i][j], horizontal_next_1s[i][j]), 1 + dp[i + 1][j + 1]);
8767 ans = max(ans, dp[i][j]);
8775 namespace maximal_rectangle {
8777 const int m = matrix.size();
8781 const int n = matrix[0].size();
8782 vector
left(m, vector(n, 0));
8784 for(
int i = 0; i < m; i++) {
8785 for(
int j = 0; j < n; j++) {
8786 if(matrix[i][j] ==
'1') {
8787 left[i][j] = (j == 0 ? 0 :
left[i][j - 1]) + 1;
8793 for(
int j = 0; j < n; j++) {
8795 vector<int>
up(m, 0),
down(m, 0);
8798 for(
int i = 0; i < m; i++) {
8799 while(!stk.empty() &&
left[stk.top()][j] >=
left[i][j]) {
8802 up[i] = stk.empty() ? -1 : stk.top();
8806 for(
int i = m - 1; i >= 0; i--) {
8807 while(!stk.empty() &&
left[stk.top()][j] >=
left[i][j]) {
8810 down[i] = stk.empty() ? m : stk.top();
8814 for(
int i = 0; i < m; i++) {
8815 const int height =
down[i] -
up[i] - 1;
8816 int area = height *
left[i][j];
8817 ret = max(ret, area);
8824 namespace predict_the_winner {
8826 const int length = nums.size();
8827 auto dp = vector<int>(length);
8828 for(
int i = 0; i < length; i++) {
8831 for(
int i = length - 2; i >= 0; i--) {
8832 for(
int j = i + 1; j < length; j++) {
8833 dp[j] = max(nums[i] - dp[j], nums[j] - dp[j - 1]);
8836 return dp[length - 1] >= 0;
8840 namespace palindrome_partitioning {
8843 const vector<string>
vec;
8844 vector<vector<string>> ans;
8850 for(
int i = start, j = end; i < j; i++, j--) {
8858 void Solution::dfs(
const vector<string> ¤t,
const string &s, vector<vector<string>> &ans,
int start,
int cursor) {
8859 if(cursor == s.length() - 1 &&
is_palindromic(s, start, cursor)) {
8860 ans.emplace_back(current);
8861 ans.back().emplace_back(s.substr(start, cursor - start + 1));
8864 if(cursor >= s.length() - 1 || start >= s.length()) {
8868 vector next = current;
8869 next.emplace_back(s.substr(start, cursor - start + 1));
8870 dfs(next, s, ans, cursor + 1, cursor + 1);
8872 dfs(current, s, ans, start, cursor + 1);
8876 namespace palindrome_partitioning_ii {
8879 for(
int i = 0; i < s.length(); i++) {
8880 for(
int j = 0; i - j >= 0 && i + j < s.length() && s[i - j] == s[i + j]; j++) {
8884 for(
int i = 0; i < s.length() - 1; i++) {
8885 if(s[i] == s[i + 1]) {
8886 for(
int j = 0; i - j >= 0 && i + 1 + j < s.length() && s[i - j] == s[i + 1 + j]; j++) {
8891 vector dp(s.length(), 2000);
8893 for(
int j = 1; j < dp.size(); j++) {
8898 for(
int i = j; i >= 0; i--) {
8900 dp[j] = min(dp[j], dp[i - 1] + 1);
8908 namespace partition_equal_subset_sum {
8910 const int n = nums.size();
8914 const int sum = accumulate(nums.begin(), nums.end(), 0);
8915 const int maxNum = *max_element(nums.begin(), nums.end());
8919 const int target = sum / 2;
8920 if(maxNum > target) {
8923 vector dp(n, vector(target + 1, 0));
8924 for(
int i = 0; i < n; i++) {
8927 dp[0][nums[0]] =
true;
8928 for(
int i = 1; i < n; i++) {
8929 const int num = nums[i];
8930 for(
int j = 1; j <= target; j++) {
8932 dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
8934 dp[i][j] = dp[i - 1][j];
8938 return dp[n - 1][target];
8942 namespace minimum_cost_for_tickets {
8944 unordered_set<int> us;
8946 for(
const auto &day: days) {
8948 end = max(end, day);
8950 vector dp(end + 1, 0);
8951 for(
int i = 1; i <= end; i++) {
8952 dp[i] = i - 1 >= 0 ? dp[i - 1] : 0;
8953 if(us.contains(i)) {
8955 dp[i] = min(dp[i], (i - 7 >= 0 ? dp[i - 7] : 0) + costs[1]);
8956 dp[i] = min(dp[i], (i - 30 >= 0 ? dp[i - 30] : 0) + costs[2]);
8963 namespace best_time_to_buy_and_sell_stock_iii {
8965 vector dp(5, vector<long>(prices.size(), -10000000000));
8972 dp[1][0] = -prices[0];
8973 for(
int i = 1; i < prices.size(); i++) {
8974 dp[0][i] = dp[0][i - 1];
8975 dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] - prices[i]);
8976 dp[2][i] = max(dp[2][i - 1], dp[1][i - 1] + prices[i]);
8977 dp[3][i] = max(dp[3][i - 1], dp[2][i - 1] - prices[i]);
8978 dp[4][i] = max(dp[4][i - 1], dp[3][i - 1] + prices[i]);
8980 long ans = dp[0].back();
8981 for(
int i = 1; i <= 4; i++) {
8982 ans = max(ans, dp[i].back());
8988 namespace dungeon_game {
8990 const int n = dungeon.size(), m = dungeon[0].size();
8991 vector dp(n + 1, vector(m + 1, INT_MAX));
8992 dp[n][m - 1] = dp[n - 1][m] = 1;
8993 for(
int i = n - 1; i >= 0; --i) {
8994 for(
int j = m - 1; j >= 0; --j) {
8995 const int minn = min(dp[i + 1][j], dp[i][j + 1]);
8996 dp[i][j] = max(minn - dungeon[i][j], 1);
9003 namespace course_schedule {
9005 vector<int> in(numCourses);
9006 vector<unordered_set<int>> out(numCourses);
9007 unordered_set<int> learned;
9008 for(
auto &prerequisite: prerequisites) {
9009 in[prerequisite[1]]++;
9010 out[prerequisite[0]].insert(prerequisite[1]);
9012 bool hasChange =
true;
9015 for(
int i = 0; i < numCourses; i++) {
9016 if(in[i] == 0 && !learned.contains(i)) {
9019 for(
auto &next: out[i]) {
9025 for(
int i = 0; i < numCourses; i++) {
9034 namespace course_schedule_ii {
9037 vector<int> in(numCourses);
9038 vector<unordered_set<int>> out(numCourses);
9039 unordered_set<int> learned;
9040 for(
auto &prerequisite: prerequisites) {
9041 in[prerequisite[0]]++;
9042 out[prerequisite[1]].insert(prerequisite[0]);
9044 bool hasChange =
true;
9047 for(
int i = 0; i < numCourses; i++) {
9048 if(in[i] == 0 && !learned.contains(i)) {
9051 ans.emplace_back(i);
9052 for(
auto &next: out[i]) {
9058 if(ans.size() == numCourses) {
9065 namespace longest_increasing_path_in_a_matrix {
9067 if(matrix.empty() || matrix[0].empty()) {
9070 rows = matrix.size();
9072 auto outdegrees = vector(
rows, vector<int>(
columns));
9073 for(
int i = 0; i <
rows; ++i) {
9074 for(
int j = 0; j <
columns; ++j) {
9075 for(
int k = 0; k < 4; ++k) {
9076 const int newRow = i +
dirs[k][0], newColumn = j +
dirs[k][1];
9077 if(newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn <
columns && matrix[newRow][newColumn] > matrix[i][j]) {
9083 queue<pair<int, int>> q;
9084 for(
int i = 0; i <
rows; ++i) {
9085 for(
int j = 0; j <
columns; ++j) {
9086 if(outdegrees[i][j] == 0) {
9094 const int size = q.size();
9095 for(
int i = 0; i < size; ++i) {
9096 const auto cell = q.front();
9098 const int row = cell.first, column = cell.second;
9099 for(
int k = 0; k < 4; ++k) {
9100 int newRow = row +
dirs[k][0], newColumn = column +
dirs[k][1];
9101 if(newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn <
columns && matrix[newRow][newColumn] < matrix[row][column]) {
9102 --outdegrees[newRow][newColumn];
9103 if(outdegrees[newRow][newColumn] == 0) {
9104 q.push({newRow, newColumn});
9114 namespace parallel_courses {
9116 vector<node *> nodes(n);
9117 for(
int i = 1; i <= n; i++) {
9118 nodes[i - 1] =
new node(i, 0);
9120 for(
const auto &relation: relations) {
9121 nodes[relation[1] - 1]->pred.insert(nodes[relation[0] - 1]);
9122 nodes[relation[0] - 1]->out++;
9125 unordered_set<int> vis;
9128 for(
int i = 0; i < n; i++) {
9129 if(nodes[i]->out == 0) {
9130 if(vis.contains(i)) {
9135 for(
node *next: nodes[i]->pred) {
9137 next->len = max(next->len, nodes[i]->len + 1);
9143 for(
int i = 0; i < n; i++) {
9144 if(nodes[i]->out != 0) {
9147 ans = max(ans, nodes[i]->len);
9153 namespace alien_dictionary {
9155 unordered_map<char, unordered_set<char>> g;
9156 unordered_map<char, int> in;
9158 unordered_set<char> charset;
9159 for(
const auto &word: words) {
9160 for(
const auto &ch: word) {
9164 for(
const auto &ch: charset) {
9165 g[ch] = unordered_set<char>();
9169 for(
const auto &word: words) {
9170 max_len = max(max_len,
static_cast<int>(word.length()));
9172 for(
int i = 0; i < max_len; i++) {
9173 unordered_map<string, vector<string>> um;
9174 for(
const auto &word: words) {
9175 if(word.length() >= i) {
9176 um[i > 0 ? word.substr(0, i) :
""].emplace_back(word);
9179 for(
const auto &[pred, section]: um) {
9180 for(
int j = 0, k = 1; k < section.size(); j++, k++) {
9181 if(i < section[j].length() && i < section[k].length()) {
9182 if(section[j][i] != section[k][i]) {
9183 g[section[j][i]].insert(section[k][i]);
9185 }
else if(i < section[j].length()) {
9191 for(
const auto &[k, section]: g) {
9192 for(
const auto &n: section) {
9197 unordered_set<char> vis;
9200 for(
const auto &[ch, n]: in) {
9201 if(n == 0 && !vis.contains(ch)) {
9205 for(
const auto &nc: g[ch]) {
9211 for(
const auto &[ch, n]: in) {
9220 namespace single_number_iii {
9223 for(
const int num: nums) {
9227 const int lsb = xorsum == INT_MIN ? xorsum : xorsum & -xorsum;
9228 int type1 = 0, type2 = 0;
9229 for(
const int num: nums) {
9236 return {type1, type2};
9240 namespace shortest_path_to_get_all_keys {
9242 priority_queue<frame> pq;
9243 int m = grid.size();
9244 int n = grid[0].size();
9248 unordered_map<unsigned, vector<vector<int>>> min_step;
9249 for(
int i = 0; i < m; i++) {
9250 for(
int j = 0; j < n; j++) {
9251 if(grid[i][j] ==
START) {
9254 }
else if(isupper(grid[i][j])) {
9259 frame start(start_x, start_y, lock_cnt);
9261 while(!pq.empty()) {
9264 if(f.
keys.size() == lock_cnt) {
9267 if(!min_step.contains(f.
get_mask())) {
9268 min_step[f.
get_mask()] = vector(m, vector(n, INT_MAX));
9274 const pair<int, int> nexts[4] = {{f.
x + 1, f.
y}, {f.
x - 1, f.
y}, {f.
x, f.
y + 1}, {f.
x, f.
y - 1}};
9275 for(
const auto &[n_x, n_y]: nexts) {
9276 if(n_x >= 0 && n_x < m && n_y >= 0 && n_y < n && grid[n_x][n_y] !=
WALL) {
9277 if(islower(grid[n_x][n_y])) {
9282 next.
keys.insert(grid[n_x][n_y]);
9283 if(!min_step.contains(next.
get_mask())) {
9284 min_step[next.
get_mask()] = vector(m, vector(n, INT_MAX));
9289 }
else if(isupper(grid[n_x][n_y])) {
9290 if(f.
keys.contains(
static_cast<char>(tolower(grid[n_x][n_y])))) {
9295 if(!min_step.contains(next.
get_mask())) {
9296 min_step[next.
get_mask()] = vector(m, vector(n, INT_MAX));
9307 if(!min_step.contains(next.
get_mask())) {
9308 min_step[next.
get_mask()] = vector(m, vector(n, INT_MAX));
9324 return keys.size() < f.
keys.size();
9329 for(
const auto &key:
keys) {
9330 mask |= 1 << key -
'a';
9336 namespace minimum_number_of_k_consecutive_bit_flips {
9338 const int n = nums.size();
9339 int ans = 0, revCnt = 0;
9340 for(
int i = 0; i < n; ++i) {
9341 if(i >= k && nums[i - k] > 1) {
9345 if(nums[i] == revCnt) {
9358 namespace design_underground_system {
9364 for(
const auto t:
um[startStation][endStation]) {
9367 return static_cast<double>(total) /
um[startStation][endStation].size();
9371 namespace lru_cache {
9373 : capacity(capacity) {}
9376 if(
um.contains(key)) {
9377 if(key !=
keys.back()) {
9379 keys.emplace_back(key);
9388 if(
um.contains(key)) {
9390 if(key !=
keys.back()) {
9392 keys.emplace_back(key);
9398 keys.emplace_back(key);
9401 if(
um.contains(key)) {
9403 if(key !=
keys.back()) {
9405 keys.emplace_back(key);
9409 keys.emplace_back(key);
9416 namespace time_based_key_value_store {
9417 void TimeMap::set(
const string &key,
string value,
int timestamp) {
um[key][timestamp] = std::move(value); }
9420 const auto it =
um[key].lower_bound(timestamp);
9421 return it ==
um[key].end() ?
"" : it->second;
9425 namespace range_module {
9433 namespace lfu_cache {
9439 if(
um.contains(key)) {
9443 const auto it =
find(
tnc[
cnt[key] - 1].begin(),
tnc[
cnt[key] - 1].end(), key);
9444 if(it !=
tnc[
cnt[key] - 1].end()) {
9445 tnc[
cnt[key] - 1].erase(it);
9446 if(
tnc[
cnt[key] - 1].empty()) {
9450 tnc[
cnt[key]].emplace_back(key);
9462 if(
um.contains(key)) {
9465 if(
tnc[
cnt[key] - 1].empty()) {
9470 while(
tnc.begin()->second.empty()) {
9473 const auto evicted =
tnc.begin()->second.begin();
9474 const int val = *evicted;
9475 tnc.begin()->second.erase(evicted);
9481 if(
um.contains(key)) {
9484 if(
tnc[
cnt[key] - 1].empty()) {
9491 tnc[
cnt[key]].emplace_back(key);
9496 namespace leetcode454_4sum_ii {
9498 if(
mem[i].contains(sum)) {
9501 if(i ==
vec.size() - 1) {
9505 for(
const auto &[k, v]:
vec[i]) {
9506 ans += v *
sumCount(sum - k, i + 1);
9513 mem = vector<unordered_map<int, int>>(4);
9514 vec = vector<unordered_map<int, int>>(4);
9515 for(
const auto &num: nums1) {
9518 for(
const auto &num: nums2) {
9521 for(
const auto &num: nums3) {
9524 for(
const auto &num: nums4) {
9531 namespace maximum_size_subarray_sum_equals_k {
9533 auto pref_sum = vector(nums.size(), 0);
9534 pref_sum[0] = nums[0];
9535 unordered_map<int, set<int>> um;
9537 um[nums[0]].insert(0);
9538 for(
int i = 1; i < nums.size(); i++) {
9539 pref_sum[i] += nums[i] + pref_sum[i - 1];
9540 um[pref_sum[i]].insert(i);
9543 for(
int i = nums.size() - 1; i >= 0; i--) {
9544 const int r = pref_sum[i];
9546 if(!um[l].empty()) {
9547 ans = max(ans, i - *um[l].begin());
9554 namespace minimum_swaps_to_group_all_1s_together {
9556 auto one_count = vector(data.size(), 0);
9558 for(
int i = 0; i < one_count.size(); i++) {
9559 one_count[i] = cnt1 + data[i];
9560 cnt1 = one_count[i];
9565 int ans = cnt1 - one_count[cnt1 - 1];
9566 for(
int i = 0; i + cnt1 < one_count.size(); i++) {
9567 ans = min(ans, cnt1 - (one_count[i + cnt1] - one_count[i]));
void ms(vector< int > &arr, int l, int r, int *ans)
bool cmp(const pair< int, int > &a, const pair< int, int > &b)
bool find(vector< unordered_set< int > > &g, int x, vector< bool > &st, vector< int > &match)
void reverse(struct ListNode *head)
void remove(TreeNode *&root, int x)
unsigned long long qmi(unsigned long long m, unsigned long long k)
bool equal(TreeNode *tn1, TreeNode *tn2)
bool is_valid(int year, int month, int day)
bool is_palindromic(string str)
bool operator==(const TreeNode &) const
bool operator!=(const TreeNode &) const
static vector< string > findAllConcatenatedWordsInADict(vector< string > &)
bool dfs(TrieNode *, const string &, int, bool) const
void insert(const string &str)
static int titleToNumber(const string &columnTitle)
static string convertToTitle(int columnNumber)
int majorityElement(vector< int > &nums)
static int countQuadruplets(vector< int > &)
static bool isNStraightHand(vector< int > &hand, int groupSize)
static bool checkPerfectNumber(int num)
static void get_sum(FriendTreeNode *)
static TreeNode * convertBST(TreeNode *root)
static void convert(FriendTreeNode *)
static FriendTreeNode * copy(TreeNode *)
static vector< vector< int > > construct2DArray(vector< int > &original, int m, int n)
static int lastRemaining(int)
static bool checkString(const string &)
static int numberOfBeams(vector< string > &)
static int deviceCount(const string &)
static bool asteroidsDestroyed(int mass, vector< int > &asteroids)
static string dayOfTheWeek(int day, int month, int year)
int getResult(int mouse, int cat, int turns)
int dp[MAXN][MAXN][MAXN *2]
int catMouseGame(vector< vector< int > > &graph)
void getNextResult(int mouse, int cat, int turns)
vector< vector< int > > graph
static string modifyString(string s)
static string simplifyPath(const string &path)
static int maxDepth(const string &s)
static vector< int > grayCode(int n)
static bool checkValid(vector< vector< int > > &matrix)
static int minSwaps(vector< int > &nums)
static unsigned int str2bin(const string &)
static int wordCount(vector< string > &startWords, vector< string > &targetWords)
static char slowestKey(vector< int > &releaseTimes, string keysPressed)
static bool dfs(unsigned long long n1, unsigned long long n2, const char *, unsigned short length, unsigned short current)
static bool isAdditiveNumber(string num)
static unsigned long long str2ui(const char *, unsigned short start, unsigned short length)
将字符串的一个子串转换为整数
static bool equal(string, const char *, unsigned short start, unsigned short length)
判断一个字符串与另一个字符串的子串是否相等
static string decodeCiphertext(string encodedText, int rows)
static string rtrim(string &s)
去除字符串右边的空白符
bool operator==(const point &p) const
bool operator<(const point &p) const
size_t operator()(const point &p) const
static bool isEscapePossible(vector< vector< int > > &blocked, vector< int > &source, vector< int > &target)
static unsigned int search(unordered_set< point, point_hash > &block_set, point *source, point *target, unsigned int limit)
在迷宫中以source为起点搜索
static bool increasingTriplet(vector< int > &nums)
static int dominantIndex(vector< int > &nums)
bool operator<(const pair &) const
static vector< vector< int > > kSmallestPairs(vector< int > &nums1, vector< int > &nums2, int k)
static vector< vector< int > > permute(vector< int > &nums)
static int totalMoney(int n)
static vector< string > divideString(const string &s, int k, char fill)
static int minMoves(int target, int maxDoubles)
static long long mostPoints(vector< vector< int > > &questions)
static long long maxRunTime(int n, vector< int > &batteries)
static int countVowelPermutation(int n)
static int findMinDifference(vector< string > &timePoints)
static bool containsNearbyDuplicate(vector< int > &nums, int k)
static bool stoneGameIX(vector< int > &stones)
static int minJumps(vector< int > &arr)
static int removePalindromeSub(string s)
void insert(const string &str)
string get_prefix(string root, const string &str) const
static string replaceWords(vector< string > &dictionary, const string &sentence)
static int minimumCost(vector< int > &cost)
static int numberOfArrays(vector< int > &differences, int lower, int upper)
bool operator<(const item &) const
static vector< vector< int > > highestRankedKItems(vector< vector< int > > &grid, vector< int > &pricing, vector< int > &start, int k)
static int numberOfWays(string corridor)
static int countElements(vector< int > &nums)
static vector< int > rearrangeArray(vector< int > &nums)
static vector< int > findLonely(vector< int > &nums)
static int maximumGood(vector< vector< int > > &statements)
static pair< int, unordered_map< int, bool > > dfs(vector< vector< int > > &statements, unordered_map< int, bool > um, queue< msg > que)
void update(int timestamp, int price)
bool operator<(const status &s) const
static int secondMinimum(int n, vector< vector< int > > &edges, int time, int change)
static int numberOfMatches(int n)
multiset< pair< int, int > > ms
void add(vector< int > point)
int count(vector< int > point) const
static int countValidWords(const string &sentence)
static int numberOfWeakCharacters(vector< vector< int > > &properties)
static bool patternMatching(const string &pattern, const string &value)
static vector< vector< int > > highestPeak(vector< vector< int > > &isWater)
static vector< string > uncommonFromSentences(const string &s1, const string &s2)
static int findFinalValue(vector< int > &nums, int original)
static vector< int > maxScoreIndices(vector< int > &nums)
static string subStrHash(string s, int power, int modulo, int k, int hashValue)
unordered_map< unsigned int, unsigned int > rank
unordered_map< unsigned int, unsigned int > size
unordered_map< unsigned int, unsigned int > parent
static unsigned int compress(const string &word)
void insert(unsigned int num)
vector< int > groupStrings(vector< string > &words)
void to_union(unsigned int x1, unsigned int x2)
unsigned int find(unsigned int x)
static int numberOfSteps(int num)
static string longestNiceSubstring(const string &s)
static pair< int, int > dfs(string s, int start, int end)
static string reversePrefix(string word, char ch)
static int findMinFibonacciNumbers(int k)
static int find_min(set< int, greater<> > &fibb, int k, set< int, greater<> >::iterator begin)
static int countGoodRectangles(vector< vector< int > > &rectangles)
static int get_sum(int current, int x, int y, int m, int n, vector< vector< int > > &grid, bool **occupied)
static int getMaximumGold(vector< vector< int > > &grid)
static int minimumSum(int num)
static vector< int > pivotArray(vector< int > &nums, int pivot)
static int get_cost(int startAt, int moveCost, int pushCost, const int num[4])
static int minCostSetTime(int startAt, int moveCost, int pushCost, int targetSeconds)
static long long minimumDifference(vector< int > &nums)
static int sumOfUnique(vector< int > &nums)
static vector< int > sortEvenOdd(vector< int > &nums)
static long long smallestNumber(long long num)
set< unsigned int > * zero0
Bitset(int size)
用 size 个位初始化 Bitset ,所有位都是 0 。
string toString() const
返回 Bitset 的当前组成情况。注意,在结果字符串中,第 i 个下标处的字符应该与 Bitset 中的第 i 位一致。
bool one() const
检查 Bitset 中 是否 至少一位 的值是 1 。如果满足此条件,返回 true ;否则,返回 false 。
void fix(int idx) const
将下标为 idx 的位上的值更新为 1 。如果值已经是 1 ,则不会发生任何改变。
bool all() const
检查 Bitset 中 每一位 的值是否都是 1 。如果满足此条件,返回 true ;否则,返回 false 。
void flip()
翻转 Bitset 中每一位上的值。换句话说,所有值为 0 的位将会变成 1 ,反之亦然。
set< unsigned int > * one1
int count() const
返回 Bitset 中值为 1 的位的 总数 。
void unfix(int idx) const
将下标为 idx 的位上的值更新为 0 。如果值已经是 0 ,则不会发生任何改变。
static int * get_p(char ch, int *a, int *b, int *c)
static void sort(char ch[3], int a, int b, int c)
static string longestDiverseString(int a, int b, int c)
unsigned long long operator()(const pair< int, int > &) const
static vector< int > gridIllumination(int n, vector< vector< int > > &lamps, vector< vector< int > > &queries)
static int countKDifference(vector< int > &nums, int k)
static vector< string > simplifiedFractions(int n)
static int gcd(int m, int n)
static int minimumDifference(vector< int > &nums, int k)
static int numEnclaves(vector< vector< int > > &grid)
static int maxNumberOfBalloons(const string &text)
static bool canTransform(const string &start, const string &end)
static int countOperations(int num1, int num2)
static int minimumOperations(vector< int > &nums)
static long long minimumRemoval(vector< int > &beans)
static int maximumANDSum(vector< int > &nums, int numSlots)
static int singleNonDuplicate(vector< int > &nums)
static vector< int > luckyNumbers(vector< vector< int > > &matrix)
static int checkWays(vector< vector< int > > &pairs)
static int findCenter(vector< vector< int > > &edges)
unsigned int operator()(const status &) const
bool operator()(const status &, const status &) const
unordered_map< status, double, status_hash, status_equal > um
double knightProbability(int n, int k, int row, int column)
static vector< int > pancakeSort(vector< int > &arr)
static int countPairs(vector< int > &nums, int k)
static vector< long long > sumOfThree(long long num)
static vector< long long > maximumEvenSplit(long long finalSum)
void update(int idx, T delta)
static long long goodTriplets(vector< int > &nums1, vector< int > &nums2)
static int countEven(int num)
static ListNode * mergeNodes(ListNode *head)
static string repeatLimitedString(const string &s, int repeatLimit)
static long long coutPairs(vector< int > &nums, int k)
static bool isOneBitCharacter(vector< int > &bits)
static int longestMountain(vector< int > &arr)
static string pushDominoes(string dominoes)
static int numberOfGoodSubsets(vector< int > &nums)
static constexpr int mask_max
static constexpr int num_max
static constexpr array< int, 10 > primes
static string reverseOnlyLetters(string s)
static vector< int > findBall(vector< vector< int > > &grid)
static string complexNumberMultiply(const string &num1, const string &num2)
static int maximumDifference(vector< int > &nums)
static string optimalDivision(vector< int > &nums)
static int prefixCount(vector< string > &words, string pref)
static int minSteps(const string &s, const string &t)
static long long minimumTime(vector< int > &time, int totalTrips)
static int minimumFinishTime(vector< vector< int > > &tires, int changeTime, int numLaps)
static int maximumRequests(int n, vector< vector< int > > &requests)
static string convert(string s, int numRows)
static string nearestPalindromic(const string &n)
static int addDigits(int num)
static long long subArrayRanges(vector< int > &nums)
static int findLUSlength(const string &a, const string &b)
static int mostFrequent(vector< int > &nums, int key)
static vector< int > sortJumbled(vector< int > &mapping, vector< int > &nums)
unordered_map< int, unordered_set< int > > nexts
void dfs(bool *dfsd, int v, int i)
vector< vector< int > > getAncestors(int n, vector< vector< int > > &edges)
unordered_map< int, set< int > > ancestors
static int minMovesToMakePalindrome(string s)
static vector< string > cellsInRange(const string &s)
static long long minimalKSum(vector< int > &nums, int k)
static TreeNode * createBinaryTree(vector< vector< int > > &descriptions)
static vector< int > replaceNonCoprimes(vector< int > &nums)
static vector< int > goodDaysToRobBank(vector< int > &security, int time)
static string convertToBase7(int num)
static vector< int > platesBetweenCandles(string s, vector< vector< int > > &queries)
static int bestRotation(vector< int > &nums)
static vector< int > preorder(Node *root)
TreeNode * get_parent() const
void add_child(TreeNode *node)
const vector< TreeNode * > & get_children() const
vector< TreeNode * > children
static int countHighestScoreNodes(vector< int > &parents)
static vector< int > postorder(Node *root)
unordered_map< pair< int, int >, int, function< unsigned int(const pair< int, int > &)> > size
unordered_map< pair< int, int >, int, function< unsigned int(const pair< int, int > &)> > rank
bool same(pair< int, int > a, pair< int, int > b)
int get_size(pair< int, int > p)
void merge(pair< int, int > a, pair< int, int > b)
bool contains(pair< int, int > p) const
unordered_map< pair< int, int >, pair< int, int >, function< unsigned int(const pair< int, int > &)> > parent
pair< int, int > find(pair< int, int > val)
static int maxAreaOfIsland(vector< vector< int > > &grid)
static vector< int > findKDistantIndices(vector< int > &nums, int key, int k)
static int digArtifacts(int n, vector< vector< int > > &artifacts, vector< vector< int > > &dig)
static int maximumTop(vector< int > &nums, int k)
static void calc_dist(int s, vector< pair< int, int > > *graph, vector< long long int > &dist)
static long long minimumWeight(int n, vector< vector< int > > &edges, int src1, int src2, int dest)
static bool validUtf8(vector< int > &data)
static vector< string > findRestaurant(vector< string > &list1, vector< string > &list2)
static int countMaxOrSubsets(vector< int > &nums)
static int dfs(int current, int target, vector< int > nums)
AllOne()
Initializes the object of the data structure.
string getMaxKey()
Returns one of the keys with the maximal count.
string getMinKey()
Returns one of the keys with the minimum count.
map< int, unordered_set< string > > count_str
void dec(const string &key)
Decrements the count of the string key by 1. If the count of key is 0 after the decrement,...
unordered_map< string, int > str_count
void inc(const string &key)
Increments the count of the string key by 1. If key does not exist in the data structure,...
static string longestWord(vector< string > &words)
static string dfs(const string &str, TrieNode *node)
bool transfer(int account1, int account2, long long money)
Transfers money dollars from the account numbered account1 to the account numbered account2.
bool withdraw(int account, long long money)
Withdraw money dollars from the account numbered account.
bool deposit(int account, long long money)
Deposit money dollars into the account numbered account.
Bank(vector< long long > &balance)
Initializes the object with the 0-indexed integer array balance.
unordered_map< int, long long > accounts
static string tree2str(TreeNode *root)
static long long maximumSubsequenceCount(string text, string pattern)
static int halveArray(vector< int > &nums)
static int minimumWhiteTiles(string floor, int numCarpets, int carpetLen)
static int countHillValley(vector< int > &nums)
static int countCollisions(const string &directions)
static vector< int > maximumBobPoints(int numArrows, vector< int > &aliceArrows)
unordered_set< int > linked
static int networkBecomesIdle(vector< vector< int > > &edges, vector< int > &patience)
static bool findTarget(TreeNode *root, int k)
static bool winnerOfGame(string colors)
static int findKthNumber(int n, int k)
static int getSteps(int curr, long n)
static vector< vector< int > > imageSmoother(vector< vector< int > > &img)
static int trailingZeroes(int n)
static int calPoints(vector< string > &ops)
static int minDeletion(vector< int > &nums)
static vector< long long > kthPalindrome(vector< int > &queries, int intLength)
static vector< int > missingRolls(vector< int > &rolls, int mean, int n)
static bool hasAlternatingBits(int n)
static int maxConsecutiveAnswers(string answerKey, int k)
bool operator<(const event &e) const
static vector< int > busiestServers(int k, vector< int > &arrival, vector< int > &load)
static vector< int > selfDividingNumbers(int left, int right)
static bool canReorderDoubled(vector< int > &arr)
static int strongPasswordChecker(const string &password)
static long long numberOfWays(string s)
static long long sumScores(string s)
static int convertTime(string current, string correct)
static vector< vector< int > > findWinners(vector< vector< int > > &matches)
static int maximumCandies(vector< int > &candies, long long k)
Encrypter(vector< char > &keys, vector< string > &values, vector< string > &dictionary)
用 keys、values 和 dictionary 初始化 Encrypter 类。
int decrypt(const string &word2)
统计可以由 word2 解密得到且出现在 dictionary 中的字符串数目
string encrypt(const string &word1) const
按上述加密过程完成对 word1 的加密
unordered_map< string, int > count
NumArray(vector< int > &nums)
Initializes the object with the integer array nums.
void update(int index, int val)
Updates the value of nums[index] to be val.
int sumRange(int left, int right) const
Returns the sum of the elements of nums between indices left and right inclusive (i....
static vector< bool > friendRequests(int n, vector< vector< int > > &restrictions, vector< vector< int > > &requests)
static int countPrimeSetBits(int left, int right)
static vector< int > findMinHeightTrees(int n, vector< vector< int > > &edges)
static int findLongestNode(int u, vector< int > &parent, vector< vector< int > > &adj)
static bool rotateString(string s, const string &goal)
static vector< vector< int > > levelOrder(Node *root)
static bool reachingPoints(int sx, int sy, int tx, int ty)
static int maximumProduct(vector< int > &nums, int k)
static long long maximumBeauty(vector< int > &flowers, long long newFlowers, int target, int full, int partial)
static int countNumbersWithUniqueDigits(int n)
static vector< int > numberOfLines(vector< int > &widths, string s)
static bool checkInclusion(const string &s1, string s2)
int getRandom()
Returns a random element from the current set of elements (it's guaranteed that at least one element ...
bool insert(int val)
Inserts an item val into the set if not present.
unordered_map< int, int > map
RandomizedSet()
Initializes the RandomizedSet object.
bool remove(int val)
Removes an item val from the set if present.
uniform_int_distribution< int > distribution
default_random_engine generator
static int projectionArea(vector< vector< int > > &grid)
int medium
The number of slots for medium parking space
ParkingSystem(int big, int medium, int small)
Initializes object of the ParkingSystem class.
int big
The number of slots for big parking space
bool addCar(int carType)
Checks whether there is a parking space of carType for the car that wants to get into the parking lot...
int small
The number of slots for small parking space
NumArray(vector< int > &nums)
Initializes the object with the integer array nums.
int sumRange(int left, int right) const
Returns the sum of the elements of nums between indices left and right inclusive (i....
static int rob(vector< int > &nums)
static int minimumTotal(vector< vector< int > > &triangle)
static TreeNode * lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
static void copy(TreeNode *tn, TreeNodeP *tnp, int low, int high, TreeNodeP **p, TreeNodeP **q)
vector< int > shuffle() const
Returns a random shuffling of the array.
Solution(vector< int > &nums)
Initializes the object with the integer array nums.
vector< int > reset()
Resets the array to its original configuration and returns it.
static vector< int > findAnagrams(string s, const string &p)
static int numSubarrayProductLessThanK(vector< int > &nums, int k)
static int minSubArrayLen(int target, vector< int > &nums)
static Node * connect(Node *root)
static bool isSubtree(TreeNode *root, TreeNode *subRoot)
static bool equal(TreeNode *tn1, TreeNode *tn2)
static int shortestPathBinaryMatrix(vector< vector< int > > &grid)
static void solve(vector< vector< char > > &board)
static void dfs(vector< vector< char > > &board, int x, int y)
static int dfs(vector< vector< int > > &graph, vector< vector< int > > &ans, int cur)
static vector< vector< int > > allPathsSourceTarget(vector< vector< int > > &graph)
static vector< vector< int > > permuteUnique(vector< int > &nums)
static void dfs(set< vector< int > > &s, const vector< int > ¤t, vector< int > rest)
static vector< vector< int > > combinationSum(vector< int > &candidates, int target)
static vector< vector< int > > recurse(vector< int > &candidates, int target, int index)
static vector< vector< int > > combinationSum2(vector< int > &candidates, int target)
static vector< vector< int > > recurse(vector< int > &candidates, int target, int index)
static int rob(vector< int > &nums)
static bool canJump(vector< int > &nums)
static int jump(vector< int > &nums)
static int uniquePaths(int m, int n)
static string longestPalindrome(string s)
static int numberOfArithmeticSlices(vector< int > &nums)
static int numDecodings(string s)
static void search(const TrieNode *tn, const string &s, int i, vector< bool > &end)
static bool wordBreak(const string &s, vector< string > &wordDict)
static int lengthOfLIS(vector< int > &nums)
static int findNumberOfLIS(vector< int > &nums)
static int longestCommonSubsequence(string text1, string text2)
static int minDistance(const string &word1, const string &word2)
static int minDistance(string word1, string word2)
static int coinChange(vector< int > &coins, int amount)
static int integerBreak(int n)
static int maxPoints(vector< vector< int > > &points)
static vector< vector< string > > groupAnagrams(vector< string > &strs)
static void qsort(vector< int > &nums, int l, int r)
static void sortColors(vector< int > &nums)
static vector< int > topKFrequent(vector< int > &nums, int k)
static int findKthLargest(vector< int > &nums, int k)
static vector< vector< int > > merge(vector< vector< int > > &intervals)
static bool searchMatrix(vector< vector< int > > &matrix, int target)
static bool search(const vector< vector< int > > &matrix, int target, int x_start, int x_end, int y_start, int y_end)
static TreeNode * deserialize(string data)
Decodes your encoded data to tree.
static string serialize(TreeNode *root)
Encodes a tree to a single string.
static int leastInterval(vector< char > &tasks, int n)
MyHashMap()
initializes the object with an empty map.
void put(int key, int value)
inserts a (key, value) pair into the HashMap. If the key already exists in the map,...
void remove(int key)
removes the key and its corresponding value if the map contains the mapping for the key.
array< list< pair< int, int > >, SZ > arr
static vector< vector< int > > generateMatrix(int n)
static int eraseOverlapIntervals(vector< vector< int > > &intervals)
static vector< int > productExceptSelf(vector< int > &nums)
static int subarraySum(vector< int > &nums, int k)
static vector< int > partitionLabels(string s)
static vector< string > findRepeatedDnaSequences(string s)
int get(int index) const
Get the value of the indexth node in the linked list. If the index is invalid, return -1.
void deleteAtIndex(int index)
Delete the indexth node in the linked list, if the index is valid.
void addAtHead(int val)
Add a node of value val before the first element of the linked list. After the insertion,...
void addAtTail(int val)
Append a node of value val as the last element of the linked list.
void addAtIndex(int index, int val)
Add a node of value val before the indexth node in the linked list. If index equals the length of the...
MyLinkedList()
Initializes the MyLinkedList object.
TreeNode * deleteNode(TreeNode *root, int key)
TreeNode * findMinimum(TreeNode *node)
TreeNode * findMaximum(TreeNode *node)
void remove(TreeNode *node)
static unsigned missing(vector< int > &nums, int i)
static int missingElement(vector< int > &nums, int k)
static vector< int > findPeakGridLR(vector< vector< int > > &mat, int l, int r)
static int get(vector< vector< int > > &mat, int i, int j)
static vector< int > findPeakGrid(vector< vector< int > > &mat)
static int count(vector< int > &sweetness, int x)
static int maximizeSweetness(vector< int > &sweetness, int k)
static vector< int > shortestDistanceColor(vector< int > &colors, vector< vector< int > > &queries)
static vector< int > minAvailableDuration(vector< vector< int > > &slots1, vector< vector< int > > &slots2, int duration)
static pair< int, int > merge(const vector< int > &vec1, const vector< int > &vec2)
static int countInRange(vector< int > &nums, int l, int r)
static int findDuplicate(vector< int > &nums)
static int trap(vector< int > &height)
static vector< vector< int > > findRLEArray(vector< vector< int > > &encoded1, vector< vector< int > > &encoded2)
static int getMinUniqueCharCnt(const string &s, int len)
static int lengthOfLongestSubstringTwoDistinct(const string &s)
static int lengthOfLongestSubstringKDistinct(const string &s, int k)
static int cntMinFlip(vector< int > &nums, int len)
static int longestOnes(vector< int > &nums, int k)
static vector< int > maxSlidingWindow(vector< int > &nums, int k)
static string minWindow(string s, const string &t)
static bool valid(unordered_map< char, int > &ums, const unordered_map< char, int > &umt)
static void wallsAndGates(vector< vector< int > > &rooms)
size_t operator()(const pair< int, int > &p) const
bool operator()(const pair< int, int > &p1, const pair< int, int > &p2) const
static vector< vector< int > > pacificAtlantic(vector< vector< int > > &heights)
static vector< int > getLonelyNodes(TreeNode *root)
unordered_set< Node * > children
static vector< int > killProcess(vector< int > &pid, vector< int > &ppid, int kill)
static vector< int > distanceK(TreeNode *root, TreeNode *target, int k)
static int openLock(vector< string > &deadends, const string &target)
static int makeConnected(int n, vector< vector< int > > &connections)
static void dfs(int &edge_cnt, int &node_cnt, unordered_set< int > &vis, int node, vector< unordered_set< int > > &g)
bool operator()(const pair< int, Node * > &p1, const pair< int, Node * > &p2) const
static int minCost(vector< vector< int > > &grid)
static void tarjan(int prev, int &step, vector< int > &dfn, int node, vector< unordered_set< int > > &g, vector< int > &low, vector< vector< int > > &ans)
static vector< vector< int > > criticalConnections(int n, vector< vector< int > > &connections)
static vector< vector< int > > getFactorsWithMin(int n, int minimum)
static vector< vector< int > > getFactors(int n)
static string decodeString(string s)
static bool valid(const vector< vector< bool > > &board, int n, int x, int y)
static vector< string > toStringVec(const vector< vector< bool > > &board)
static void dfs(const vector< vector< bool > > &board, int line, int n, vector< vector< string > > &ans)
static vector< vector< string > > solveNQueens(int n)
static bool valid(const vector< vector< char > > &board, int x, int y, char num)
static bool dfs(const vector< vector< char > > &board, vector< vector< char > > &ans)
static void solveSudoku(vector< vector< char > > &board)
static bool isMatch(const string &s, const string &p)
static bool dfs(const string &s, const string &p, int si, int pi)
static vector< int > diffWaysToCompute(const string &expression)
static vector< int > eval(const string &expr, int start, int end)
static bool isValid(const string &str)
static vector< string > removeInvalidParentheses(const string &s)
static double findMedianSortedArrays(vector< int > &nums1, vector< int > &nums2)
vector< int > countSmaller(vector< int > &nums)
void Discretization(vector< int > &nums)
static int maxProfit(vector< int > &prices)
static int maxProfit(vector< int > &prices, int fee)
static int get_m(const vector< int > &nums, int msum)
static int splitArray(vector< int > &nums, int m)
size_t operator()(const pair< TreeNode *, bool > &p) const
bool operator()(const pair< TreeNode *, bool > &p1, const pair< TreeNode *, bool > &p2) const
int dfs(bool steal, TreeNode *node)
unordered_map< pair< TreeNode *, bool >, int, myhash, myeq > um
static int maximalSquare(vector< vector< char > > &matrix)
static int maximalRectangle(vector< vector< char > > &matrix)
static bool PredictTheWinner(vector< int > &nums)
static vector< vector< string > > partition(const string &s)
static void dfs(const vector< string > ¤t, const string &s, vector< vector< string > > &ans, int start, int cursor)
static bool is_palindromic(const string &s, int start, int end)
static int minCut(string s)
static bool canPartition(vector< int > &nums)
static int mincostTickets(vector< int > &days, vector< int > &costs)
static int maxProfit(vector< int > &prices)
static int calculateMinimumHP(vector< vector< int > > &dungeon)
static bool canFinish(int numCourses, vector< vector< int > > &prerequisites)
static vector< int > findOrder(int numCourses, vector< vector< int > > &prerequisites)
int longestIncreasingPath(vector< vector< int > > &matrix)
static constexpr int dirs[4][2]
static int minimumSemesters(int n, vector< vector< int > > &relations)
static string alienOrder(vector< string > &words)
static vector< int > singleNumber(vector< int > &nums)
unsigned get_mask() const
unordered_set< char > keys
bool operator<(const frame &f) const
static int shortestPathAllKeys(vector< string > &grid)
static int minKBitFlips(vector< int > &nums, int k)
unordered_map< string, unordered_map< string, vector< int > > > um
unordered_map< int, pair< string, int > > records
void checkOut(int id, const string &stationName, int t)
通行卡 ID 等于 id 的乘客,在时间 t ,从 stationName 站离开
double getAverageTime(const string &startStation, const string &endStation)
平均时间会根据截至目前所有从 startStation 站 直接 到达 endStation 站的行程进行计算,也就是从 startStation 站进入并从 endStation 离开的行程 从 st...
void checkIn(int id, const string &stationName, int t)
通行卡 ID 等于 id 的乘客,在时间 t ,从 stationName 站进入 乘客一次只能从一个站进入
void put(int key, int value)
如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。
LRUCache(int capacity)
以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key)
如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
unordered_map< int, int > um
string get(const string &key, int timestamp)
返回先前调用 set(key, value, timestamp_prev) 所存储的值,其中 timestamp_prev <= timestamp 。
unordered_map< string, map< int, string, greater< int > > > um
void set(const string &key, string value, int timestamp)
存储键 key、值 value,以及给定的时间戳 timestamp。
void assign(unsigned l, unsigned r, type val=false)
bool check(unsigned l, unsigned r)
void removeRange(int left, int right)
停止跟踪 半开区间 [left, right) 中当前正在跟踪的每个实数。
void addRange(int left, int right)
添加 半开区间 [left, right),跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时,应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。
bool queryRange(int left, int right)
只有在当前正在跟踪区间 [left, right) 中的每一个实数时,才返回 true ,否则返回 false 。
int get(int key)
如果键 key 存在于缓存中,则获取键的值,否则返回 -1 。
unordered_map< int, int > um
map< int, list< int > > tnc
unordered_map< int, int > cnt
void put(int key, int value)
如果键 key 已存在,则变更其值;如果键不存在,请插入键值对。当缓存达到其容量 capacity 时,则应该在插入新项之前,移除最不经常使用的项。在此问题中,当存在平局(即两个或更多个键具有相同使用频...
int sumCount(int sum, int i)
vector< unordered_map< int, int > > mem
int fourSumCount(vector< int > &nums1, vector< int > &nums2, vector< int > &nums3, vector< int > &nums4)
vector< unordered_map< int, int > > vec
static int maxSubArrayLen(vector< int > &nums, int k)
static int minSwaps(vector< int > &data)
array< TrieNode *, 26 > nexts
void insert(const string &str)