leetcode.h

浏览该文件的文档.

#ifndef PROBLEMSCPP_LEETCODE_H
#define PROBLEMSCPP_LEETCODE_H
 
#include "templates.h"
#include <algorithm>
#include <array>
#include <bitset>
#include <functional>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_set>
#include <utility>
#include <vector>
 
using namespace std;
 
namespace leetcode {
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
 
        TreeNode()
            : val(0), left(nullptr), right(nullptr) {}
 
        explicit TreeNode(int x)
            : val(x), left(nullptr), right(nullptr) {}
 
        TreeNode(int x, TreeNode *left, TreeNode *right)
            : val(x), left(left), right(right) {}
 
        bool operator==(const TreeNode & /*node*/) const;
 
        bool operator!=(const TreeNode & /*node*/) const;
    };
 
    struct ListNode {
        int val;
        ListNode *next;
 
        ListNode()
            : val(0), next(nullptr){};
 
        explicit ListNode(int x)
            : val(x), next(nullptr){};
 
        ListNode(int x, ListNode *next)
            : val(x), next(next){};
    };
 
    class Node {
    public:
        int val;
        Node *left;
        Node *right;
        Node *next;
 
        Node()
            : val(0), left(nullptr), right(nullptr), next(nullptr) {}
 
        explicit Node(int _val)
            : val(_val), left(nullptr), right(nullptr), next(nullptr) {}
 
        Node(int _val, Node *_left, Node *_right, Node *_next)
            : val(_val), left(_left), right(_right), next(_next) {}
    };
 
    namespace concatenated_words {
        class Solution {
        public:
            static vector<string> findAllConcatenatedWordsInADict(vector<string> & /*words*/);
        };
 
        class TrieNode {
        public:
            bool is_end;
            char ch;
            TrieNode *nexts[26] = {
                    nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr,
                    nullptr,
                    nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr,
                    nullptr,
                    nullptr, nullptr, nullptr, nullptr, nullptr, nullptr};
 
            explicit TrieNode(char /*ch*/);
 
            void insert(const string &str);
 
            bool dfs(TrieNode * /*root*/, const string & /*str*/, int /*start*/, bool /*flag*/) const;
        };
    }// namespace concatenated_words
 
    namespace excel_sheet_column_number {
        class Solution {
        public:
            static int titleToNumber(const string &columnTitle);
        };
    }// namespace excel_sheet_column_number
 
    namespace excel_sheet_column_title {
        class Solution {
        public:
            static string convertToTitle(int columnNumber);
        };
    }// namespace excel_sheet_column_title
 
    namespace majority_element {
        class Solution {
        private:
            map<int, int> m;
 
        public:
            Solution();
 
            int majorityElement(vector<int> &nums);
        };
    }// namespace majority_element
 
    namespace count_special_quadruplets {
        class Solution {
        public:
            static int countQuadruplets(vector<int> & /*nums*/);
        };
    }// namespace count_special_quadruplets
 
    namespace hand_of_straights {
        class Solution {
        public:
            static bool isNStraightHand(vector<int> &hand, int groupSize);
        };
    }// namespace hand_of_straights
 
    namespace perfect_number {
        class Solution {
        public:
            static bool checkPerfectNumber(int num);
        };
    }// namespace perfect_number
 
    namespace convert_bst_to_greater_tree {
        struct FriendTreeNode {
            int sum;
            int val;
            FriendTreeNode *left;
            FriendTreeNode *right;
            TreeNode *friend_node;
 
            explicit FriendTreeNode(int x, TreeNode *friend_node)
                : sum(x), val(0), left(nullptr), right(nullptr),
                  friend_node(friend_node) {}
        };
 
        class Solution {
        public:
            static TreeNode *convertBST(TreeNode *root);
 
            static FriendTreeNode *copy(TreeNode * /*node*/);
 
            static void get_sum(FriendTreeNode * /*node*/);
 
            static void convert(FriendTreeNode * /*sum_node*/);
        };
    }// namespace convert_bst_to_greater_tree
 
    namespace convert_1d_array_into_2d_array {
        class Solution {
        public:
            static vector<vector<int>> construct2DArray(vector<int> &original, int m, int n);
        };
    }// namespace convert_1d_array_into_2d_array
 
    namespace elimination_game {
        class Solution {
        public:
            static int lastRemaining(int /*n*/);
        };
    }// namespace elimination_game
 
    namespace check_if_all_as_appears_before_all_bs {
        class Solution {
        public:
            static bool checkString(const string & /*s*/);
        };
    }// namespace check_if_all_as_appears_before_all_bs
 
    namespace number_of_laser_beams_in_a_bank {
        class Solution {
        public:
            static int numberOfBeams(vector<string> & /*bank*/);
 
            static int deviceCount(const string & /*str*/);
        };
    }// namespace number_of_laser_beams_in_a_bank
 
    namespace destroying_asteroids {
        class Solution {
        public:
            static bool asteroidsDestroyed(int mass, vector<int> &asteroids);
        };
    }// namespace destroying_asteroids
 
    namespace maximum_employees_to_be_invited_to_a_meeting {
        class Solution {
        public:
            static int maximumInvitations(vector<int> &);
        };
    }// namespace maximum_employees_to_be_invited_to_a_meeting
 
    namespace day_of_the_week {
        class Solution {
        public:
            static string dayOfTheWeek(int day, int month, int year);
        };
    }// namespace day_of_the_week
 
    namespace cat_and_mouse {
        const int MOUSE_WIN = 1;
 
        const int CAT_WIN = 2;
 
        const int DRAW = 0;
 
        const int MAXN = 51;
 
        class Solution {
        public:
            int n;
            int dp[MAXN][MAXN][MAXN * 2];
            vector<vector<int>> graph;
 
            int catMouseGame(vector<vector<int>> &graph);
 
            int getResult(int mouse, int cat, int turns);
 
            void getNextResult(int mouse, int cat, int turns);
        };
    }// namespace cat_and_mouse
 
    namespace replace_all_s_to_avoid_consecutive_repeating_characters {
        class Solution {
        public:
            static string modifyString(string s);
        };
    }// namespace replace_all_s_to_avoid_consecutive_repeating_characters
 
    namespace simplify_path {
        class Solution {
        public:
            static string simplifyPath(const string &path);
        };
    }// namespace simplify_path
 
    namespace maximum_nesting_depth_of_the_parentheses {
        class Solution {
        public:
            static int maxDepth(const string &s);
        };
    }// namespace maximum_nesting_depth_of_the_parentheses
 
    namespace gray_code {
        class Solution {
        public:
            static vector<int> grayCode(int n);
        };
    }// namespace gray_code
 
    namespace check_if_every_row_and_column_contains_all_numbers {
        class Solution {
        public:
            static bool checkValid(vector<vector<int>> &matrix);
        };
    }// namespace check_if_every_row_and_column_contains_all_numbers
 
    namespace minimum_swaps_to_group_all_1s_together_ii {
        class Solution {
        public:
            static int minSwaps(vector<int> &nums);
        };
    }// namespace minimum_swaps_to_group_all_1s_together_ii
 
    namespace count_words_obtained_after_adding_a_letter {
        class Solution {
        public:
            static int wordCount(vector<string> &startWords, vector<string> &targetWords);
 
            static unsigned int str2bin(const string & /*str*/);
        };
    }// namespace count_words_obtained_after_adding_a_letter
 
    namespace slowest_key {
        class Solution {
        public:
            static char slowestKey(vector<int> &releaseTimes, string keysPressed);
        };
    }// namespace slowest_key
 
    namespace additive_number {
        class Solution {
        public:
            static bool isAdditiveNumber(string num);
            static bool dfs(unsigned long long n1, unsigned long long n2, const char * /*nums*/, unsigned short length, unsigned short current);
            static unsigned long long str2ui(const char * /*str*/, unsigned short start, unsigned short length);
 
            static bool equal(string /*sum*/, const char * /*nums*/, unsigned short start, unsigned short length);
        };
    }// namespace additive_number
 
    namespace decode_the_slanted_ciphertext {
        class Solution {
        public:
            static string decodeCiphertext(string encodedText, int rows);
            static string rtrim(string &s);
        };
    }// namespace decode_the_slanted_ciphertext
 
    namespace escape_a_large_maze {
        struct point {
            unsigned int x;
            unsigned int y;
            unsigned int distance;
            point *target;
 
            point()
                : x(0), y(0), distance(0), target(nullptr){};
 
            point(unsigned int x, unsigned int y, int distance, point *target)
                : x(x), y(y), distance(distance), target(target){};
            bool operator<(const point &p) const;
            bool operator==(const point &p) const;
        };
 
        struct point_hash {
            size_t operator()(const point &p) const;
        };
 
        class Solution {
        public:
            static bool isEscapePossible(vector<vector<int>> &blocked, vector<int> &source, vector<int> &target);
 
            static unsigned int search(unordered_set<point, point_hash> &block_set, point *source, point *target, unsigned int limit);
        };
    }// namespace escape_a_large_maze
 
    namespace increasing_triplet_subsequence {
        class Solution {
        public:
            static bool increasingTriplet(vector<int> &nums);
        };
    }// namespace increasing_triplet_subsequence
 
    namespace largest_number_at_least_twice_of_others {
        class Solution {
        public:
            static int dominantIndex(vector<int> &nums);
        };
    }// namespace largest_number_at_least_twice_of_others
 
    namespace find_k_pairs_with_smallest_sums {
        struct pair {
            int u;
            int v;
 
            pair(int u, int v)
                : u(u), v(v){};
            bool operator<(const pair & /*p*/) const;
        };
 
        class Solution {
        public:
            static vector<vector<int>> kSmallestPairs(vector<int> &nums1, vector<int> &nums2, int k);
        };
    }// namespace find_k_pairs_with_smallest_sums
 
    namespace permutations {
        class Solution {
        public:
            static vector<vector<int>> permute(vector<int> &nums);
        };
    }// namespace permutations
 
    namespace calculate_money_in_leetcode_bank {
        class Solution {
        public:
            static int totalMoney(int n);
        };
    }// namespace calculate_money_in_leetcode_bank
 
    namespace linked_list_random_node {
        class Solution {
        private:
            ListNode *head;
 
        public:
            explicit Solution(ListNode *head)
                : head(head){};
            [[nodiscard]] int getRandom() const;
        };
 
    }// namespace linked_list_random_node
 
    namespace divide_a_string_into_groups_of_size_k {
        class Solution {
        public:
            static vector<string> divideString(const string &s, int k, char fill);
        };
    }// namespace divide_a_string_into_groups_of_size_k
 
    namespace minimum_moves_to_reach_target_score {
        class Solution {
        public:
            static int minMoves(int target, int maxDoubles);
        };
    }// namespace minimum_moves_to_reach_target_score
 
    namespace solving_questions_with_brainpower {
        class Solution {
        public:
            static long long mostPoints(vector<vector<int>> &questions);
        };
    }// namespace solving_questions_with_brainpower
 
    namespace maximum_running_time_of_n_computers {
        class Solution {
        public:
            static long long maxRunTime(int n, vector<int> &batteries);
        };
    }// namespace maximum_running_time_of_n_computers
 
    namespace coun_vowels_permutation {
        class Solution {
        public:
            static int countVowelPermutation(int n);
        };
    }// namespace coun_vowels_permutation
 
    namespace minimum_time_difference {
        class Solution {
        public:
            static int findMinDifference(vector<string> &timePoints);
        };
    }// namespace minimum_time_difference
 
    namespace contains_duplicate_ii {
        class Solution {
        public:
            static bool containsNearbyDuplicate(vector<int> &nums, int k);
        };
    }// namespace contains_duplicate_ii
 
    namespace stone_game_ix {
        class Solution {
        public:
            static bool stoneGameIX(vector<int> &stones);
        };
    }// namespace stone_game_ix
 
    namespace jump_game_iv {
        class Solution {
        public:
            static int minJumps(vector<int> &arr);
        };
    }// namespace jump_game_iv
 
    namespace remove_palindromic_subsequences {
        class Solution {
        public:
            static int removePalindromeSub(string s);
        };
    }// namespace remove_palindromic_subsequences
 
    namespace UhWRSj {
        struct TrieNode {
            char ch;
            TrieNode *next[26] = {};
            bool endroot;
 
            TrieNode()
                : ch(0), endroot(false){};
 
            explicit TrieNode(char ch)
                : ch(ch), endroot(false){};
            void insert(const string &str);
            [[nodiscard]] string get_prefix(string root, const string &str) const;
        };
 
        class Solution {
        public:
            static string replaceWords(vector<string> &dictionary, const string &sentence);
        };
    }// namespace UhWRSj
 
    namespace minimum_cost_of_buying_candies_with_discount {
        class Solution {
        public:
            static int minimumCost(vector<int> &cost);
        };
    }// namespace minimum_cost_of_buying_candies_with_discount
 
    namespace count_the_hidden_sequences {
        class Solution {
        public:
            static int numberOfArrays(vector<int> &differences, int lower, int upper);
        };
    }// namespace count_the_hidden_sequences
 
    namespace k_highest_ranked_items_within_a_price_range {
        struct item {
            int distance;
            int price;
            int row;
            int col;
 
            item(int distance, int price, int row, int col)
                : distance(distance), price(price), row(row), col(col){};
            bool operator<(const item & /*i*/) const;
        };
 
        class Solution {
        public:
            static vector<vector<int>> highestRankedKItems(vector<vector<int>> &grid, vector<int> &pricing, vector<int> &start, int k);
        };
    }// namespace k_highest_ranked_items_within_a_price_range
 
    namespace number_of_ways_to_divide_a_long_corridor {
        class Solution {
        public:
            static int numberOfWays(string corridor);
        };
    }// namespace number_of_ways_to_divide_a_long_corridor
 
    namespace count_elements_with_strictly_smaller_and_greater_elements {
        class Solution {
        public:
            static int countElements(vector<int> &nums);
        };
    }// namespace count_elements_with_strictly_smaller_and_greater_elements
 
    namespace rearrange_array_elements_by_sign {
        class Solution {
        public:
            static vector<int> rearrangeArray(vector<int> &nums);
        };
    }// namespace rearrange_array_elements_by_sign
 
    namespace find_all_lonely_numbers_in_the_array {
        class Solution {
        public:
            static vector<int> findLonely(vector<int> &nums);
        };
    }// namespace find_all_lonely_numbers_in_the_array
 
    namespace maximum_good_people_based_on_statements {
        struct msg {
            int person;
            bool good;
 
            msg(int person, bool good)
                : person(person), good(good){};
        };
 
        class Solution {
        public:
            static int maximumGood(vector<vector<int>> &statements);
            static pair<int, unordered_map<int, bool>> dfs(vector<vector<int>> &statements, unordered_map<int, bool> um, queue<msg> que);
        };
    }// namespace maximum_good_people_based_on_statements
 
    namespace stock_price_fluctuation {
        class StockPrice {
            multiset<int> ms;
            map<int, int> m;
 
        public:
            StockPrice();
            void update(int timestamp, int price);
            [[nodiscard]] int current() const;
            [[nodiscard]] int maximum() const;
            [[nodiscard]] int minimum() const;
        };
    }// namespace stock_price_fluctuation
 
    namespace second_minimum_time_to_reach_destination {
        struct status {
            int position;
            int time;
 
            status(int position, int time)
                : position(position), time(time){};
            bool operator<(const status &s) const;
        };
 
        class Solution {
        public:
            static int secondMinimum(int n, vector<vector<int>> &edges, int time, int change);
        };
    }// namespace second_minimum_time_to_reach_destination
 
    namespace count_of_matches_in_tournament {
        class Solution {
        public:
            static int numberOfMatches(int n);
        };
    }// namespace count_of_matches_in_tournament
 
    namespace detect_squares {
        class DetectSquares {
            multiset<pair<int, int>> ms;
 
        public:
            DetectSquares();
            void add(vector<int> point);
            [[nodiscard]] int count(vector<int> point) const;
        };
    }// namespace detect_squares
 
    namespace number_of_valid_words_in_a_sentence {
        class Solution {
        public:
            static int countValidWords(const string &sentence);
        };
    }// namespace number_of_valid_words_in_a_sentence
 
    namespace the_number_of_weak_characters_in_the_game {
        class Solution {
        public:
            static int numberOfWeakCharacters(vector<vector<int>> &properties);
        };
    }// namespace the_number_of_weak_characters_in_the_game
 
    namespace pattern_matching_lcci {
        class Solution {
        public:
            static bool patternMatching(const string &pattern, const string &value);
        };
    }// namespace pattern_matching_lcci
 
    namespace map_of_highest_peak {
        class Solution {
        public:
            static vector<vector<int>> highestPeak(vector<vector<int>> &isWater);
        };
    }// namespace map_of_highest_peak
 
    namespace uncommon_words_from_two_sentences {
        class Solution {
        public:
            static vector<string> uncommonFromSentences(const string &s1, const string &s2);
        };
    }// namespace uncommon_words_from_two_sentences
 
    namespace keep_multiplying_found_values_by_two {
        class Solution {
        public:
            static int findFinalValue(vector<int> &nums, int original);
        };
    }// namespace keep_multiplying_found_values_by_two
 
    namespace all_divisions_with_the_highest_score_of_a_binary_array {
        class Solution {
        public:
            static vector<int> maxScoreIndices(vector<int> &nums);
        };
    }// namespace all_divisions_with_the_highest_score_of_a_binary_array
 
    namespace find_substring_with_given_hash_value {
        class Solution {
        public:
            static string subStrHash(string s, int power, int modulo, int k, int hashValue);
        };
    }// namespace find_substring_with_given_hash_value
 
    namespace groups_of_strings {
        class Solution {
            int groups                                       = 0;
            unsigned int max_size                            = 1;
            unordered_map<unsigned int, unsigned int> parent = unordered_map<unsigned int, unsigned int>();
            unordered_map<unsigned int, unsigned int> rank   = unordered_map<unsigned int, unsigned int>();
            unordered_map<unsigned int, unsigned int> size   = unordered_map<unsigned int, unsigned int>();
 
        public:
            vector<int> groupStrings(vector<string> &words);
            static unsigned int compress(const string &word);
            void insert(unsigned int num);
            unsigned int find(unsigned int x);
            void to_union(unsigned int x1, unsigned int x2);
        };
    }// namespace groups_of_strings
 
    namespace number_of_steps_to_reduce_a_number_to_zero {
        class Solution {
        public:
            static int numberOfSteps(int num);
        };
    }// namespace number_of_steps_to_reduce_a_number_to_zero
 
    namespace longest_nice_substring {
        class Solution {
        public:
            static string longestNiceSubstring(const string &s);
            static pair<int, int> dfs(string s, int start, int end);
        };
    }// namespace longest_nice_substring
 
    namespace reverse_prefix_of_word {
        class Solution {
        public:
            static string reversePrefix(string word, char ch);
        };
    }// namespace reverse_prefix_of_word
 
    namespace find_the_minimum_number_of_fibonacci_numbers_whose_sum_is_k {
        class Solution {
        public:
            static int findMinFibonacciNumbers(int k);
            static int find_min(set<int, greater<>> &fibb, int k, set<int, greater<>>::iterator begin);
        };
    }// namespace find_the_minimum_number_of_fibonacci_numbers_whose_sum_is_k
 
    namespace number_of_rectangles_that_can_form_the_largest_square {
        class Solution {
        public:
            static int countGoodRectangles(vector<vector<int>> &rectangles);
        };
    }// namespace number_of_rectangles_that_can_form_the_largest_square
 
    namespace path_with_maximum_gold {
        class Solution {
        public:
            static int getMaximumGold(vector<vector<int>> &grid);
            static int get_sum(int current, int x, int y, int m, int n, vector<vector<int>> &grid, bool **occupied);
        };
    }// namespace path_with_maximum_gold
 
    namespace minimum_sum_of_four_digit_number_after_splitting_digits {
        class Solution {
        public:
            static int minimumSum(int num);
        };
    }// namespace minimum_sum_of_four_digit_number_after_splitting_digits
 
    namespace partition_array_according_to_given_pivot {
        class Solution {
        public:
            static vector<int> pivotArray(vector<int> &nums, int pivot);
        };
    }// namespace partition_array_according_to_given_pivot
 
    namespace minimum_cost_to_set_cooking_time {
        class Solution {
        public:
            static int minCostSetTime(int startAt, int moveCost, int pushCost, int targetSeconds);
            static int get_cost(int startAt, int moveCost, int pushCost, const int num[4]);
        };
    }// namespace minimum_cost_to_set_cooking_time
 
    namespace minimum_difference_in_sums_after_removal_of_elements {
        class Solution {
        public:
            static long long minimumDifference(vector<int> &nums);
        };
    }// namespace minimum_difference_in_sums_after_removal_of_elements
 
    namespace sum_of_unique_elements {
        class Solution {
        public:
            static int sumOfUnique(vector<int> &nums);
        };
    }// namespace sum_of_unique_elements
 
    namespace sort_even_and_odd_indices_independently {
        class Solution {
        public:
            static vector<int> sortEvenOdd(vector<int> &nums);
        };
    }// namespace sort_even_and_odd_indices_independently
 
    namespace smallest_value_of_the_rearranged_number {
        class Solution {
        public:
            static long long smallestNumber(long long num);
        };
    }// namespace smallest_value_of_the_rearranged_number
 
    namespace design_bitset {
        class Bitset {
            int size = 0;
            set<unsigned int> *one1;
            set<unsigned int> *zero0;
 
        public:
            explicit Bitset(int size);
            void fix(int idx) const;
            void unfix(int idx) const;
            void flip();
            [[nodiscard]] bool all() const;
            [[nodiscard]] bool one() const;
            [[nodiscard]] int count() const;
            [[nodiscard]] string toString() const;
        };
    }// namespace design_bitset
 
    namespace longest_happy_string {
        class Solution {
        public:
            static string longestDiverseString(int a, int b, int c);
            static void sort(char ch[3], int a, int b, int c);
            static int *get_p(char ch, int *a, int *b, int *c);
        };
    }// namespace longest_happy_string
 
    namespace grid_illumination {
        struct pair_hash {
            unsigned long long operator()(const pair<int, int> & /*p*/) const;
        };
 
        class Solution {
        public:
            static vector<int> gridIllumination(int n, vector<vector<int>> &lamps, vector<vector<int>> &queries);
        };
    }// namespace grid_illumination
 
    namespace count_number_of_pairs_with_absolute_difference_k {
        class Solution {
        public:
            static int countKDifference(vector<int> &nums, int k);
        };
    }// namespace count_number_of_pairs_with_absolute_difference_k
 
    namespace simplified_fractions {
        class Solution {
        public:
            static vector<string> simplifiedFractions(int n);
            static int gcd(int m, int n);
        };
    }// namespace simplified_fractions
 
    namespace minimum_difference_between_highest_and_lowest_of_k_scores {
        class Solution {
        public:
            static int minimumDifference(vector<int> &nums, int k);
        };
    }// namespace minimum_difference_between_highest_and_lowest_of_k_scores
 
    namespace number_of_enclaves {
        class Solution {
        public:
            static int numEnclaves(vector<vector<int>> &grid);
        };
    }// namespace number_of_enclaves
 
    namespace maximum_number_of_balloons {
        class Solution {
        public:
            static int maxNumberOfBalloons(const string &text);
        };
    }// namespace maximum_number_of_balloons
 
    namespace swap_adjacent_in_lr_string {
        class Solution {
        public:
            static bool canTransform(const string &start, const string &end);
        };
    }// namespace swap_adjacent_in_lr_string
 
    namespace count_operations_to_obtain_zero {
        class Solution {
        public:
            static int countOperations(int num1, int num2);
        };
    }// namespace count_operations_to_obtain_zero
 
    namespace minimum_operations_to_make_the_array_alternating {
        class Solution {
        public:
            static int minimumOperations(vector<int> &nums);
        };
    }// namespace minimum_operations_to_make_the_array_alternating
 
    namespace removing_minimum_number_of_magic_beans {
        class Solution {
        public:
            static long long minimumRemoval(vector<int> &beans);
        };
    }// namespace removing_minimum_number_of_magic_beans
 
    namespace maximum_and_sum_of_array {
        class Solution {
        public:
            static int maximumANDSum(vector<int> &nums, int numSlots);
        };
    }// namespace maximum_and_sum_of_array
 
    namespace single_element_in_a_sorted_array {
        class Solution {
        public:
            static int singleNonDuplicate(vector<int> &nums);
        };
    }// namespace single_element_in_a_sorted_array
 
 
    namespace lucky_numbers_in_a_matrix {
        class Solution {
        public:
            static vector<int> luckyNumbers(vector<vector<int>> &matrix);
        };
    }// namespace lucky_numbers_in_a_matrix
 
    namespace number_of_ways_to_reconstruct_a_tree {
        class Solution {
        public:
            static int checkWays(vector<vector<int>> &pairs);
        };
    }// namespace number_of_ways_to_reconstruct_a_tree
 
    namespace find_center_of_star_graph {
        class Solution {
        public:
            static int findCenter(vector<vector<int>> &edges);
        };
    }// namespace find_center_of_star_graph
 
    namespace knight_probability_in_chessboard {
        struct status {
            int k;
            int row;
            int column;
 
            status(int k, int row, int column)
                : k(k), row(row), column(column){};
        };
 
        struct status_hash {
            unsigned int operator()(const status & /*s*/) const;
        };
 
        struct status_equal {
            bool operator()(const status & /*s1*/, const status & /*s2*/) const;
        };
 
        class Solution {
            unordered_map<status, double, status_hash, status_equal> um = unordered_map<status, double, status_hash, status_equal>();
 
        public:
            double knightProbability(int n, int k, int row, int column);
        };
    }// namespace knight_probability_in_chessboard
 
    namespace pancake_sorting {
        class Solution {
        public:
            static vector<int> pancakeSort(vector<int> &arr);
        };
    }// namespace pancake_sorting
 
    namespace count_equal_and_divisible_pairs_in_an_array {
        class Solution {
        public:
            static int countPairs(vector<int> &nums, int k);
        };
    }// namespace count_equal_and_divisible_pairs_in_an_array
 
    namespace find_three_consecutive_integers_that_sum_to_a_given_number {
        class Solution {
        public:
            static vector<long long> sumOfThree(long long num);
        };
    }// namespace find_three_consecutive_integers_that_sum_to_a_given_number
 
    namespace maximum_split_of_positive_even_integers {
        class Solution {
        public:
            static vector<long long> maximumEvenSplit(long long finalSum);
        };
    }// namespace maximum_split_of_positive_even_integers
 
    namespace count_good_triplets_in_an_array {
        template<class T> class FenwickTree {
            int limit{};
            vector<T> arr;
 
            static int lowbit(int x) { return x & -x; }
 
        public:
            explicit FenwickTree(int limit) {
                this->limit = limit;
                arr         = vector<T>(limit + 1);
            }
 
            void update(int idx, T delta) {
                for(; idx <= limit; idx += lowbit(idx)) {
                    arr[idx] += delta;
                }
            }
 
            T query(int idx) {
                T ans = 0;
                for(; idx > 0; idx -= lowbit(idx)) {
                    ans += arr[idx];
                }
                return ans;
            }
        };
 
        class Solution {
        public:
            static long long goodTriplets(vector<int> &nums1, vector<int> &nums2);
        };
    }// namespace count_good_triplets_in_an_array
 
    namespace count_integers_with_even_digit_sum {
        class Solution {
        public:
            static int countEven(int num);
        };
    }// namespace count_integers_with_even_digit_sum
 
    namespace merge_nodes_in_between_zeros {
        class Solution {
        public:
            static ListNode *mergeNodes(ListNode *head);
        };
    }// namespace merge_nodes_in_between_zeros
 
    namespace construct_string_with_repeat_limit {
        class Solution {
        public:
            static string repeatLimitedString(const string &s, int repeatLimit);
        };
    }// namespace construct_string_with_repeat_limit
 
    namespace count_array_pairs_divisible_by_k {
        class Solution {
        public:
            static long long coutPairs(vector<int> &nums, int k);
        };
    }// namespace count_array_pairs_divisible_by_k
 
    namespace leetcode717_1_bit_and_2_bit_characters {
        class Solution {
        public:
            static bool isOneBitCharacter(vector<int> &bits);
        };
    }// namespace leetcode717_1_bit_and_2_bit_characters
 
    namespace longest_mountain_in_array {
        class Solution {
        public:
            static int longestMountain(vector<int> &arr);
        };
    }// namespace longest_mountain_in_array
 
    namespace push_dominoes {
        class Solution {
        public:
            static string pushDominoes(string dominoes);
        };
    }// namespace push_dominoes
 
    namespace the_number_of_good_subsets {
        class Solution {
        private:
            static constexpr array<int, 10> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
            static constexpr int num_max           = 30;
            static constexpr int mod               = 1000000007;
            static constexpr int mask_max          = 1 << primes.size();
 
        public:
            static int numberOfGoodSubsets(vector<int> &nums);
        };
    }// namespace the_number_of_good_subsets
 
    namespace reverse_only_letters {
        class Solution {
        public:
            static string reverseOnlyLetters(string s);
        };
    }// namespace reverse_only_letters
 
    namespace where_will_the_ball_fall {
        class Solution {
        public:
            static vector<int> findBall(vector<vector<int>> &grid);
        };
    }// namespace where_will_the_ball_fall
 
    namespace complex_number_multiplication {
        class Solution {
        public:
            static string complexNumberMultiply(const string &num1, const string &num2);
        };
    }// namespace complex_number_multiplication
 
    namespace maximum_difference_between_increasing_elements {
        class Solution {
        public:
            static int maximumDifference(vector<int> &nums);
        };
    }// namespace maximum_difference_between_increasing_elements
 
    namespace optimal_division {
        class Solution {
        public:
            static string optimalDivision(vector<int> &nums);
        };
    }// namespace optimal_division
 
    namespace counting_words_with_a_given_prefix {
        class Solution {
        public:
            static int prefixCount(vector<string> &words, string pref);
        };
    }// namespace counting_words_with_a_given_prefix
 
    namespace minimum_number_of_steps_to_make_two_strings_anagram_ii {
        class Solution {
        public:
            static int minSteps(const string &s, const string &t);
        };
    }// namespace minimum_number_of_steps_to_make_two_strings_anagram_ii
 
    namespace minimum_time_to_complete_trips {
        class Solution {
        public:
            static long long minimumTime(vector<int> &time, int totalTrips);
        };
    }// namespace minimum_time_to_complete_trips
 
    namespace minimum_time_to_finish_the_race {
        class Solution {
        public:
            static int minimumFinishTime(vector<vector<int>> &tires, int changeTime, int numLaps);
        };
    }// namespace minimum_time_to_finish_the_race
 
    namespace maximum_number_of_achievable_transfer_requests {
        class Solution {
        public:
            static int maximumRequests(int n, vector<vector<int>> &requests);
        };
    }// namespace maximum_number_of_achievable_transfer_requests
 
    namespace zigzag_conversion {
        class Solution {
        public:
            static string convert(string s, int numRows);
        };
    }// namespace zigzag_conversion
 
    namespace find_the_closest_palindrome {
        class Solution {
        public:
            static string nearestPalindromic(const string &n);
        };
    }// namespace find_the_closest_palindrome
 
    namespace add_digits {
        class Solution {
        public:
            static int addDigits(int num);
        };
    }// namespace add_digits
 
    namespace sum_of_subarray_ranges {
        class Solution {
        public:
            static long long subArrayRanges(vector<int> &nums);
        };
    }// namespace sum_of_subarray_ranges
 
    namespace longest_uncommon_subsequence_i {
        class Solution {
        public:
            static int findLUSlength(const string &a, const string &b);
        };
    }// namespace longest_uncommon_subsequence_i
 
    namespace most_frequent_number_following_key_in_an_array {
        class Solution {
        public:
            static int mostFrequent(vector<int> &nums, int key);
        };
    }// namespace most_frequent_number_following_key_in_an_array
 
    namespace sort_the_jumbled_numbers {
        struct cmp {
            bool operator()(const tuple<int, int, int> &s1, const tuple<int, int, int> &s2) const {
                auto [i1, num1, rev1] = s1;
                auto [i2, num2, rev2] = s2;
                if(rev1 != rev2) {
                    return rev1 < rev2;
                }
                return i1 < i2;
            }
        };
 
        class Solution {
        public:
            static vector<int> sortJumbled(vector<int> &mapping, vector<int> &nums);
        };
    }// namespace sort_the_jumbled_numbers
 
    namespace all_ancestors_of_a_node_in_a_directed_acyclic_graph {
        class Solution {
            unordered_map<int, unordered_set<int>> nexts;
            unordered_map<int, set<int>> ancestors;
 
        public:
            vector<vector<int>> getAncestors(int n, vector<vector<int>> &edges);
            void dfs(bool *dfsd, int v, int i);
        };
    }// namespace all_ancestors_of_a_node_in_a_directed_acyclic_graph
 
    namespace minimum_number_of_moves_to_make_palindrome {
        class Solution {
        public:
            static int minMovesToMakePalindrome(string s);
        };
    }// namespace minimum_number_of_moves_to_make_palindrome
 
    namespace cells_in_a_range_on_an_excel_sheet {
        class Solution {
        public:
            static vector<string> cellsInRange(const string &s);
        };
    }// namespace cells_in_a_range_on_an_excel_sheet
 
    namespace append_k_integers_with_minimal_sum {
        class Solution {
        public:
            static long long minimalKSum(vector<int> &nums, int k);
        };
    }// namespace append_k_integers_with_minimal_sum
 
    namespace create_binary_tree_from_descriptions {
        class Solution {
        public:
            static TreeNode *createBinaryTree(vector<vector<int>> &descriptions);
        };
    }// namespace create_binary_tree_from_descriptions
 
    namespace replace_non_coprime_numbers_in_array {
        class Solution {
        public:
            static vector<int> replaceNonCoprimes(vector<int> &nums);
        };
    }// namespace replace_non_coprime_numbers_in_array
 
    namespace find_good_days_to_rob_the_bank {
        class Solution {
        public:
            static vector<int> goodDaysToRobBank(vector<int> &security, int time);
        };
    }// namespace find_good_days_to_rob_the_bank
 
    namespace base_7 {
        class Solution {
        public:
            static string convertToBase7(int num);
        };
    }// namespace base_7
 
    namespace plates_between_candles {
        class Solution {
        public:
            static vector<int> platesBetweenCandles(string s, vector<vector<int>> &queries);
        };
    }// namespace plates_between_candles
 
    namespace smallest_rotation_with_highest_score {
        class Solution {
        public:
            static int bestRotation(vector<int> &nums);
        };
    }// namespace smallest_rotation_with_highest_score
 
    namespace n_ary_tree_preorder_traversal {
        class Node {
        public:
            int val{};
            vector<Node *> children;
            Node() = default;
 
            explicit Node(int _val)
                : val(_val) {}
 
            Node(int _val, vector<Node *> _children)
                : val(_val), children(std::move(std::move(_children))) {}
        };
 
        class Solution {
        public:
            static vector<int> preorder(Node *root);
        };
    }// namespace n_ary_tree_preorder_traversal
 
    namespace count_nodes_with_the_highest_score {
        class TreeNode {
        private:
            int val;
            int count = 0;
            vector<TreeNode *> children;
            TreeNode *parent = nullptr;
 
        public:
            explicit TreeNode(int val)
                : val(val){};
            void add_child(TreeNode *node);
            [[nodiscard]] const vector<TreeNode *> &get_children() const;
            [[nodiscard]] int get_count() const;
            [[nodiscard]] TreeNode *get_parent() const;
            int dfs();
        };
 
        class Solution {
        public:
            static int countHighestScoreNodes(vector<int> &parents);
        };
    }// namespace count_nodes_with_the_highest_score
 
    namespace n_ary_tree_postorder_traversal {
        class Node {
        public:
            int val{};
            vector<Node *> children;
            Node() = default;
 
            explicit Node(int _val)
                : val(_val) {}
 
            Node(int _val, vector<Node *> _children)
                : val(_val), children(std::move(std::move(_children))) {}
        };
 
        class Solution {
        public:
            static vector<int> postorder(Node *root);
        };
    }// namespace n_ary_tree_postorder_traversal
 
    namespace max_area_of_island {
        class UnionFind {
        private:
            int m;
            int n;
            unordered_map<pair<int, int>, pair<int, int>, function<unsigned int(const pair<int, int> &)>> parent;
            unordered_map<pair<int, int>, int, function<unsigned int(const pair<int, int> &)>> size;
            unordered_map<pair<int, int>, int, function<unsigned int(const pair<int, int> &)>> rank;
 
        public:
            UnionFind(int m, int n);
            pair<int, int> find(pair<int, int> val);
            void merge(pair<int, int> a, pair<int, int> b);
            bool same(pair<int, int> a, pair<int, int> b);
            [[nodiscard]] bool contains(pair<int, int> p) const;
            int get_size(pair<int, int> p);
        };
 
        class Solution {
        public:
            static int maxAreaOfIsland(vector<vector<int>> &grid);
        };
    }// namespace max_area_of_island
 
    namespace find_all_k_distant_indices_in_an_array {
        class Solution {
        public:
            static vector<int> findKDistantIndices(vector<int> &nums, int key, int k);
        };
    }// namespace find_all_k_distant_indices_in_an_array
 
    namespace count_artifacts_that_can_be_extracted {
        class Solution {
        public:
            static int digArtifacts(int n, vector<vector<int>> &artifacts, vector<vector<int>> &dig);
        };
    }// namespace count_artifacts_that_can_be_extracted
 
    namespace maximize_the_topmost_element_after_k_moves {
        class Solution {
        public:
            static int maximumTop(vector<int> &nums, int k);
        };
    }// namespace maximize_the_topmost_element_after_k_moves
 
    namespace minimum_weighted_subgraph_with_the_required_paths {
        class Solution {
        public:
            static long long minimumWeight(int n, vector<vector<int>> &edges, int src1, int src2, int dest);
            static void calc_dist(int s, vector<pair<int, int>> *graph, vector<long long int> &dist);
        };
    }// namespace minimum_weighted_subgraph_with_the_required_paths
 
    namespace utf_8_validation {
        class Solution {
        public:
            static bool validUtf8(vector<int> &data);
        };
    }// namespace utf_8_validation
 
    namespace minimum_index_sum_of_two_lists {
        class Solution {
        public:
            static vector<string> findRestaurant(vector<string> &list1, vector<string> &list2);
        };
    }// namespace minimum_index_sum_of_two_lists
 
    namespace count_number_of_maximum_bitwise_or_subsets {
        class Solution {
        public:
            static int countMaxOrSubsets(vector<int> &nums);
            static int dfs(int current, int target, vector<int> nums);
        };
    }// namespace count_number_of_maximum_bitwise_or_subsets
 
    namespace all_oone_data_structure {
        class AllOne {
            int max = 0;
            int min = 50000;
            unordered_map<string, int> str_count;
            map<int, unordered_set<string>> count_str;
 
        public:
            AllOne();
            void inc(const string &key);
            void dec(const string &key);
            string getMaxKey();
            string getMinKey();
        };
    }// namespace all_oone_data_structure
 
    namespace longest_word_in_dictionary {
        class Solution {
        public:
            static string longestWord(vector<string> &words);
            static string dfs(const string &str, TrieNode *node);
        };
    }// namespace longest_word_in_dictionary
 
    namespace simple_bank_system {
        class Bank {
            unordered_map<int, long long> accounts;
 
        public:
            explicit Bank(vector<long long> &balance);
            bool transfer(int account1, int account2, long long money);
            bool deposit(int account, long long money);
            bool withdraw(int account, long long money);
        };
    }// namespace simple_bank_system
 
    namespace construct_string_from_binary_tree {
        class Solution {
        public:
            static string tree2str(TreeNode *root);
        };
    }// namespace construct_string_from_binary_tree
 
    namespace maximize_number_of_subsequences_in_a_string {
        class Solution {
        public:
            static long long maximumSubsequenceCount(string text, string pattern);
        };
    }// namespace maximize_number_of_subsequences_in_a_string
 
    namespace minimum_operations_to_halve_array_sum {
        class Solution {
        public:
            static int halveArray(vector<int> &nums);
        };
    }// namespace minimum_operations_to_halve_array_sum
 
    namespace minimum_white_tiles_after_covering_with_carpets {
        class Solution {
        public:
            static int minimumWhiteTiles(string floor, int numCarpets, int carpetLen);
        };
    }// namespace minimum_white_tiles_after_covering_with_carpets
 
    namespace count_hills_and_valleys_in_an_array {
        class Solution {
        public:
            static int countHillValley(vector<int> &nums);
        };
    }// namespace count_hills_and_valleys_in_an_array
 
    namespace count_collisions_on_a_road {
        class Solution {
        public:
            static int countCollisions(const string &directions);
        };
    }// namespace count_collisions_on_a_road
 
    namespace maximum_points_in_an_archery_competition {
        class Solution {
        public:
            static vector<int> maximumBobPoints(int numArrows, vector<int> &aliceArrows);
        };
    }// namespace maximum_points_in_an_archery_competition
 
    namespace the_time_when_the_network_becomes_idle {
        struct Node {
            int num;
            int time = 0;
            int patience;
            unordered_set<int> linked = {};
 
            Node(int num, int patience)
                : num(num), patience(patience) {}
        };
 
        class Solution {
        public:
            static int networkBecomesIdle(vector<vector<int>> &edges, vector<int> &patience);
        };
    }// namespace the_time_when_the_network_becomes_idle
 
    namespace two_sum_iv_input_is_a_bst {
        class Solution {
        public:
            static bool findTarget(TreeNode *root, int k);
        };
    }// namespace two_sum_iv_input_is_a_bst
 
    namespace remove_colored_pieces_if_both_neighbors_are_the_same_color {
        class Solution {
        public:
            static bool winnerOfGame(string colors);
        };
    }// namespace remove_colored_pieces_if_both_neighbors_are_the_same_color
 
    namespace k_th_smallest_in_lexicographical_order {
        class Solution {
        public:
            static int findKthNumber(int n, int k);
            static int getSteps(int curr, long n);
        };
    }// namespace k_th_smallest_in_lexicographical_order
 
    namespace image_smoother {
        class Solution {
        public:
            static vector<vector<int>> imageSmoother(vector<vector<int>> &img);
        };
    }// namespace image_smoother
 
    namespace factorial_trailing_zeroes {
        class Solution {
        public:
            static int trailingZeroes(int n);
        };
    }// namespace factorial_trailing_zeroes
 
    namespace baseball_game {
        class Solution {
        public:
            static int calPoints(vector<string> &ops);
        };
    }// namespace baseball_game
 
    namespace minimum_deletions_to_make_array_beautiful {
        class Solution {
        public:
            static int minDeletion(vector<int> &nums);
        };
    }// namespace minimum_deletions_to_make_array_beautiful
 
    namespace find_palindrome_with_fixed_length {
        unsigned long long qmi(unsigned long long m, unsigned long long k);
 
        class Solution {
        public:
            static vector<long long> kthPalindrome(vector<int> &queries, int intLength);
        };
    }// namespace find_palindrome_with_fixed_length
 
    namespace find_missing_observations {
        class Solution {
        public:
            static vector<int> missingRolls(vector<int> &rolls, int mean, int n);
        };
    }// namespace find_missing_observations
 
    namespace binary_number_with_alternating_bits {
        class Solution {
        public:
            static bool hasAlternatingBits(int n);
        };
    }// namespace binary_number_with_alternating_bits
 
    namespace maximize_the_confusion_of_an_exam {
        class Solution {
        public:
            static int maxConsecutiveAnswers(string answerKey, int k);
        };
    }// namespace maximize_the_confusion_of_an_exam
 
    namespace find_servers_that_handled_most_number_of_requests {
        struct event {
            int time;
            bool start;
            int index;
            int server_index;
 
            bool operator<(const event &e) const;
        };
 
        class Solution {
        public:
            static vector<int> busiestServers(int k, vector<int> &arrival, vector<int> &load);
        };
    }// namespace find_servers_that_handled_most_number_of_requests
 
    namespace self_dividing_numbers {
        class Solution {
        public:
            static vector<int> selfDividingNumbers(int left, int right);
        };
    }// namespace self_dividing_numbers
 
    namespace array_of_doubled_pairs {
        class Solution {
        public:
            static bool canReorderDoubled(vector<int> &arr);
        };
    }// namespace array_of_doubled_pairs
 
    namespace strong_password_checker {
        class Solution {
        public:
            static int strongPasswordChecker(const string &password);
        };
    }// namespace strong_password_checker
 
    namespace number_of_ways_to_select_buildings {
        class Solution {
        public:
            static long long numberOfWays(string s);
        };
    }// namespace number_of_ways_to_select_buildings
 
    namespace sum_of_scores_of_built_strings {
        class Solution {
        public:
            static long long sumScores(string s);
        };
    }// namespace sum_of_scores_of_built_strings
 
    namespace minimum_number_of_operations_to_convert_time {
        class Solution {
        public:
            static int convertTime(string current, string correct);
        };
    }// namespace minimum_number_of_operations_to_convert_time
 
    namespace find_players_with_zero_or_one_losses {
        class Solution {
        public:
            static vector<vector<int>> findWinners(vector<vector<int>> &matches);
        };
    }// namespace find_players_with_zero_or_one_losses
 
    namespace maximum_candies_allocated_to_k_children {
        class Solution {
        public:
            static int maximumCandies(vector<int> &candies, long long k);
        };
    }// namespace maximum_candies_allocated_to_k_children
 
    namespace encrypt_and_decrypt_strings {
        class Encrypter {
            array<string, 26> mp;
            unordered_map<string, int> count;
 
        public:
            Encrypter(vector<char> &keys, vector<string> &values, vector<string> &dictionary);
            [[nodiscard]] string encrypt(const string &word1) const;
            [[nodiscard]] int decrypt(const string &word2);
        };
    }// namespace encrypt_and_decrypt_strings
 
    namespace range_sum_query_mutable {
        class NumArray {
            vector<int> sum;// sum[i] 表示第 i 个块的元素和
            int size;       // 块的大小
            vector<int> &nums;
 
        public:
            explicit NumArray(vector<int> &nums);
            void update(int index, int val);
            [[nodiscard]] int sumRange(int left, int right) const;
        };
    }// namespace range_sum_query_mutable
 
    namespace process_restricted_friend_requests {
        class Solution {
        public:
            static vector<bool> friendRequests(int n, vector<vector<int>> &restrictions, vector<vector<int>> &requests);
        };
    }// namespace process_restricted_friend_requests
 
    namespace prime_number_of_set_bits_in_binary_representation {
        class Solution {
        public:
            static int countPrimeSetBits(int left, int right);
        };
    }// namespace prime_number_of_set_bits_in_binary_representation
 
    namespace minimum_height_trees {
        class Solution {
        public:
            static int findLongestNode(int u, vector<int> &parent, vector<vector<int>> &adj);
            static vector<int> findMinHeightTrees(int n, vector<vector<int>> &edges);
        };
    }// namespace minimum_height_trees
 
    namespace rotate_string {
        class Solution {
        public:
            static bool rotateString(string s, const string &goal);
        };
    }// namespace rotate_string
 
    namespace n_ary_tree_level_order_traversal {
        class Node {
        public:
            int val{};
            vector<Node *> children;
            Node() = default;
 
            explicit Node(int _val)
                : val(_val){};
 
            Node(int _val, vector<Node *> _children)
                : val(_val), children(std::move(std::move(_children))){};
        };
 
        class Solution {
        public:
            static vector<vector<int>> levelOrder(Node *root);
        };
    }// namespace n_ary_tree_level_order_traversal
 
    namespace reaching_points {
        class Solution {
        public:
            static bool reachingPoints(int sx, int sy, int tx, int ty);
        };
    }// namespace reaching_points
 
    namespace maximum_product_after_k_increments {
        class Solution {
        public:
            static int maximumProduct(vector<int> &nums, int k);
        };
    }// namespace maximum_product_after_k_increments
 
    namespace maximum_total_beauty_of_the_gardens {
        class Solution {
        public:
            static long long maximumBeauty(vector<int> &flowers, long long newFlowers, int target, int full, int partial);
        };
    }// namespace maximum_total_beauty_of_the_gardens
 
    namespace count_numbers_with_unique_digits {
        class Solution {
        public:
            static int countNumbersWithUniqueDigits(int n);
        };
    }// namespace count_numbers_with_unique_digits
 
    namespace number_of_lines_to_write_string {
        class Solution {
        public:
            static vector<int> numberOfLines(vector<int> &widths, string s);
        };
    }// namespace number_of_lines_to_write_string
 
    namespace permutation_in_string {
        class Solution {
        public:
            static bool checkInclusion(const string &s1, string s2);
        };
    }// namespace permutation_in_string
 
    namespace insert_delete_getrandom_o1 {
        class RandomizedSet {
            unordered_map<int, int> map;
            vector<int> nums;
            default_random_engine generator;
            uniform_int_distribution<int> distribution;
 
        public:
            RandomizedSet();
            bool insert(int val);
            bool remove(int val);
            int getRandom();
        };
    }// namespace insert_delete_getrandom_o1
 
    namespace projection_area_of_3d_shapes {
        class Solution {
        public:
            static int projectionArea(vector<vector<int>> &grid);
        };
    }// namespace projection_area_of_3d_shapes
 
    namespace design_parking_system {
        class ParkingSystem {
            int big;   
            int medium;
            int small; 
 
        public:
            ParkingSystem(int big, int medium, int small);
            bool addCar(int carType);
        };
    }// namespace design_parking_system
 
    namespace range_sum_query_immutable {
        class NumArray {
            vector<int> pref_sum;
 
        public:
            explicit NumArray(vector<int> &nums);
            [[nodiscard]] int sumRange(int left, int right) const;
        };
    }// namespace range_sum_query_immutable
 
    namespace house_robber {
        class Solution {
        public:
            static int rob(vector<int> &nums);
        };
    }// namespace house_robber
 
    namespace triangle {
        class Solution {
        public:
            static int minimumTotal(vector<vector<int>> &triangle);
        };
    }// namespace triangle
 
    namespace lowest_common_ancestor_of_a_binary_search_tree {
        struct TreeNodeP {
            int val;
            TreeNodeP *left;
            TreeNodeP *right;
            TreeNodeP *parent;
            TreeNode *mirror{};
            bool ed;
 
            explicit TreeNodeP(int x)
                : val(x), left(nullptr), right(nullptr), parent(nullptr), ed(false) {}
        };
 
        class Solution {
        public:
            static TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q);
            static void copy(TreeNode *tn, TreeNodeP *tnp, int low, int high, TreeNodeP **p, TreeNodeP **q);
        };
    }// namespace lowest_common_ancestor_of_a_binary_search_tree
 
    namespace shuffle_an_array {
        class Solution {
            vector<int> nums;
 
        public:
            explicit Solution(vector<int> &nums);
            vector<int> reset();
            [[nodiscard]] vector<int> shuffle() const;
        };
    }// namespace shuffle_an_array
 
    namespace find_all_anagrams_in_a_string {
        class Solution {
        public:
            static vector<int> findAnagrams(string s, const string &p);
        };
    }// namespace find_all_anagrams_in_a_string
 
    namespace subarray_product_less_than_k {
        class Solution {
        public:
            static int numSubarrayProductLessThanK(vector<int> &nums, int k);
        };
    }// namespace subarray_product_less_than_k
 
    namespace minimum_size_subarray_sum {
        class Solution {
        public:
            static int minSubArrayLen(int target, vector<int> &nums);
        };
    }// namespace minimum_size_subarray_sum
 
    namespace populating_next_right_pointers_in_each_node_ii {
        class Solution {
        public:
            static Node *connect(Node *root);
        };
    }// namespace populating_next_right_pointers_in_each_node_ii
 
    namespace subtree_of_another_tree {
        class Solution {
        public:
            static bool isSubtree(TreeNode *root, TreeNode *subRoot);
            static bool equal(TreeNode *tn1, TreeNode *tn2);
        };
    }// namespace subtree_of_another_tree
 
    namespace shortest_path_in_binary_matrix {
        class Solution {
        public:
            static int shortestPathBinaryMatrix(vector<vector<int>> &grid);
        };
    }// namespace shortest_path_in_binary_matrix
 
    namespace surrounded_regions {
        class Solution {
        public:
            static void dfs(vector<vector<char>> &board, int x, int y);
            static void solve(vector<vector<char>> &board);
        };
    }// namespace surrounded_regions
 
    namespace all_paths_from_source_to_target {
        class Solution {
        public:
            static int dfs(vector<vector<int>> &graph, vector<vector<int>> &ans, int cur);
            static vector<vector<int>> allPathsSourceTarget(vector<vector<int>> &graph);
        };
    }// namespace all_paths_from_source_to_target
 
    namespace permutations_ii {
        class Solution {
        public:
            static void dfs(set<vector<int>> &s, const vector<int> &current, vector<int> rest);
            static vector<vector<int>> permuteUnique(vector<int> &nums);
        };
    }// namespace permutations_ii
 
    namespace combination_sum {
        class Solution {
        public:
            static vector<vector<int>> recurse(vector<int> &candidates, int target, int index);
            static vector<vector<int>> combinationSum(vector<int> &candidates, int target);
        };
    }// namespace combination_sum
 
    namespace combination_sum_ii {
        class Solution {
        public:
            static vector<vector<int>> recurse(vector<int> &candidates, int target, int index);
            static vector<vector<int>> combinationSum2(vector<int> &candidates, int target);
        };
    }// namespace combination_sum_ii
 
    namespace house_robber_ii {
        class Solution {
        public:
            static int rob(vector<int> &nums);
        };
    }// namespace house_robber_ii
 
    namespace jump_game {
        class Solution {
        public:
            static bool canJump(vector<int> &nums);
        };
    }// namespace jump_game
 
    namespace jump_game_ii {
        class Solution {
        public:
            static int jump(vector<int> &nums);
        };
    }// namespace jump_game_ii
 
    namespace unique_paths {
        class Solution {
        public:
            static int uniquePaths(int m, int n);
        };
    }// namespace unique_paths
 
    namespace longest_palindromic_substring {
        class Solution {
        public:
            static string longestPalindrome(string s);
        };
    }// namespace longest_palindromic_substring
 
    namespace arithmetic_slices {
        class Solution {
        public:
            static int numberOfArithmeticSlices(vector<int> &nums);
        };
    }// namespace arithmetic_slices
 
    namespace decode_ways {
        class Solution {
        public:
            static int numDecodings(string s);
        };
    }// namespace decode_ways
 
    namespace word_break {
        class Solution {
        public:
            static void search(const TrieNode *tn, const string &s, int i, vector<bool> &end);
            static bool wordBreak(const string &s, vector<string> &wordDict);
        };
    }// namespace word_break
 
    namespace longest_increasing_subsequence {
        class Solution {
        public:
            static int lengthOfLIS(vector<int> &nums);
        };
    }// namespace longest_increasing_subsequence
 
    namespace number_of_longest_increasing_subsequence {
        class Solution {
        public:
            static int findNumberOfLIS(vector<int> &nums);
        };
    }// namespace number_of_longest_increasing_subsequence
 
    namespace longest_common_subsequence {
        class Solution {
        public:
            static int longestCommonSubsequence(string text1, string text2);
        };
    }// namespace longest_common_subsequence
 
    namespace delete_operation_for_two_strings {
        class Solution {
        public:
            static int minDistance(const string &word1, const string &word2);
        };
    }// namespace delete_operation_for_two_strings
 
    namespace edit_distance {
        class Solution {
        public:
            static int minDistance(string word1, string word2);
        };
    }// namespace edit_distance
 
    namespace coin_change {
        class Solution {
        public:
            static int coinChange(vector<int> &coins, int amount);
        };
    }// namespace coin_change
 
    namespace integer_break {
        class Solution {
        public:
            static int integerBreak(int n);
        };
    }// namespace integer_break
 
    namespace max_points_on_a_line {
        class Solution {
        public:
            static int maxPoints(vector<vector<int>> &points);
        };
    }// namespace max_points_on_a_line
 
    namespace group_anagrams {
        class Solution {
        public:
            static vector<vector<string>> groupAnagrams(vector<string> &strs);
        };
    }// namespace group_anagrams
 
    namespace sort_colors {
        class Solution {
        public:
            static void qsort(vector<int> &nums, int l, int r);
            static void sortColors(vector<int> &nums);
        };
    }// namespace sort_colors
 
    namespace top_k_frequent_elements {
        class Solution {
        public:
            static vector<int> topKFrequent(vector<int> &nums, int k);
        };
    }// namespace top_k_frequent_elements
 
    namespace kth_largest_element_in_an_array {
        class Solution {
        public:
            static int findKthLargest(vector<int> &nums, int k);
        };
    }// namespace kth_largest_element_in_an_array
 
    namespace merge_intervals {
        class Solution {
        public:
            static vector<vector<int>> merge(vector<vector<int>> &intervals);
        };
    }// namespace merge_intervals
 
    namespace search_a_2d_matrix_ii {
        class Solution {
        public:
            static bool search(const vector<vector<int>> &matrix, int target, int x_start, int x_end, int y_start, int y_end);
            static bool searchMatrix(vector<vector<int>> &matrix, int target);
        };
    }// namespace search_a_2d_matrix_ii
 
    namespace serialize_and_deserialize_binary_tree {
        class Codec {
        public:
            static string serialize(TreeNode *root);
 
            [[nodiscard]] static TreeNode *deserialize(string data);
        };
    }// namespace serialize_and_deserialize_binary_tree
 
    namespace task_scheduler {
        class Solution {
        public:
            static int leastInterval(vector<char> &tasks, int n);
        };
    }// namespace task_scheduler
 
    namespace design_hashmap {
        class MyHashMap {
            static const unsigned SZ = 1021;
            array<list<pair<int, int>>, SZ> arr;
 
        public:
            MyHashMap();
 
            void put(int key, int value);
 
            int get(int key);
 
            void remove(int key);
        };
    }// namespace design_hashmap
 
    namespace spiral_matrix_ii {
        class Solution {
        public:
            static vector<vector<int>> generateMatrix(int n);
        };
    }// namespace spiral_matrix_ii
 
    namespace non_overlapping_intervals {
        class Solution {
        public:
            static int eraseOverlapIntervals(vector<vector<int>> &intervals);
        };
    }// namespace non_overlapping_intervals
 
    namespace product_of_array_except_self {
        class Solution {
        public:
            static vector<int> productExceptSelf(vector<int> &nums);
        };
    }// namespace product_of_array_except_self
 
    namespace subarray_sum_equals_k {
        class Solution {
        public:
            static int subarraySum(vector<int> &nums, int k);
        };
    }// namespace subarray_sum_equals_k
 
    namespace partition_labels {
        class Solution {
        public:
            static vector<int> partitionLabels(string s);
        };
    }// namespace partition_labels
 
    namespace repeated_dna_sequences {
        class Solution {
        public:
            static vector<string> findRepeatedDnaSequences(string s);
        };
    }// namespace repeated_dna_sequences
 
    namespace design_linked_list {
        class MyLinkedList {
            ListNode *head;
            ListNode *tail;
 
        public:
            MyLinkedList();
            [[nodiscard]] int get(int index) const;
            void addAtHead(int val);
            void addAtTail(int val);
            void addAtIndex(int index, int val);
            void deleteAtIndex(int index);
        };
    }// namespace design_linked_list
 
    namespace delete_node_in_a_bst {
        class Solution {
            TreeNode *prev;
 
        public:
            TreeNode *findMaximum(TreeNode *node);
            TreeNode *findMinimum(TreeNode *node);
            void remove(TreeNode *node);
            TreeNode *deleteNode(TreeNode *root, int key);
        };
    }// namespace delete_node_in_a_bst
 
    namespace missing_element_in_sorted_array {
        class Solution {
        public:
            static unsigned missing(vector<int> &nums, int i);
            static int missingElement(vector<int> &nums, int k);
        };
    }// namespace missing_element_in_sorted_array
 
    namespace find_a_peak_element_ii {
        class Solution {
        public:
            static int get(vector<vector<int>> &mat, int i, int j);
            static vector<int> findPeakGridLR(vector<vector<int>> &mat, int l, int r);
            static vector<int> findPeakGrid(vector<vector<int>> &mat);
        };
    }// namespace find_a_peak_element_ii
 
    namespace divide_chocolate {
        class Solution {
        public:
            static int count(vector<int> &sweetness, int x);
            static int maximizeSweetness(vector<int> &sweetness, int k);
        };
    }// namespace divide_chocolate
 
    namespace shortest_distance_to_target_color {
        class Solution {
        public:
            static vector<int> shortestDistanceColor(vector<int> &colors, vector<vector<int>> &queries);
        };
    }// namespace shortest_distance_to_target_color
 
    namespace meeting_scheduler {
        class Solution {
        public:
            static pair<int, int> merge(const vector<int> &vec1, const vector<int> &vec2);
            static vector<int> minAvailableDuration(vector<vector<int>> &slots1, vector<vector<int>> &slots2, int duration);
        };
    }// namespace meeting_scheduler
 
    namespace find_the_duplicate_number {
        class Solution {
        public:
            static int countInRange(vector<int> &nums, int l, int r);
            static int findDuplicate(vector<int> &nums);
        };
    }// namespace find_the_duplicate_number
 
    namespace trapping_rain_water {
        class Solution {
        public:
            static int trap(vector<int> &height);
        };
    }// namespace trapping_rain_water
 
    namespace product_of_two_run_length_encoded_arrays {
        class Solution {
        public:
            static vector<vector<int>> findRLEArray(vector<vector<int>> &encoded1, vector<vector<int>> &encoded2);
        };
    }// namespace product_of_two_run_length_encoded_arrays
 
    namespace longest_substring_with_at_most_two_distinct_characters {
        class Solution {
        public:
            static int getMinUniqueCharCnt(const string &s, int len);
            static int lengthOfLongestSubstringTwoDistinct(const string &s);
        };
    }// namespace longest_substring_with_at_most_two_distinct_characters
 
    namespace longest_substring_with_at_most_k_distinct_characters {
        class Solution {
        public:
            static int lengthOfLongestSubstringKDistinct(const string &s, int k);
        };
    }// namespace longest_substring_with_at_most_k_distinct_characters
 
    namespace max_consecutive_ones_iii {
        class Solution {
        public:
            static int cntMinFlip(vector<int> &nums, int len);
            static int longestOnes(vector<int> &nums, int k);
        };
    }// namespace max_consecutive_ones_iii
 
    namespace sliding_window_maximum {
        class Solution {
        public:
            static vector<int> maxSlidingWindow(vector<int> &nums, int k);
        };
    }// namespace sliding_window_maximum
 
    namespace minimum_window_substring {
        class Solution {
        public:
            static bool valid(unordered_map<char, int> &ums, const unordered_map<char, int> &umt);
            static string minWindow(string s, const string &t);
        };
    }// namespace minimum_window_substring
 
    namespace walls_and_gates {
        class Solution {
        public:
            static void wallsAndGates(vector<vector<int>> &rooms);
        };
    }// namespace walls_and_gates
 
    namespace pacific_atlantic_waterflow {
        struct myhash {
            size_t operator()(const pair<int, int> &p) const;
        };
 
        struct myeq {
            bool operator()(const pair<int, int> &p1, const pair<int, int> &p2) const;
        };
 
        class Solution {
        public:
            static vector<vector<int>> pacificAtlantic(vector<vector<int>> &heights);
        };
    }// namespace pacific_atlantic_waterflow
 
    namespace find_all_the_lonely_nodes {
        class Solution {
        public:
            static vector<int> getLonelyNodes(TreeNode *root);
        };
    }// namespace find_all_the_lonely_nodes
 
    namespace kill_process {
        struct Node {
            int val;
            unordered_set<Node *> children;
 
            explicit Node(int val)
                : val(val) {}
        };
 
        class Solution {
        public:
            static vector<int> killProcess(vector<int> &pid, vector<int> &ppid, int kill);
        };
    }// namespace kill_process
 
    namespace all_nodes_distance_k_in_binary_tree {
        struct Node {
            int val;
            unordered_set<Node *> siblings;
 
            explicit Node(int val)
                : val(val) {}
        };
 
        class Solution {
        public:
            static vector<int> distanceK(TreeNode *root, TreeNode *target, int k);
        };
    }// namespace all_nodes_distance_k_in_binary_tree
 
    namespace open_the_lock {
        class Solution {
        public:
            static int openLock(vector<string> &deadends, const string &target);
        };
    }// namespace open_the_lock
 
    namespace number_of_operations_to_make_network_connected {
        class Solution {
        public:
            static void dfs(int &edge_cnt, int &node_cnt, unordered_set<int> &vis, int node, vector<unordered_set<int>> &g);
            static int makeConnected(int n, vector<vector<int>> &connections);
        };
    }// namespace number_of_operations_to_make_network_connected
 
    namespace minimum_cost_to_make_at_least_one_valid_path_in_a_grid {
        struct Node {
            int x;
            int y;
            unordered_map<Node *, int> siblings;
 
            Node(int x, int y)
                : x(x), y(y) {}
        };
 
        struct mycmp {
            bool operator()(const pair<int, Node *> &p1, const pair<int, Node *> &p2) const;
        };
 
        class Solution {
        public:
            static int minCost(vector<vector<int>> &grid);
        };
    }// namespace minimum_cost_to_make_at_least_one_valid_path_in_a_grid
 
    namespace critical_connections_in_a_network {
        class Solution {
        public:
            static void tarjan(int prev, int &step, vector<int> &dfn, int node, vector<unordered_set<int>> &g, vector<int> &low, vector<vector<int>> &ans);
            static vector<vector<int>> criticalConnections(int n, vector<vector<int>> &connections);
        };
    }// namespace critical_connections_in_a_network
 
    namespace factor_combinations {
        class Solution {
        public:
            static vector<vector<int>> getFactorsWithMin(int n, int minimum);
            static vector<vector<int>> getFactors(int n);
        };
    }// namespace factor_combinations
 
    namespace decode_string {
        class Solution {
        public:
            static string decodeString(string s);
        };
    }// namespace decode_string
 
    namespace n_queens {
        class Solution {
            static void dfs(const vector<vector<bool>> &board, int line, int n, vector<vector<string>> &ans);
            static bool valid(const vector<vector<bool>> &board, int n, int x, int y);
            static vector<string> toStringVec(const vector<vector<bool>> &board);
 
        public:
            static vector<vector<string>> solveNQueens(int n);
        };
    }// namespace n_queens
 
    namespace sudoku_solver {
        class Solution {
            static bool dfs(const vector<vector<char>> &board, vector<vector<char>> &ans);
            static bool valid(const vector<vector<char>> &board, int x, int y, char num);
 
        public:
            static void solveSudoku(vector<vector<char>> &board);
        };
    }// namespace sudoku_solver
 
    namespace regular_expression_matching {
        class Solution {
        public:
            static bool dfs(const string &s, const string &p, int si, int pi);
            static bool isMatch(const string &s, const string &p);
        };
    }// namespace regular_expression_matching
 
    namespace different_ways_to_add_parentheses {
        class Solution {
        public:
            static vector<int> diffWaysToCompute(const string &expression);
            static vector<int> eval(const string &expr, int start, int end);
        };
    }// namespace different_ways_to_add_parentheses
 
    namespace remove_invalid_parentheses {
        class Solution {
        public:
            static bool isValid(const string &str);
            static vector<string> removeInvalidParentheses(const string &s);
        };
    }// namespace remove_invalid_parentheses
 
    namespace median_of_two_sorted_arrays {
        class Solution {
        public:
            static double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2);
        };
    }// namespace median_of_two_sorted_arrays
 
    namespace count_of_smaller_numbers_after_self {
        class Solution {
        private:
            vector<int> c;
            vector<int> a;
            void Init(int length);
            static int LowBit(int x);
            void Update(int pos);
            [[nodiscard]] int Query(int pos) const;
            void Discretization(vector<int> &nums);
            int getId(int x);
 
        public:
            vector<int> countSmaller(vector<int> &nums);
        };
    }// namespace count_of_smaller_numbers_after_self
 
    namespace best_time_to_buy_and_sell_stock_with_cooldown {
        class Solution {
        public:
            static int maxProfit(vector<int> &prices);
        };
    }// namespace best_time_to_buy_and_sell_stock_with_cooldown
 
    namespace best_time_to_buy_and_sell_stock_with_transaction_fee {
        class Solution {
        public:
            static int maxProfit(vector<int> &prices, int fee);
        };
    }// namespace best_time_to_buy_and_sell_stock_with_transaction_fee
 
    namespace split_array_largest_sum {
        class Solution {
        public:
            static int get_m(const vector<int> &nums, int msum);
            static int splitArray(vector<int> &nums, int m);
        };
    }// namespace split_array_largest_sum
 
    namespace house_robber_iii {
        struct myhash {
            size_t operator()(const pair<TreeNode *, bool> &p) const;
        };
 
        struct myeq {
            bool operator()(const pair<TreeNode *, bool> &p1, const pair<TreeNode *, bool> &p2) const;
        };
 
        class Solution {
            unordered_map<pair<TreeNode *, bool>, int, myhash, myeq> um;
 
        public:
            int dfs(bool steal, TreeNode *node);
            int rob(TreeNode *root);
        };
    }// namespace house_robber_iii
 
    namespace maximal_square {
        class Solution {
        public:
            static int maximalSquare(vector<vector<char>> &matrix);
        };
    }// namespace maximal_square
 
    namespace maximal_rectangle {
        class Solution {
        public:
            static int maximalRectangle(vector<vector<char>> &matrix);
        };
    }// namespace maximal_rectangle
 
    namespace predict_the_winner {
        class Solution {
        public:
            static bool PredictTheWinner(vector<int> &nums);
        };
    }// namespace predict_the_winner
 
    namespace palindrome_partitioning {
        class Solution {
        public:
            static bool is_palindromic(const string &s, int start, int end);
            static void dfs(const vector<string> &current, const string &s, vector<vector<string>> &ans, int start, int cursor);
            static vector<vector<string>> partition(const string &s);
        };
    }// namespace palindrome_partitioning
 
    namespace palindrome_partitioning_ii {
        class Solution {
        public:
            static int minCut(string s);
        };
    }// namespace palindrome_partitioning_ii
 
    namespace partition_equal_subset_sum {
        class Solution {
        public:
            static bool canPartition(vector<int> &nums);
        };
    }// namespace partition_equal_subset_sum
 
    namespace minimum_cost_for_tickets {
        class Solution {
        public:
            static int mincostTickets(vector<int> &days, vector<int> &costs);
        };
    }// namespace minimum_cost_for_tickets
 
    namespace best_time_to_buy_and_sell_stock_iii {
        class Solution {
        public:
            static int maxProfit(vector<int> &prices);
        };
    }// namespace best_time_to_buy_and_sell_stock_iii
 
    namespace dungeon_game {
        class Solution {
        public:
            static int calculateMinimumHP(vector<vector<int>> &dungeon);
        };
    }// namespace dungeon_game
 
    namespace course_schedule {
        class Solution {
        public:
            static bool canFinish(int numCourses, vector<vector<int>> &prerequisites);
        };
    }// namespace course_schedule
 
    namespace course_schedule_ii {
        class Solution {
        public:
            static vector<int> findOrder(int numCourses, vector<vector<int>> &prerequisites);
        };
    }// namespace course_schedule_ii
 
    namespace longest_increasing_path_in_a_matrix {
        class Solution {
        public:
            int rows;
            int columns;
            static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            int longestIncreasingPath(vector<vector<int>> &matrix);
        };
    }// namespace longest_increasing_path_in_a_matrix
 
    namespace parallel_courses {
        struct node {
            int n;
            int out;
            int len = 1;
            unordered_set<node *> pred;
 
            node(int n, int out)
                : n(n), out(out) {}
        };
 
        class Solution {
        public:
            static int minimumSemesters(int n, vector<vector<int>> &relations);
        };
    }// namespace parallel_courses
 
    namespace alien_dictionary {
        class Solution {
        public:
            static string alienOrder(vector<string> &words);
        };
    }// namespace alien_dictionary
 
    namespace single_number_iii {
        class Solution {
        public:
            static vector<int> singleNumber(vector<int> &nums);
        };
    }// namespace single_number_iii
 
    namespace shortest_path_to_get_all_keys {
        constexpr char EMPTY = '.';
        constexpr char WALL  = '#';
        constexpr char START = '@';
 
        struct frame {
            int x;
            int y;
            int lock_left;
            int step = 0;
            unordered_set<char> keys;
 
            frame(int x, int y, int lock_left)
                : x(x), y(y), lock_left(lock_left) {}
 
            bool operator<(const frame &f) const;
            [[nodiscard]] unsigned get_mask() const;
        };
 
        class Solution {
        public:
            static int shortestPathAllKeys(vector<string> &grid);
        };
    }// namespace shortest_path_to_get_all_keys
 
    namespace minimum_number_of_k_consecutive_bit_flips {
        class Solution {
        public:
            static int minKBitFlips(vector<int> &nums, int k);
        };
    }// namespace minimum_number_of_k_consecutive_bit_flips
 
    namespace design_underground_system {
        class UndergroundSystem {
            unordered_map<string, unordered_map<string, vector<int>>> um;
            unordered_map<int, pair<string, int>> records;
 
        public:
            UndergroundSystem() = default;
            void checkIn(int id, const string &stationName, int t);
            void checkOut(int id, const string &stationName, int t);
            double getAverageTime(const string &startStation, const string &endStation);
        };
    }// namespace design_underground_system
 
    namespace lru_cache {
        class LRUCache {
            int capacity;
            list<int> keys;
            unordered_map<int, int> um;
 
        public:
            LRUCache(int capacity);
            int get(int key);
            void put(int key, int value);
        };
    }// namespace lru_cache
 
    namespace time_based_key_value_store {
        class TimeMap {
            unordered_map<string, map<int, string, greater<int>>> um;
 
        public:
            TimeMap() = default;
            void set(const string &key, string value, int timestamp);
            // 如果有多个这样的值，则返回对应最大的  timestamp_prev 的那个值。
            // 如果没有值，则返回空字符串（""）。
            string get(const string &key, int timestamp);
        };
    }// namespace time_based_key_value_store
 
    namespace range_module {
        class Chtholly {
            using type = bool;
 
            struct Node {
                unsigned l{}, r{};
                type data{};
 
                Node(unsigned l, unsigned r = 0, type data = false)
                    : l(l), r(r), data(data) {}
 
                bool operator<(const Node &rhs) const { return l < rhs.l; }
            };
 
        public:
            set<Node> s;
 
            auto split(unsigned pos) {
                auto it = s.lower_bound({pos});
                if(it != s.end() && it->l == pos)
                    return it;
                auto [l, r, d]{*--it};
                s.erase(it);
                s.emplace(l, pos - 1, d);
                return s.emplace(pos, r, d).first;
            }
 
            void assign(unsigned l, unsigned r, type val = false) {
                const auto it = split(r + 1);
                s.erase(split(l), it);
                s.emplace(l, r, val);
            }
 
            bool check(unsigned l, unsigned r) {
                const auto it = split(r + 1);
                return std::all_of(split(l), it, [](auto &&n) { return n.data; });
            }
        };
 
        class RangeModule {
            Chtholly tree{{{1, 100000000}}};
 
        public:
            RangeModule() = default;
            void addRange(int left, int right);
            bool queryRange(int left, int right);
            void removeRange(int left, int right);
        };
    }// namespace range_module
 
    namespace lfu_cache {
        class LFUCache {
            unordered_map<int, int> um;
            unordered_map<int, int> cnt;
            map<int, list<int>> tnc;
            int capacity;
 
        public:
            LFUCache(int capacity)
                : capacity(capacity){};
            int get(int key);
            void put(int key, int value);
        };
    }// namespace lfu_cache
 
    namespace leetcode454_4sum_ii {
        class Solution {
            vector<unordered_map<int, int>> mem;
            vector<unordered_map<int, int>> vec;
 
        public:
            int sumCount(int sum, int i);
            int fourSumCount(vector<int> &nums1, vector<int> &nums2, vector<int> &nums3, vector<int> &nums4);
        };
    }// namespace leetcode454_4sum_ii
 
    namespace maximum_size_subarray_sum_equals_k {
        class Solution {
        public:
            static int maxSubArrayLen(vector<int> &nums, int k);
        };
    }// namespace maximum_size_subarray_sum_equals_k
 
    namespace minimum_swaps_to_group_all_1s_together {
        class Solution {
        public:
            static int minSwaps(vector<int> &data);
        };
    }// namespace minimum_swaps_to_group_all_1s_together
}// namespace leetcode
 
#endif//PROBLEMSCPP_LEETCODE_H