Untitled
unknown
plain_text
2 years ago
3.4 kB
42
Indexable
/* Написать метод, который заменит все пробелы в строке на "%20" inplace. На вход подается строка с зарезервированными под расширение символами (гарантируется, что resize до разумных размеров не будет аллоцировать память). ,*/ void urlify(std::string& s){ if (s.empty()){ return; } size_t spaces = 0; for (auto c: s){ if (c == ' '){ ++spaces; } } size_t size = s.size(); s.resize(s.size() + 2 * spaces); for (size_t i = size - 1; i >= 0; --i){ if (i == 0){ if (s[i] == ' '){ s[i] = '%'; s[i + 1] = '2'; s[i + 2] = '0'; } break; } if (s[i] == ' '){ s[i] = '%'; s[i + 1] = '2'; s[i + 2] = '0'; --spaces; if (spaces == 0){ return; } } else { s[i + spaces * 2] = s[i]; } } } std::string s0 = "my url"; std::string s0 = "my%20url"; s0.reserve(20); urlify(s0); assert(s0 == "my%20url"); /* Дано бинарное дерево с выделенным корнем, в каждой вершине которого записано по одной букве A-Z. Две вершины считаются эквивалентными, если поддеревья этих вершин содержат одинаковое множество (т.е. без учета частот) букв. В примере ниже эквивалентными являются вершины B и C -- прямые потомки корня А (Плюсами помечены эквивалентные вершины): A / \ C+ B+ / \ / \ A D A D / \ B C A / \ X+ B+ / \ / \ F D F D / \ B+ B+ \ B A / \ X+ B+ / \ F D \ B+ \ B */ struct TNode { char Value = '\0'; // [A-Z] TNode* Left = nullptr; TNode* Right = nullptr; }; std::pair<TNode*, TNode*> FindEquivalentSubtrees(TNode* root){ if (root == nullptr){ return {nullptr, nullptr}; } std::unordered_map<unsigned int, TNode*> sets; std::pair<TNode*, TNode*> answer; auto ret_val = recursive(root, sets, answer); return answer; } unsigned int recursive(TNode *root, std::unorded_map<unsigned int, TNode*> &sets, std::pair<TNode*, TNode*> &answer){ if (answer.first != nullptr){ return 0; } if (root == nullptr){ return 0; } unsigned int curSet = 1 << (root->Value - 'A'); unsigned int leftSet = recursive(root->Left, sets, answer); unsigned int rightSet = recursive(root->Right, sets, answer); curSet = curSet | leftSet | rightSet; if (sets.contains(curSet)){ answer.first = root; answer.second = sets[curSet]; } else{ sets[curSet] = root; } return curSet; }
Editor is loading...