problemscpp
A collection of my answers to algorithm problems in c++.
载入中...
搜索中...
未找到
leetcode_test.cpp
浏览该文件的文档.
1#include "leetcode.h"
2#include "gtest/gtest.h"
3#include <algorithm>
4#include <vector>
5
6using namespace std;
7
8namespace leetcode {
11 ASSERT_EQ(std::string("A"), Solution::convertToTitle(1));
12 }
13
15 ASSERT_EQ(std::string("AB"), Solution::convertToTitle(28));
16 }
17
19 ASSERT_EQ(std::string("ZY"), Solution::convertToTitle(701));
20 }
21
23 ASSERT_EQ(std::string("FXSHRXW"), Solution::convertToTitle(2147483647));
24 }
25
27 ASSERT_EQ(std::string("AZ"), Solution::convertToTitle(52));
28 }
29 }// namespace excel_sheet_column_title
30
31 namespace majority_element {
33 auto sol = Solution();
34 int arr[] = {3, 2, 3};
35 auto vec = std::vector(arr, arr + 3);
36 ASSERT_EQ(3, sol.majorityElement(vec));
37 }
38
40 auto sol = Solution();
41 int arr[] = {2, 2, 1, 1, 1, 2, 2};
42 auto vec = std::vector(arr, arr + 7);
43 ASSERT_EQ(2, sol.majorityElement(vec));
44 }
45
47 auto sol = Solution();
48 int arr[] = {3, 2, 3};
49 auto vec = std::vector(arr, arr + 3);
50 ASSERT_EQ(3, sol.majorityElement(vec));
51 }
52 }// namespace majority_element
53
54 namespace excel_sheet_column_number {
56 ASSERT_EQ(1, Solution::titleToNumber("A"));
57 }
58
60 ASSERT_EQ(28, Solution::titleToNumber("AB"));
61 }
62
64 ASSERT_EQ(701, Solution::titleToNumber("ZY"));
65 }
66
68 ASSERT_EQ(2147483647, Solution::titleToNumber("FXSHRXW"));
69 }
70 }// namespace excel_sheet_column_number
71
72 namespace concatenated_words {
74 basic_string<char> input[] = {
75 "cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat",
76 "ratcatdogcat"};
77 auto vec = vector(begin(input), end(input));
79 string outputstr[] = {"catsdogcats", "dogcatsdog", "ratcatdogcat"};
80 const auto output = vector(begin(outputstr), end(outputstr));
81 for(const string &str: ans) {
82 ASSERT_TRUE(find(output.cbegin(), output.cend(), str) != output.cend());
83 }
84 for(const string &str: output) {
85 ASSERT_TRUE(find(ans.cbegin(), ans.cend(), str) != ans.cend());
86 }
87 ASSERT_EQ(ans.size(), output.size());
88 }
89
91 basic_string<char> input[] = {"cat", "dog", "catdog"};
92 auto vec = vector(begin(input), end(input));
94 string outputstr[] = {"catdog"};
95 const auto output = vector(begin(outputstr), end(outputstr));
96 for(const string &str: ans) {
97 ASSERT_TRUE(find(output.cbegin(), output.cend(), str) != output.cend());
98 }
99 for(const string &str: output) {
100 ASSERT_TRUE(find(ans.cbegin(), ans.cend(), str) != ans.cend());
101 }
102 ASSERT_EQ(ans.size(), output.size());
103 }
104
106 basic_string<char> input[] = {"nuqhmfj", "mf", "jf", "n", "u", "q", "h"};
107 auto vec = vector(begin(input), end(input));
108 const auto ans = Solution::findAllConcatenatedWordsInADict(vec);
109 const auto output = vector<string>();
110 for(const string &str: ans) {
111 ASSERT_TRUE(find(output.cbegin(), output.cend(), str) != output.cend());
112 }
113 for(const string &str: output) {
114 ASSERT_TRUE(find(ans.cbegin(), ans.cend(), str) != ans.cend());
115 }
116 ASSERT_EQ(ans.size(), output.size());
117 }
118 }// namespace concatenated_words
119
120 namespace count_special_quadruplets {
122 int input[] = {1, 2, 3, 6};
123 auto vec = vector(begin(input), end(input));
124 ASSERT_EQ(1, Solution::countQuadruplets(vec));
125 }
126
128 int input[] = {3, 3, 6, 4, 5};
129 auto vec = vector(begin(input), end(input));
130 ASSERT_EQ(0, Solution::countQuadruplets(vec));
131 }
132
134 int input[] = {1, 1, 1, 3, 5};
135 auto vec = vector(begin(input), end(input));
136 ASSERT_EQ(4, Solution::countQuadruplets(vec));
137 }
138
140 int input[] = {28, 8, 49, 85, 37, 90, 20, 8};
141 auto vec = vector(begin(input), end(input));
142 ASSERT_EQ(1, Solution::countQuadruplets(vec));
143 }
144 }// namespace count_special_quadruplets
145
146 namespace hand_of_straights {
148 int input[] = {1, 2, 3, 6, 2, 3, 4, 7, 8};
149 auto vec = vector(begin(input), end(input));
150 ASSERT_TRUE(Solution::isNStraightHand(vec, 3));
151 }
152
154 int input[] = {1, 2, 3, 4, 5};
155 auto vec = vector(begin(input), end(input));
156 ASSERT_FALSE(Solution::isNStraightHand(vec, 4));
157 }
158
160 int input[] = {1, 2, 3, 4, 5, 6};
161 auto vec = vector(begin(input), end(input));
162 ASSERT_TRUE(Solution::isNStraightHand(vec, 2));
163 }
164
166 int input[] = {
167 9, 13, 15, 23, 22, 25, 4, 4, 29, 15, 8, 23, 12, 19, 24, 17, 18, 11, 22, 24, 17, 17, 10, 23,
168 21, 18, 14, 18, 7, 6, 3, 6, 19, 11, 16, 11, 12, 13, 8, 26, 17, 20, 13, 19, 22, 21, 27, 9, 20,
169 15, 20, 27, 8, 13, 25, 23, 22, 15, 9, 14, 20, 10, 6, 5, 14, 12, 7, 16, 21, 18, 21, 24, 23,
170 10, 21, 16, 18, 16, 18, 5, 20, 19, 20, 10, 14, 26, 2, 9, 19, 12, 28, 17, 5, 7, 25, 22, 16,
171 17, 21, 11};
172 auto vec = vector(begin(input), end(input));
173 ASSERT_FALSE(Solution::isNStraightHand(vec, 10));
174 }
175 }// namespace hand_of_straights
176
177 namespace perfect_number {
179 ASSERT_TRUE(Solution::checkPerfectNumber(28));
180 }
181
183 ASSERT_TRUE(Solution::checkPerfectNumber(6));
184 }
185
187 ASSERT_TRUE(Solution::checkPerfectNumber(496));
188 }
189
191 ASSERT_TRUE(Solution::checkPerfectNumber(8128));
192 }
193
195 ASSERT_FALSE(Solution::checkPerfectNumber(2));
196 }
197 }// namespace perfect_number
198
199 namespace convert_bst_to_greater_tree {
201 auto *input = new TreeNode(4, new TreeNode(1, new TreeNode(0), new TreeNode(2, nullptr, new TreeNode(3))),
202 new TreeNode(6, new TreeNode(5), new TreeNode(7, nullptr, new TreeNode(8))));
203 const auto *ans = new TreeNode(30, new TreeNode(36, new TreeNode(36), new TreeNode(35, nullptr, new TreeNode(33))),
204 new TreeNode(21, new TreeNode(26), new TreeNode(15, nullptr, new TreeNode(8))));
205 const auto *output = Solution::convertBST(input);
206 ASSERT_TRUE(*ans == *output);
207 }
208 }// namespace convert_bst_to_greater_tree
209
210 namespace convert_1d_array_into_2d_array {
212 int input[4] = {1, 2, 3, 4};
213 auto vec = vector(begin(input), end(input));
214 const auto ans = Solution::construct2DArray(vec, 2, 2);
215 int output1[] = {1, 2};
216 int output2[] = {3, 4};
217 const auto vec1 = vector(begin(output1), end(output1));
218 const auto vec2 = vector(begin(output2), end(output2));
219 auto vec_output = vector<vector<int>>();
220 vec_output.push_back(vec1);
221 vec_output.push_back(vec2);
222 ASSERT_EQ(vec_output, ans);
223 }
224 }// namespace convert_1d_array_into_2d_array
225
226 namespace elimination_game {
228 ASSERT_EQ(1, Solution::lastRemaining(1));
229 ASSERT_EQ(2, Solution::lastRemaining(2));
230 ASSERT_EQ(2, Solution::lastRemaining(3));
231 ASSERT_EQ(2, Solution::lastRemaining(4));
232 ASSERT_EQ(2, Solution::lastRemaining(5));
233 ASSERT_EQ(4, Solution::lastRemaining(6));
234 ASSERT_EQ(4, Solution::lastRemaining(7));
235 ASSERT_EQ(6, Solution::lastRemaining(8));
236 ASSERT_EQ(6, Solution::lastRemaining(9));
237 }
238 }// namespace elimination_game
239
240 namespace check_if_all_as_appears_before_all_bs {
242 ASSERT_TRUE(Solution::checkString("aaabbb"));
243 }
244
246 ASSERT_FALSE(Solution::checkString("abab"));
247 }
248
250 ASSERT_TRUE(Solution::checkString("bbb"));
251 }
252 }// namespace check_if_all_as_appears_before_all_bs
253
254 namespace number_of_laser_beams_in_a_bank {
256 string input[] = {"011001", "000000", "010100", "001000"};
257 auto vec = vector(begin(input), end(input));
258 ASSERT_EQ(8, Solution::numberOfBeams(vec));
259 }
260
262 string input[] = {"000", "111", "000"};
263 auto vec = vector(begin(input), end(input));
264 ASSERT_EQ(0, Solution::numberOfBeams(vec));
265 }
266 }// namespace number_of_laser_beams_in_a_bank
267
268 namespace destroying_asteroids {
270 int input[] = {3, 9, 19, 5, 21};
271 auto vec = vector(begin(input), end(input));
272 ASSERT_TRUE(Solution::asteroidsDestroyed(10, vec));
273 }
274
276 int input[] = {4, 9, 23, 4};
277 auto vec = vector(begin(input), end(input));
278 ASSERT_FALSE(Solution::asteroidsDestroyed(5, vec));
279 }
280 }// namespace destroying_asteroids
281
282 namespace day_of_the_week {
284 ASSERT_EQ("Saturday", Solution::dayOfTheWeek(31, 8, 2019));
285 }
286
288 ASSERT_EQ("Sunday", Solution::dayOfTheWeek(18, 7, 1999));
289 }
290
292 ASSERT_EQ("Sunday", Solution::dayOfTheWeek(15, 8, 1993));
293 }
294
296 ASSERT_EQ("Monday", Solution::dayOfTheWeek(29, 2, 2016));
297 }
298
300 ASSERT_EQ("Tuesday", Solution::dayOfTheWeek(31, 8, 2100));
301 }
302 }// namespace day_of_the_week
303
304 namespace replace_all_s_to_avoid_consecutive_repeating_characters {
308
312
314 ASSERT_EQ("jaqgacb", Solution::modifyString("j?qg??b"));
315 }
316
318 ASSERT_EQ("abywaipkja", Solution::modifyString("??yw?ipkj?"));
319 }
320 }// namespace replace_all_s_to_avoid_consecutive_repeating_characters
321
322 namespace simplify_path {
324 ASSERT_EQ("/home", Solution::simplifyPath("/home/"));
325 }
326
328 ASSERT_EQ("/", Solution::simplifyPath("/../"));
329 }
330
332 ASSERT_EQ("/home/foo", Solution::simplifyPath("/home//foo/"));
333 }
334
336 ASSERT_EQ("/c", Solution::simplifyPath("/a/./b/../../c/"));
337 }
338
340 ASSERT_EQ("/a/b/c", Solution::simplifyPath("/a//b////c/d//././/.."));
341 }
342 }// namespace simplify_path
343
344 namespace maximum_nesting_depth_of_the_parentheses {
346 ASSERT_EQ(3, Solution::maxDepth("(1+(2*3)+((8)/4))+1"));
347 }
348
350 ASSERT_EQ(3, Solution::maxDepth("(1)+((2))+(((3)))"));
351 }
352
354 ASSERT_EQ(1, Solution::maxDepth("1+(2*3)/(2-1)"));
355 }
356
358 ASSERT_EQ(0, Solution::maxDepth("1"));
359 }
360 }// namespace maximum_nesting_depth_of_the_parentheses
361
362 namespace gray_code {
363 TEST(gray_code, case1) {
364 int output[] = {0, 1, 3, 2};
365 const auto vec = vector(begin(output), end(output));
366 ASSERT_EQ(vec, Solution::grayCode(2));
367 }
368 }// namespace gray_code
369
370 namespace minimum_swaps_to_group_all_1s_together_ii {
372 int input[] = {0, 1, 0, 1, 1, 0, 0};
373 auto vec = vector(begin(input), end(input));
374 ASSERT_EQ(1, Solution::minSwaps(vec));
375 }
376
378 int input[] = {0, 1, 1, 1, 0, 0, 1, 1, 0};
379 auto vec = vector(begin(input), end(input));
380 ASSERT_EQ(2, Solution::minSwaps(vec));
381 }
382
384 int input[] = {1, 1, 0, 0, 1};
385 auto vec = vector(begin(input), end(input));
386 ASSERT_EQ(0, Solution::minSwaps(vec));
387 }
388
390 int input[] = {1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0,
391 1, 0, 0};
392 auto vec = vector(begin(input), end(input));
393 ASSERT_EQ(7, Solution::minSwaps(vec));
394 }
395 }// namespace minimum_swaps_to_group_all_1s_together_ii
396
397 namespace count_words_obtained_after_adding_a_letter {
399 string input1[] = {"ant", "act", "tack"};
400 auto vec1 = vector(begin(input1), end(input1));
401 string input2[] = {"tack", "act", "acti"};
402 auto vec2 = vector(begin(input2), end(input2));
403 ASSERT_EQ(2, Solution::wordCount(vec1, vec2));
404 }
405
407 string input1[] = {"ab", "a"};
408 auto vec1 = vector(begin(input1), end(input1));
409 string input2[] = {"abc", "abcd"};
410 auto vec2 = vector(begin(input2), end(input2));
411 ASSERT_EQ(1, Solution::wordCount(vec1, vec2));
412 }
413
415 string input1[] = {"g", "vf", "ylpuk", "nyf", "gdj", "j", "fyqzg", "sizec"};
416 auto vec1 = vector(begin(input1), end(input1));
417 string input2[] = {"r", "am", "jg", "umhjo", "fov", "lujy", "b", "uz", "y"};
418 auto vec2 = vector(begin(input2), end(input2));
419 ASSERT_EQ(2, Solution::wordCount(vec1, vec2));
420 }
421 }// namespace count_words_obtained_after_adding_a_letter
422
423 namespace slowest_key {
425 int input[] = {9, 29, 49, 50};
426 auto vec = vector(begin(input), end(input));
427 ASSERT_EQ('c', Solution::slowestKey(vec, "cbcd"));
428 }
429
431 int input[] = {12, 23, 36, 46, 62};
432 auto vec = vector(begin(input), end(input));
433 ASSERT_EQ('a', Solution::slowestKey(vec, "spuda"));
434 }
435 }// namespace slowest_key
436
437 namespace additive_number {
439 ASSERT_TRUE(Solution::isAdditiveNumber("112358"));
440 }
441
443 ASSERT_TRUE(Solution::isAdditiveNumber("199100199"));
444 }
445
447 ASSERT_FALSE(Solution::isAdditiveNumber("0235813"));
448 }
449
451 ASSERT_TRUE(Solution::isAdditiveNumber("000000"));
452 }
453
455 ASSERT_TRUE(Solution::isAdditiveNumber("11011"));
456 }
457
458 TEST(str2ui, case1) {
459 const char input[] = {'2'};
460 ASSERT_EQ(2, Solution::str2ui(input, 0, 1));
461 }
462
463 TEST(str2ui, case2) {
464 const char input[] = {'2', '3', '4'};
465 ASSERT_EQ(234, Solution::str2ui(input, 0, 3));
466 }
467
468 TEST(str2ui, case3) {
469 const char input[] = {'2', '3', '4'};
470 ASSERT_EQ(23, Solution::str2ui(input, 0, 2));
471 }
472
473 TEST(str2ui, case4) {
474 const char input[] = {'2', '3', '4'};
475 ASSERT_EQ(34, Solution::str2ui(input, 1, 2));
476 }
477
478 TEST(equal, case1) {
479 const char input[] = {'1', '2'};
480 ASSERT_TRUE(Solution::equal(string("12"), input, 0, 2));
481 }
482
483 TEST(equal, case2) {
484 const char input[] = {'1', '2', '4'};
485 ASSERT_TRUE(Solution::equal(string("12"), input, 0, 3));
486 }
487
488 TEST(equal, case3) {
489 const char input[] = {'3', '2', '4'};
490 ASSERT_FALSE(Solution::equal(string("12"), input, 0, 3));
491 }
492
493 TEST(equal, case4) {
494 const char input[] = {'3', '2', '4', '5'};
495 ASSERT_TRUE(Solution::equal(string("24"), input, 1, 4));
496 }
497
498 TEST(equal, case5) {
499 const char input[] = {'3', '2', '4', '5'};
500 ASSERT_FALSE(Solution::equal(string("2456"), input, 1, 4));
501 }
502
503 TEST(dfs, case1) {
504 const char input[] = {'1', '1', '2'};
505 ASSERT_TRUE(Solution::dfs(1, 1, input, 3, 2));
506 }
507
508 TEST(dfs, case2) {
509 const char input[] = {'1', '1', '2', '3'};
510 ASSERT_TRUE(Solution::dfs(1, 1, input, 4, 2));
511 }
512
513 TEST(dfs, case3) {
514 const char input[] = {'1', '1', '2', '4'};
515 ASSERT_FALSE(Solution::dfs(1, 1, input, 4, 2));
516 }
517
518 TEST(dfs, case4) {
519 const char input[] = {'1', '1', '2', '3', '3', '4'};
520 ASSERT_TRUE(Solution::dfs(11, 23, input, 6, 4));
521 }
522 }// namespace additive_number
523
524 namespace decode_the_slanted_ciphertext {
526 ASSERT_EQ("cipher", Solution::decodeCiphertext("ch ie pr", 3));
527 }
528
530 ASSERT_EQ("i love leetcode", Solution::decodeCiphertext("iveo eed l te olc", 4));
531 }
532
534 ASSERT_EQ("coding", Solution::decodeCiphertext("coding", 1));
535 }
536
538 ASSERT_EQ(" abc", Solution::decodeCiphertext(" b ac", 2));
539 }
540 }// namespace decode_the_slanted_ciphertext
541
542 namespace increasing_triplet_subsequence {
544 int input[] = {1, 2, 3, 4, 5};
545 auto vec = vector(begin(input), end(input));
546 ASSERT_TRUE(Solution::increasingTriplet(vec));
547 }
548
550 int input[] = {5, 4, 3, 2, 1};
551 auto vec = vector(begin(input), end(input));
552 ASSERT_FALSE(Solution::increasingTriplet(vec));
553 }
554
556 int input[] = {2, 1, 5, 0, 4, 6};
557 auto vec = vector(begin(input), end(input));
558 ASSERT_TRUE(Solution::increasingTriplet(vec));
559 }
560
562 int input[] = {20, 100, 10, 12, 5, 13};
563 auto vec = vector(begin(input), end(input));
564 ASSERT_TRUE(Solution::increasingTriplet(vec));
565 }
566 }// namespace increasing_triplet_subsequence
567
568 namespace largest_number_at_least_twice_of_others {
570 int input[] = {3, 6, 1, 0};
571 auto vec = vector(begin(input), end(input));
572 ASSERT_EQ(1, Solution::dominantIndex(vec));
573 }
574
576 int input[] = {1, 2, 3, 4};
577 auto vec = vector(begin(input), end(input));
578 ASSERT_EQ(-1, Solution::dominantIndex(vec));
579 }
580
582 int input[] = {1};
583 auto vec = vector(begin(input), end(input));
584 ASSERT_EQ(0, Solution::dominantIndex(vec));
585 }
586
588 int input[] = {0, 0, 0, 1};
589 auto vec = vector(begin(input), end(input));
590 ASSERT_EQ(3, Solution::dominantIndex(vec));
591 }
592
594 int input[] = {0, 0, 3, 2};
595 auto vec = vector(begin(input), end(input));
596 ASSERT_EQ(-1, Solution::dominantIndex(vec));
597 }
598 }// namespace largest_number_at_least_twice_of_others
599
600 namespace permutations {
602 int input[] = {1};
603 auto vec = vector(begin(input), end(input));
604 auto ans = vector<vector<int>>();
605 auto ans1 = vector<int>();
606 ans1.push_back(1);
607 ans.push_back(ans1);
608 ASSERT_EQ(ans, Solution::permute(vec));
609 }
610
612 int input[] = {0, 1};
613 auto vec = vector(begin(input), end(input));
614 auto ans = vector<vector<int>>();
615 auto ans1 = vector<int>();
616 ans1.push_back(0);
617 ans1.push_back(1);
618 ans.push_back(ans1);
619 auto ans2 = vector<int>();
620 ans2.push_back(1);
621 ans2.push_back(0);
622 ans.push_back(ans2);
623 ASSERT_EQ(ans, Solution::permute(vec));
624 }
625
627 int input[] = {1, 2, 3};
628 auto vec = vector(begin(input), end(input));
629 auto ans = vector<vector<int>>();
630 int outputs[6][3] = {{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}};
631 for(auto &output: outputs) {
632 ans.emplace_back(begin(output), end(output));
633 }
634 ASSERT_EQ(ans, Solution::permute(vec));
635 }
636 }// namespace permutations
637
638 namespace calculate_money_in_leetcode_bank {
640 ASSERT_EQ(10, Solution::totalMoney(4));
641 }
642
644 ASSERT_EQ(37, Solution::totalMoney(10));
645 }
646
648 ASSERT_EQ(96, Solution::totalMoney(20));
649 }
650 }// namespace calculate_money_in_leetcode_bank
651
652 namespace divide_a_string_into_groups_of_size_k {
654 string output[] = {"abc", "def", "ghi"};
655 const auto vec = vector(begin(output), end(output));
656 ASSERT_EQ(vec, Solution::divideString("abcdefghi", 3, 'x'));
657 }
658
660 string output[] = {"abc", "def", "ghi", "jxx"};
661 const auto vec = vector(begin(output), end(output));
662 ASSERT_EQ(vec, Solution::divideString("abcdefghij", 3, 'x'));
663 }
664
666 string output[] = {"ctoyjrwt", "ngqwtnnn"};
667 const auto vec = vector(begin(output), end(output));
668 ASSERT_EQ(vec, Solution::divideString("ctoyjrwtngqwt", 8, 'n'));
669 }
670 }// namespace divide_a_string_into_groups_of_size_k
671
672 namespace minimum_moves_to_reach_target_score {
674 ASSERT_EQ(4, Solution::minMoves(5, 0));
675 }
676
678 ASSERT_EQ(7, Solution::minMoves(19, 2));
679 }
680
682 ASSERT_EQ(4, Solution::minMoves(10, 4));
683 }
684 }// namespace minimum_moves_to_reach_target_score
685
686 namespace maximum_running_time_of_n_computers {
688 int input[] = {3, 3, 3};
689 auto vec = vector(begin(input), end(input));
690 ASSERT_EQ(4, Solution::maxRunTime(2, vec));
691 }
692
694 int input[] = {1, 1, 1, 1};
695 auto vec = vector(begin(input), end(input));
696 ASSERT_EQ(2, Solution::maxRunTime(2, vec));
697 }
698 }// namespace maximum_running_time_of_n_computers
699
700 namespace coun_vowels_permutation {
702 ASSERT_EQ(5, Solution::countVowelPermutation(1));
703 }
704
706 ASSERT_EQ(10, Solution::countVowelPermutation(2));
707 }
708
710 ASSERT_EQ(68, Solution::countVowelPermutation(5));
711 }
712 }// namespace coun_vowels_permutation
713
714 namespace minimum_time_difference {
716 string input[] = {"23:59", "00:00"};
717 auto vec = vector(begin(input), end(input));
718 ASSERT_EQ(1, Solution::findMinDifference(vec));
719 }
720
722 string input[] = {"00:00", "23:59", "00:00"};
723 auto vec = vector(begin(input), end(input));
724 ASSERT_EQ(0, Solution::findMinDifference(vec));
725 }
726
728 string input[] = {"00:00", "04:00", "22:00"};
729 auto vec = vector(begin(input), end(input));
730 ASSERT_EQ(120, Solution::findMinDifference(vec));
731 }
732 }// namespace minimum_time_difference
733
734 namespace contains_duplicate_ii {
736 int input[] = {1, 2, 3, 1};
737 auto vec = vector(begin(input), end(input));
738 ASSERT_TRUE(Solution::containsNearbyDuplicate(vec, 3));
739 }
740
742 int input[] = {1, 0, 1, 1};
743 auto vec = vector(begin(input), end(input));
744 ASSERT_TRUE(Solution::containsNearbyDuplicate(vec, 3));
745 }
746
748 int input[] = {1, 2, 3, 1, 2, 3};
749 auto vec = vector(begin(input), end(input));
750 ASSERT_FALSE(Solution::containsNearbyDuplicate(vec, 2));
751 }
752 }// namespace contains_duplicate_ii
753
754 namespace stone_game_ix {
756 int input[] = {2, 1};
757 auto vec = vector(begin(input), end(input));
758 ASSERT_TRUE(Solution::stoneGameIX(vec));
759 }
760
762 int input[] = {2};
763 auto vec = vector(begin(input), end(input));
764 ASSERT_FALSE(Solution::stoneGameIX(vec));
765 }
766
768 int input[] = {5, 1, 2, 4, 3};
769 auto vec = vector(begin(input), end(input));
770 ASSERT_FALSE(Solution::stoneGameIX(vec));
771 }
772
774 int input[] = {3, 4, 6, 6, 8, 9, 2, 4, 5};
775 auto vec = vector(begin(input), end(input));
776 ASSERT_TRUE(Solution::stoneGameIX(vec));
777 }
778
780 int input[] = {2, 3, 7, 9, 4, 32, 2, 5, 8, 2, 6, 8, 3, 2, 6, 8, 3, 2, 5, 7, 8, 3, 5, 67, 8};
781 auto vec = vector(begin(input), end(input));
782 ASSERT_TRUE(Solution::stoneGameIX(vec));
783 }
784
786 int input[] = {15, 20, 10, 13, 14, 15, 5, 2, 3};
787 auto vec = vector(begin(input), end(input));
788 ASSERT_FALSE(Solution::stoneGameIX(vec));
789 }
790 }// namespace stone_game_ix
791
792 namespace jump_game_iv {
794 int input[] = {100, -23, -23, 404, 100, 23, 23, 23, 3, 404};
795 auto vec = vector(begin(input), end(input));
796 ASSERT_EQ(3, Solution::minJumps(vec));
797 }
798
800 int input[] = {7};
801 auto vec = vector(begin(input), end(input));
802 ASSERT_EQ(0, Solution::minJumps(vec));
803 }
804
806 int input[] = {7, 6, 9, 6, 9, 6, 9, 7};
807 auto vec = vector(begin(input), end(input));
808 ASSERT_EQ(1, Solution::minJumps(vec));
809 }
810
812 int input[] = {6, 1, 9};
813 auto vec = vector(begin(input), end(input));
814 ASSERT_EQ(2, Solution::minJumps(vec));
815 }
816
818 int input[] = {100, -23, -23, 404, 100, 23, 23, 23, 3, 404};
819 auto vec = vector(begin(input), end(input));
820 ASSERT_EQ(3, Solution::minJumps(vec));
821 }
822
824 int input[] = {-76, 3, 66, -32, 64, 2, -19, -8, -5, -93, 80, -5, -76, -78, 64, 2, 16};
825 auto vec = vector(begin(input), end(input));
826 ASSERT_EQ(5, Solution::minJumps(vec));
827 }
828
830 int input[] = {-10, -25, 58, -67, 28, 86, 58, -29, -10, -10, 45, -80, 86, 35, -10, 58, -10, -98, -9, -98, -10, -67, -29, -6, 74, 46, -29, -5, 58, 58, -17, 28, -4, -67, 28, -98, -4, 86, -29, -92, -67, 58, -76, -27, -9, 58, -92, -42, -27, -41, 58, -25, 74, -98, -92, -10, -67, -6, -17, -5, -29, -17, -4, 28, -17, -80, 35, -9, 32, -29, -76, 46, -29, -5, -27, 35, 74, -92, -4, -98, -9, -10, -4, -27, -92, 74, -98, -29, -42, -9, 45, -10, -98, 28};
831 auto vec = vector(begin(input), end(input));
832 ASSERT_EQ(3, Solution::minJumps(vec));
833 }
834
836 int input[] = {7};
837 auto vec = vector(begin(input), end(input));
838 ASSERT_EQ(0, Solution::minJumps(vec));
839 }
840 }// namespace jump_game_iv
841
842 namespace remove_palindromic_subsequences {
844 ASSERT_EQ(1, Solution::removePalindromeSub("ababa"));
845 }
846
848 ASSERT_EQ(2, Solution::removePalindromeSub("abb"));
849 }
850
852 ASSERT_EQ(2, Solution::removePalindromeSub("baabb"));
853 }
854 }// namespace remove_palindromic_subsequences
855
856 namespace UhWRSj {
857 TEST(UhWRSj, case1) {
858 string input[] = {"cat", "bat", "rat"};
859 auto vec = vector(begin(input), end(input));
860 ASSERT_EQ("the cat was rat by the bat", Solution::replaceWords(vec, "the cattle was rattled by the battery"));
861 }
862
863 TEST(UhWRSj, case2) {
864 string input[] = {"a", "b", "c"};
865 auto vec = vector(begin(input), end(input));
866 ASSERT_EQ("a a b c", Solution::replaceWords(vec, "aadsfasf absbs bbab cadsfafs"));
867 }
868
869 TEST(UhWRSj, case3) {
870 string input[] = {"a", "aa", "aaa", "aaaa"};
871 auto vec = vector(begin(input), end(input));
872 ASSERT_EQ("a a a a a a a a bbb baba a", Solution::replaceWords(vec, "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"));
873 }
874
875 TEST(UhWRSj, case4) {
876 string input[] = {"catt", "cat", "bat", "rat"};
877 auto vec = vector(begin(input), end(input));
878 ASSERT_EQ("the cat was rat by the bat", Solution::replaceWords(vec, "the cattle was rattled by the battery"));
879 }
880
881 TEST(UhWRSj, case5) {
882 string input[] = {"ac", "ab"};
883 auto vec = vector(begin(input), end(input));
884 ASSERT_EQ("it is ab that this solution is ac", Solution::replaceWords(vec, "it is abnormal that this solution is accepted"));
885 }
886 }// namespace UhWRSj
887
888 namespace minimum_cost_of_buying_candies_with_discount {
890 int input[] = {1, 2, 3};
891 auto vec = vector(begin(input), end(input));
892 ASSERT_EQ(5, Solution::minimumCost(vec));
893 }
894
896 int input[] = {6, 5, 7, 9, 2, 2};
897 auto vec = vector(begin(input), end(input));
898 ASSERT_EQ(23, Solution::minimumCost(vec));
899 }
900
902 int input[] = {5, 5};
903 auto vec = vector(begin(input), end(input));
904 ASSERT_EQ(10, Solution::minimumCost(vec));
905 }
906 }// namespace minimum_cost_of_buying_candies_with_discount
907
908 namespace count_the_hidden_sequences {
910 int input[] = {1, -3, 4};
911 auto vec = vector(begin(input), end(input));
912 ASSERT_EQ(2, Solution::numberOfArrays(vec, 1, 6));
913 }
914
916 int input[] = {3, -4, 5, 1, -2};
917 auto vec = vector(begin(input), end(input));
918 ASSERT_EQ(4, Solution::numberOfArrays(vec, -4, 5));
919 }
920
922 int input[] = {4, -7, 2};
923 auto vec = vector(begin(input), end(input));
924 ASSERT_EQ(0, Solution::numberOfArrays(vec, 3, 6));
925 }
926 }// namespace count_the_hidden_sequences
927
928 namespace number_of_ways_to_divide_a_long_corridor {
930 ASSERT_EQ(3, Solution::numberOfWays("SSPPSPS"));
931 }
932
934 ASSERT_EQ(1, Solution::numberOfWays("PPSPSP"));
935 }
936
940
944
946 ASSERT_EQ(1, Solution::numberOfWays("PSSSSP"));
947 }
948 }// namespace number_of_ways_to_divide_a_long_corridor
949
950 namespace count_elements_with_strictly_smaller_and_greater_elements {
952 int input[] = {11, 7, 2, 15};
953 auto vec = vector(begin(input), end(input));
954 ASSERT_EQ(2, Solution::countElements(vec));
955 }
956
958 int input[] = {-3, 3, 3, 90};
959 auto vec = vector(begin(input), end(input));
960 ASSERT_EQ(2, Solution::countElements(vec));
961 }
962 }// namespace count_elements_with_strictly_smaller_and_greater_elements
963
964 namespace rearrange_array_elements_by_sign {
966 int input[] = {3, 1, -2, -5, 2, -4};
967 auto vec_input = vector(begin(input), end(input));
968 int output[] = {3, -2, 1, -5, 2, -4};
969 const auto vec_output = vector(begin(output), end(output));
970 ASSERT_EQ(vec_output, Solution::rearrangeArray(vec_input));
971 }
972
974 int input[] = {-1, 1};
975 auto vec_input = vector(begin(input), end(input));
976 int output[] = {1, -1};
977 const auto vec_output = vector(begin(output), end(output));
978 ASSERT_EQ(vec_output, Solution::rearrangeArray(vec_input));
979 }
980 }// namespace rearrange_array_elements_by_sign
981
982 namespace find_all_lonely_numbers_in_the_array {
984 int input[] = {10, 6, 5, 8};
985 auto vec_input = vector(begin(input), end(input));
986 int output[] = {10, 8};
987 const auto vec_output = vector(begin(output), end(output));
988 ASSERT_EQ(vec_output, Solution::findLonely(vec_input));
989 }
990
992 int input[] = {1, 3, 5, 3};
993 auto vec_input = vector(begin(input), end(input));
994 int output[] = {1, 5};
995 const auto vec_output = vector(begin(output), end(output));
996 ASSERT_EQ(vec_output, Solution::findLonely(vec_input));
997 }
998 }// namespace find_all_lonely_numbers_in_the_array
999
1000 namespace maximum_good_people_based_on_statements {
1002 int input1[] = {2, 1, 2};
1003 int input2[] = {1, 2, 2};
1004 int input3[] = {2, 0, 2};
1005 vector<int> input[] = {vector(begin(input1), end(input1)), vector(begin(input2), end(input2)), vector(begin(input3), end(input3))};
1006 auto vec_input = vector(begin(input), end(input));
1007 ASSERT_EQ(2, Solution::maximumGood(vec_input));
1008 }
1009
1011 int input1[] = {2, 0};
1012 int input2[] = {0, 2};
1013 vector<int> input[] = {vector(begin(input1), end(input1)), vector(begin(input2), end(input2))};
1014 auto vec_input = vector(begin(input), end(input));
1015 ASSERT_EQ(1, Solution::maximumGood(vec_input));
1016 }
1017 }// namespace maximum_good_people_based_on_statements
1018
1019 namespace second_minimum_time_to_reach_destination {
1021 int inputs[][2] = {{1, 2}, {1, 3}, {1, 4}, {3, 4}, {4, 5}};
1022 auto vec = vector<vector<int>>();
1023 for(const auto *input: inputs) {
1024 auto n_vec = vector<int>();
1025 n_vec.resize(2);
1026 n_vec[0] = input[0];
1027 n_vec[1] = input[1];
1028 vec.push_back(n_vec);
1029 }
1030 ASSERT_EQ(13, Solution::secondMinimum(5, vec, 3, 5));
1031 }
1032
1034 int inputs[][2] = {{1, 2}};
1035 auto vec = vector<vector<int>>();
1036 for(const auto *input: inputs) {
1037 auto n_vec = vector<int>();
1038 n_vec.resize(2);
1039 n_vec[0] = input[0];
1040 n_vec[1] = input[1];
1041 vec.push_back(n_vec);
1042 }
1043 ASSERT_EQ(11, Solution::secondMinimum(2, vec, 3, 2));
1044 }
1045 }// namespace second_minimum_time_to_reach_destination
1046
1047 namespace count_of_matches_in_tournament {
1049 ASSERT_EQ(6, Solution::numberOfMatches(7));
1050 }
1051
1053 ASSERT_EQ(13, Solution::numberOfMatches(14));
1054 }
1055 }// namespace count_of_matches_in_tournament
1056
1057 namespace number_of_valid_words_in_a_sentence {
1059 ASSERT_EQ(3, Solution::countValidWords("cat and dog"));
1060 }
1061
1063 ASSERT_EQ(0, Solution::countValidWords("!this 1-s b8d!"));
1064 }
1065
1067 ASSERT_EQ(5, Solution::countValidWords("alice and bob are playing stone-game10"));
1068 }
1069
1071 ASSERT_EQ(6, Solution::countValidWords("he bought 2 pencils, 3 erasers, and 1 pencil-sharpener."));
1072 }
1073 }// namespace number_of_valid_words_in_a_sentence
1074
1075 namespace pattern_matching_lcci {
1077 ASSERT_TRUE(Solution::patternMatching("abba", "dogcatcatdog"));
1078 }
1079
1081 ASSERT_FALSE(Solution::patternMatching("abba", "dogcatcatfish"));
1082 }
1083
1085 ASSERT_FALSE(Solution::patternMatching("aaaa", "dogcatcatdog"));
1086 }
1087
1089 ASSERT_TRUE(Solution::patternMatching("abba", "dogdogdogdog"));
1090 }
1091
1093 ASSERT_TRUE(Solution::patternMatching("bb", "tttt"));
1094 }
1095
1097 ASSERT_TRUE(Solution::patternMatching("aaaaab", "xahnxdxyaahnxdxyaahnxdxyaahnxdxyaauxuhuo"));
1098 }
1099 }// namespace pattern_matching_lcci
1100
1101 namespace map_of_highest_peak {
1103 int input[2][2] = {{0, 1}, {0, 0}};
1104 auto vec_in = vector<vector<int>>();
1105 vec_in.resize(2);
1106 for(int i = 0; i < 2; i++) {
1107 vec_in[i] = vector(begin(input[i]), end(input[i]));
1108 }
1109 int output[2][2] = {{1, 0}, {2, 1}};
1110 auto vec_out = vector<vector<int>>();
1111 vec_out.resize(2);
1112 for(int i = 0; i < 2; i++) {
1113 vec_out[i] = vector(begin(output[i]), end(output[i]));
1114 }
1115 ASSERT_EQ(vec_out, Solution::highestPeak(vec_in));
1116 }
1117
1119 int input[3][3] = {{0, 0, 1}, {1, 0, 0}, {0, 0, 0}};
1120 auto vec_in = vector<vector<int>>();
1121 vec_in.resize(3);
1122 for(int i = 0; i < 3; i++) {
1123 vec_in[i] = vector(begin(input[i]), end(input[i]));
1124 }
1125 int output[3][3] = {{1, 1, 0}, {0, 1, 1}, {1, 2, 2}};
1126 auto vec_out = vector<vector<int>>();
1127 vec_out.resize(3);
1128 for(int i = 0; i < 3; i++) {
1129 vec_out[i] = vector(begin(output[i]), end(output[i]));
1130 }
1131 ASSERT_EQ(vec_out, Solution::highestPeak(vec_in));
1132 }
1133 }// namespace map_of_highest_peak
1134
1135 namespace find_substring_with_given_hash_value {
1137 ASSERT_EQ("ee", Solution::subStrHash("leetcode", 7, 20, 2, 0));
1138 }
1139
1141 ASSERT_EQ("fbx", Solution::subStrHash("fbxzaad", 31, 100, 3, 32));
1142 }
1143 }// namespace find_substring_with_given_hash_value
1144
1145 namespace groups_of_strings {
1147 string input[] = {"a", "b", "ab", "cde"};
1148 auto input_vec = vector(begin(input), end(input));
1149 int output[] = {2, 3};
1150 const auto output_vec = vector(begin(output), end(output));
1151 auto sol = Solution();
1152 ASSERT_EQ(output_vec, sol.groupStrings(input_vec));
1153 }
1154
1156 string input[] = {"a", "ab", "abc"};
1157 auto input_vec = vector(begin(input), end(input));
1158 int output[] = {1, 3};
1159 const auto output_vec = vector(begin(output), end(output));
1160 auto sol = Solution();
1161 ASSERT_EQ(output_vec, sol.groupStrings(input_vec));
1162 }
1163
1165 string input[] = {"qamp", "am", "khdrn"};
1166 auto input_vec = vector(begin(input), end(input));
1167 int output[] = {3, 1};
1168 const auto output_vec = vector(begin(output), end(output));
1169 auto sol = Solution();
1170 ASSERT_EQ(output_vec, sol.groupStrings(input_vec));
1171 }
1172
1174 string input[] = {"ghnv", "uip", "tenv", "hvepx", "e", "ktc", "byjdt", "ulm", "cae", "ea"};
1175 auto input_vec = vector(begin(input), end(input));
1176 int output[] = {8, 3};
1177 const auto output_vec = vector(begin(output), end(output));
1178 auto sol = Solution();
1179 ASSERT_EQ(output_vec, sol.groupStrings(input_vec));
1180 }
1181
1183 string input[] = {"web", "a", "te", "hsx", "v", "k", "a", "roh"};
1184 auto input_vec = vector(begin(input), end(input));
1185 int output[] = {5, 4};
1186 const auto output_vec = vector(begin(output), end(output));
1187 auto sol = Solution();
1188 ASSERT_EQ(output_vec, sol.groupStrings(input_vec));
1189 }
1190 }// namespace groups_of_strings
1191
1192 namespace number_of_steps_to_reduce_a_number_to_zero {
1196
1200
1204 }// namespace number_of_steps_to_reduce_a_number_to_zero
1205
1206 namespace longest_nice_substring {
1208 ASSERT_EQ("aAa", Solution::longestNiceSubstring("YazaAay"));
1209 }
1210
1212 ASSERT_EQ("Bb", Solution::longestNiceSubstring("Bb"));
1213 }
1214
1216 ASSERT_EQ("", Solution::longestNiceSubstring("c"));
1217 }
1218
1220 ASSERT_EQ("dD", Solution::longestNiceSubstring("dDzeE"));
1221 }
1222 }// namespace longest_nice_substring
1223
1224 namespace reverse_prefix_of_word {
1226 ASSERT_EQ("dcbaefd", Solution::reversePrefix("abcdefd", 'd'));
1227 }
1228
1230 ASSERT_EQ("zxyxxe", Solution::reversePrefix("xyxzxe", 'z'));
1231 }
1232
1234 ASSERT_EQ("abcd", Solution::reversePrefix("abcd", 'z'));
1235 }
1236 }// namespace reverse_prefix_of_word
1237
1238 namespace find_the_minimum_number_of_fibonacci_numbers_whose_sum_is_k {
1242
1246
1250 }// namespace find_the_minimum_number_of_fibonacci_numbers_whose_sum_is_k
1251
1252 namespace number_of_rectangles_that_can_form_the_largest_square {
1254 vector<vector<int>> input = {{5, 8}, {3, 9}, {5, 12}, {16, 5}};
1255 ASSERT_EQ(3, Solution::countGoodRectangles(input));
1256 }
1257
1259 vector<vector<int>> input = {{2, 3}, {3, 7}, {4, 3}, {3, 7}};
1260 ASSERT_EQ(3, Solution::countGoodRectangles(input));
1261 }
1262 }// namespace number_of_rectangles_that_can_form_the_largest_square
1263
1264 namespace path_with_maximum_gold {
1266 vector<vector<int>> input = {{0, 6, 0}, {5, 8, 7}, {0, 9, 0}};
1267 ASSERT_EQ(24, Solution::getMaximumGold(input));
1268 }
1269
1271 vector<vector<int>> input = {{1, 0, 7}, {2, 0, 6}, {3, 4, 5}, {0, 3, 0}, {9, 0, 20}};
1272 ASSERT_EQ(28, Solution::getMaximumGold(input));
1273 }
1274 }// namespace path_with_maximum_gold
1275
1276 namespace minimum_difference_in_sums_after_removal_of_elements {
1278 vector input = {3, 1, 2};
1279 ASSERT_EQ(-1, Solution::minimumDifference(input));
1280 }
1281
1283 vector input = {7, 9, 5, 8, 1, 3};
1284 ASSERT_EQ(1, Solution::minimumDifference(input));
1285 }
1286 }// namespace minimum_difference_in_sums_after_removal_of_elements
1287
1288 namespace sum_of_unique_elements {
1290 vector input = {1, 2, 3, 2};
1291 ASSERT_EQ(4, Solution::sumOfUnique(input));
1292 }
1293
1295 vector input = {1, 1, 1, 1, 1};
1296 ASSERT_EQ(0, Solution::sumOfUnique(input));
1297 }
1298
1300 vector input = {1, 2, 3, 4, 5};
1301 ASSERT_EQ(15, Solution::sumOfUnique(input));
1302 }
1303 }// namespace sum_of_unique_elements
1304
1305 namespace smallest_value_of_the_rearranged_number {
1307 ASSERT_EQ(103, Solution::smallestNumber(310));
1308 }
1309
1311 ASSERT_EQ(-7650, Solution::smallestNumber(-7605));
1312 }
1313
1315 ASSERT_EQ(-6333221000, Solution::smallestNumber(-2230363001));
1316 }
1317 }// namespace smallest_value_of_the_rearranged_number
1318
1319 namespace design_bitset {
1321 auto bt = Bitset(5);
1322 bt.fix(3);
1323 bt.fix(1);
1324 bt.flip();
1325 ASSERT_FALSE(bt.all());
1326 bt.unfix(0);
1327 bt.flip();
1328 ASSERT_TRUE(bt.one());
1329 bt.unfix(0);
1330 ASSERT_EQ(2, bt.count());
1331 ASSERT_EQ("01010", bt.toString());
1332 }
1333 }// namespace design_bitset
1334
1335 namespace longest_happy_string {
1337 ASSERT_EQ("ccbccacc", Solution::longestDiverseString(1, 1, 7));
1338 }
1339
1341 ASSERT_EQ("aabaa", Solution::longestDiverseString(7, 1, 0));
1342 }
1343 }// namespace longest_happy_string
1344
1345 namespace grid_illumination {
1347 vector<vector<int>> lamps = {{0, 0}, {4, 4}};
1348 vector<vector<int>> queries = {{1, 1}, {1, 0}};
1349 const vector output = {1, 0};
1350 ASSERT_EQ(output, Solution::gridIllumination(5, lamps, queries));
1351 }
1352
1354 vector<vector<int>> lamps = {{0, 0}, {4, 4}};
1355 vector<vector<int>> queries = {{1, 1}, {1, 1}};
1356 const vector output = {1, 1};
1357 ASSERT_EQ(output, Solution::gridIllumination(5, lamps, queries));
1358 }
1359
1361 vector<vector<int>> lamps = {{0, 0}, {0, 4}};
1362 vector<vector<int>> queries = {{0, 4}, {0, 1}, {1, 4}};
1363 const vector output = {1, 1, 0};
1364 ASSERT_EQ(output, Solution::gridIllumination(5, lamps, queries));
1365 }
1366
1368 vector<vector<int>> lamps = {{1, 1}};
1369 vector<vector<int>> queries = {{2, 0}, {1, 0}};
1370 const vector output = {1, 0};
1371 ASSERT_EQ(output, Solution::gridIllumination(6, lamps, queries));
1372 }
1373
1375 vector<vector<int>> lamps = {{2, 5}, {4, 2}, {0, 3}, {0, 5}, {1, 4}, {4, 2}, {3, 3}, {1, 0}};
1376 vector<vector<int>> queries = {{4, 3}, {3, 1}, {5, 3}, {0, 5}, {4, 4}, {3, 3}};
1377 const vector output = {1, 0, 1, 1, 0, 1};
1378 ASSERT_EQ(output, Solution::gridIllumination(6, lamps, queries));
1379 }
1380 }// namespace grid_illumination
1381
1382 namespace count_number_of_pairs_with_absolute_difference_k {
1384 vector input = {1, 2, 2, 1};
1385 ASSERT_EQ(4, Solution::countKDifference(input, 1));
1386 }
1387
1389 vector input = {1, 3};
1390 ASSERT_EQ(0, Solution::countKDifference(input, 3));
1391 }
1392
1394 vector input = {3, 2, 1, 5, 4};
1395 ASSERT_EQ(3, Solution::countKDifference(input, 2));
1396 }
1397 }// namespace count_number_of_pairs_with_absolute_difference_k
1398
1399 namespace simplified_fractions {
1401 const vector<string> output = {"1/2"};
1402 ASSERT_EQ(output, Solution::simplifiedFractions(2));
1403 }
1404
1406 const vector<string> output = {"1/2", "1/3", "2/3"};
1407 ASSERT_EQ(output, Solution::simplifiedFractions(3));
1408 }
1409
1411 const vector<string> output = {"1/2", "1/3", "2/3", "1/4", "3/4"};
1412 ASSERT_EQ(output, Solution::simplifiedFractions(4));
1413 }
1414 }// namespace simplified_fractions
1415
1416 namespace minimum_difference_between_highest_and_lowest_of_k_scores {
1418 vector input = {90};
1419 ASSERT_EQ(0, Solution::minimumDifference(input, 1));
1420 }
1421
1423 vector input = {9, 4, 1, 7};
1424 ASSERT_EQ(2, Solution::minimumDifference(input, 2));
1425 }
1426 }// namespace minimum_difference_between_highest_and_lowest_of_k_scores
1427
1428 namespace number_of_enclaves {
1430 vector<vector<int>> input = {{0, 0, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 0}, {0, 0, 0, 0}};
1431 ASSERT_EQ(3, Solution::numEnclaves(input));
1432 }
1433
1435 vector<vector<int>> input = {{0, 1, 1, 0}, {0, 0, 1, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}};
1436 ASSERT_EQ(0, Solution::numEnclaves(input));
1437 }
1438 }// namespace number_of_enclaves
1439
1440 namespace maximum_number_of_balloons {
1442 ASSERT_EQ(1, Solution::maxNumberOfBalloons("nlaebolko"));
1443 }
1444
1446 ASSERT_EQ(2, Solution::maxNumberOfBalloons("loonbalxballpoon"));
1447 }
1448
1450 ASSERT_EQ(0, Solution::maxNumberOfBalloons("leetcode"));
1451 }
1452 }// namespace maximum_number_of_balloons
1453
1454 namespace swap_adjacent_in_lr_string {
1456 ASSERT_TRUE(Solution::canTransform("RXXLRXRXL", "XRLXXRRLX"));
1457 }
1458
1460 ASSERT_FALSE(Solution::canTransform("X", "L"));
1461 }
1462
1464 ASSERT_FALSE(Solution::canTransform("LXXLXRLXXL", "XLLXRXLXLX"));
1465 }
1466 }// namespace swap_adjacent_in_lr_string
1467
1468 namespace count_operations_to_obtain_zero {
1470 ASSERT_EQ(3, Solution::countOperations(2, 3));
1471 }
1472
1474 ASSERT_EQ(1, Solution::countOperations(10, 10));
1475 }
1476 }// namespace count_operations_to_obtain_zero
1477
1478 namespace minimum_operations_to_make_the_array_alternating {
1480 vector input = {3, 1, 3, 2, 4, 3};
1481 ASSERT_EQ(3, Solution::minimumOperations(input));
1482 }
1483
1485 vector input = {1, 2, 2, 2, 2};
1486 ASSERT_EQ(2, Solution::minimumOperations(input));
1487 }
1488
1490 vector input = {69, 91, 47, 74, 75, 94, 22, 100, 43, 50, 82, 47, 40, 51, 90, 27, 98, 85, 47, 14, 55, 82, 52, 9, 65, 90, 86, 45, 52, 52, 95, 40, 85, 3, 46, 77, 16, 59, 32, 22, 41, 87, 89, 78, 59, 78, 34, 26, 71, 9, 82, 68, 80, 74, 100, 6, 10, 53, 84, 80, 7, 87, 3, 82, 26, 26, 14, 37, 26, 58, 96, 73, 41, 2, 79, 43, 56, 74, 30, 71, 6, 100, 72, 93, 83, 40, 28, 79, 24};
1491 ASSERT_EQ(84, Solution::minimumOperations(input));
1492 }
1493 }// namespace minimum_operations_to_make_the_array_alternating
1494
1495 namespace removing_minimum_number_of_magic_beans {
1497 vector input = {4, 1, 6, 5};
1498 ASSERT_EQ(4, Solution::minimumRemoval(input));
1499 }
1500
1502 vector input = {2, 10, 3, 2};
1503 ASSERT_EQ(7, Solution::minimumRemoval(input));
1504 }
1505 }// namespace removing_minimum_number_of_magic_beans
1506
1507 namespace maximum_and_sum_of_array {
1509 vector input = {1, 2, 3, 4, 5, 6};
1510 ASSERT_EQ(9, Solution::maximumANDSum(input, 3));
1511 }
1512
1514 vector input = {1, 3, 10, 4, 7, 1};
1515 ASSERT_EQ(24, Solution::maximumANDSum(input, 9));
1516 }
1517 }// namespace maximum_and_sum_of_array
1518
1519 namespace single_element_in_a_sorted_array {
1521 vector input = {1, 1, 2, 3, 3, 4, 4, 8, 8};
1522 ASSERT_EQ(2, Solution::singleNonDuplicate(input));
1523 }
1524
1526 vector input = {3, 3, 7, 7, 10, 11, 11};
1527 ASSERT_EQ(10, Solution::singleNonDuplicate(input));
1528 }
1529 }// namespace single_element_in_a_sorted_array
1530
1531 namespace lucky_numbers_in_a_matrix {
1533 vector<vector<int>> input = {{3, 7, 8}, {9, 11, 13}, {15, 16, 17}};
1534 const vector output = {15};
1535 ASSERT_EQ(output, Solution::luckyNumbers(input));
1536 }
1537
1539 vector<vector<int>> input = {{1, 10, 4, 2}, {9, 3, 8, 7}, {15, 16, 17, 12}};
1540 const vector output = {12};
1541 ASSERT_EQ(output, Solution::luckyNumbers(input));
1542 }
1543
1545 vector<vector<int>> input = {{7, 8}, {1, 2}};
1546 const vector output = {7};
1547 ASSERT_EQ(output, Solution::luckyNumbers(input));
1548 }
1549 }// namespace lucky_numbers_in_a_matrix
1550
1551 namespace number_of_ways_to_reconstruct_a_tree {
1553 vector<vector<int>> input = {{1, 2}, {2, 3}};
1554 ASSERT_EQ(1, Solution::checkWays(input));
1555 }
1556
1558 vector<vector<int>> input = {{1, 2}, {2, 3}, {1, 3}};
1559 ASSERT_EQ(2, Solution::checkWays(input));
1560 }
1561
1563 vector<vector<int>> input = {{1, 2}, {2, 3}, {2, 4}, {1, 5}};
1564 ASSERT_EQ(0, Solution::checkWays(input));
1565 }
1566 }// namespace number_of_ways_to_reconstruct_a_tree
1567
1568 namespace find_center_of_star_graph {
1570 vector<vector<int>> input = {{1, 2}, {2, 3}, {4, 2}};
1571 ASSERT_EQ(2, Solution::findCenter(input));
1572 }
1573
1575 vector<vector<int>> input = {{1, 2}, {5, 1}, {1, 3}, {1, 4}};
1576 ASSERT_EQ(1, Solution::findCenter(input));
1577 }
1578 }// namespace find_center_of_star_graph
1579
1580 namespace knight_probability_in_chessboard {
1582 auto sol = Solution();
1583 ASSERT_EQ(0.06250, sol.knightProbability(3, 2, 0, 0));
1584 }
1585
1587 auto sol = Solution();
1588 ASSERT_EQ(1.00000, sol.knightProbability(1, 0, 0, 0));
1589 }
1590 }// namespace knight_probability_in_chessboard
1591
1592 namespace count_equal_and_divisible_pairs_in_an_array {
1594 vector input = {3, 1, 2, 2, 2, 1, 3};
1595 ASSERT_EQ(4, Solution::countPairs(input, 2));
1596 }
1597
1599 vector input = {1, 2, 3, 4};
1600 ASSERT_EQ(0, Solution::countPairs(input, 1));
1601 }
1602 }// namespace count_equal_and_divisible_pairs_in_an_array
1603
1604 namespace find_three_consecutive_integers_that_sum_to_a_given_number {
1606 const vector<long long> output = {10, 11, 12};
1607 ASSERT_EQ(output, Solution::sumOfThree(33));
1608 }
1609
1611 const vector<long long> output = {};
1612 ASSERT_EQ(output, Solution::sumOfThree(4));
1613 }
1614 }// namespace find_three_consecutive_integers_that_sum_to_a_given_number
1615
1616 namespace maximum_split_of_positive_even_integers {
1618 const vector<long long> output = {2, 4, 6};
1619 ASSERT_EQ(output, Solution::maximumEvenSplit(12));
1620 }
1621
1623 const vector<long long> output = {};
1624 ASSERT_EQ(output, Solution::maximumEvenSplit(7));
1625 }
1626
1628 const vector<long long> output = {2, 4, 6, 16};
1629 ASSERT_EQ(output, Solution::maximumEvenSplit(28));
1630 }
1631 }// namespace maximum_split_of_positive_even_integers
1632
1633 namespace count_good_triplets_in_an_array {
1635 vector input1 = {2, 0, 1, 3};
1636 vector input2 = {0, 1, 2, 3};
1637 ASSERT_EQ(1, Solution::goodTriplets(input1, input2));
1638 }
1639
1641 vector input1 = {4, 0, 1, 3, 2};
1642 vector input2 = {4, 1, 0, 2, 3};
1643 ASSERT_EQ(4, Solution::goodTriplets(input1, input2));
1644 }
1645 }// namespace count_good_triplets_in_an_array
1646
1647 namespace count_integers_with_even_digit_sum {
1649 ASSERT_EQ(2, Solution::countEven(4));
1650 }
1651
1653 ASSERT_EQ(14, Solution::countEven(30));
1654 }
1655 }// namespace count_integers_with_even_digit_sum
1656
1657 namespace construct_string_with_repeat_limit {
1659 ASSERT_EQ("zzcccac", Solution::repeatLimitedString("cczazcc", 3));
1660 }
1661
1663 ASSERT_EQ("bbabaa", Solution::repeatLimitedString("aababab", 2));
1664 }
1665
1667 ASSERT_EQ("yxxvvuvusrrqqppopponliihgfeeddcbba", Solution::repeatLimitedString("robnsdvpuxbapuqgopqvxdrchivlifeepy", 2));
1668 }
1669 }// namespace construct_string_with_repeat_limit
1670
1671 namespace count_array_pairs_divisible_by_k {
1673 vector input = {1, 2, 3, 4, 5};
1674 ASSERT_EQ(7, Solution::coutPairs(input, 2));
1675 }
1676
1678 vector input = {1, 2, 3, 4};
1679 ASSERT_EQ(0, Solution::coutPairs(input, 5));
1680 }
1681
1683 vector input = {8, 10, 2, 5, 9, 6, 3, 8, 2};
1684 ASSERT_EQ(18, Solution::coutPairs(input, 6));
1685 }
1686 }// namespace count_array_pairs_divisible_by_k
1687
1688 namespace leetcode717_1_bit_and_2_bit_characters {
1690 vector input = {1, 0, 0};
1691 ASSERT_TRUE(Solution::isOneBitCharacter(input));
1692 }
1693
1695 vector input = {1, 1, 1, 0};
1696 ASSERT_FALSE(Solution::isOneBitCharacter(input));
1697 }
1698 }// namespace leetcode717_1_bit_and_2_bit_characters
1699
1700 namespace longest_mountain_in_array {
1702 vector input = {2, 1, 4, 7, 3, 2, 5};
1703 ASSERT_EQ(5, Solution::longestMountain(input));
1704 }
1705
1707 vector input = {2, 2, 2};
1708 ASSERT_EQ(0, Solution::longestMountain(input));
1709 }
1710 }// namespace longest_mountain_in_array
1711
1712 namespace push_dominoes {
1714 ASSERT_EQ("RR.L", Solution::pushDominoes("RR.L"));
1715 }
1716
1718 ASSERT_EQ("LL.RR.LLRRLL..", Solution::pushDominoes(".L.R...LR..L.."));
1719 }
1720 }// namespace push_dominoes
1721
1722 namespace the_number_of_good_subsets {
1724 vector input = {1, 2, 3, 4};
1725 ASSERT_EQ(6, Solution::numberOfGoodSubsets(input));
1726 }
1727
1729 vector input = {4, 2, 3, 15};
1730 ASSERT_EQ(5, Solution::numberOfGoodSubsets(input));
1731 }
1732 }// namespace the_number_of_good_subsets
1733
1734 namespace reverse_only_letters {
1736 ASSERT_EQ("dc-ba", Solution::reverseOnlyLetters("ab-cd"));
1737 }
1738
1740 ASSERT_EQ("j-Ih-gfE-dCba", Solution::reverseOnlyLetters("a-bC-dEf-ghIj"));
1741 }
1742
1744 ASSERT_EQ("Qedo1ct-eeLg=ntse-T!", Solution::reverseOnlyLetters("Test1ng-Leet=code-Q!"));
1745 }
1746 }// namespace reverse_only_letters
1747
1748 namespace where_will_the_ball_fall {
1750 vector<vector<int>> input = {{1, 1, 1, -1, -1}, {1, 1, 1, -1, -1}, {-1, -1, -1, 1, 1}, {1, 1, 1, 1, -1}, {-1, -1, -1, -1, -1}};
1751 const vector output = {1, -1, -1, -1, -1};
1752 ASSERT_EQ(output, Solution::findBall(input));
1753 }
1754
1756 vector<vector<int>> input = {{-1}};
1757 const vector output = {-1};
1758 ASSERT_EQ(output, Solution::findBall(input));
1759 }
1760
1762 vector<vector<int>> input = {{1, 1, 1, 1, 1, 1}, {-1, -1, -1, -1, -1, -1}, {1, 1, 1, 1, 1, 1}, {-1, -1, -1, -1, -1, -1}};
1763 const vector output = {0, 1, 2, 3, 4, -1};
1764 ASSERT_EQ(output, Solution::findBall(input));
1765 }
1766 }// namespace where_will_the_ball_fall
1767
1768 namespace complex_number_multiplication {
1770 ASSERT_EQ("0+2i", Solution::complexNumberMultiply("1+1i", "1+1i"));
1771 }
1772
1774 ASSERT_EQ("0+-2i", Solution::complexNumberMultiply("1+-1i", "1+-1i"));
1775 }
1776 }// namespace complex_number_multiplication
1777
1778 namespace counting_words_with_a_given_prefix {
1780 vector<string> input = {"pay", "attention", "practice", "attend"};
1781 ASSERT_EQ(2, Solution::prefixCount(input, "at"));
1782 }
1783
1785 vector<string> input = {"leetcode", "win", "loops", "success"};
1786 ASSERT_EQ(0, Solution::prefixCount(input, "code"));
1787 }
1788 }// namespace counting_words_with_a_given_prefix
1789
1790 namespace minimum_number_of_steps_to_make_two_strings_anagram_ii {
1792 ASSERT_EQ(7, Solution::minSteps("leetcode", "coats"));
1793 }
1794
1796 ASSERT_EQ(0, Solution::minSteps("night", "thing"));
1797 }
1798 }// namespace minimum_number_of_steps_to_make_two_strings_anagram_ii
1799
1800 namespace maximum_difference_between_increasing_elements {
1802 vector input = {7, 1, 5, 4};
1803 ASSERT_EQ(4, Solution::maximumDifference(input));
1804 }
1805
1807 vector input = {9, 4, 3, 2};
1808 ASSERT_EQ(-1, Solution::maximumDifference(input));
1809 }
1810
1812 vector input = {1, 5, 2, 10};
1813 ASSERT_EQ(9, Solution::maximumDifference(input));
1814 }
1815 }// namespace maximum_difference_between_increasing_elements
1816
1817 namespace optimal_division {
1819 vector input = {1000, 100, 10, 2};
1820 ASSERT_EQ("1000/(100/10/2)", Solution::optimalDivision(input));
1821 }
1822
1824 vector input = {2, 3, 4};
1825 ASSERT_EQ("2/(3/4)", Solution::optimalDivision(input));
1826 }
1827
1829 vector input = {2};
1830 ASSERT_EQ("2", Solution::optimalDivision(input));
1831 }
1832 }// namespace optimal_division
1833
1834 namespace minimum_time_to_complete_trips {
1836 vector input = {1, 2, 3};
1837 ASSERT_EQ(3, Solution::minimumTime(input, 5));
1838 }
1839
1841 vector input = {2};
1842 ASSERT_EQ(2, Solution::minimumTime(input, 1));
1843 }
1844
1846 vector input = {5, 10, 10};
1847 ASSERT_EQ(25, Solution::minimumTime(input, 9));
1848 }
1849 }// namespace minimum_time_to_complete_trips
1850
1851 namespace minimum_time_to_finish_the_race {
1853 vector<vector<int>> input = {{2, 3}, {3, 4}};
1854 ASSERT_EQ(21, Solution::minimumFinishTime(input, 5, 4));
1855 }
1856
1858 vector<vector<int>> input = {{1, 10}, {2, 2}, {3, 4}};
1859 ASSERT_EQ(25, Solution::minimumFinishTime(input, 6, 5));
1860 }
1861 }// namespace minimum_time_to_finish_the_race
1862
1863 namespace maximum_number_of_achievable_transfer_requests {
1865 vector<vector<int>> input = {{0, 1}, {1, 0}, {0, 1}, {1, 2}, {2, 0}, {3, 4}};
1866 ASSERT_EQ(5, Solution::maximumRequests(5, input));
1867 }
1868
1870 vector<vector<int>> input = {{0, 0}, {1, 2}, {2, 1}};
1871 ASSERT_EQ(3, Solution::maximumRequests(3, input));
1872 }
1873
1875 vector<vector<int>> input = {{0, 3}, {3, 1}, {1, 2}, {2, 0}};
1876 ASSERT_EQ(4, Solution::maximumRequests(4, input));
1877 }
1878 }// namespace maximum_number_of_achievable_transfer_requests
1879
1880 namespace zigzag_conversion {
1882 ASSERT_EQ("PAHNAPLSIIGYIR", Solution::convert("PAYPALISHIRING", 3));
1883 }
1884
1886 ASSERT_EQ("PINALSIGYAHRPI", Solution::convert("PAYPALISHIRING", 4));
1887 }
1888
1890 ASSERT_EQ("A", Solution::convert("A", 1));
1891 }
1892 }// namespace zigzag_conversion
1893
1894 namespace find_the_closest_palindrome {
1896 ASSERT_EQ("121", Solution::nearestPalindromic("123"));
1897 }
1898
1900 ASSERT_EQ("0", Solution::nearestPalindromic("1"));
1901 }
1902
1904 ASSERT_EQ("1221", Solution::nearestPalindromic("1234"));
1905 }
1906
1908 ASSERT_EQ("1001", Solution::nearestPalindromic("999"));
1909 }
1910
1912 ASSERT_EQ("999", Solution::nearestPalindromic("1000"));
1913 }
1914
1916 ASSERT_EQ("12921", Solution::nearestPalindromic("12932"));
1917 }
1918
1920 ASSERT_EQ("99799", Solution::nearestPalindromic("99800"));
1921 }
1922
1924 ASSERT_EQ("12121", Solution::nearestPalindromic("12120"));
1925 }
1926
1928 ASSERT_EQ("1805115081", Solution::nearestPalindromic("1805170081"));
1929 }
1930 }// namespace find_the_closest_palindrome
1931
1932 namespace add_digits {
1934 ASSERT_EQ(2, Solution::addDigits(38));
1935 }
1936
1938 ASSERT_EQ(0, Solution::addDigits(0));
1939 }
1940 }// namespace add_digits
1941
1942 namespace sum_of_subarray_ranges {
1944 vector input = {1, 2, 3};
1945 ASSERT_EQ(4, Solution::subArrayRanges(input));
1946 }
1947
1949 vector input = {1, 3, 3};
1950 ASSERT_EQ(4, Solution::subArrayRanges(input));
1951 }
1952
1954 vector input = {4, -2, -3, 4, 1};
1955 ASSERT_EQ(59, Solution::subArrayRanges(input));
1956 }
1957 }// namespace sum_of_subarray_ranges
1958
1959 namespace longest_uncommon_subsequence_i {
1961 ASSERT_EQ(3, Solution::findLUSlength("aba", "cdc"));
1962 }
1963
1965 ASSERT_EQ(3, Solution::findLUSlength("aaa", "bbb"));
1966 }
1967
1969 ASSERT_EQ(-1, Solution::findLUSlength("aaa", "aaa"));
1970 }
1971 }// namespace longest_uncommon_subsequence_i
1972
1973 namespace most_frequent_number_following_key_in_an_array {
1975 vector input = {1, 100, 200, 1, 100};
1976 ASSERT_EQ(100, Solution::mostFrequent(input, 1));
1977 }
1978
1980 vector input = {2, 2, 2, 2, 3};
1981 ASSERT_EQ(2, Solution::mostFrequent(input, 2));
1982 }
1983 }// namespace most_frequent_number_following_key_in_an_array
1984
1985 namespace sort_the_jumbled_numbers {
1987 vector mapping = {8, 9, 4, 0, 2, 1, 3, 5, 7, 6};
1988 vector nums = {991, 338, 38};
1989 const vector output = {338, 38, 991};
1990 ASSERT_EQ(output, Solution::sortJumbled(mapping, nums));
1991 }
1992
1994 vector mapping = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
1995 vector nums = {789, 456, 123};
1996 const vector output = {123, 456, 789};
1997 ASSERT_EQ(output, Solution::sortJumbled(mapping, nums));
1998 }
1999 }// namespace sort_the_jumbled_numbers
2000
2001 namespace all_ancestors_of_a_node_in_a_directed_acyclic_graph {
2003 vector<vector<int>> input = {{0, 3}, {0, 4}, {1, 3}, {2, 4}, {2, 7}, {3, 5}, {3, 6}, {3, 7}, {4, 6}};
2004 const vector<vector<int>> output = {{}, {}, {}, {0, 1}, {0, 2}, {0, 1, 3}, {0, 1, 2, 3, 4}, {0, 1, 2, 3}};
2005 auto sol = Solution();
2006 ASSERT_EQ(output, sol.getAncestors(8, input));
2007 }
2008
2010 vector<vector<int>> input = {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}};
2011 const vector<vector<int>> output = {{}, {0}, {0, 1}, {0, 1, 2}, {0, 1, 2, 3}};
2012 auto sol = Solution();
2013 ASSERT_EQ(output, sol.getAncestors(5, input));
2014 }
2015 }// namespace all_ancestors_of_a_node_in_a_directed_acyclic_graph
2016
2017 namespace minimum_number_of_moves_to_make_palindrome {
2021
2025
2027 ASSERT_EQ(163, Solution::minMovesToMakePalindrome("skwhhaaunskegmdtutlgtteunmuuludii"));
2028 }
2029 }// namespace minimum_number_of_moves_to_make_palindrome
2030
2031 namespace cells_in_a_range_on_an_excel_sheet {
2033 const vector<string> output = {"K1", "K2", "L1", "L2"};
2034 ASSERT_EQ(output, Solution::cellsInRange("K1:L2"));
2035 }
2036
2038 const vector<string> output = {"A1", "B1", "C1", "D1", "E1", "F1"};
2039 ASSERT_EQ(output, Solution::cellsInRange("A1:F1"));
2040 }
2041 }// namespace cells_in_a_range_on_an_excel_sheet
2042
2043 namespace append_k_integers_with_minimal_sum {
2045 vector input = {96, 44, 99, 25, 61, 84, 88, 18, 19, 33, 60, 86, 52, 19, 32, 47, 35, 50, 94, 17, 29, 98, 22, 21, 72, 100, 40, 84};
2046 ASSERT_EQ(794, Solution::minimalKSum(input, 35));
2047 }
2048
2050 vector input = {5, 6};
2051 ASSERT_EQ(25, Solution::minimalKSum(input, 6));
2052 }
2053
2055 vector input = {1, 4, 25, 10, 25};
2056 ASSERT_EQ(5, Solution::minimalKSum(input, 2));
2057 }
2058
2060 vector input = {1, 2};
2061 ASSERT_EQ(3, Solution::minimalKSum(input, 1));
2062 }
2063
2065 vector input = {2, 2, 2, 2};
2066 ASSERT_EQ(8, Solution::minimalKSum(input, 3));
2067 }
2068 }// namespace append_k_integers_with_minimal_sum
2069
2070 namespace replace_non_coprime_numbers_in_array {
2072 vector input = {6, 4, 3, 2, 7, 6, 2};
2073 const vector output = {12, 7, 6};
2074 ASSERT_EQ(output, Solution::replaceNonCoprimes(input));
2075 }
2076
2078 vector input = {2, 2, 1, 1, 3, 3, 3};
2079 const vector output = {2, 1, 1, 3};
2080 ASSERT_EQ(output, Solution::replaceNonCoprimes(input));
2081 }
2082 }// namespace replace_non_coprime_numbers_in_array
2083
2084 namespace find_good_days_to_rob_the_bank {
2086 vector input = {5, 3, 3, 3, 5, 6, 2};
2087 const vector output = {2, 3};
2088 ASSERT_EQ(output, Solution::goodDaysToRobBank(input, 2));
2089 }
2090
2092 vector input = {1, 1, 1, 1, 1};
2093 const vector output = {0, 1, 2, 3, 4};
2094 ASSERT_EQ(output, Solution::goodDaysToRobBank(input, 0));
2095 }
2096
2098 vector input = {1, 2, 3, 4, 5, 6};
2099 const vector<int> output = {};
2100 ASSERT_EQ(output, Solution::goodDaysToRobBank(input, 2));
2101 }
2102
2104 vector input = {4, 3, 2, 1};
2105 const vector<int> output = {};
2106 ASSERT_EQ(output, Solution::goodDaysToRobBank(input, 1));
2107 }
2108 }// namespace find_good_days_to_rob_the_bank
2109
2110 namespace base_7 {
2111 TEST(base_7, case1) {
2112 ASSERT_EQ("202", Solution::convertToBase7(100));
2113 }
2114
2115 TEST(base_7, case2) {
2116 ASSERT_EQ("-10", Solution::convertToBase7(-7));
2117 }
2118 }// namespace base_7
2119
2120 namespace plates_between_candles {
2122 vector<vector<int>> input = {{2, 5}, {5, 9}};
2123 const vector output = {2, 3};
2124 ASSERT_EQ(output, Solution::platesBetweenCandles("**|**|***|", input));
2125 }
2126
2128 vector<vector<int>> input = {{1, 17}, {4, 5}, {14, 17}, {5, 11}, {15, 16}};
2129 const vector output = {9, 0, 0, 0, 0};
2130 ASSERT_EQ(output, Solution::platesBetweenCandles("***|**|*****|**||**|*", input));
2131 }
2132 }// namespace plates_between_candles
2133
2134 namespace smallest_rotation_with_highest_score {
2136 vector input = {2, 3, 1, 4, 0};
2137 ASSERT_EQ(3, Solution::bestRotation(input));
2138 }
2139
2141 vector input = {1, 3, 0, 2, 4};
2142 ASSERT_EQ(0, Solution::bestRotation(input));
2143 }
2144 }// namespace smallest_rotation_with_highest_score
2145
2146 namespace count_nodes_with_the_highest_score {
2148 vector input = {-1, 2, 0, 2, 0};
2149 ASSERT_EQ(3, Solution::countHighestScoreNodes(input));
2150 }
2151
2153 vector input = {-1, 2, 0};
2154 ASSERT_EQ(2, Solution::countHighestScoreNodes(input));
2155 }
2156 }// namespace count_nodes_with_the_highest_score
2157
2158 namespace max_area_of_island {
2160 vector<vector<int>> input = {{0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
2161 {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
2162 {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
2163 {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
2164 {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
2165 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
2166 {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
2167 {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}};
2168 ASSERT_EQ(6, Solution::maxAreaOfIsland(input));
2169 }
2170
2172 vector<vector<int>> input = {{0, 0, 0, 0, 0, 0, 0, 0}};
2173 ASSERT_EQ(0, Solution::maxAreaOfIsland(input));
2174 }
2175 }// namespace max_area_of_island
2176
2177 namespace find_all_k_distant_indices_in_an_array {
2179 vector nums = {3, 4, 9, 1, 3, 9, 5};
2180 const vector output = {1, 2, 3, 4, 5, 6};
2181 ASSERT_EQ(output, Solution::findKDistantIndices(nums, 9, 1));
2182 }
2183
2185 vector nums = {2, 2, 2, 2, 2};
2186 const vector output = {0, 1, 2, 3, 4};
2187 ASSERT_EQ(output, Solution::findKDistantIndices(nums, 2, 2));
2188 }
2189 }// namespace find_all_k_distant_indices_in_an_array
2190
2191 namespace count_artifacts_that_can_be_extracted {
2193 vector<vector<int>> artifacts = {{0, 0, 0, 0}, {0, 1, 1, 1}};
2194 vector<vector<int>> dig = {{0, 0}, {0, 1}};
2195 ASSERT_EQ(1, Solution::digArtifacts(2, artifacts, dig));
2196 }
2197
2199 vector<vector<int>> artifacts = {{0, 0, 0, 0}, {0, 1, 1, 1}};
2200 vector<vector<int>> dig = {{0, 0}, {0, 1}, {1, 1}};
2201 ASSERT_EQ(2, Solution::digArtifacts(2, artifacts, dig));
2202 }
2203 }// namespace count_artifacts_that_can_be_extracted
2204
2205 namespace maximize_the_topmost_element_after_k_moves {
2207 vector nums = {5, 2, 2, 4, 0, 6};
2208 ASSERT_EQ(5, Solution::maximumTop(nums, 4));
2209 }
2210
2212 vector nums = {2};
2213 ASSERT_EQ(-1, Solution::maximumTop(nums, 1));
2214 }
2215 }// namespace maximize_the_topmost_element_after_k_moves
2216
2217 namespace minimum_weighted_subgraph_with_the_required_paths {
2219 vector<vector<int>> edges = {{0, 2, 2}, {0, 5, 6}, {1, 0, 3}, {1, 4, 5}, {2, 1, 1}, {2, 3, 3}, {2, 3, 4}, {3, 4, 2}, {4, 5, 1}};
2220 ASSERT_EQ(9, Solution::minimumWeight(6, edges, 0, 1, 5));
2221 }
2222
2224 vector<vector<int>> edges = {{0, 1, 1}, {2, 1, 1}};
2225 ASSERT_EQ(-1, Solution::minimumWeight(3, edges, 0, 1, 2));
2226 }
2227
2229 vector<vector<int>> edges = {{4, 2, 20}, {4, 3, 46}, {0, 1, 15}, {0, 1, 43}, {0, 1, 32}, {3, 1, 13}};
2230 ASSERT_EQ(74, Solution::minimumWeight(5, edges, 0, 4, 1));
2231 }
2232
2234 vector<vector<int>> edges = {{31, 64, 44}, {31, 6, 14}, {46, 21, 45}, {46, 65, 27}, {46, 30, 46}, {31, 0, 14}, {31, 29, 40}, {46, 95, 6}, {46, 73, 62}, {31, 74, 16}, {31, 55, 35}, {46, 40, 89}, {46, 57, 93}, {31, 90, 27}, {46, 58, 59}, {46, 12, 80}, {31, 44, 26}, {46, 67, 82}, {31, 8, 64}, {31, 23, 15}, {31, 7, 27}, {31, 94, 33}, {31, 86, 36}, {31, 33, 61}, {46, 88, 46}, {46, 69, 76}, {46, 39, 89}, {46, 53, 17}, {31, 75, 69}, {31, 72, 30}, {46, 83, 87}, {31, 35, 86}, {31, 62, 84}, {46, 51, 47}, {46, 66, 16}, {46, 50, 85}, {46, 81, 65}, {46, 36, 89}, {46, 60, 21}, {46, 10, 76}, {31, 18, 70}, {46, 3, 93}, {31, 47, 52}, {46, 16, 61}, {31, 15, 77}, {46, 28, 3}, {31, 93, 53}, {46, 43, 94}, {31, 38, 25}, {46, 1, 42}, {31, 22, 49}, {46, 45, 55}, {46, 99, 43}, {46, 24, 90}, {31, 9, 28}, {46, 13, 15}, {46, 27, 93}, {46, 49, 83}, {31, 71, 51}, {31, 59, 93}, {31, 91, 98}, {31, 54, 67}, {31, 25, 75}, {31, 68, 24}, {31, 76, 13}, {31, 41, 31}, {31, 19, 36}, {31, 87, 37}, {46, 17, 70}, {46, 97, 46}, {46, 61, 82}, {46, 79, 74}, {46, 85, 18}, {46, 14, 74}, {31, 32, 60}, {46, 84, 69}, {31, 34, 69}, {31, 4, 13}, {46, 70, 27}, {31, 48, 27}, {31, 11, 63}, {46, 5, 14}, {46, 37, 88}, {31, 96, 70}, {46, 52, 17}, {46, 42, 9}, {46, 20, 68}, {31, 77, 79}, {31, 80, 68}, {46, 78, 13}, {46, 26, 48}, {46, 2, 10}, {46, 63, 6}, {31, 89, 66}, {31, 56, 96}, {46, 92, 36}, {46, 98, 12}, {46, 82, 94}, {8, 82, 84}, {92, 82, 23}, {40, 82, 98}, {39, 82, 67}, {86, 82, 37}, {75, 82, 21}};
2235 ASSERT_EQ(132, Solution::minimumWeight(100, edges, 46, 31, 82));
2236 }
2237 }// namespace minimum_weighted_subgraph_with_the_required_paths
2238
2239 namespace utf_8_validation {
2241 vector data = {193, 130, 1};
2242 ASSERT_TRUE(Solution::validUtf8(data));
2243 }
2244
2246 vector data = {235, 140, 4};
2247 ASSERT_FALSE(Solution::validUtf8(data));
2248 }
2249
2251 vector data = {250, 145, 145, 145, 145};
2252 ASSERT_FALSE(Solution::validUtf8(data));
2253 }
2254 }// namespace utf_8_validation
2255
2256 namespace minimum_index_sum_of_two_lists {
2258 vector<string> list1 = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
2259 vector<string> list2 = {"Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"};
2260 const vector<string> output = {"Shogun"};
2261 ASSERT_EQ(output, Solution::findRestaurant(list1, list2));
2262 }
2263
2265 vector<string> list1 = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
2266 vector<string> list2 = {"KFC", "Shogun", "Burger King"};
2267 const vector<string> output = {"Shogun"};
2268 ASSERT_EQ(output, Solution::findRestaurant(list1, list2));
2269 }
2270 }// namespace minimum_index_sum_of_two_lists
2271
2272 namespace count_number_of_maximum_bitwise_or_subsets {
2274 vector nums = {3, 1};
2275 ASSERT_EQ(2, Solution::countMaxOrSubsets(nums));
2276 }
2277
2279 vector nums = {2, 2, 2};
2280 ASSERT_EQ(7, Solution::countMaxOrSubsets(nums));
2281 }
2282
2284 vector nums = {3, 2, 1, 5};
2285 ASSERT_EQ(6, Solution::countMaxOrSubsets(nums));
2286 }
2287 }// namespace count_number_of_maximum_bitwise_or_subsets
2288
2289 namespace all_oone_data_structure {
2291 AllOne ao;
2292 ao.inc("a");
2293 ao.inc("b");
2294 ao.inc("b");
2295 ao.inc("c");
2296 ao.inc("c");
2297 ao.inc("c");
2298 ao.dec("b");
2299 ao.dec("b");
2300 ao.getMinKey();
2301 ao.dec("a");
2302 ao.getMaxKey();
2303 ao.getMinKey();
2304 }
2305 }// namespace all_oone_data_structure
2306
2307 namespace longest_word_in_dictionary {
2309 vector<string> words = {"w", "wo", "wor", "worl", "world"};
2310 const string output = "world";
2311 ASSERT_EQ(output, Solution::longestWord(words));
2312 }
2313
2315 vector<string> words = {"a", "banana", "app", "appl", "ap", "apply", "apple"};
2316 const string output = "apple";
2317 ASSERT_EQ(output, Solution::longestWord(words));
2318 }
2319 }// namespace longest_word_in_dictionary
2320
2321 namespace maximize_number_of_subsequences_in_a_string {
2323 ASSERT_EQ(4, Solution::maximumSubsequenceCount("abdcdbc", "ac"));
2324 }
2325
2329 }// namespace maximize_number_of_subsequences_in_a_string
2330
2331 namespace minimum_operations_to_halve_array_sum {
2333 vector nums = {5, 19, 8, 1};
2334 ASSERT_EQ(3, Solution::halveArray(nums));
2335 }
2336
2338 vector nums = {3, 8, 20};
2339 ASSERT_EQ(3, Solution::halveArray(nums));
2340 }
2341 }// namespace minimum_operations_to_halve_array_sum
2342
2343 namespace minimum_white_tiles_after_covering_with_carpets {
2345 ASSERT_EQ(2, Solution::minimumWhiteTiles("10110101", 2, 2));
2346 }
2347
2349 ASSERT_EQ(0, Solution::minimumWhiteTiles("11111", 2, 3));
2350 }
2351
2353 ASSERT_EQ(0, Solution::minimumWhiteTiles("10111101", 2, 4));
2354 }
2355 }// namespace minimum_white_tiles_after_covering_with_carpets
2356
2357 namespace count_hills_and_valleys_in_an_array {
2359 vector num = {2, 4, 1, 1, 6, 5};
2360 ASSERT_EQ(3, Solution::countHillValley(num));
2361 }
2362
2364 vector num = {6, 6, 5, 5, 4, 1};
2365 ASSERT_EQ(0, Solution::countHillValley(num));
2366 }
2367 }// namespace count_hills_and_valleys_in_an_array
2368
2369 namespace count_collisions_on_a_road {
2371 ASSERT_EQ(5, Solution::countCollisions("RLRSLL"));
2372 }
2373
2375 ASSERT_EQ(0, Solution::countCollisions("LLRR"));
2376 }
2377 }// namespace count_collisions_on_a_road
2378
2379 namespace maximum_points_in_an_archery_competition {
2381 vector aliceArrows = {1, 1, 0, 1, 0, 0, 2, 1, 0, 1, 2, 0};
2382 const vector output = {0, 0, 0, 0, 1, 1, 0, 0, 1, 2, 3, 1};
2383 ASSERT_EQ(output, Solution::maximumBobPoints(9, aliceArrows));
2384 }
2385
2387 vector aliceArrows = {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 2};
2388 const vector output = {0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0};
2389 ASSERT_EQ(output, Solution::maximumBobPoints(3, aliceArrows));
2390 }
2391 }// namespace maximum_points_in_an_archery_competition
2392
2393 namespace the_time_when_the_network_becomes_idle {
2395 vector<vector<int>> edges = {{0, 1}, {1, 2}};
2396 vector patience = {0, 2, 1};
2397 ASSERT_EQ(8, Solution::networkBecomesIdle(edges, patience));
2398 }
2399
2401 vector<vector<int>> edges = {{0, 1}, {0, 2}, {1, 2}};
2402 vector patience = {0, 10, 10};
2403 ASSERT_EQ(3, Solution::networkBecomesIdle(edges, patience));
2404 }
2405 }// namespace the_time_when_the_network_becomes_idle
2406
2407 namespace remove_colored_pieces_if_both_neighbors_are_the_same_color {
2411
2415
2419 }// namespace remove_colored_pieces_if_both_neighbors_are_the_same_color
2420
2421 namespace k_th_smallest_in_lexicographical_order {
2423 ASSERT_EQ(10, Solution::findKthNumber(13, 2));
2424 }
2425
2427 ASSERT_EQ(1, Solution::findKthNumber(1, 1));
2428 }
2429 }// namespace k_th_smallest_in_lexicographical_order
2430
2431 namespace image_smoother {
2433 vector<vector<int>> img = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
2434 const vector<vector<int>> output = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
2435 ASSERT_EQ(output, Solution::imageSmoother(img));
2436 }
2437
2439 vector<vector<int>> img = {{100, 200, 100}, {200, 50, 200}, {100, 200, 100}};
2440 const vector<vector<int>> output = {{137, 141, 137}, {141, 138, 141}, {137, 141, 137}};
2441 ASSERT_EQ(output, Solution::imageSmoother(img));
2442 }
2443 }// namespace image_smoother
2444
2445 namespace factorial_trailing_zeroes {
2447 ASSERT_EQ(0, Solution::trailingZeroes(3));
2448 }
2449
2451 ASSERT_EQ(1, Solution::trailingZeroes(5));
2452 }
2453
2455 ASSERT_EQ(0, Solution::trailingZeroes(0));
2456 }
2457 }// namespace factorial_trailing_zeroes
2458
2459 namespace baseball_game {
2461 vector<string> ops = {"5", "2", "C", "D", "+"};
2462 ASSERT_EQ(30, Solution::calPoints(ops));
2463 }
2464
2466 vector<string> ops = {"5", "-2", "4", "C", "D", "9", "+", "+"};
2467 ASSERT_EQ(27, Solution::calPoints(ops));
2468 }
2469
2471 vector<string> ops = {"1"};
2472 ASSERT_EQ(1, Solution::calPoints(ops));
2473 }
2474 }// namespace baseball_game
2475
2476 namespace find_palindrome_with_fixed_length {
2478 vector queries = {1, 2, 3, 4, 5, 90};
2479 const vector<long long> output = {101, 111, 121, 131, 141, 999};
2480 ASSERT_EQ(output, Solution::kthPalindrome(queries, 3));
2481 }
2482
2484 vector queries = {2, 4, 6};
2485 const vector<long long> output = {1111, 1331, 1551};
2486 ASSERT_EQ(output, Solution::kthPalindrome(queries, 4));
2487 }
2488
2490 vector queries = {10};
2491 const vector<long long> output = {191};
2492 ASSERT_EQ(output, Solution::kthPalindrome(queries, 3));
2493 }
2494
2496 vector queries = {9};
2497 const vector<long long> output = {10801};
2498 ASSERT_EQ(output, Solution::kthPalindrome(queries, 5));
2499 }
2500
2502 vector queries = {60};
2503 const vector<long long> output = {15951};
2504 ASSERT_EQ(output, Solution::kthPalindrome(queries, 5));
2505 }
2506 }// namespace find_palindrome_with_fixed_length
2507
2508 namespace find_missing_observations {
2510 vector rolls = {3, 2, 4, 3};
2511 const vector output = {6, 6};
2512 ASSERT_EQ(output, Solution::missingRolls(rolls, 4, 2));
2513 }
2514
2516 vector rolls = {1, 2, 3, 4};
2517 const vector<int> output = {};
2518 ASSERT_EQ(output, Solution::missingRolls(rolls, 6, 4));
2519 }
2520 }// namespace find_missing_observations
2521
2522 namespace binary_number_with_alternating_bits {
2526
2530
2534 }// namespace binary_number_with_alternating_bits
2535
2536 namespace maximize_the_confusion_of_an_exam {
2538 ASSERT_EQ(4, Solution::maxConsecutiveAnswers("TTFF", 2));
2539 }
2540
2542 ASSERT_EQ(3, Solution::maxConsecutiveAnswers("TFFT", 1));
2543 }
2544
2546 ASSERT_EQ(5, Solution::maxConsecutiveAnswers("TTFTTFTT", 1));
2547 }
2548
2550 ASSERT_EQ(1, Solution::maxConsecutiveAnswers("F", 1));
2551 }
2552 }// namespace maximize_the_confusion_of_an_exam
2553
2554 namespace find_servers_that_handled_most_number_of_requests {
2556 vector arrival = {1, 2, 3, 4, 5};
2557 vector load = {5, 2, 3, 3, 3};
2558 const vector output = {1};
2559 ASSERT_EQ(output, Solution::busiestServers(3, arrival, load));
2560 }
2561
2563 vector arrival = {1, 2, 3, 4};
2564 vector load = {1, 2, 1, 2};
2565 const vector output = {0};
2566 ASSERT_EQ(output, Solution::busiestServers(3, arrival, load));
2567 }
2568
2570 vector arrival = {1, 2, 3};
2571 vector load = {10, 12, 11};
2572 const vector output = {0, 1, 2};
2573 ASSERT_EQ(output, Solution::busiestServers(3, arrival, load));
2574 }
2575
2577 vector arrival = {1, 2, 3};
2578 vector load = {1000000000, 1, 1000000000};
2579 const vector output = {1};
2580 ASSERT_EQ(output, Solution::busiestServers(2, arrival, load));
2581 }
2582 }// namespace find_servers_that_handled_most_number_of_requests
2583
2584 namespace self_dividing_numbers {
2586 const vector output = {1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22};
2587 ASSERT_EQ(output, Solution::selfDividingNumbers(1, 22));
2588 }
2589
2591 const vector output = {48, 55, 66, 77};
2592 ASSERT_EQ(output, Solution::selfDividingNumbers(47, 85));
2593 }
2594 }// namespace self_dividing_numbers
2595
2596 namespace array_of_doubled_pairs {
2598 vector arr = {3, 1, 3, 6};
2599 ASSERT_FALSE(Solution::canReorderDoubled(arr));
2600 }
2601
2603 vector arr = {2, 1, 2, 6};
2604 ASSERT_FALSE(Solution::canReorderDoubled(arr));
2605 }
2606 }// namespace array_of_doubled_pairs
2607
2608 namespace strong_password_checker {
2610 ASSERT_EQ(5, Solution::strongPasswordChecker("a"));
2611 }
2612
2614 ASSERT_EQ(3, Solution::strongPasswordChecker("aA1"));
2615 }
2616
2618 ASSERT_EQ(0, Solution::strongPasswordChecker("1337C0d3"));
2619 }
2620
2622 ASSERT_EQ(1, Solution::strongPasswordChecker("1111b"));
2623 }
2624
2626 ASSERT_EQ(2, Solution::strongPasswordChecker("aaaa"));
2627 }
2628 }// namespace strong_password_checker
2629
2630 namespace sum_of_scores_of_built_strings {
2632 ASSERT_EQ(9, Solution::sumScores("babab"));
2633 }
2634
2636 ASSERT_EQ(14, Solution::sumScores("azbazbzaz"));
2637 }
2638 }// namespace sum_of_scores_of_built_strings
2639
2640 namespace minimum_number_of_operations_to_convert_time {
2642 ASSERT_EQ(3, Solution::convertTime("02:30", "04:35"));
2643 }
2644
2646 ASSERT_EQ(1, Solution::convertTime("11:00", "11:01"));
2647 }
2648
2650 ASSERT_EQ(32, Solution::convertTime("00:00", "23:59"));
2651 }
2652 }// namespace minimum_number_of_operations_to_convert_time
2653
2654 namespace find_players_with_zero_or_one_losses {
2656 vector<vector<int>> matches = {{1, 3},
2657 {2, 3},
2658 {3, 6},
2659 {5, 6},
2660 {5, 7},
2661 {4, 5},
2662 {4, 8},
2663 {4, 9},
2664 {10, 4},
2665 {10, 9}};
2666 const vector<vector<int>> output = {{1, 2, 10}, {4, 5, 7, 8}};
2667 ASSERT_EQ(output, Solution::findWinners(matches));
2668 }
2669
2671 vector<vector<int>> matches = {{2, 3}, {1, 3}, {5, 4}, {6, 4}};
2672 const vector<vector<int>> output = {{1, 2, 5, 6}, {}};
2673 ASSERT_EQ(output, Solution::findWinners(matches));
2674 }
2675 }// namespace find_players_with_zero_or_one_losses
2676
2677 namespace maximum_candies_allocated_to_k_children {
2679 vector candies = {5, 8, 6};
2680 ASSERT_EQ(5, Solution::maximumCandies(candies, 3));
2681 }
2682
2684 vector candies = {2, 5};
2685 ASSERT_EQ(0, Solution::maximumCandies(candies, 11));
2686 }
2687
2689 vector candies = {1, 2, 3, 4, 10};
2690 ASSERT_EQ(3, Solution::maximumCandies(candies, 5));
2691 }
2692
2694 vector candies = {123, 13300, 1000, 23, 11, 41, 311};
2695 ASSERT_EQ(15, Solution::maximumCandies(candies, 980));
2696 }
2697 }// namespace maximum_candies_allocated_to_k_children
2698
2699 namespace encrypt_and_decrypt_strings {
2701 vector keys = {'a', 'b', 'c', 'd'};
2702 vector<string> values = {"ei", "zf", "ei", "am"};
2703 vector<string> dictionary = {"abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"};
2704 auto enc = Encrypter(keys, values, dictionary);
2705 ASSERT_EQ("eizfeiam", enc.encrypt("abcd"));
2706 ASSERT_EQ(2, enc.decrypt("eizfeiam"));
2707 }
2708 }// namespace encrypt_and_decrypt_strings
2709
2710 namespace process_restricted_friend_requests {
2712 vector<vector<int>> restrictions = {{0, 1}};
2713 vector<vector<int>> requests = {{0, 2}, {2, 1}};
2714 const vector output = {true, false};
2715 ASSERT_EQ(output, Solution::friendRequests(3, restrictions, requests));
2716 }
2717
2719 vector<vector<int>> restrictions = {{0, 1}};
2720 vector<vector<int>> requests = {{1, 2}, {0, 2}};
2721 const vector output = {true, false};
2722 ASSERT_EQ(output, Solution::friendRequests(3, restrictions, requests));
2723 }
2724 }// namespace process_restricted_friend_requests
2725
2726 namespace prime_number_of_set_bits_in_binary_representation {
2730
2734 }// namespace prime_number_of_set_bits_in_binary_representation
2735
2736 namespace minimum_height_trees {
2738 vector<vector<int>> edges = {{1, 0}, {1, 2}, {1, 3}};
2739 const vector output = {1};
2740 auto sol = Solution();
2741 ASSERT_EQ(output, sol.findMinHeightTrees(4, edges));
2742 }
2743
2745 vector<vector<int>> edges = {{3, 0}, {3, 1}, {3, 2}, {3, 4}, {5, 4}};
2746 const vector output = {3, 4};
2747 auto sol = Solution();
2748 ASSERT_EQ(output, sol.findMinHeightTrees(6, edges));
2749 }
2750 }// namespace minimum_height_trees
2751
2752 namespace rotate_string {
2754 ASSERT_TRUE(Solution::rotateString("abcde", "cdeab"));
2755 }
2756
2758 ASSERT_FALSE(Solution::rotateString("abcde", "abced"));
2759 }
2760 }// namespace rotate_string
2761
2762 namespace reaching_points {
2764 ASSERT_TRUE(Solution::reachingPoints(1, 1, 3, 5));
2765 }
2766
2768 ASSERT_FALSE(Solution::reachingPoints(1, 1, 2, 2));
2769 }
2770
2772 ASSERT_TRUE(Solution::reachingPoints(1, 1, 1, 1));
2773 }
2774 }// namespace reaching_points
2775
2776 namespace maximum_product_after_k_increments {
2778 vector nums = {0, 4};
2779 ASSERT_EQ(20, Solution::maximumProduct(nums, 5));
2780 }
2781
2783 vector nums = {6, 3, 3, 2};
2784 ASSERT_EQ(216, Solution::maximumProduct(nums, 2));
2785 }
2786 }// namespace maximum_product_after_k_increments
2787
2788 namespace maximum_total_beauty_of_the_gardens {
2790 vector flowers = {1, 3, 1, 1};
2791 ASSERT_EQ(14, Solution::maximumBeauty(flowers, 7, 6, 12, 1));
2792 }
2793
2795 vector flowers = {2, 4, 5, 3};
2796 ASSERT_EQ(30, Solution::maximumBeauty(flowers, 10, 5, 2, 6));
2797 }
2798
2800 vector flowers = {19, 17, 6, 9, 19};
2801 ASSERT_EQ(104, Solution::maximumBeauty(flowers, 24, 10, 17, 4));
2802 }
2803 }// namespace maximum_total_beauty_of_the_gardens
2804
2805 namespace count_numbers_with_unique_digits {
2809
2813 }// namespace count_numbers_with_unique_digits
2814
2815 namespace number_of_lines_to_write_string {
2817 vector width = {10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10};
2818 const vector output = {3, 60};
2819 ASSERT_EQ(output, Solution::numberOfLines(width, "abcdefghijklmnopqrstuvwxyz"));
2820 }
2821
2823 vector width = {4, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10};
2824 const vector output = {2, 4};
2825 ASSERT_EQ(output, Solution::numberOfLines(width, "bbbcccdddaaa"));
2826 }
2827 }// namespace number_of_lines_to_write_string
2828
2829 namespace permutation_in_string {
2831 ASSERT_TRUE(Solution::checkInclusion("ab", "eidbaooo"));
2832 }
2833
2835 ASSERT_FALSE(Solution::checkInclusion("ab", "eidboaoo"));
2836 }
2837
2839 ASSERT_FALSE(Solution::checkInclusion("dinitrophenylhydrazine", "dimethylhydrazine"));
2840 }
2841 }// namespace permutation_in_string
2842
2843 namespace projection_area_of_3d_shapes {
2845 vector<vector<int>> grid = {{1, 2}, {3, 4}};
2846 ASSERT_EQ(17, Solution::projectionArea(grid));
2847 }
2848
2850 vector<vector<int>> grid = {{2}};
2851 ASSERT_EQ(5, Solution::projectionArea(grid));
2852 }
2853
2855 vector<vector<int>> grid = {{1, 0}, {0, 2}};
2856 ASSERT_EQ(8, Solution::projectionArea(grid));
2857 }
2858 }// namespace projection_area_of_3d_shapes
2859
2860 namespace house_robber {
2862 vector nums = {1, 2, 3, 1};
2863 ASSERT_EQ(4, Solution::rob(nums));
2864 }
2865
2867 vector nums = {2, 7, 9, 3, 1};
2868 ASSERT_EQ(12, Solution::rob(nums));
2869 }
2870 }// namespace house_robber
2871
2872 namespace triangle {
2873 TEST(triangle, case1) {
2874 vector<vector<int>> triangle = {{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
2875 ASSERT_EQ(11, Solution::minimumTotal(triangle));
2876 }
2877
2878 TEST(triangle, case2) {
2879 vector<vector<int>> triangle = {{-10}};
2880 ASSERT_EQ(-10, Solution::minimumTotal(triangle));
2881 }
2882 }// namespace triangle
2883
2884 namespace lowest_common_ancestor_of_a_binary_search_tree {
2886 auto *root = new TreeNode(6);
2887 root->left = new TreeNode(2);
2888 root->right = new TreeNode(8);
2889 root->left->left = new TreeNode(0);
2890 root->left->right = new TreeNode(4);
2891 root->left->right->left = new TreeNode(3);
2892 root->left->right->right = new TreeNode(5);
2893 root->right->left = new TreeNode(7);
2894 root->right->right = new TreeNode(9);
2895 Solution s;
2896 ASSERT_EQ(6, s.lowestCommonAncestor(root, root->left, root->right)->val);
2897 }
2898 }// namespace lowest_common_ancestor_of_a_binary_search_tree
2899
2900 namespace find_all_anagrams_in_a_string {
2902 const string s = "cbaebabacd";
2903 const string p = "abc";
2904 const vector expected = {0, 6};
2905 ASSERT_EQ(expected, Solution::findAnagrams(s, p));
2906 }
2907
2909 const string s = "abab";
2910 const string p = "ab";
2911 const vector expected = {0, 1, 2};
2912 ASSERT_EQ(expected, Solution::findAnagrams(s, p));
2913 }
2914 }// namespace find_all_anagrams_in_a_string
2915
2916 namespace subarray_product_less_than_k {
2918 vector nums = {10, 5, 2, 6};
2919 const int k = 100;
2920 ASSERT_EQ(8, Solution::numSubarrayProductLessThanK(nums, k));
2921 }
2922
2924 vector nums = {1, 2, 3};
2925 const int k = 0;
2926 ASSERT_EQ(0, Solution::numSubarrayProductLessThanK(nums, k));
2927 }
2928 }// namespace subarray_product_less_than_k
2929
2930 namespace minimum_size_subarray_sum {
2932 vector nums = {2, 3, 1, 2, 4, 3};
2933 const int target = 7;
2934 ASSERT_EQ(2, Solution::minSubArrayLen(target, nums));
2935 }
2936
2938 vector nums = {1, 4, 4};
2939 const int target = 4;
2940 ASSERT_EQ(1, Solution::minSubArrayLen(target, nums));
2941 }
2942
2944 vector nums = {1, 1, 1, 1, 1, 1, 1, 1};
2945 const int target = 11;
2946 ASSERT_EQ(0, Solution::minSubArrayLen(target, nums));
2947 }
2948
2950 vector nums = {5, 1, 3, 5, 10, 7, 4, 9, 2, 8};
2951 const int target = 15;
2952 ASSERT_EQ(2, Solution::minSubArrayLen(target, nums));
2953 }
2954
2956 vector nums = {10, 5, 13, 4, 8, 4, 5, 11, 14, 9, 16, 10, 20, 8};
2957 const int target = 80;
2958 ASSERT_EQ(6, Solution::minSubArrayLen(target, nums));
2959 }
2960 }// namespace minimum_size_subarray_sum
2961
2962 namespace house_robber_ii {
2964 vector nums = {2, 3, 2};
2965 ASSERT_EQ(3, Solution::rob(nums));
2966 }
2967
2969 vector nums = {1, 2, 3, 1};
2970 ASSERT_EQ(4, Solution::rob(nums));
2971 }
2972
2974 vector nums = {1, 2, 3};
2975 ASSERT_EQ(3, Solution::rob(nums));
2976 }
2977 }// namespace house_robber_ii
2978
2979 namespace jump_game {
2980 TEST(jump_game, case1) {
2981 vector nums = {2, 3, 1, 1, 4};
2982 ASSERT_TRUE(Solution::canJump(nums));
2983 }
2984
2985 TEST(jump_game, case2) {
2986 vector nums = {3, 2, 1, 0, 4};
2987 ASSERT_FALSE(Solution::canJump(nums));
2988 }
2989 }// namespace jump_game
2990
2991 namespace jump_game_ii {
2993 vector nums = {2, 3, 1, 1, 4};
2994 ASSERT_EQ(2, Solution::jump(nums));
2995 }
2996
2998 vector nums = {2, 3, 0, 1, 4};
2999 ASSERT_EQ(2, Solution::jump(nums));
3000 }
3001 }// namespace jump_game_ii
3002
3003 namespace unique_paths {
3005 ASSERT_EQ(28, Solution::uniquePaths(3, 7));
3006 }
3007
3009 ASSERT_EQ(3, Solution::uniquePaths(3, 2));
3010 }
3011 }// namespace unique_paths
3012
3013 namespace longest_palindromic_substring {
3015 ASSERT_EQ("bab", Solution::longestPalindrome("babad"));
3016 }
3017
3019 ASSERT_EQ("bb", Solution::longestPalindrome("cbbd"));
3020 }
3021
3023 ASSERT_EQ("aaabbaaa", Solution::longestPalindrome("aaabbaaaa"));
3024 }
3025
3027 ASSERT_EQ("ccc", Solution::longestPalindrome("ccc"));
3028 }
3029
3031 ASSERT_EQ("bbbb", Solution::longestPalindrome("bbbb"));
3032 }
3033
3035 ASSERT_EQ("anana", Solution::longestPalindrome("bananas"));
3036 }
3037 }// namespace longest_palindromic_substring
3038
3039 namespace arithmetic_slices {
3041 vector nums = {1, 2, 3, 4};
3042 ASSERT_EQ(3, Solution::numberOfArithmeticSlices(nums));
3043 }
3044
3046 vector nums = {1};
3047 ASSERT_EQ(0, Solution::numberOfArithmeticSlices(nums));
3048 }
3049 }// namespace arithmetic_slices
3050
3051 namespace decode_ways {
3053 ASSERT_EQ(2, Solution::numDecodings("12"));
3054 }
3055
3057 ASSERT_EQ(3, Solution::numDecodings("226"));
3058 }
3059
3061 ASSERT_EQ(0, Solution::numDecodings("06"));
3062 }
3063
3065 ASSERT_EQ(1, Solution::numDecodings("27"));
3066 }
3067 }// namespace decode_ways
3068
3069 namespace word_break {
3071 vector<string> wordDict = {"leet", "code"};
3072 const string s = "leetcode";
3073 ASSERT_TRUE(Solution::wordBreak(s, wordDict));
3074 }
3075
3077 vector<string> wordDict = {"apple", "pen"};
3078 const string s = "applepenapple";
3079 ASSERT_TRUE(Solution::wordBreak(s, wordDict));
3080 }
3081
3083 vector<string> wordDict = {"cats", "dog", "sand", "and", "cat"};
3084 const string s = "catsandog";
3085 ASSERT_FALSE(Solution::wordBreak(s, wordDict));
3086 }
3087 }// namespace word_break
3088
3089 namespace longest_increasing_subsequence {
3091 vector nums = {10, 9, 2, 5, 3, 7, 101, 18};
3092 ASSERT_EQ(4, Solution::lengthOfLIS(nums));
3093 }
3094
3096 vector nums = {0, 1, 0, 3, 2, 3};
3097 ASSERT_EQ(4, Solution::lengthOfLIS(nums));
3098 }
3099
3101 vector nums = {7, 7, 7, 7, 7, 7, 7};
3102 ASSERT_EQ(1, Solution::lengthOfLIS(nums));
3103 }
3104 }// namespace longest_increasing_subsequence
3105
3106 namespace number_of_longest_increasing_subsequence {
3108 vector nums = {1, 3, 5, 4, 7};
3109 ASSERT_EQ(2, Solution::findNumberOfLIS(nums));
3110 }
3111
3113 vector nums = {2, 2, 2, 2, 2};
3114 ASSERT_EQ(5, Solution::findNumberOfLIS(nums));
3115 }
3116 }// namespace number_of_longest_increasing_subsequence
3117
3118 namespace longest_common_subsequence {
3120 const string text1 = "abcde";
3121 const string text2 = "ace";
3122 ASSERT_EQ(3, Solution::longestCommonSubsequence(text1, text2));
3123 }
3124
3126 const string text1 = "abc";
3127 const string text2 = "abc";
3128 ASSERT_EQ(3, Solution::longestCommonSubsequence(text1, text2));
3129 }
3130
3132 const string text1 = "abc";
3133 const string text2 = "def";
3134 ASSERT_EQ(0, Solution::longestCommonSubsequence(text1, text2));
3135 }
3136
3138 const string text1 = "abcde";
3139 const string text2 = "akccle";
3140 ASSERT_EQ(3, Solution::longestCommonSubsequence(text1, text2));
3141 }
3142 }// namespace longest_common_subsequence
3143
3144 namespace delete_operation_for_two_strings {
3146 const string s1 = "sea";
3147 const string s2 = "eat";
3148 ASSERT_EQ(2, Solution::minDistance(s1, s2));
3149 }
3150
3152 const string s1 = "leetcode";
3153 const string s2 = "etco";
3154 ASSERT_EQ(4, Solution::minDistance(s1, s2));
3155 }
3156 }// namespace delete_operation_for_two_strings
3157
3158 namespace edit_distance {
3160 const string word1 = "horse";
3161 const string word2 = "ros";
3162 ASSERT_EQ(3, Solution::minDistance(word1, word2));
3163 }
3164
3166 const string word1 = "intention";
3167 const string word2 = "execution";
3168 ASSERT_EQ(5, Solution::minDistance(word1, word2));
3169 }
3170 }// namespace edit_distance
3171
3172 namespace coin_change {
3174 vector coins = {1, 2, 5};
3175 const int amount = 11;
3176 ASSERT_EQ(3, Solution::coinChange(coins, amount));
3177 }
3178
3180 vector coins = {2};
3181 const int amount = 3;
3182 ASSERT_EQ(-1, Solution::coinChange(coins, amount));
3183 }
3184
3186 vector coins = {1};
3187 const int amount = 0;
3188 ASSERT_EQ(0, Solution::coinChange(coins, amount));
3189 }
3190
3192 vector coins = {186, 419, 83, 408};
3193 const int amount = 6249;
3194 ASSERT_EQ(20, Solution::coinChange(coins, amount));
3195 }
3196
3198 vector coins = {2};
3199 const int amount = 3;
3200 ASSERT_EQ(-1, Solution::coinChange(coins, amount));
3201 }
3202 }// namespace coin_change
3203
3204 namespace integer_break {
3206 const int n = 2;
3207 ASSERT_EQ(1, Solution::integerBreak(n));
3208 }
3209
3211 const int n = 10;
3212 ASSERT_EQ(36, Solution::integerBreak(n));
3213 }
3214 }// namespace integer_break
3215
3216 namespace max_points_on_a_line {
3218 vector<vector<int>> points = {{1, 1}, {2, 2}, {3, 3}};
3219 ASSERT_EQ(3, Solution::maxPoints(points));
3220 }
3221
3223 vector<vector<int>> points = {{1, 1}, {3, 2}, {5, 3}, {4, 1}, {2, 3}, {1, 4}};
3224 ASSERT_EQ(4, Solution::maxPoints(points));
3225 }
3226 }// namespace max_points_on_a_line
3227
3228 namespace sort_colors {
3230 vector nums = {2, 0, 2, 1, 1, 0};
3232 const vector expected = {0, 0, 1, 1, 2, 2};
3233 ASSERT_EQ(expected, nums);
3234 }
3235
3237 vector nums = {2, 0, 1};
3239 const vector expected = {0, 1, 2};
3240 ASSERT_EQ(expected, nums);
3241 }
3242 }// namespace sort_colors
3243
3244 namespace kth_largest_element_in_an_array {
3246 vector nums = {3, 2, 1, 5, 6, 4};
3247 ASSERT_EQ(5, Solution::findKthLargest(nums, 2));
3248 }
3249
3251 vector nums = {3, 2, 3, 1, 2, 4, 5, 5, 6};
3252 ASSERT_EQ(4, Solution::findKthLargest(nums, 4));
3253 }
3254 }// namespace kth_largest_element_in_an_array
3255
3256 namespace merge_intervals {
3258 vector<vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
3259 const vector<vector<int>> expected = {{1, 6}, {8, 10}, {15, 18}};
3260 ASSERT_EQ(expected, Solution::merge(intervals));
3261 }
3262
3264 vector<vector<int>> intervals = {{1, 4}, {4, 5}};
3265 const vector<vector<int>> expected = {{1, 5}};
3266 ASSERT_EQ(expected, Solution::merge(intervals));
3267 }
3268
3269 }// namespace merge_intervals
3270
3271 namespace search_a_2d_matrix_ii {
3273 vector<vector<int>> matrix = {{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}};
3274 ASSERT_TRUE(Solution::searchMatrix(matrix, 5));
3275 }
3276
3278 vector<vector<int>> matrix = {{1, 1}};
3279 ASSERT_FALSE(Solution::searchMatrix(matrix, 0));
3280 }
3281 }// namespace search_a_2d_matrix_ii
3282
3283 namespace serialize_and_deserialize_binary_tree {
3285 const auto c = Codec();
3286 const string serialized = "[1,2,3,null,null,4,5]";
3287 TreeNode *root = Codec::deserialize(serialized);
3288 ASSERT_EQ(serialized, c.serialize(root));
3289 }
3290
3292 const auto c = Codec();
3293 const string serialized = "[]";
3294 TreeNode *root = Codec::deserialize(serialized);
3295 ASSERT_EQ(serialized, c.serialize(root));
3296 }
3297
3299 const auto c = Codec();
3300 const string serialized = "[1,null,2,3]";
3301 TreeNode *root = Codec::deserialize(serialized);
3302 ASSERT_EQ(serialized, c.serialize(root));
3303 }
3304
3306 const auto c = Codec();
3307 const string serialized = "[1,2,3]";
3308 TreeNode *root = Codec::deserialize(serialized);
3309 ASSERT_EQ(serialized, c.serialize(root));
3310 }
3311
3313 const auto c = Codec();
3314 const string serialized = "[5,4,7,3,null,2,null,-1,null,9]";
3315 TreeNode *root = Codec::deserialize(serialized);
3316 ASSERT_EQ(serialized, c.serialize(root));
3317 }
3318 }// namespace serialize_and_deserialize_binary_tree
3319
3320 namespace task_scheduler {
3322 vector tasks = {'A', 'A', 'A', 'B', 'B', 'B'};
3323 ASSERT_EQ(8, Solution::leastInterval(tasks, 2));
3324 }
3325
3327 vector tasks = {'A', 'A', 'A', 'B', 'B', 'B'};
3328 ASSERT_EQ(6, Solution::leastInterval(tasks, 0));
3329 }
3330
3332 vector tasks = {'A', 'A', 'A', 'A', 'A', 'A', 'B', 'C', 'D', 'E', 'F', 'G'};
3333 ASSERT_EQ(16, Solution::leastInterval(tasks, 2));
3334 }
3335
3337 vector tasks = {'A', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
3338 ASSERT_EQ(31, Solution::leastInterval(tasks, 29));
3339 }
3340
3342 vector tasks = {'A', 'B', 'C', 'A'};
3343 ASSERT_EQ(8, Solution::leastInterval(tasks, 6));
3344 }
3345 }// namespace task_scheduler
3346
3347 namespace spiral_matrix_ii {
3349 const vector<vector<int>> ans = {{1, 2, 3}, {8, 9, 4}, {7, 6, 5}};
3350 ASSERT_EQ(ans, Solution::generateMatrix(3));
3351 }
3352
3354 const vector<vector<int>> ans = {{1}};
3355 ASSERT_EQ(ans, Solution::generateMatrix(1));
3356 }
3357 }// namespace spiral_matrix_ii
3358
3359 namespace non_overlapping_intervals {
3361 vector<vector<int>> intervals = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
3362 ASSERT_EQ(1, Solution::eraseOverlapIntervals(intervals));
3363 }
3364
3366 vector<vector<int>> intervals = {{1, 2}, {1, 2}, {1, 2}};
3367 ASSERT_EQ(2, Solution::eraseOverlapIntervals(intervals));
3368 }
3369
3371 vector<vector<int>> intervals = {{1, 2}, {2, 3}};
3372 ASSERT_EQ(0, Solution::eraseOverlapIntervals(intervals));
3373 }
3374
3376 vector<vector<int>> intervals = {{-52, 31}, {-73, -26}, {82, 97}, {-65, -11}, {-62, -49}, {95, 99}, {58, 95}, {-31, 49}, {66, 98}, {-63, 2}, {30, 47}, {-40, -26}};
3377 ASSERT_EQ(7, Solution::eraseOverlapIntervals(intervals));
3378 }
3379
3381 vector<vector<int>> intervals = {{-25322, -4602}, {-35630, -28832}, {-33802, 29009}, {13393, 24550}, {-10655, 16361}, {-2835, 10053}, {-2290, 17156}, {1236, 14847}, {-45022, -1296}, {-34574, -1993}, {-14129, 15626}, {3010, 14502}, {42403, 45946}, {-22117, 13380}, {7337, 33635}, {-38153, 27794}, {47640, 49108}, {40578, 46264}, {-38497, -13790}, {-7530, 4977}, {-29009, 43543}, {-49069, 32526}, {21409, 43622}, {-28569, 16493}, {-28301, 34058}};
3382 ASSERT_EQ(19, Solution::eraseOverlapIntervals(intervals));
3383 }
3384 }// namespace non_overlapping_intervals
3385
3386 namespace product_of_array_except_self {
3388 vector nums = {1, 2, 3, 4};
3389 const vector output = {24, 12, 8, 6};
3390 ASSERT_EQ(output, Solution::productExceptSelf(nums));
3391 }
3392
3394 vector nums = {-1, 1, 0, -3, 3};
3395 const vector output = {0, 0, 9, 0, 0};
3396 ASSERT_EQ(output, Solution::productExceptSelf(nums));
3397 }
3398 }// namespace product_of_array_except_self
3399
3400 namespace subarray_sum_equals_k {
3402 vector nums = {1, 1, 1};
3403 ASSERT_EQ(2, Solution::subarraySum(nums, 2));
3404 }
3405
3407 vector nums = {1, 2, 3};
3408 ASSERT_EQ(2, Solution::subarraySum(nums, 3));
3409 }
3410
3412 vector nums = {1};
3413 ASSERT_EQ(0, Solution::subarraySum(nums, 0));
3414 }
3415
3417 vector nums = {-1, -1, 1};
3418 ASSERT_EQ(1, Solution::subarraySum(nums, 0));
3419 }
3420
3422 vector nums = {-1, -1, 1};
3423 ASSERT_EQ(1, Solution::subarraySum(nums, 1));
3424 }
3425 }// namespace subarray_sum_equals_k
3426
3427 namespace partition_labels {
3429 const vector output = {9, 7, 8};
3430 ASSERT_EQ(output, Solution::partitionLabels("ababcbacadefegdehijhklij"));
3431 }
3432
3434 const vector output = {10};
3435 ASSERT_EQ(output, Solution::partitionLabels("eccbbbbdec"));
3436 }
3437 }// namespace partition_labels
3438
3439 namespace design_linked_list {
3441 MyLinkedList mll;
3442 mll.addAtHead(1);
3443 mll.addAtTail(3);
3444 mll.addAtIndex(1, 2);
3445 ASSERT_EQ(2, mll.get(1));
3446 mll.deleteAtIndex(1);
3447 ASSERT_EQ(3, mll.get(1));
3448 }
3449 }// namespace design_linked_list
3450
3451 namespace delete_node_in_a_bst {
3452 bool equal(TreeNode *tn1, TreeNode *tn2) {
3453 if(tn1 == nullptr != (tn2 == nullptr)) {
3454 return false;
3455 }
3456 if(tn1 != nullptr && tn2 != nullptr) {
3457 if(tn1->val != tn2->val) {
3458 return false;
3459 }
3460 if(!equal(tn1->left, tn2->left)) {
3461 return false;
3462 }
3463 if(!equal(tn1->right, tn2->right)) {
3464 return false;
3465 }
3466 }
3467 return true;
3468 }
3469
3474 auto sol = Solution();
3475 ASSERT_TRUE(equal(output, sol.deleteNode(root, 3)));
3476 }
3477
3482 auto sol = Solution();
3483 ASSERT_TRUE(equal(output, sol.deleteNode(root, 0)));
3484 }
3485
3490 auto sol = Solution();
3491 ASSERT_TRUE(equal(output, sol.deleteNode(root, 0)));
3492 }
3493
3496 TreeNode *root = serialize_and_deserialize_binary_tree::Codec::deserialize("[3,2,5,null,null,4,10,null,null,8,15,7]");
3497 TreeNode *output = serialize_and_deserialize_binary_tree::Codec::deserialize("[3,2,7,null,null,4,10,null,null,8,15]");
3498 auto sol = Solution();
3499 ASSERT_TRUE(equal(output, sol.deleteNode(root, 5)));
3500 }
3501 }// namespace delete_node_in_a_bst
3502
3503 namespace missing_element_in_sorted_array {
3505 vector nums = {4, 7, 9, 10};
3506 ASSERT_EQ(Solution::missingElement(nums, 1), 5);
3507 }
3508
3510 vector nums = {4, 7, 9, 10};
3511 ASSERT_EQ(Solution::missingElement(nums, 3), 8);
3512 }
3513
3515 vector nums = {1, 2, 4};
3516 ASSERT_EQ(Solution::missingElement(nums, 3), 6);
3517 }
3518 }// namespace missing_element_in_sorted_array
3519
3520 namespace find_a_peak_element_ii {
3522 vector<vector<int>> mat = {{1, 4}, {3, 2}};
3523 const vector ans = {0, 1};
3524 ASSERT_EQ(Solution::findPeakGrid(mat), ans);
3525 }
3526
3528 vector<vector<int>> mat = {{10, 20, 15}, {21, 30, 14}, {7, 16, 32}};
3529 const vector ans = {2, 2};
3530 ASSERT_EQ(Solution::findPeakGrid(mat), ans);
3531 }
3532 }// namespace find_a_peak_element_ii
3533
3534 namespace divide_chocolate {
3536 vector sweetness = {1, 2, 3, 4, 5, 6, 7, 8, 9};
3537 ASSERT_EQ(6, Solution::maximizeSweetness(sweetness, 5));
3538 }
3539
3541 vector sweetness = {5, 6, 7, 8, 9, 1, 2, 3, 4};
3542 ASSERT_EQ(1, Solution::maximizeSweetness(sweetness, 8));
3543 }
3544
3546 vector sweetness = {1, 2, 2, 1, 2, 2, 1, 2, 2};
3547 ASSERT_EQ(5, Solution::maximizeSweetness(sweetness, 2));
3548 }
3549 }// namespace divide_chocolate
3550
3551 namespace shortest_distance_to_target_color {
3553 vector colors = {1, 1, 2, 1, 3, 2, 2, 3, 3};
3554 vector<vector<int>> queries = {{1, 3}, {2, 2}, {6, 1}};
3555 const vector ans = {3, 0, 3};
3556 ASSERT_EQ(ans, Solution::shortestDistanceColor(colors, queries));
3557 }
3558
3560 vector colors = {1, 2};
3561 vector<vector<int>> queries = {{0, 3}};
3562 const vector ans = {-1};
3563 ASSERT_EQ(ans, Solution::shortestDistanceColor(colors, queries));
3564 }
3565 }// namespace shortest_distance_to_target_color
3566
3567 namespace meeting_scheduler {
3569 vector<vector<int>> slots1 = {{10, 50}, {60, 120}, {140, 210}};
3570 vector<vector<int>> slots2 = {{0, 15}, {60, 70}};
3571 const vector ans = {60, 68};
3572 ASSERT_EQ(ans, Solution::minAvailableDuration(slots1, slots2, 8));
3573 }
3574
3576 vector<vector<int>> slots1 = {{10, 50}, {60, 120}, {140, 210}};
3577 vector<vector<int>> slots2 = {{0, 15}, {60, 70}};
3578 const vector<int> ans = {};
3579 ASSERT_EQ(ans, Solution::minAvailableDuration(slots1, slots2, 12));
3580 }
3581
3583 vector<vector<int>> slots1 = {{10, 60}};
3584 vector<vector<int>> slots2 = {{12, 17}, {21, 50}};
3585 const vector ans = {21, 29};
3586 ASSERT_EQ(ans, Solution::minAvailableDuration(slots1, slots2, 8));
3587 }
3588 }// namespace meeting_scheduler
3589
3590 namespace find_the_duplicate_number {
3592 vector nums = {1, 3, 4, 2, 2};
3593 ASSERT_EQ(2, Solution::findDuplicate(nums));
3594 }
3595
3597 vector nums = {3, 1, 3, 4, 2};
3598 ASSERT_EQ(3, Solution::findDuplicate(nums));
3599 }
3600
3602 vector nums = {1, 4, 4, 2, 4};
3603 ASSERT_EQ(4, Solution::findDuplicate(nums));
3604 }
3605 }// namespace find_the_duplicate_number
3606
3607 namespace trapping_rain_water {
3609 vector height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
3610 ASSERT_EQ(6, Solution::trap(height));
3611 }
3612
3614 vector height = {4, 2, 0, 3, 2, 5};
3615 ASSERT_EQ(9, Solution::trap(height));
3616 }
3617 }// namespace trapping_rain_water
3618
3619 namespace product_of_two_run_length_encoded_arrays {
3621 vector<vector<int>> encoded1 = {{1, 3}, {2, 3}};
3622 vector<vector<int>> encoded2 = {{6, 3}, {3, 3}};
3623 const vector<vector<int>> output = {{6, 6}};
3624 ASSERT_EQ(output, Solution::findRLEArray(encoded1, encoded2));
3625 }
3626
3628 vector<vector<int>> encoded1 = {{1, 3}, {2, 1}, {3, 2}};
3629 vector<vector<int>> encoded2 = {{2, 3}, {3, 3}};
3630 const vector<vector<int>> output = {{2, 3}, {6, 1}, {9, 2}};
3631 ASSERT_EQ(output, Solution::findRLEArray(encoded1, encoded2));
3632 }
3633 }// namespace product_of_two_run_length_encoded_arrays
3634
3635 namespace longest_substring_with_at_most_two_distinct_characters {
3639
3643 }// namespace longest_substring_with_at_most_two_distinct_characters
3644
3645 namespace longest_substring_with_at_most_k_distinct_characters {
3649
3653 }// namespace longest_substring_with_at_most_k_distinct_characters
3654
3655 namespace max_consecutive_ones_iii {
3657 vector nums = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0};
3658 ASSERT_EQ(6, Solution::longestOnes(nums, 2));
3659 }
3660
3662 vector nums = {0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1};
3663 ASSERT_EQ(10, Solution::longestOnes(nums, 3));
3664 }
3665 }// namespace max_consecutive_ones_iii
3666
3667 namespace sliding_window_maximum {
3669 vector nums = {1, 3, -1, -3, 5, 3, 6, 7};
3670 const vector ans = {3, 3, 5, 5, 6, 7};
3671 ASSERT_EQ(ans, Solution::maxSlidingWindow(nums, 3));
3672 }
3673
3675 vector nums = {1};
3676 const vector ans = {1};
3677 ASSERT_EQ(ans, Solution::maxSlidingWindow(nums, 1));
3678 }
3679 }// namespace sliding_window_maximum
3680
3681 namespace minimum_window_substring {
3683 ASSERT_EQ("BANC", Solution::minWindow("ADOBECODEBANC", "ABC"));
3684 }
3685
3687 ASSERT_EQ("a", Solution::minWindow("a", "a"));
3688 }
3689
3691 ASSERT_EQ("", Solution::minWindow("a", "aa"));
3692 }
3693 }// namespace minimum_window_substring
3694
3695 namespace walls_and_gates {
3697 vector<vector<int>> rooms = {{2147483647, -1, 0, 2147483647}, {2147483647, 2147483647, 2147483647, -1}, {2147483647, -1, 2147483647, -1}, {0, -1, 2147483647, 2147483647}};
3698 const vector<vector<int>> ans = {{3, -1, 0, 1}, {2, 2, 1, -1}, {1, -1, 2, -1}, {0, -1, 3, 4}};
3700 ASSERT_EQ(ans, rooms);
3701 }
3702
3704 vector<vector<int>> rooms = {{2147483647}};
3705 const vector<vector<int>> ans = {{2147483647}};
3707 ASSERT_EQ(ans, rooms);
3708 }
3709
3711 vector<vector<int>> rooms = {{0}};
3712 const vector<vector<int>> ans = {{0}};
3714 ASSERT_EQ(ans, rooms);
3715 }
3716 }// namespace walls_and_gates
3717
3718 namespace pacific_atlantic_waterflow {
3720 vector<vector<int>> heights = {{1, 2, 2, 3, 5}, {3, 2, 3, 4, 4}, {2, 4, 5, 3, 1}, {6, 7, 1, 4, 5}, {5, 1, 1, 2, 4}};
3721 const vector<vector<int>> ans = {{0, 4}, {1, 3}, {1, 4}, {2, 2}, {3, 0}, {3, 1}, {4, 0}};
3722 ASSERT_EQ(ans, Solution::pacificAtlantic(heights));
3723 }
3724
3726 vector<vector<int>> heights = {{2, 1}, {1, 2}};
3727 const vector<vector<int>> ans = {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
3728 ASSERT_EQ(ans, Solution::pacificAtlantic(heights));
3729 }
3730 }// namespace pacific_atlantic_waterflow
3731
3732 namespace kill_process {
3734 vector pid = {1, 3, 10, 5};
3735 vector ppid = {3, 0, 5, 3};
3736 const vector ans = {5, 10};
3737 ASSERT_EQ(ans, Solution::killProcess(pid, ppid, 5));
3738 }
3739
3741 vector pid = {1};
3742 vector ppid = {0};
3743 const vector ans = {1};
3744 ASSERT_EQ(ans, Solution::killProcess(pid, ppid, 1));
3745 }
3746 }// namespace kill_process
3747
3748 namespace open_the_lock {
3750 vector<string> deadends = {"0201", "0101", "0102", "1212", "2002"};
3751 ASSERT_EQ(6, Solution::openLock(deadends, "0202"));
3752 }
3753
3755 vector<string> deadends = {"8888"};
3756 ASSERT_EQ(1, Solution::openLock(deadends, "0009"));
3757 }
3758
3760 vector<string> deadends = {"8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"};
3761 ASSERT_EQ(-1, Solution::openLock(deadends, "8888"));
3762 }
3763 }// namespace open_the_lock
3764
3765 namespace number_of_operations_to_make_network_connected {
3767 vector<vector<int>> connections = {{0, 1}, {0, 2}, {1, 2}};
3768 ASSERT_EQ(1, Solution::makeConnected(4, connections));
3769 }
3770
3772 vector<vector<int>> connections = {{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}};
3773 ASSERT_EQ(2, Solution::makeConnected(6, connections));
3774 }
3775
3777 vector<vector<int>> connections = {{0, 1}, {0, 2}, {0, 3}, {1, 2}};
3778 ASSERT_EQ(-1, Solution::makeConnected(6, connections));
3779 }
3780
3782 vector<vector<int>> connections = {{0, 1}, {0, 2}, {3, 4}, {2, 3}};
3783 ASSERT_EQ(0, Solution::makeConnected(5, connections));
3784 }
3785 }// namespace number_of_operations_to_make_network_connected
3786
3787 namespace minimum_cost_to_make_at_least_one_valid_path_in_a_grid {
3789 vector<vector<int>> grid = {{1, 1, 1, 1}, {2, 2, 2, 2}, {1, 1, 1, 1}, {2, 2, 2, 2}};
3790 ASSERT_EQ(3, Solution::minCost(grid));
3791 }
3792
3794 vector<vector<int>> grid = {{1, 1, 3}, {3, 2, 2}, {1, 1, 4}};
3795 ASSERT_EQ(0, Solution::minCost(grid));
3796 }
3797
3799 vector<vector<int>> grid = {{1, 2}, {4, 3}};
3800 ASSERT_EQ(1, Solution::minCost(grid));
3801 }
3802
3804 vector<vector<int>> grid = {{2, 2, 2}, {2, 2, 2}};
3805 ASSERT_EQ(3, Solution::minCost(grid));
3806 }
3807
3809 vector<vector<int>> grid = {{4}};
3810 ASSERT_EQ(0, Solution::minCost(grid));
3811 }
3812 }// namespace minimum_cost_to_make_at_least_one_valid_path_in_a_grid
3813
3814 namespace critical_connections_in_a_network {
3816 vector<vector<int>> connections = {{0, 1}, {1, 2}, {2, 0}, {1, 3}};
3817 const vector<vector<int>> ans = {{1, 3}};
3818 ASSERT_EQ(ans, Solution::criticalConnections(4, connections));
3819 }
3820
3822 vector<vector<int>> connections = {{0, 1}};
3823 const vector<vector<int>> ans = {{0, 1}};
3824 ASSERT_EQ(ans, Solution::criticalConnections(2, connections));
3825 }
3826
3828 vector<vector<int>> connections = {{0, 1}, {1, 2}, {2, 0}, {1, 3}, {3, 4}, {4, 5}, {5, 3}};
3829 const vector<vector<int>> ans = {{1, 3}};
3830 ASSERT_EQ(ans, Solution::criticalConnections(6, connections));
3831 }
3832 }// namespace critical_connections_in_a_network
3833
3834 namespace factor_combinations {
3836 const vector<vector<int>> ans = {};
3837 ASSERT_EQ(ans, Solution::getFactors(1));
3838 }
3839
3841 const vector<vector<int>> ans = {};
3842 ASSERT_EQ(ans, Solution::getFactors(37));
3843 }
3844
3846 const vector<vector<int>> ans = {{2, 6}, {2, 2, 3}, {3, 4}};
3847 ASSERT_EQ(ans, Solution::getFactors(12));
3848 }
3849
3851 const vector<vector<int>> ans = {{2, 16}, {2, 2, 8}, {2, 2, 2, 4}, {2, 2, 2, 2, 2}, {2, 4, 4}, {4, 8}};
3852 ASSERT_EQ(ans, Solution::getFactors(32));
3853 }
3854 }// namespace factor_combinations
3855
3856 namespace decode_string {
3858 ASSERT_EQ("aaabcbc", Solution::decodeString("3[a]2[bc]"));
3859 }
3860
3862 ASSERT_EQ("accaccacc", Solution::decodeString("3[a2[c]]"));
3863 }
3864
3866 ASSERT_EQ("abcabccdcdcdef", Solution::decodeString("2[abc]3[cd]ef"));
3867 }
3868
3870 ASSERT_EQ("abccdcdcdxyz", Solution::decodeString("abc3[cd]xyz"));
3871 }
3872 }// namespace decode_string
3873
3874 namespace n_queens {
3875 TEST(n_queens, case1) {
3876 const vector<vector<string>> ans = {{".Q..", "...Q", "Q...", "..Q."}, {"..Q.", "Q...", "...Q", ".Q.."}};
3877 ASSERT_EQ(ans, Solution::solveNQueens(4));
3878 }
3879
3880 TEST(n_queens, case2) {
3881 const vector<vector<string>> ans = {{"Q"}};
3882 ASSERT_EQ(ans, Solution::solveNQueens(1));
3883 }
3884 }// namespace n_queens
3885
3886 namespace sudoku_solver {
3888 vector<vector<char>> board = {{'5', '3', '.', '.', '7', '.', '.', '.', '.'}, {'6', '.', '.', '1', '9', '5', '.', '.', '.'}, {'.', '9', '8', '.', '.', '.', '.', '6', '.'}, {'8', '.', '.', '.', '6', '.', '.', '.', '3'}, {'4', '.', '.', '8', '.', '3', '.', '.', '1'}, {'7', '.', '.', '.', '2', '.', '.', '.', '6'}, {'.', '6', '.', '.', '.', '.', '2', '8', '.'}, {'.', '.', '.', '4', '1', '9', '.', '.', '5'}, {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};
3889 Solution sol;
3890 Solution::solveSudoku(board);
3891 const vector<vector<char>> ans = {{'5', '3', '4', '6', '7', '8', '9', '1', '2'}, {'6', '7', '2', '1', '9', '5', '3', '4', '8'}, {'1', '9', '8', '3', '4', '2', '5', '6', '7'}, {'8', '5', '9', '7', '6', '1', '4', '2', '3'}, {'4', '2', '6', '8', '5', '3', '7', '9', '1'}, {'7', '1', '3', '9', '2', '4', '8', '5', '6'}, {'9', '6', '1', '5', '3', '7', '2', '8', '4'}, {'2', '8', '7', '4', '1', '9', '6', '3', '5'}, {'3', '4', '5', '2', '8', '6', '1', '7', '9'}};
3892 ASSERT_EQ(ans, board);
3893 }
3894 }// namespace sudoku_solver
3895
3896 namespace regular_expression_matching {
3898 ASSERT_FALSE(Solution::isMatch("aa", "a"));
3899 }
3900
3902 ASSERT_TRUE(Solution::isMatch("aa", "a*"));
3903 }
3904
3906 ASSERT_TRUE(Solution::isMatch("ab", ".*"));
3907 }
3908
3910 ASSERT_TRUE(Solution::isMatch("a", "ab*"));
3911 }
3912 }// namespace regular_expression_matching
3913
3914 namespace different_ways_to_add_parentheses {
3916 const vector ans = {0, 2};
3917 ASSERT_EQ(ans, Solution::diffWaysToCompute("2-1-1"));
3918 }
3919
3921 const vector ans = {-34, -14, -10, -10, 10};
3922 ASSERT_EQ(ans, Solution::diffWaysToCompute("2*3-4*5"));
3923 }
3924 }// namespace different_ways_to_add_parentheses
3925
3926 namespace remove_invalid_parentheses {
3928 const vector<string> ans = {"(())()", "()()()"};
3929 ASSERT_EQ(ans, Solution::removeInvalidParentheses("()())()"));
3930 }
3931
3933 const vector<string> ans = {"(a())()", "(a)()()"};
3934 ASSERT_EQ(ans, Solution::removeInvalidParentheses("(a)())()"));
3935 }
3936
3938 const vector<string> ans = {""};
3939 ASSERT_EQ(ans, Solution::removeInvalidParentheses(")("));
3940 }
3941
3943 const vector<string> ans = {"x"};
3944 ASSERT_EQ(ans, Solution::removeInvalidParentheses("x("));
3945 }
3946
3948 const vector<string> ans = {"aaaaa"};
3949 ASSERT_EQ(ans, Solution::removeInvalidParentheses("((((((((((((((((((((aaaaa"));
3950 }
3951 }// namespace remove_invalid_parentheses
3952
3953 namespace median_of_two_sorted_arrays {
3955 vector nums1 = {1, 3};
3956 vector nums2 = {2};
3957 ASSERT_EQ(2, Solution::findMedianSortedArrays(nums1, nums2));
3958 }
3959
3961 vector nums1 = {1, 2};
3962 vector nums2 = {3, 4};
3963 ASSERT_EQ(2.5, Solution::findMedianSortedArrays(nums1, nums2));
3964 }
3965
3967 vector nums1 = {1, 3};
3968 vector nums2 = {2, 7};
3969 ASSERT_EQ(2.5, Solution::findMedianSortedArrays(nums1, nums2));
3970 }
3971 }// namespace median_of_two_sorted_arrays
3972
3973 namespace count_of_smaller_numbers_after_self {
3975 vector nums = {5, 2, 6, 1};
3976 const vector ans = {2, 1, 1, 0};
3977 Solution sol;
3978 ASSERT_EQ(ans, sol.countSmaller(nums));
3979 }
3980
3982 vector nums = {-1};
3983 const vector ans = {0};
3984 Solution sol;
3985 ASSERT_EQ(ans, sol.countSmaller(nums));
3986 }
3987
3989 vector nums = {-1, -1};
3990 const vector ans = {0, 0};
3991 Solution sol;
3992 ASSERT_EQ(ans, sol.countSmaller(nums));
3993 }
3994 }// namespace count_of_smaller_numbers_after_self
3995
3996 namespace best_time_to_buy_and_sell_stock_with_cooldown {
3998 vector prices = {1, 2, 3, 0, 2};
3999 ASSERT_EQ(3, Solution::maxProfit(prices));
4000 }
4001
4003 vector prices = {1};
4004 ASSERT_EQ(0, Solution::maxProfit(prices));
4005 }
4006
4008 vector prices = {1, 2};
4009 ASSERT_EQ(1, Solution::maxProfit(prices));
4010 }
4011 }// namespace best_time_to_buy_and_sell_stock_with_cooldown
4012
4013 namespace best_time_to_buy_and_sell_stock_with_transaction_fee {
4015 vector prices = {1, 3, 2, 8, 4, 9};
4016 ASSERT_EQ(8, Solution::maxProfit(prices, 2));
4017 }
4018
4020 vector prices = {1, 3, 7, 5, 10, 3};
4021 ASSERT_EQ(6, Solution::maxProfit(prices, 3));
4022 }
4023 }// namespace best_time_to_buy_and_sell_stock_with_transaction_fee
4024
4025 namespace split_array_largest_sum {
4027 vector nums = {7, 2, 5, 10, 8};
4028 ASSERT_EQ(18, Solution::splitArray(nums, 2));
4029 }
4030
4032 vector nums = {1, 2, 3, 4, 5};
4033 ASSERT_EQ(9, Solution::splitArray(nums, 2));
4034 }
4035
4037 vector nums = {1, 4, 4};
4038 ASSERT_EQ(4, Solution::splitArray(nums, 3));
4039 }
4040 }// namespace split_array_largest_sum
4041
4042 namespace maximal_square {
4044 vector<vector<char>> matrix = {{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}};
4045 ASSERT_EQ(4, Solution::maximalSquare(matrix));
4046 }
4047
4049 vector<vector<char>> matrix = {{'0', '1'}, {'1', '0'}};
4050 ASSERT_EQ(1, Solution::maximalSquare(matrix));
4051 }
4052
4054 vector<vector<char>> matrix = {{'0'}};
4055 ASSERT_EQ(0, Solution::maximalSquare(matrix));
4056 }
4057 }// namespace maximal_square
4058
4059 namespace maximal_rectangle {
4061 vector<vector<char>> matrix = {{'1', '0', '1', '0', '0'}, {'1', '0', '1', '1', '1'}, {'1', '1', '1', '1', '1'}, {'1', '0', '0', '1', '0'}};
4062 ASSERT_EQ(6, Solution::maximalRectangle(matrix));
4063 }
4064
4066 vector<vector<char>> matrix = {};
4067 ASSERT_EQ(0, Solution::maximalRectangle(matrix));
4068 }
4069
4071 vector<vector<char>> matrix = {{'0'}};
4072 ASSERT_EQ(0, Solution::maximalRectangle(matrix));
4073 }
4074
4076 vector<vector<char>> matrix = {{'1'}};
4077 ASSERT_EQ(1, Solution::maximalRectangle(matrix));
4078 }
4079
4081 vector<vector<char>> matrix = {{'0', '0'}};
4082 ASSERT_EQ(0, Solution::maximalRectangle(matrix));
4083 }
4084 }// namespace maximal_rectangle
4085
4086 namespace predict_the_winner {
4088 vector nums = {1, 5, 2};
4089 ASSERT_FALSE(Solution::PredictTheWinner(nums));
4090 }
4091
4093 vector nums = {1, 5, 233, 7};
4094 ASSERT_TRUE(Solution::PredictTheWinner(nums));
4095 }
4096 }// namespace predict_the_winner
4097
4098 namespace palindrome_partitioning {
4100 const string s = "aab";
4101 const vector<vector<string>> ans = {{"a", "a", "b"}, {"aa", "b"}};
4102 ASSERT_EQ(ans, Solution::partition(s));
4103 }
4104
4106 const string s = "a";
4107 const vector<vector<string>> ans = {{"a"}};
4108 ASSERT_EQ(ans, Solution::partition(s));
4109 }
4110 }// namespace palindrome_partitioning
4111
4112 namespace palindrome_partitioning_ii {
4114 const string s = "aab";
4115 ASSERT_EQ(1, Solution::minCut(s));
4116 }
4117
4119 const string s = "a";
4120 ASSERT_EQ(0, Solution::minCut(s));
4121 }
4122
4124 const string s = "ab";
4125 ASSERT_EQ(1, Solution::minCut(s));
4126 }
4127 }// namespace palindrome_partitioning_ii
4128
4129 namespace partition_equal_subset_sum {
4131 vector nums = {1, 5, 11, 5};
4132 ASSERT_TRUE(Solution::canPartition(nums));
4133 }
4134
4136 vector nums = {1, 2, 3, 5};
4137 ASSERT_FALSE(Solution::canPartition(nums));
4138 }
4139 }// namespace partition_equal_subset_sum
4140
4141 namespace minimum_cost_for_tickets {
4143 vector days = {1, 4, 6, 7, 8, 20};
4144 vector costs = {2, 7, 15};
4145 ASSERT_EQ(11, Solution::mincostTickets(days, costs));
4146 }
4147
4149 vector days = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31};
4150 vector costs = {2, 7, 15};
4151 ASSERT_EQ(17, Solution::mincostTickets(days, costs));
4152 }
4153 }// namespace minimum_cost_for_tickets
4154
4155 namespace best_time_to_buy_and_sell_stock_iii {
4157 vector prices = {3, 3, 5, 0, 0, 3, 1, 4};
4158 ASSERT_EQ(6, Solution::maxProfit(prices));
4159 }
4160
4162 vector prices = {1, 2, 3, 4, 5};
4163 ASSERT_EQ(4, Solution::maxProfit(prices));
4164 }
4165
4167 vector prices = {7, 6, 4, 3, 1};
4168 ASSERT_EQ(0, Solution::maxProfit(prices));
4169 }
4170
4172 vector prices = {1};
4173 ASSERT_EQ(0, Solution::maxProfit(prices));
4174 }
4175 }// namespace best_time_to_buy_and_sell_stock_iii
4176
4177 namespace dungeon_game {
4179 vector<vector<int>> dungeon = {{-2, -3, 3}, {-5, -10, 1}, {10, 30, -5}};
4180 ASSERT_EQ(7, Solution::calculateMinimumHP(dungeon));
4181 }
4182
4184 vector<vector<int>> dungeon = {{0}};
4185 ASSERT_EQ(1, Solution::calculateMinimumHP(dungeon));
4186 }
4187
4189 vector<vector<int>> dungeon = {{29, -78, -52, -1, -38, 6, 24, -45, 35, -29}, {-48, -48, -52, 2, -96, -78, -96, 40, -78, -73}, {-31, -73, -19, 38, 14, -95, 28, -59, 29, -20}, {17, -86, 45, 15, -3, -53, 43, 42, -97, -1}, {20, -99, -4, -2, -87, -98, 7, -90, -33, -42}, {-77, -66, -54, -46, 38, -42, 3, -5, -45, -49}, {13, -13, -52, -63, 25, 9, -63, -6, -58, -86}, {-57, 38, -83, 41, -71, -18, 9, -57, 35, -33}, {-2, -2, -95, -85, -37, -9, -60, -95, -87, -99}, {46, -98, -77, -13, -76, 36, -38, -19, -63, 5}, {-66, -15, -45, -81, -51, 6, -29, -96, 6, 28}, {-22, 17, 34, -52, -14, -65, -17, -70, 10, -40}, {18, -37, 23, -76, -5, 4, -31, -59, -22, 30}, {-26, -12, -34, 9, -78, -53, -98, -37, -1, 29}, {-54, -94, 37, -8, 22, -16, -84, -100, -45, 13}, {25, -96, 28, -77, 5, -93, 4, 20, -41, -89}, {-90, -99, -47, 29, 14, -47, -78, -40, -56, 26}, {-82, -69, -56, -40, 6, 0, -20, 5, -39, -73}, {-100, 44, 11, 37, 43, 45, -23, 8, 16, 45}, {-33, 41, -89, -13, -63, 46, 17, 26, -65, 23}, {-48, 2, -32, -56, -55, -21, -63, -9, -23, -61}, {-56, 44, -34, 45, 45, -23, 41, 9, 7, -90}, {34, 49, -66, -41, 37, -56, -62, -71, 28, -87}, {-54, -36, -78, -37, -22, 27, -64, -58, -3, -70}, {-77, -23, -60, -99, 45, -47, -42, 9, -72, -3}, {30, 29, 2, -50, -46, 6, -72, 0, -39, -4}, {32, 29, -67, -38, -56, -43, 50, -65, -81, -3}, {31, -31, -93, 34, 40, 47, -28, -6, -60, 48}, {42, -68, -14, -94, -36, -26, 13, -96, -39, -71}, {-96, 1, 37, -42, 17, 1, 34, -30, -31, 48}, {-93, -24, 12, -15, -98, 49, 30, -73, -4, 16}, {-86, -35, -100, 4, 15, 14, -1, 47, -11, 46}, {-76, -67, 0, -95, 25, 5, -83, -54, 45, 30}, {-27, -84, 17, 9, -63, -39, 37, -69, -62, 24}, {-40, -37, -52, -39, 10, -69, -73, -51, 48, 27}, {5, -86, -92, -8, 37, -44, 33, 0, -83, -37}, {-82, 45, 23, -95, 15, 35, 27, -28, -80, -80}, {-57, 26, -52, -13, -65, -80, -18, 46, 11, -14}, {49, 23, 26, 9, 18, -57, -18, -82, -85, -10}, {38, -25, -11, -38, 44, -29, -14, -80, -16, 4}, {-46, 48, 39, -65, -59, -13, 47, -23, -58, -100}, {42, -69, -93, -18, 22, 5, -26, -77, -37, 20}, {30, 41, -34, -93, -74, -49, -89, -53, -18, -51}, {-3, 12, 28, 8, 28, -31, 4, -75, -57, -89}, {-70, 0, -6, -74, -14, 43, -53, -23, -76, -22}, {14, -82, -25, -14, 14, -78, -46, -16, 28, -72}, {5, 48, 45, -87, 20, -13, -63, -48, -7, -64}, {49, -3, -63, -43, -58, -23, -21, -60, 11, 15}, {-65, -58, -50, 47, 45, -93, -71, 20, -90, -58}, {-49, -62, -16, 11, 43, -31, -39, 13, -43, 30}, {8, -45, -98, -22, 10, -46, -51, -22, -81, -99}, {4, -87, -53, -53, -19, -38, 24, -42, -15, -21}, {-77, 30, -95, 39, 42, 10, 41, -40, -46, -51}, {-69, 45, -99, 14, -54, 35, 18, -46, 11, -80}, {-12, 50, -12, 50, 45, -58, 18, -19, 29, -24}, {-63, 12, -14, -28, -48, 42, -8, -67, -87, 43}, {9, -87, 26, -29, -53, -70, -11, -43, -88, 15}, {-1, -12, 15, -42, -44, 41, 22, -46, 7, -31}, {-13, 6, 11, 13, -98, -96, -54, -95, -84, -34}, {13, -47, -42, -94, -90, -86, 50, -91, 19, 48}, {-26, -66, -18, 45, -72, -60, -7, 40, 37, -45}, {-11, 15, 48, -70, -89, -92, 25, -82, -36, 23}, {27, -11, -4, 35, -32, -30, -33, 50, 29, -24}, {-32, 26, -10, -5, 25, -30, 18, -70, -98, -3}, {-80, -45, -65, 42, -84, -56, -50, -97, -13, -65}, {19, -41, 26, -11, -66, 18, -52, -16, 28, -22}, {45, -23, -79, -44, -38, -100, 8, 11, -99, -67}, {-8, -48, -20, -15, -11, -52, 20, 30, -43, 24}, {-49, 23, -58, -73, 18, 43, 26, 1, -33, 32}, {-15, 27, -49, -87, -72, -45, -56, -91, -30, -40}, {3, -55, -22, -44, -71, -100, -53, -99, -85, 14}, {-34, -67, 25, -93, -21, -4, -37, -92, 12, -97}, {-14, 17, -72, -3, -25, -44, -26, -98, 10, -68}, {-90, -97, -1, -31, -44, -27, 43, -77, -35, -77}, {28, -53, -27, -100, -51, -45, 45, -67, -70, -61}, {-24, -38, 40, 36, 39, 2, 43, -38, -64, 3}, {-77, -85, -54, -88, 41, -85, -57, -100, -93, -75}, {40, -98, -59, -60, -15, 39, -64, 32, -77, 13}, {-50, 9, -64, 28, -8, -61, -16, -79, -77, -69}, {10, 16, -54, 47, -11, -4, -54, -10, 3, -10}, {-76, -62, -78, -23, -34, -97, -17, -67, -23, 13}, {-67, -27, -74, -62, -56, -36, -9, -51, 6, 37}, {23, 32, -93, -3, 28, -35, -13, 11, 7, -99}, {-20, -54, -54, -82, -36, 8, 25, 38, 43, 32}, {-97, -71, 38, -73, 27, -71, 47, -69, -74, 19}, {-61, -10, 5, -84, 48, 49, 6, -86, -28, -48}, {20, -92, -54, -7, 2, -90, -68, 14, -32, -12}, {-27, -100, 18, -47, 5, -73, 10, -50, -91, -75}, {-30, -43, -31, -96, -34, -54, -72, -70, 32, -72}, {-51, -55, -17, 24, 39, 39, -35, 4, 19, -82}, {11, -14, -97, 10, 42, 28, -31, -61, -96, 38}, {-94, -78, -42, 10, -36, -72, 2, -26, 3, -68}, {-44, 23, 5, -82, -81, -38, 13, -76, 0, -20}, {-36, 1, -90, -65, -67, -14, -79, 46, 35, 30}, {-85, -79, -34, 46, -39, -79, 8, -61, -75, -100}, {-58, -54, -84, 5, -93, -55, 7, 19, -27, -24}, {1, -51, -30, -4, -39, -94, 32, 14, -46, -91}, {37, -4, -18, -16, 7, 4, -98, -63, -15, 44}, {-4, -55, -33, 30, -37, 43, 5, -13, -56, -17}, {-19, -74, -31, -64, -50, -72, -63, 50, 1, -10}};
4190 ASSERT_EQ(558, Solution::calculateMinimumHP(dungeon));
4191 }
4192 }// namespace dungeon_game
4193
4194 namespace course_schedule {
4196 vector<vector<int>> prerequisites = {{1, 0}};
4197 ASSERT_TRUE(Solution::canFinish(2, prerequisites));
4198 }
4199
4201 vector<vector<int>> prerequisites = {{1, 0}, {0, 1}};
4202 ASSERT_FALSE(Solution::canFinish(2, prerequisites));
4203 }
4204 }// namespace course_schedule
4205
4206 namespace course_schedule_ii {
4208 vector<vector<int>> prerequisites = {{1, 0}};
4209 const vector ans = {0, 1};
4210 ASSERT_EQ(ans, Solution::findOrder(2, prerequisites));
4211 }
4212
4214 vector<vector<int>> prerequisites = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
4215 const vector ans = {0, 1, 2, 3};
4216 ASSERT_EQ(ans, Solution::findOrder(4, prerequisites));
4217 }
4218
4220 vector<vector<int>> prerequisites = {};
4221 const vector ans = {0};
4222 ASSERT_EQ(ans, Solution::findOrder(1, prerequisites));
4223 }
4224 }// namespace course_schedule_ii
4225
4226 namespace longest_increasing_path_in_a_matrix {
4228 vector<vector<int>> matrix = {{9, 9, 4}, {6, 6, 8}, {2, 1, 1}};
4229 Solution sol{};
4230 ASSERT_EQ(4, sol.longestIncreasingPath(matrix));
4231 }
4232
4234 vector<vector<int>> matrix = {{3, 4, 5}, {3, 2, 6}, {2, 2, 1}};
4235 Solution sol{};
4236 ASSERT_EQ(4, sol.longestIncreasingPath(matrix));
4237 }
4238
4240 vector<vector<int>> matrix = {{1}};
4241 Solution sol{};
4242 ASSERT_EQ(1, sol.longestIncreasingPath(matrix));
4243 }
4244
4246 vector<vector<int>> matrix = {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, {19, 18, 17, 16, 15, 14, 13, 12, 11, 10}, {20, 21, 22, 23, 24, 25, 26, 27, 28, 29}, {39, 38, 37, 36, 35, 34, 33, 32, 31, 30}, {40, 41, 42, 43, 44, 45, 46, 47, 48, 49}, {59, 58, 57, 56, 55, 54, 53, 52, 51, 50}, {60, 61, 62, 63, 64, 65, 66, 67, 68, 69}, {79, 78, 77, 76, 75, 74, 73, 72, 71, 70}, {80, 81, 82, 83, 84, 85, 86, 87, 88, 89}, {99, 98, 97, 96, 95, 94, 93, 92, 91, 90}, {100, 101, 102, 103, 104, 105, 106, 107, 108, 109}, {119, 118, 117, 116, 115, 114, 113, 112, 111, 110}, {120, 121, 122, 123, 124, 125, 126, 127, 128, 129}, {139, 138, 137, 136, 135, 134, 133, 132, 131, 130}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
4247 Solution sol{};
4248 ASSERT_EQ(140, sol.longestIncreasingPath(matrix));
4249 }
4250 }// namespace longest_increasing_path_in_a_matrix
4251
4252 namespace parallel_courses {
4254 vector<vector<int>> relations = {{1, 3}, {2, 3}};
4255 ASSERT_EQ(2, Solution::minimumSemesters(3, relations));
4256 }
4257
4259 vector<vector<int>> relations = {{1, 3}, {2, 3}, {3, 1}};
4260 ASSERT_EQ(-1, Solution::minimumSemesters(3, relations));
4261 }
4262 }// namespace parallel_courses
4263
4264 namespace alien_dictionary {
4266 vector<string> words = {"wrt", "wrf", "er", "ett", "rftt"};
4267 ASSERT_EQ("wertf", Solution::alienOrder(words));
4268 }
4269
4271 vector<string> words = {"z", "x"};
4272 ASSERT_EQ("zx", Solution::alienOrder(words));
4273 }
4274
4276 vector<string> words = {"z", "x", "z"};
4277 ASSERT_EQ("", Solution::alienOrder(words));
4278 }
4279
4281 vector<string> words = {"z", "z"};
4282 ASSERT_EQ("z", Solution::alienOrder(words));
4283 }
4284
4286 vector<string> words = {"abc", "ab"};
4287 ASSERT_EQ("", Solution::alienOrder(words));
4288 }
4289 }// namespace alien_dictionary
4290
4291 namespace single_number_iii {
4293 vector nums = {1, 2, 1, 3, 2, 5};
4294 const vector ans = {3, 5};
4295 ASSERT_EQ(ans, Solution::singleNumber(nums));
4296 }
4297
4299 vector nums = {-1, 0};
4300 const vector ans = {-1, 0};
4301 ASSERT_EQ(ans, Solution::singleNumber(nums));
4302 }
4303
4305 vector nums = {0, 1};
4306 const vector ans = {1, 0};
4307 ASSERT_EQ(ans, Solution::singleNumber(nums));
4308 }
4309 }// namespace single_number_iii
4310
4311 namespace shortest_path_to_get_all_keys {
4313 vector<string> grid = {"@.a.#", "###.#", "b.A.B"};
4314 ASSERT_EQ(8, Solution::shortestPathAllKeys(grid));
4315 }
4316
4318 vector<string> grid = {"@..aA", "..B#.", "....b"};
4319 ASSERT_EQ(6, Solution::shortestPathAllKeys(grid));
4320 }
4321
4323 vector<string> grid = {"@Aa"};
4324 ASSERT_EQ(-1, Solution::shortestPathAllKeys(grid));
4325 }
4326
4328 vector<string> grid = {".@aA"};
4329 ASSERT_EQ(1, Solution::shortestPathAllKeys(grid));
4330 }
4331
4333 vector<string> grid = {"..#....##.", "....d.#.D#", "#...#.c...", "..##.#..a.", "...#....##", "#....b....", ".#..#.....", "..........", ".#..##..A.", ".B..C.#..@"};
4334 ASSERT_EQ(19, Solution::shortestPathAllKeys(grid));
4335 }
4336 }// namespace shortest_path_to_get_all_keys
4337
4338 namespace minimum_number_of_k_consecutive_bit_flips {
4340 vector nums = {0, 1, 0};
4341 ASSERT_EQ(2, Solution::minKBitFlips(nums, 1));
4342 }
4343
4345 vector nums = {1, 1, 0};
4346 ASSERT_EQ(-1, Solution::minKBitFlips(nums, 2));
4347 }
4348
4350 vector nums = {0, 0, 0, 1, 0, 1, 1, 0};
4351 ASSERT_EQ(3, Solution::minKBitFlips(nums, 3));
4352 }
4353 }// namespace minimum_number_of_k_consecutive_bit_flips
4354
4355 namespace lfu_cache {
4356 TEST(lfu_cache, case1) {
4357 LFUCache c(2);
4358 c.put(1, 1);
4359 c.put(2, 2);
4360 ASSERT_EQ(1, c.get(1));
4361 c.put(3, 3);
4362 ASSERT_EQ(-1, c.get(2));
4363 ASSERT_EQ(3, c.get(3));
4364 c.put(4, 4);
4365 ASSERT_EQ(-1, c.get(1));
4366 ASSERT_EQ(3, c.get(3));
4367 ASSERT_EQ(4, c.get(4));
4368 }
4369 }// namespace lfu_cache
4370
4371 namespace leetcode454_4sum_ii {
4373 vector nums1 = {1, 2};
4374 vector nums2 = {-2, -1};
4375 vector nums3 = {-1, 2};
4376 vector nums4 = {0, 2};
4377 Solution sol;
4378 ASSERT_EQ(2, sol.fourSumCount(nums1, nums2, nums3, nums4));
4379 }
4380
4382 vector nums1 = {0};
4383 vector nums2 = {0};
4384 vector nums3 = {0};
4385 vector nums4 = {0};
4386 Solution sol;
4387 ASSERT_EQ(1, sol.fourSumCount(nums1, nums2, nums3, nums4));
4388 }
4389 }// namespace leetcode454_4sum_ii
4390
4391 namespace maximum_size_subarray_sum_equals_k {
4393 vector nums = {1, -1, 5, -2, 3};
4394 ASSERT_EQ(4, Solution::maxSubArrayLen(nums, 3));
4395 }
4396
4398 vector nums = {-2, -1, 2, 1};
4399 ASSERT_EQ(2, Solution::maxSubArrayLen(nums, 1));
4400 }
4401 }// namespace maximum_size_subarray_sum_equals_k
4402
4403 namespace minimum_swaps_to_group_all_1s_together {
4405 vector data = {1, 0, 1, 0, 1};
4406 ASSERT_EQ(1, Solution::minSwaps(data));
4407 }
4408
4410 vector data = {0, 0, 0, 1, 0};
4411 ASSERT_EQ(0, Solution::minSwaps(data));
4412 }
4413
4415 vector data = {1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1};
4416 ASSERT_EQ(3, Solution::minSwaps(data));
4417 }
4418
4420 vector data = {1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1};
4421 ASSERT_EQ(8, Solution::minSwaps(data));
4422 }
4423 }// namespace minimum_swaps_to_group_all_1s_together
4424}// namespace leetcode
TEST(concatenated_words, case1)
TEST(excel_sheet_column_number, case1)
TEST(excel_sheet_column_title, case1)
TEST(majority_element, case1)
TEST(count_special_quadruplets, case1)
TEST(hand_of_straights, case1)
TEST(perfect_number, case1)
TEST(convert_bst_to_greater_tree, case1)
TEST(convert_1d_array_into_2d_array, case1)
TEST(elimination_game, case1)
TEST(check_if_all_as_appears_before_all_bs, case1)
TEST(number_of_laser_beams_in_a_bank, case1)
TEST(destroying_asteroids, case1)
LeetCode 1185. 一周中的第几天
TEST(day_of_the_week, case1)
TEST(replace_all_s_to_avoid_consecutive_repeating_characters, case1)
LeetCode 71. 简化路径
LeetCode 1614. 括号的最大嵌套深度
TEST(maximum_nesting_depth_of_the_parentheses, case1)
LeetCode 89. 格雷编码
LeetCode 5977. 最少交换次数来组合所有的 1 II
TEST(minimum_swaps_to_group_all_1s_together_ii, case1)
LeetCode 5978. 统计追加字母可以获得的单词数
TEST(count_words_obtained_after_adding_a_letter, case1)
LeetCode 1629. 按键持续时间最长的键
LeetCode 306. 累加数
TEST(additive_number, case1)
LeetCode 2075. 解码斜向换位密码
TEST(decode_the_slanted_ciphertext, case1)
LeetCode 334. 递增的三元子序列
TEST(increasing_triplet_subsequence, case1)
LeetCode 747. 至少是其他数字两倍的最大数
TEST(largest_number_at_least_twice_of_others, case1)
LeetCode 46. 全排列
LeetCode 1716. 计算力扣银行的钱
TEST(calculate_money_in_leetcode_bank, case1)
LeetCode 5980. 将字符串拆分为若干长度为 k 的组
TEST(divide_a_string_into_groups_of_size_k, case1)
LeetCode 5194. 得到目标值的最少行动次数
TEST(minimum_moves_to_reach_target_score, case1)
LeetCode 5983. 同时运行 N 台电脑的最长时间
TEST(maximum_running_time_of_n_computers, case1)
LeetCode 1220. 统计元音字母序列的数目
TEST(coun_vowels_permutation, case1)
LeetCode 539. 最小时间差
TEST(minimum_time_difference, case1)
LeetCode 219. 存在重复元素 II
TEST(contains_duplicate_ii, case1)
LeetCode 2029. 石子游戏 IX
LeetCode 1345. 跳跃游戏 IV
LeetCode 1332. 删除回文子序列
TEST(remove_palindromic_subsequences, case1)
剑指 Offer II 063. 替换单词
LeetCode 5971. 打折购买糖果的最小开销
TEST(minimum_cost_of_buying_candies_with_discount, case1)
LeetCode 5972. 统计隐藏数组数目
TEST(count_the_hidden_sequences, case1)
LeetCode 5974. 分隔长廊的方案数
TEST(number_of_ways_to_divide_a_long_corridor, case1)
TEST(count_elements_with_strictly_smaller_and_greater_elements, case1)
LeetCode 5991. 按符号重排数组
TEST(rearrange_array_elements_by_sign, case1)
LeetCode 5990. 找出数组中的所有孤独数字
TEST(find_all_lonely_numbers_in_the_array, case1)
LeetCode 5992. 基于陈述统计最多好人数
TEST(maximum_good_people_based_on_statements, case1)
LeetCode 2045. 到达目的地的第二短时间
TEST(second_minimum_time_to_reach_destination, case1)
LeetCode 1688. 比赛中的配对次数
TEST(count_of_matches_in_tournament, case1)
LeetCode 2047. 句子中的有效单词数
TEST(number_of_valid_words_in_a_sentence, case1)
LeetCode 面试题 16.18. 模式匹配
TEST(pattern_matching_lcci, case1)
LeetCode 1765. 地图中的最高点
TEST(map_of_highest_peak, case1)
LeetCode 5994. 查找给定哈希值的子串
TEST(find_substring_with_given_hash_value, case1)
LeetCode 5995. 字符串分组
TEST(groups_of_strings, case1)
LeetCode 1342. 将数字变成 0 的操作次数
TEST(number_of_steps_to_reduce_a_number_to_zero, case1)
LeetCode 1763. 最长的美好子字符串
TEST(longest_nice_substring, case1)
LeetCode 2000. 反转单词前缀
TEST(reverse_prefix_of_word, case1)
LeetCode 1414. 和为 K 的最少斐波那契数字数目
TEST(find_the_minimum_number_of_fibonacci_numbers_whose_sum_is_k, case1)
LeetCode 1725. 可以形成最大正方形的矩形数目
TEST(number_of_rectangles_that_can_form_the_largest_square, case1)
LeetCode 1219. Path with Maximum Gold
TEST(path_with_maximum_gold, case1)
LeetCode 5987. 删除元素后和的最小差值
TEST(minimum_difference_in_sums_after_removal_of_elements, case1)
LeetCode 1748. 唯一元素的和
TEST(sum_of_unique_elements, case1)
LeetCode 6001. 重排数字的最小值
TEST(smallest_value_of_the_rearranged_number, case1)
LeetCode 6002. 设计位集
LeetCode 1405. Longest Happy String
TEST(longest_happy_string, case1)
LeetCode 1001. Grid Illumination
TEST(grid_illumination, case1)
LeetCode 2006. Count Number of Pairs With Absolute Difference K
TEST(count_number_of_pairs_with_absolute_difference_k, case1)
LeetCode 1447. Simplified Fractions
TEST(simplified_fractions, case1)
LeetCode 1984. Minimum Difference Between Highest and Lowest of K Scores
TEST(minimum_difference_between_highest_and_lowest_of_k_scores, case1)
LeetCode 1020. Number of Enclaves
TEST(number_of_enclaves, case1)
LeetCode 1189. “气球” 的最大数量
TEST(maximum_number_of_balloons, case1)
LeetCode 777. 在LR字符串中交换相邻字符
TEST(swap_adjacent_in_lr_string, case1)
LeetCode 6004. 得到 0 的操作数
TEST(count_operations_to_obtain_zero, case1)
LeetCode 6005. 使数组变成交替数组的最少操作数
TEST(minimum_operations_to_make_the_array_alternating, case1)
LeetCode 6006. 拿出最少数目的魔法豆
TEST(removing_minimum_number_of_magic_beans, case1)
LeetCode 6007. 数组的最大与和
TEST(maximum_and_sum_of_array, case1)
LeetCode 540. Single Element in a Sorted Array
TEST(single_element_in_a_sorted_array, case1)
LeetCode 1380. Lucky Numbers in a Matrix
TEST(lucky_numbers_in_a_matrix, case1)
LeetCode 1719. Number Of Ways To Reconstruct A Tree
TEST(number_of_ways_to_reconstruct_a_tree, case1)
LeetCode 1791. Find Center of Star Graph
TEST(find_center_of_star_graph, case1)
LeetCode 688. Knight Probability in Chessboard
TEST(knight_probability_in_chessboard, case1)
LeetCode 5996. 统计数组中相等且可以被整除的数对
TEST(count_equal_and_divisible_pairs_in_an_array, case1)
LeetCode 5997. 找到和为给定整数的三个连续整数
TEST(find_three_consecutive_integers_that_sum_to_a_given_number, case1)
LeetCode 5998. 拆分成最多数目的偶整数之和
TEST(maximum_split_of_positive_even_integers, case1)
LeetCode 5999. 统计数组中好三元组数目
TEST(count_good_triplets_in_an_array, case1)
LeetCode 6012. 统计各位数字之和为偶数的整数个数
TEST(count_integers_with_even_digit_sum, case1)
LeetCode 6014. 构造限制重复的字符串
TEST(construct_string_with_repeat_limit, case1)
LeetCode 6015. 统计可以被 K 整除的下标对数目
TEST(count_array_pairs_divisible_by_k, case1)
LeetCode 717. 1比特与2比特字符
TEST(leetcode717_1_bit_and_2_bit_characters, case1)
LeetCode 845. 数组中的最长山脉
TEST(longest_mountain_in_array, case1)
LeetCode 838. 推多米诺
LeetCode 1994. 好子集的数目
TEST(the_number_of_good_subsets, case1)
LeetCode 917. Reverse Only Letters
TEST(reverse_only_letters, case1)
LeetCode 1706. Where Will the Ball Fall
TEST(where_will_the_ball_fall, case1)
LeetCode 537. Complex Number Multiplication
TEST(complex_number_multiplication, case1)
LeetCode 2016. Maximum Difference Between Increasing Elements
TEST(maximum_difference_between_increasing_elements, case1)
LeetCode 553. Optimal Division
TEST(optimal_division, case1)
LeetCode 6008. 统计包含给定前缀的字符串
TEST(counting_words_with_a_given_prefix, case1)
LeetCode 6009. 使两字符串互为字母异位词的最少步骤数
TEST(minimum_number_of_steps_to_make_two_strings_anagram_ii, case1)
LeetCode 6010. 完成旅途的最少时间
TEST(minimum_time_to_complete_trips, case1)
LeetCode 6011. 完成比赛的最少时间
TEST(minimum_time_to_finish_the_race, case1)
LeetCode 1601. Maximum Number of Achievable Transfer Requests
TEST(maximum_number_of_achievable_transfer_requests, case1)
LeetCode 6. ZigZag Conversion
TEST(zigzag_conversion, case1)
LeetCode 564. Find the Closest Palindrome
TEST(find_the_closest_palindrome, case1)
LeetCode 258. Add Digits
LeetCode 2104. Sum of Subarray Ranges
TEST(sum_of_subarray_ranges, case1)
LeetCode 521. Longest Uncommon Subsequence I
TEST(longest_uncommon_subsequence_i, case1)
LeetCode 6024. 数组中紧跟 key 之后出现最频繁的数字
TEST(most_frequent_number_following_key_in_an_array, case1)
LeetCode 5217. 将杂乱无章的数字排序
TEST(sort_the_jumbled_numbers, case1)
LeetCode 5300. 有向无环图中一个节点的所有祖先
TEST(all_ancestors_of_a_node_in_a_directed_acyclic_graph, case1)
LeetCode 5237. 得到回文串的最少操作次数
TEST(minimum_number_of_moves_to_make_palindrome, case1)
LeetCode 6016. Excel 表中某个范围内的单元格
TEST(cells_in_a_range_on_an_excel_sheet, case1)
LeetCode 6017. 向数组中追加 K 个整数
TEST(append_k_integers_with_minimal_sum, case1)
LeetCode 6019. 替换数组中的非互质数
TEST(replace_non_coprime_numbers_in_array, case1)
LeetCode 2100. Find Good Days to Rob the Bank
TEST(find_good_days_to_rob_the_bank, case1)
LeetCode 504. Base 7
LeetCode 2055. Plates Between Candles
TEST(plates_between_candles, case1)
LeetCode 798. Smallest Rotation with Highest Score
TEST(smallest_rotation_with_highest_score, case1)
LeetCode 2049. Count Nodes With the Highest Score
TEST(count_nodes_with_the_highest_score, case1)
LeetCode 695. Max Area of Island
TEST(max_area_of_island, case1)
LeetCode 6031. 找出数组中的所有 K 近邻下标
TEST(find_all_k_distant_indices_in_an_array, case1)
LeetCode 5203. 统计可以提取的工件
TEST(count_artifacts_that_can_be_extracted, case1)
LeetCode 5227. K 次操作后最大化顶端元素
TEST(maximize_the_topmost_element_after_k_moves, case1)
LeetCode 6032. 得到要求路径的最小带权子图
TEST(minimum_weighted_subgraph_with_the_required_paths, case1)
LeetCode 393. UTF-8 Validation
TEST(utf_8_validation, case1)
LeetCode 599. Minimum Index Sum of Two Lists
TEST(minimum_index_sum_of_two_lists, case1)
LeetCode 2044. Count Number of Maximum Bitwise-OR Subsets
TEST(count_number_of_maximum_bitwise_or_subsets, case1)
LeetCode 432. All O`one Data Structure
TEST(all_oone_data_structure, case1)
LeetCode 720. Longest Word in Dictionary
TEST(longest_word_in_dictionary, case1)
LeetCode 6021. Maximize Number of Subsequences in a String
TEST(maximize_number_of_subsequences_in_a_string, case1)
LeetCode 6022. Minimum Operations to Halve Array Sum
TEST(minimum_operations_to_halve_array_sum, case1)
LeetCode 6023. Minimum White Tiles After Covering With Carpets
TEST(minimum_white_tiles_after_covering_with_carpets, case1)
LeetCode 6027. Count Hills and Valleys in an Array
TEST(count_hills_and_valleys_in_an_array, case1)
LeetCode 6028. Count Collisions on a Road
TEST(count_collisions_on_a_road, case1)
LeetCode 6029. Maximum Points in an Archery Competition
TEST(maximum_points_in_an_archery_competition, case1)
LeetCode 2039. The Time When the Network Becomes Idle
TEST(the_time_when_the_network_becomes_idle, case1)
Remove Colored Pieces if Both Neighbors are the Same Color
TEST(remove_colored_pieces_if_both_neighbors_are_the_same_color, case1)
K-th Smallest in Lexicographical Order
TEST(k_th_smallest_in_lexicographical_order, case1)
TEST(factorial_trailing_zeroes, case1)
TEST(find_palindrome_with_fixed_length, case1)
TEST(find_missing_observations, case1)
Binary Number with Alternating Bits
TEST(binary_number_with_alternating_bits, case1)
Maximize the Confusion of an Exam
TEST(maximize_the_confusion_of_an_exam, case1)
Find Servers That Handled Most Number of Requests
TEST(find_servers_that_handled_most_number_of_requests, case1)
TEST(self_dividing_numbers, case1)
TEST(array_of_doubled_pairs, case1)
TEST(strong_password_checker, case1)
TEST(sum_of_scores_of_built_strings, case1)
Minimum Number of Operations to Convert Time
TEST(minimum_number_of_operations_to_convert_time, case1)
Find Players With Zero or One Losses
TEST(find_players_with_zero_or_one_losses, case1)
Maximum Candies Allocated to K Children
TEST(maximum_candies_allocated_to_k_children, case1)
TEST(encrypt_and_decrypt_strings, case1)
Process Restricted Friend Requests
TEST(process_restricted_friend_requests, case1)
Prime Number of Set Bits in Binary Representation
TEST(prime_number_of_set_bits_in_binary_representation, case1)
TEST(minimum_height_trees, case1)
TEST(maximum_product_after_k_increments, case1)
TEST(maximum_total_beauty_of_the_gardens, case1)
TEST(count_numbers_with_unique_digits, case1)
TEST(number_of_lines_to_write_string, case1)
TEST(permutation_in_string, case1)
TEST(projection_area_of_3d_shapes, case1)
Lowest Common Ancestor of a Binary Search Tree
TEST(lowest_common_ancestor_of_a_binary_search_tree, case1)
TEST(find_all_anagrams_in_a_string, case1)
TEST(subarray_product_less_than_k, case1)
TEST(minimum_size_subarray_sum, case1)
TEST(longest_palindromic_substring, case1)
TEST(arithmetic_slices, case1)
TEST(longest_increasing_subsequence, case1)
Number of Longest Increasing Subsequence
TEST(number_of_longest_increasing_subsequence, case1)
TEST(longest_common_subsequence, case1)
TEST(delete_operation_for_two_strings, case1)
TEST(max_points_on_a_line, case1)
TEST(kth_largest_element_in_an_array, case1)
TEST(search_a_2d_matrix_ii, case1)
Serialize and Deserialize Binary Tree
TEST(serialize_and_deserialize_binary_tree, case1)
TEST(spiral_matrix_ii, case1)
TEST(non_overlapping_intervals, case1)
TEST(product_of_array_except_self, case1)
TEST(subarray_sum_equals_k, case1)
TEST(partition_labels, case1)
TEST(design_linked_list, case1)
TEST(delete_node_in_a_bst, case1)
bool equal(TreeNode *tn1, TreeNode *tn2)
TEST(missing_element_in_sorted_array, case1)
TEST(find_a_peak_element_ii, case1)
TEST(divide_chocolate, case1)
与目标颜色间的最短距离
TEST(shortest_distance_to_target_color, case1)
TEST(meeting_scheduler, case1)
TEST(find_the_duplicate_number, case1)
TEST(trapping_rain_water, case1)
TEST(product_of_two_run_length_encoded_arrays, case1)
TEST(longest_substring_with_at_most_two_distinct_characters, case1)
TEST(longest_substring_with_at_most_k_distinct_characters, case1)
TEST(max_consecutive_ones_iii, case1)
TEST(sliding_window_maximum, case1)
TEST(minimum_window_substring, case1)
太平洋大西洋水流问题
TEST(pacific_atlantic_waterflow, case1)
TEST(number_of_operations_to_make_network_connected, case1)
使网格图至少有一条有效路径的最小代价
TEST(minimum_cost_to_make_at_least_one_valid_path_in_a_grid, case1)
查找集群内的「关键连接」
TEST(critical_connections_in_a_network, case1)
TEST(factor_combinations, case1)
TEST(regular_expression_matching, case1)
为运算表达式设计优先级
TEST(different_ways_to_add_parentheses, case1)
TEST(remove_invalid_parentheses, case1)
寻找两个正序数组的中位数
TEST(median_of_two_sorted_arrays, case1)
计算右侧小于当前元素的个数
TEST(count_of_smaller_numbers_after_self, case1)
TEST(best_time_to_buy_and_sell_stock_with_cooldown, case1)
TEST(best_time_to_buy_and_sell_stock_with_transaction_fee, case1)
TEST(split_array_largest_sum, case1)
TEST(maximal_rectangle, case1)
TEST(predict_the_winner, case1)
TEST(palindrome_partitioning, case1)
TEST(palindrome_partitioning_ii, case1)
TEST(partition_equal_subset_sum, case1)
TEST(minimum_cost_for_tickets, case1)
TEST(best_time_to_buy_and_sell_stock_iii, case1)
TEST(course_schedule_ii, case1)
TEST(longest_increasing_path_in_a_matrix, case1)
TEST(parallel_courses, case1)
TEST(alien_dictionary, case1)
只出现一次的数字 III
TEST(single_number_iii, case1)
获取所有钥匙的最短路径
TEST(shortest_path_to_get_all_keys, case1)
TEST(minimum_number_of_k_consecutive_bit_flips, case1)
TEST(leetcode454_4sum_ii, case1)
和等于 k 的最长子数组长度
TEST(maximum_size_subarray_sum_equals_k, case1)
最少交换次数来组合所有的 1
TEST(minimum_swaps_to_group_all_1s_together, case1)
static vector< string > findAllConcatenatedWordsInADict(vector< string > &)
static int titleToNumber(const string &columnTitle)
static string convertToTitle(int columnNumber)
static bool isNStraightHand(vector< int > &hand, int groupSize)
static TreeNode * convertBST(TreeNode *root)
static vector< vector< int > > construct2DArray(vector< int > &original, int m, int n)
static bool asteroidsDestroyed(int mass, vector< int > &asteroids)
static string dayOfTheWeek(int day, int month, int year)
static string simplifyPath(const string &path)
static vector< int > grayCode(int n)
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 bool increasingTriplet(vector< int > &nums)
static vector< vector< int > > permute(vector< int > &nums)
static vector< string > divideString(const string &s, int k, char fill)
static long long maxRunTime(int n, vector< int > &batteries)
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 string replaceWords(vector< string > &dictionary, const string &sentence)
static int numberOfArrays(vector< int > &differences, int lower, int upper)
static vector< int > rearrangeArray(vector< int > &nums)
static vector< int > findLonely(vector< int > &nums)
static int maximumGood(vector< vector< int > > &statements)
static int secondMinimum(int n, vector< vector< int > > &edges, int time, int change)
static bool patternMatching(const string &pattern, const string &value)
static vector< vector< int > > highestPeak(vector< vector< int > > &isWater)
static string subStrHash(string s, int power, int modulo, int k, int hashValue)
static string longestNiceSubstring(const string &s)
static string reversePrefix(string word, char ch)
static int countGoodRectangles(vector< vector< int > > &rectangles)
static int getMaximumGold(vector< vector< int > > &grid)
static int sumOfUnique(vector< int > &nums)
static string longestDiverseString(int a, int b, int c)
static vector< int > gridIllumination(int n, vector< vector< int > > &lamps, vector< vector< int > > &queries)
static vector< string > simplifiedFractions(int n)
static int numEnclaves(vector< vector< int > > &grid)
static int maxNumberOfBalloons(const string &text)
static bool canTransform(const string &start, const string &end)
static int maximumANDSum(vector< int > &nums, int numSlots)
static vector< int > luckyNumbers(vector< vector< int > > &matrix)
static int checkWays(vector< vector< int > > &pairs)
static int findCenter(vector< vector< int > > &edges)
static vector< long long > maximumEvenSplit(long long finalSum)
static long long goodTriplets(vector< int > &nums1, vector< int > &nums2)
static string repeatLimitedString(const string &s, int repeatLimit)
static long long coutPairs(vector< int > &nums, int k)
static int longestMountain(vector< int > &arr)
static string pushDominoes(string dominoes)
static int numberOfGoodSubsets(vector< int > &nums)
static vector< int > findBall(vector< vector< int > > &grid)
static string complexNumberMultiply(const string &num1, const string &num2)
static string optimalDivision(vector< int > &nums)
static int prefixCount(vector< string > &words, string pref)
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 long long subArrayRanges(vector< int > &nums)
static int findLUSlength(const string &a, const string &b)
static vector< int > sortJumbled(vector< int > &mapping, vector< int > &nums)
static vector< string > cellsInRange(const string &s)
static long long minimalKSum(vector< int > &nums, int k)
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 countHighestScoreNodes(vector< int > &parents)
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 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)
string getMaxKey()
Returns one of the keys with the maximal count.
string getMinKey()
Returns one of the keys with the minimum count.
void dec(const string &key)
Decrements the count of the string key by 1. If the count of key is 0 after the decrement,...
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 long long maximumSubsequenceCount(string text, string pattern)
static int minimumWhiteTiles(string floor, int numCarpets, int carpetLen)
static int countCollisions(const string &directions)
static vector< int > maximumBobPoints(int numArrows, vector< int > &aliceArrows)
static int networkBecomesIdle(vector< vector< int > > &edges, vector< int > &patience)
static vector< vector< int > > imageSmoother(vector< vector< int > > &img)
static int calPoints(vector< string > &ops)
static vector< long long > kthPalindrome(vector< int > &queries, int intLength)
static vector< int > missingRolls(vector< int > &rolls, int mean, int n)
static int maxConsecutiveAnswers(string answerKey, int k)
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 vector< vector< int > > findWinners(vector< vector< int > > &matches)
static int maximumCandies(vector< int > &candies, long long k)
static vector< bool > friendRequests(int n, vector< vector< int > > &restrictions, vector< vector< int > > &requests)
static bool rotateString(string s, const string &goal)
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 vector< int > numberOfLines(vector< int > &widths, string s)
static bool checkInclusion(const string &s1, string s2)
static int projectionArea(vector< vector< int > > &grid)
static int rob(vector< int > &nums)
static int minimumTotal(vector< vector< int > > &triangle)
static TreeNode * lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
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 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 int numberOfArithmeticSlices(vector< int > &nums)
static bool wordBreak(const string &s, vector< string > &wordDict)
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 maxPoints(vector< vector< int > > &points)
static void sortColors(vector< int > &nums)
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 TreeNode * deserialize(string data)
Decodes your encoded data to tree.
static int leastInterval(vector< char > &tasks, int n)
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)
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...
static int missingElement(vector< int > &nums, int k)
static vector< int > findPeakGrid(vector< vector< int > > &mat)
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 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 longestOnes(vector< int > &nums, int k)
static vector< int > maxSlidingWindow(vector< int > &nums, int k)
static string minWindow(string s, const string &t)
static void wallsAndGates(vector< vector< int > > &rooms)
static vector< vector< int > > pacificAtlantic(vector< vector< int > > &heights)
static vector< int > killProcess(vector< int > &pid, vector< int > &ppid, int kill)
static int openLock(vector< string > &deadends, const string &target)
static int makeConnected(int n, vector< vector< int > > &connections)
static vector< vector< int > > criticalConnections(int n, vector< vector< int > > &connections)
static vector< vector< int > > getFactors(int n)
static string decodeString(string s)
static vector< vector< string > > solveNQueens(int n)
static void solveSudoku(vector< vector< char > > &board)
static bool isMatch(const string &s, const string &p)
static vector< int > diffWaysToCompute(const string &expression)
static vector< string > removeInvalidParentheses(const string &s)
static double findMedianSortedArrays(vector< int > &nums1, vector< int > &nums2)
static int splitArray(vector< int > &nums, int m)
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 bool canPartition(vector< int > &nums)
static int mincostTickets(vector< int > &days, vector< int > &costs)
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)
static int minimumSemesters(int n, vector< vector< int > > &relations)
static string alienOrder(vector< string > &words)
static vector< int > singleNumber(vector< int > &nums)
static int shortestPathAllKeys(vector< string > &grid)
int get(int key)
如果键 key 存在于缓存中,则获取键的值,否则返回 -1 。
void put(int key, int value)
如果键 key 已存在,则变更其值;如果键不存在,请插入键值对。当缓存达到其容量 capacity 时,则应该在插入新项之前,移除最不经常使用的项。在此问题中,当存在平局(即两个或更多个键具有相同使用频...
int fourSumCount(vector< int > &nums1, vector< int > &nums2, vector< int > &nums3, vector< int > &nums4)
static int maxSubArrayLen(vector< int > &nums, int k)