C/C++ | LeetCode

Задача: 832. Flipping an Image Сложность: easy Дано бинарное изображение размером n x n, необходимо перевернуть изображение по горизонтали, затем инвертировать его и вернуть результат. Перевернуть изображение по горизонтали означает, что каждая строка изображения будет развернута. Например, переворот строки [1,1,0] по горизонтали дает [0,1,1]. Инвертировать изображение означает, что каждый 0 заменяется на 1, а каждый 1 заменяется на 0. Например, инверсия строки [0,1,1] дает [1,0,0]. Пример:

Input: image = [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

👨‍💻 Алгоритм: 1⃣Переверните каждую строку по горизонтали, обменяв элементы слева направо и наоборот. 2⃣Инвертируйте каждую строку, заменив каждый 0 на 1 и каждый 1 на 0. 3⃣Верните преобразованное изображение. 😎 Решение:

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) {
        int C = A[0].size();

        for (auto& row : A) {
            for (int i = 0; i < (C + 1) / 2; ++i) {
                int tmp = row[i] ^ 1;
                row[i] = row[C - 1 - i] ^ 1;
                row[C - 1 - i] = tmp;
            }
        }

        return A;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Где вести задачи и проекты? Конечно, в Битрикс24 Бесплатный онлайн-сервис для бизнеса и совместной работы. Полный комплект для эффективности вашей команды. Ставьте первую задачу прямо сейчас Начать #реклама 16+ task-24.bitrix24.ru О рекламодателе

Задача: 58. Length of Last Word Сложность: easy Дана строка s, состоящая из слов и пробелов. Верните длину последнего слова. Слово — это максимальная подстрока без пробелов. Пример:

Input: s = "Hello World" Output: 5

👨‍💻 Алгоритм: 1⃣Идти с конца строки, пропуская пробелы, чтобы найти конец последнего слова 2⃣Затем считать символы до следующего пробела или начала строки — это и будет длина слова 3⃣Вернуть полученную длину 😎 Решение:

class Solution {
public:
    int lengthOfLastWord(string s) {
        int p = s.length() - 1;
        while (p >= 0 && s[p] == ' ') {
            p--;
        }
        int length = 0;
        while (p >= 0 && s[p] != ' ') {
            p--;
            length++;
        }
        return length;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать

Задача: 1533. Find the Index of the Large Integer Сложность: medium У нас есть целочисленный массив arr, в котором все элементы равны, кроме одного элемента, который больше остальных. Вам не будет предоставлен прямой доступ к массиву, вместо этого у вас будет API ArrayReader, который имеет следующие функции: int compareSub(int l, int r, int x, int y): где 0 <= l, r, x, y < ArrayReader.length(), l <= r и x <= y. Функция сравнивает сумму подмассива arr[l..r] с суммой подмассива arr[x..y] и возвращает: 1, если arr[l] + arr[l+1] + ... + arr[r] > arr[x] + arr[x+1] + ... + arr[y]. 0, если arr[l] + arr[l+1] + ... + arr[r] == arr[x] + arr[x+1] + ... + arr[y]. -1, если arr[l] + arr[l+1] + ... + arr[r] < arr[x] + arr[x+1] + ... + arr[y]. int length(): Возвращает размер массива. Вам разрешено вызывать compareSub() не более 20 раз. Вы можете предположить, что обе функции работают за O(1) время. Верните индекс массива arr, который содержит наибольший элемент. Пример:

Input: arr = [7,7,7,7,10,7,7,7]
Output: 4
Explanation: The following calls to the API
reader.compareSub(0, 0, 1, 1) // returns 0 this is a query comparing the sub-array (0, 0) with the sub array (1, 1), (i.e. compares arr[0] with arr[1]).
Thus we know that arr[0] and arr[1] doesn't contain the largest element.
reader.compareSub(2, 2, 3, 3) // returns 0, we can exclude arr[2] and arr[3].
reader.compareSub(4, 4, 5, 5) // returns 1, thus for sure arr[4] is the largest element in the array.
Notice that we made only 3 calls, so the answer is valid.

👨‍💻 Алгоритм: 1⃣Установите left = 0 и length = reader.length. left - это самый левый индекс нашего поискового пространства, а length - это размер нашего поискового пространства. Индекс большего числа всегда должен находиться в пределах [left, left + length). 2⃣Пока length > 1: — Обновите length до length / 2. — Установите cmp равным reader.compareSub(left, left + length - 1, left + length, left + length + length - 1). — Если cmp равно 0, верните left + length + length, так как оставшийся элемент является большим числом. Это возможно только если текущее поисковое пространство имеет нечетную длину, поэтому если у нас четная длина, мы не беспокоимся об этом случае. — Если cmp равно -1, увеличьте left на length. — Если cmp равно 1, ничего не делайте, так как наш left остается прежним и мы уже разделили length на 2. 3⃣Верните left. Это стандартная процедура для бинарного поиска, когда если поиск завершается без возврата, то левая граница указывает на ответ. 😎 Решение:

class Solution {
public:
    int getIndex(ArrayReader &reader) {
        int left = 0;
        int length = reader.length();
        while (length > 1) {
            length /= 2;
            int cmp = reader.compareSub(left, left + length - 1, left + length, left + 2 * length - 1);
            if (cmp == 0) {
                return left + 2 * length;
            }
            if (cmp < 0) {
                left += length;
            }
        }
        return left;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Онлайн-магистратура с IT специальностями от Яндекса Совместно с ИТМО, МИФИ, МФТИ. Онлайн-магистратура с актуальными программами и гибким графиком обучения. Получите высокооплачиваемую IT профессию, официальный диплом и практические знания. Господдержка оплаты. Совмещение с работой! Подать заявку #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 1143. Longest Common Subsequence Сложность: medium Даны две строки text1 и text2. Верните длину их наибольшей общей подпоследовательности. Если общей подпоследовательности нет, верните 0. Подпоследовательность строки — это новая строка, созданная из оригинальной строки путем удаления некоторых символов (может быть ни одного) без изменения относительного порядка оставшихся символов. Например, "ace" является подпоследовательностью "abcde". Общая подпоследовательность двух строк — это подпоследовательность, которая является общей для обеих строк. Пример:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

👨‍💻 Алгоритм: 1⃣Создайте двумерный массив memo для хранения промежуточных результатов, чтобы избежать повторных вычислений. Инициализируйте массив значением -1, чтобы указать, что эти ячейки еще не были рассчитаны. 2⃣Реализуйте рекурсивную функцию memoSolve, которая принимает два указателя на текущие позиции в text1 и text2 и возвращает длину наибольшей общей подпоследовательности для этих подстрок. Если текущие символы совпадают, добавьте 1 к результату рекурсивного вызова для следующих символов. Если не совпадают, найдите максимум между рекурсивными вызовами с измененными указателями. 3⃣Возвращайте значение memoSolve(0, 0), чтобы получить результат для всей строки. 😎 Решение:

class Solution {
private:
    vector<vector<int>> memo;
    string text1, text2;

public:
    int longestCommonSubsequence(string text1, string text2) {
        this->text1 = text1;
        this->text2 = text2;
        memo = vector<vector<int>>(text1.size() + 1, vector<int>(text2.size() + 1, -1));
        return memoSolve(0, 0);
    }

    int memoSolve(int p1, int p2) {
        if (p1 == text1.size() || p2 == text2.size()) return 0;
        if (memo[p1][p2] != -1) return memo[p1][p2];
        int answer = 0;
        if (text1[p1] == text2[p2]) {
            answer = 1 + memoSolve(p1 + 1, p2 + 1);
        } else {
            answer = max(memoSolve(p1, p2 + 1), memoSolve(p1 + 1, p2));
        }
        memo[p1][p2] = answer;
        return answer;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 325. Maximum Size Subarray Sum Equals k Сложность: medium Дан целочисленный массив nums и целое число k. Верните максимальную длину подмассива, сумма которого равна k. Если такого подмассива не существует, верните 0. Пример:

Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

👨‍💻 Алгоритм: 1⃣Инициализация переменных Инициализируйте prefixSum как 0 для отслеживания префиксной суммы nums. Инициализируйте longestSubarray как 0 для отслеживания самой длинной подмассы с суммой k. Инициализируйте хеш-карту indices для хранения префиксных сумм и их индексов. 2⃣Итерация по массиву На каждом индексе i, добавляйте nums[i] к prefixSum. Проверьте следующие условия: Если prefixSum == k, обновите longestSubarray как i + 1. Если prefixSum - k существует в indices, обновите longestSubarray, если текущая длина подмассива больше. Если текущий prefixSum еще не существует в indices, добавьте indices[prefixSum] = i. 3⃣Возврат результата Верните значение longestSubarray. 😎 Решение:

#include <vector>
#include <unordered_map>

class Solution {
public:
    int maxSubArrayLen(std::vector<int>& nums, int k) {
        int prefixSum = 0;
        int longestSubarray = 0;
        std::unordered_map<int, int> indices;
        
        for (int i = 0; i < nums.size(); ++i) {
            prefixSum += nums[i];
            
            if (prefixSum == k) {
                longestSubarray = i + 1;
            }
            if (indices.find(prefixSum - k) != indices.end()) {
                longestSubarray = std::max(longestSubarray, i - indices[prefixSum - k]);
            }
            if (indices.find(prefixSum) == indices.end()) {
                indices[prefixSum] = i;
            }
        }
        
        return longestSubarray;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1231. Divide Chocolate Сложность: hard У вас есть одна шоколадка, состоящая из нескольких кусочков. Каждый кусочек имеет свою сладость, заданную массивом сладости. Вы хотите поделиться шоколадом со своими k друзьями, поэтому начинаете разрезать шоколадку на k + 1 кусочков с помощью k разрезов, каждый кусочек состоит из нескольких последовательных кусочков. Будучи щедрым, вы съедите кусочек с минимальной общей сладостью, а остальные кусочки отдадите своим друзьям. Найдите максимальную общую сладость кусочка, который вы можете получить, оптимально разрезав шоколадку. Пример:

Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5
Output: 6

👨‍💻 Алгоритм: 1⃣Для решения задачи мы можем использовать метод двоичного поиска для определения максимальной минимальной сладости, которую можно получить. 2⃣Двоичный поиск: Мы будем искать ответ в диапазоне от минимальной сладости до суммы всех сладостей. Начнем с середины этого диапазона и проверим, можно ли разрезать шоколад таким образом, чтобы минимальная сладость была не менее этого значения. 3⃣Проверка делимости: Для каждой попытки значения сладости в двоичном поиске проверим, можем ли мы разрезать шоколад так, чтобы каждая из k+1 частей имела сладость не меньше текущего значения. 😎 Решение:

class Solution {
public:
    int maximizeSweetness(vector<int>& sweetness, int k) {
        auto canDivide = [&](int minSweetness) {
            int current_sum = 0, cuts = 0;
            for (int sweet : sweetness) {
                current_sum += sweet;
                if (current_sum >= minSweetness) {
                    cuts++;
                    current_sum = 0;
                }
            }
            return cuts >= k + 1;
        };
        
        int left = *min_element(sweetness.begin(), sweetness.end());
        int right = accumulate(sweetness.begin(), sweetness.end(), 0) / (k + 1);
        
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (canDivide(mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 55. Jump Game Сложность: medium Дан массив nums, где каждый элемент nums[i] — максимальная длина прыжка из позиции i. Верните true, если можно добраться до последнего индекса, иначе — false. Пример:

Input: nums = [2,3,1,1,4] Output: true

👨‍💻 Алгоритм: 1⃣Инициализируем таблицу memo, где каждый индекс может быть в состоянии UNKNOWN, GOOD или BAD Последний индекс всегда GOOD, т.к. он сам к себе уже достигнут 2⃣Для каждого индекса рекурсивно проверяем: Если индекс уже помечен как GOOD или BAD, сразу возвращаем результат Иначе, пробуем прыгнуть на все возможные позиции из текущей Если хотя бы один путь ведёт в GOOD, текущая позиция также GOOD 3⃣Сохраняем результат в memo, чтобы не проверять повторно 😎 Решение:

enum Index { GOOD, BAD, UNKNOWN };

class Solution {
public:
    vector<Index> memo;

    bool canJumpFromPosition(int position, vector<int>& nums) {
        if (memo[position] != UNKNOWN) {
            return memo[position] == GOOD;
        }

        int furthestJump = min(position + nums[position], (int)nums.size() - 1);
        for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
            if (canJumpFromPosition(nextPosition, nums)) {
                memo[position] = GOOD;
                return true;
            }
        }

        memo[position] = BAD;
        return false;
    }

    bool canJump(vector<int>& nums) {
        memo = vector<Index>(nums.size(), UNKNOWN);
        memo[memo.size() - 1] = GOOD;
        return canJumpFromPosition(0, nums);
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Высшее образование дистанционно в Московском ВУЗе Вы мечтаете получить высшее образование, но не сдали ЕГЭ или получили низкие баллы? У нас есть решение для вас! Институт Международных Экономических Связей предлагает дистанционное обучение , которое позволяет получать качественные знания из любой точки мира по 10+ направлениям обучения. ✅ Государственный диплом без отметки о дистанте ✅ Удобный личный кабинет студента ✅ Поддержка кураторов на каждом этапе обучения ✅ Можно поступить без ЕГЭ Узнать больше #реклама 16+ imes.su О рекламодателе

Задача: 1180. Count Substrings with Only One Distinct Letter Сложность: easy Дана строка s. Верните количество подстрок, которые содержат только одну уникальную букву. Пример:

Input: s = "aaaba"
Output: 8
Explanation: The substrings with one distinct letter are "aaa", "aa", "a", "b".
"aaa" occurs 1 time.
"aa" occurs 2 times.
"a" occurs 4 times.
"b" occurs 1 time.
So the answer is 1 + 2 + 4 + 1 = 8.

👨‍💻 Алгоритм: 1⃣Инициализируйте целочисленную переменную total для подсчета количества подстрок, а также два указателя left и right, которые отмечают начало и конец подстроки, содержащей только одну уникальную букву. 2⃣Итерируйте по строке S: Если мы не достигли конца и новый символ S[right] такой же, как и начальный символ S[left], увеличьте right на 1 для дальнейшего исследования строки S; в противном случае вычислите длину подстроки как right - left и примените формулу суммы арифметической последовательности; не забудьте установить right в left для начала исследования новой подстроки. 3⃣После завершения итерации добавьте к total количество подстрок для последнего сегмента, если он не был учтен. Верните значение total. 😎 Решение:

class Solution {
public:
    int countLetters(string S) {
        int total = 0;
        int left = 0;

        for (int right = 0; right <= S.size(); right++) {
            if (right == S.size() || S[left] != S[right]) {
                int lenSubstring = right - left;
                total += (1 + lenSubstring) * lenSubstring / 2;
                left = right;
            }
        }
        return total;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1312. Minimum Insertion Steps to Make a String Palindrome Сложность: hard Дана строка s. За один шаг вы можете вставить любой символ в любой индекс строки. Верните минимальное количество шагов, необходимых для превращения s в палиндром. Палиндром — это строка, которая читается одинаково как вперед, так и назад. Пример:

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we do not need any insertions.

👨‍💻 Алгоритм: 1⃣Создайте целочисленную переменную n и инициализируйте её размером строки s. Создайте строковую переменную sReverse и установите её значение как обратную строку s. 2⃣Создайте двумерный массив memo размером n + 1 на n + 1, где memo[i][j] будет содержать длину наибольшей общей подпоследовательности, учитывая первые i символов строки s и первые j символов строки sReverse. Инициализируйте массив значением -1. 3⃣Верните n - lcs(s, sReverse, n, n, memo), где lcs - это рекурсивный метод с четырьмя параметрами: первая строка s1, вторая строка s2, длина подстроки от начала s1, длина подстроки от начала s2 и memo. Метод возвращает длину наибольшей общей подпоследовательности в подстроках s1 и s2. В этом методе выполните следующее: Если m == 0 или n == 0, это означает, что одна из двух подстрок пуста, поэтому верните 0. Если memo[m][n] != -1, это означает, что мы уже решили эту подзадачу, поэтому верните memo[m][n]. Если последние символы подстрок совпадают, добавьте 1 и найдите длину наибольшей общей подпоследовательности, исключив последний символ обеих подстрок. Верните memo[i][j] = 1 + lcs(s1, s2, m - 1, n - 1, memo). В противном случае, если последние символы не совпадают, рекурсивно найдите наибольшую общую подпоследовательность в обеих подстроках, исключив их последние символы по одному. Верните memo[i][j] = max(lcs(s1, s2, m - 1, n, memo), lcs(s1, s2, m, n - 1, memo)). 😎 Решение:

class Solution {
    int lcs(const string& s1, const string& s2, int m, int n, vector<vector<int>>& memo) {
        if (m == 0 || n == 0) {
            return 0;
        }
        if (memo[m][n] != -1) {
            return memo[m][n];
        }
        if (s1[m - 1] == s2[n - 1]) {
            return memo[m][n] = 1 + lcs(s1, s2, m - 1, n - 1, memo);
        }
        return memo[m][n] = max(lcs(s1, s2, m - 1, n, memo), lcs(s1, s2, m, n - 1, memo));
    }

public:
    int minInsertions(string s) {
        int n = s.size();
        string sReverse(s.rbegin(), s.rend());
        vector<vector<int>> memo(n + 1, vector<int>(n + 1, -1));
        return n - lcs(s, sReverse, n, n, memo);
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1019. Next Greater Node In Linked List Сложность: medium Вам дана голова связного списка с n узлами. Для каждого узла в списке найдите значение следующего большего узла. То есть для каждого узла найдите значение первого узла, который находится рядом с ним и имеет строго большее значение, чем он. Верните целочисленный массив answer, где answer[i] - это значение следующего большего узла ith-узла (с индексацией по 1). Если у узла ith нет следующего большего узла, установите answer[i] = 0. Пример:

Input: head = [2,1,5]
Output: [5,5,0]

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Пройдитесь по всему списку и сохраните значения узлов в массив. Инициализируйте стек для хранения индексов узлов, которые нужно обработать. 2⃣Поиск следующего большего элемента: Итерируйте по массиву значений узлов. Для каждого элемента, пока стек не пуст и текущий элемент больше, чем элемент на вершине стека, обновите массив ответов значением текущего элемента и удалите элемент из стека. Добавьте текущий индекс в стек. 3⃣Заполнение оставшихся значений: Для всех индексов, оставшихся в стеке, установите значение ответа равным 0, так как для них не найдено большего элемента. 😎 Решение:

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        vector<int> values;
        while (head) {
            values.push_back(head->val);
            head = head->next;
        }
        
        vector<int> answer(values.size(), 0);
        stack<int> s;
        
        for (int i = 0; i < values.size(); ++i) {
            while (!s.empty() && values[s.top()] < values[i]) {
                answer[s.top()] = values[i];
                s.pop();
            }
            s.push(i);
        }
        
        return answer;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 639. Decode Ways II Сложность: hard Сообщение, содержащее буквы от A-Z, может быть закодировано в цифры с помощью следующего отображения: 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" Чтобы декодировать закодированное сообщение, все цифры должны быть сгруппированы, а затем снова преобразованы в буквы с помощью обратного отображения (может быть несколько способов). Например, "11106" может быть преобразовано в: "AAJF" с группировкой (1 1 10 6) "KJF" с группировкой (11 10 6) Обратите внимание, что группировка (1 11 06) недействительна, поскольку "06" не может быть преобразовано в "F", так как "6" отличается от "06". В дополнение к вышеуказанным преобразованиям кодированное сообщение может содержать символ "*", который может представлять любую цифру от "1" до "9" ("0" исключается). Например, кодированное сообщение "1*" может представлять любое из кодированных сообщений "11", "12", "13", "14", "15", "16", "17", "18" или "19". Декодирование "1*" эквивалентно декодированию любого из кодированных сообщений, которые оно может представлять. Если задана строка s, состоящая из цифр и символов '*', верните количество способов ее декодирования. Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Пример:

Input: s = "*"
Output: 9

👨‍💻 Алгоритм: 1⃣Инициализация: Создайте массив dp, где dp[i] представляет количество способов декодирования подстроки s[0:i]. Установите начальные значения dp[0] = 1 (пустая строка имеет один способ декодирования). 2⃣Обход строки: Используйте цикл для обхода строки и вычисления количества способов декодирования для каждого символа, включая обработку символа '*'. 3⃣Модульное вычисление: Поскольку количество способов декодирования может быть большим, вычисляйте результаты по модулю 10^9 + 7. 😎 Решение:

class Solution {
public:
    int numDecodings(string s) {
        const int MOD = 1000000007;
        int n = s.size();
        vector<long> dp(n + 1, 0);
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            if (s[i - 1] == '*') {
                dp[i] = 9 * dp[i - 1];
            } else if (s[i - 1] != '0') {
                dp[i] = dp[i - 1];
            }

            if (i > 1) {
                if (s[i - 2] == '*') {
                    if (s[i - 1] == '*') {
                        dp[i] += 15 * dp[i - 2];
                    } else if (s[i - 1] <= '6') {
                        dp[i] += 2 * dp[i - 2];
                    } else {
                        dp[i] += dp[i - 2];
                    }
                } else if (s[i - 2] == '1') {
                    if (s[i - 1] == '*') {
                        dp[i] += 9 * dp[i - 2];
                    } else {
                        dp[i] += dp[i - 2];
                    }
                } else if (s[i - 2] == '2') {
                    if (s[i - 1] == '*') {
                        dp[i] += 6 * dp[i - 2];
                    } else if (s[i - 1] <= '6') {
                        dp[i] += dp[i - 2];
                    }
                }
            }

            dp[i] %= MOD;
        }

        return dp[n];
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 439. Ternary Expression Parser Сложность: medium Дана строка expression, представляющая произвольно вложенные тернарные выражения, вычислите это выражение и верните его результат. Можно всегда считать, что данное выражение является корректным и содержит только цифры, '?', ':', 'T' и 'F', где 'T' означает истину, а 'F' - ложь. Все числа в выражении являются однозначными числами (т.е. в диапазоне от 0 до 9). Условные выражения группируются справа налево (как обычно в большинстве языков), и результат выражения всегда будет либо цифрой, либо 'T', либо 'F'. Пример:

Input: expression = "T?2:3"
Output: "2"
Explanation: If true, then result is 2; otherwise result is 3.

👨‍💻 Алгоритм: 1⃣Определите вспомогательную функцию isValidAtomic(s), которая принимает строку s и возвращает True, если s является допустимым атомарным выражением. В противном случае функция возвращает False. Функция будет вызываться только с пятисимвольными строками. Если все следующие условия выполнены, функция возвращает True, иначе - False: s[0] является T или F. s[1] является ?. s[2] является T, F или цифрой от 0 до 9. s[3] является :. s[4] является T, F или цифрой от 0 до 9. 2⃣Определите вспомогательную функцию solveAtomic(s), которая принимает строку s и возвращает значение атомарного выражения. Значение атомарного выражения равно E1, если B - это T, иначе значение равно E2. Функция будет вызываться только с пятисимвольными строками и возвращать один символ:. 3⃣Если s[0] является T, функция возвращает s[2], иначе возвращает s[4]. В функции parseTernary(expression) уменьшайте выражение до тех пор, пока не останется односимвольная строка. Инициализируйте j как expression.size() - 1 (это будет самый правый индекс окна). Пока самое правое окно длиной 5 не является допустимым атомарным выражением, уменьшайте j на 1. Когда будет найдено самое правое допустимое атомарное выражение, решите его и уменьшите до одного символа. Замените самое правое допустимое атомарное выражение одним символом, после чего длина выражения уменьшится на 4. В итоге останется односимвольная строка, которую и верните. 😎 Решение:

class Solution {
public:
    string parseTernary(string expression) {
        auto isValidAtomic = [](const string& s) {
            return (s[0] == 'T' || s[0] == 'F') &&
                   s[1] == '?' &&
                   (s[2] == 'T' || s[2] == 'F' || isdigit(s[2])) &&
                   s[3] == ':' &&
                   (s[4] == 'T' || s[4] == 'F' || isdigit(s[4]));
        };

        auto solveAtomic = [](const string& s) {
            return s[0] == 'T' ? s[2] : s[4];
        };

        while (expression.size() != 1) {
            int j = expression.size() - 1;
            while (!isValidAtomic(expression.substr(j-4, 5))) {
                j -= 1;
            }
            expression = expression.substr(0, j-4) + solveAtomic(expression.substr(j-4, 5)) + expression.substr(j+1);
        }

        return expression;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 652. Find Duplicate Subtrees Сложность: medium Если задан корень бинарного дерева, верните все дублирующие поддеревья. Для каждого вида дублирующих поддеревьев достаточно вернуть корневой узел любого из них. Два дерева являются дублирующими, если они имеют одинаковую структуру с одинаковыми значениями узлов. Пример:

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

👨‍💻 Алгоритм: 1⃣Выполните обход дерева и используйте сериализацию для представления каждого поддерева. 2⃣Храните все сериализованные представления поддеревьев в хэш-таблице и отслеживайте частоту их появления. 3⃣Найдите поддеревья, которые появляются более одного раза, и верните корневые узлы этих поддеревьев. 😎 Решение:

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        unordered_map<string, int> count;
        vector<TreeNode*> result;
        serialize(root, count, result);
        return result;
    }

private:
    string serialize(TreeNode* node, unordered_map<string, int>& count, vector<TreeNode*>& result) {
        if (!node) return "#";
        string serial = to_string(node->val) + "," + serialize(node->left, count, result) + "," + serialize(node->right, count, result);
        if (++count[serial] == 2) {
            result.push_back(node);
        }
        return serial;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1257. Smallest Common Region Сложность: medium Вам даны списки регионов, в которых первый регион каждого списка включает все остальные регионы этого списка. Естественно, если регион x содержит другой регион y, то x больше y. Также, по определению, регион x содержит сам себя. Даны два региона: region1 и region2, верните наименьший регион, который содержит их оба. Если вам даны регионы r1, r2 и r3 такие, что r1 включает r3, то гарантированно не существует r2 такого, что r2 включает r3. Гарантированно существует наименьший регион. Пример:

Input:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
Output: "North America"

👨‍💻 Алгоритм: 1⃣Построим дерево регионов, где каждый регион указывает на своего родителя. 2⃣Используя родительскую информацию, найдем путь от каждого региона до корня. 3⃣Найдем последний общий регион в путях двух заданных регионов. 😎 Решение:

class Solution {
public:
    string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
        unordered_map<string, string> parent;

        for (const auto& regionList : regions) {
            for (int i = 1; i < regionList.size(); i++) {
                parent[regionList[i]] = regionList[0];
            }
        }

        unordered_set<string> ancestors1;
        while (region1 != "") {
            ancestors1.insert(region1);
            region1 = parent[region1];
        }

        while (ancestors1.find(region2) == ancestors1.end()) {
            region2 = parent[region2];
        }

        return region2;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

👨‍💻Ищем разработчиков, DevOps, QA, аналитиков. Релокейт, удалёнка, платим много! Специально для Вас, собираем лучшие вакансии. Только вакансии с прямыми контактами в Telegram! 👩‍💻 Python 👣 GoLang 🤖 ML & DS 👩‍💻 Java 🖼️ PHP 👩‍💻 Node.js 👩‍💻 Frontend 👩‍💻 C# 🖥 SQL 🔎 QA 👩‍💻 DevOps 👩‍💻 UX/UI 👩‍💻 Mobile Dev 👩‍💻 Analyst 💼 1C Dev Подпишись чтобы не упустить свой шанс получить лучший оффер!

📺 Уникальная база IT собеседований 456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!