C/C++ | LeetCode

Задача: 339. Nested List Weight Sum Сложность: medium Вам дан вложенный список целых чисел nestedList. Каждый элемент либо целое число, либо список, элементы которого также могут быть целыми числами или другими списками. Глубина целого числа — это количество списков, в которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значения каждого целого числа, установленные в его глубину. Верните сумму каждого целого числа в nestedList, умноженного на его глубину. Пример:

Input: nestedList = [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.

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

class Solution {
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        return dfs(nestedList, 1);
    }
    
private:
    int dfs(const vector<NestedInteger>& list, int depth) {
        int total = 0;
        for (const auto& nested : list) {
            if (nested.isInteger()) {
                total += nested.getInteger() * depth;
            } else {
                total += dfs(nested.getList(), depth + 1);
            }
        }
        return total;
    }
};

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

Задача: 937. Reorder Data in Log Files Сложность: medium Вам дается массив журналов. Каждый журнал представляет собой строку слов, ограниченную пробелами, где первое слово является идентификатором. Существует два типа журналов: Буквенные журналы: Все слова (кроме идентификатора) состоят из строчных английских букв. Цифровые журналы: Все слова (кроме идентификатора) состоят из цифр. Упорядочите эти журналы таким образом: буквенные журналы идут перед всеми цифровыми журналами. Буквенные журналы сортируются лексикографически по их содержанию. Если их содержимое одинаково, то отсортируйте их лексикографически по их идентификаторам. Цифровые журналы сохраняют свой относительный порядок. Верните окончательный порядок журналов. Пример:

Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]

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

class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        auto compare = [](const string& log1, const string& log2) {
            int pos1 = log1.find(' '), pos2 = log2.find(' ');
            bool isDigit1 = isdigit(log1[pos1 + 1]), isDigit2 = isdigit(log2[pos2 + 1]);
            
            if (!isDigit1 && !isDigit2) {
                string s1 = log1.substr(pos1 + 1), s2 = log2.substr(pos2 + 1);
                if (s1 != s2) return s1 < s2;
                return log1 < log2;
            }
            return isDigit1 ? false : true;
        };
        stable_sort(logs.begin(), logs.end(), compare);
        return logs;
    }
};

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

Задача: 228. Summary Ranges Сложность: easy Вам дан отсортированный массив уникальных целых чисел nums. Диапазон [a,b] - это множество всех целых чисел от a до b (включительно). Верните наименьший отсортированный список диапазонов, которые покрывают все числа в массиве точно. То есть, каждый элемент nums покрывается ровно одним из диапазонов, и не существует такого целого числа x, чтобы x находился в одном из диапазонов, но не находился в nums. Каждый диапазон [a,b] в списке должен быть представлен в формате: "a->b" если a != b "a" если a == b Пример:

Input: nums = [0,1,2,4,5,7]
Output: ["0->2","4->5","7"]
Explanation: The ranges are:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

👨‍💻 Алгоритм: 1⃣Создайте список строк ranges, который будет содержать решение задачи, и начните итерацию по всем элементам nums с указателем i = 0. Каждая итерация внешнего цикла представляет собой поиск одного диапазона. Для начала сохраните начало текущего диапазона в start = nums[i]. 2⃣Проверьте, отличается ли следующий элемент в nums на индексе i + 1 от nums[i] на 1 или больше. Если следующий элемент отличается на 1, увеличьте i на 1, чтобы включить (i+1)-й элемент в этот диапазон и продолжайте проверку следующего элемента. Продолжайте добавлять элементы в этот диапазон, пока последовательные элементы отличаются на 1, используя цикл while для выполнения этой логики. 3⃣Если следующий элемент отличается более чем на 1 или если все элементы в nums уже обработаны, проверьте, равен ли start значению nums[i]. Если start == nums[i], добавьте только start как строку в ranges, так как у нас есть только один элемент в этом диапазоне. Если start != nums[i], добавьте строку start->nums[i] в ranges. Увеличьте i на 1, чтобы начать новый диапазон. 😎 Решение:

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> ranges;
        for (int i = 0; i < nums.size(); i++) {
            int start = nums[i];
            while (i + 1 < nums.size() && nums[i] + 1 == nums[i + 1]) {
                i++;
            }
            if (start != nums[i]) {
                ranges.push_back(to_string(start) + "->" + to_string(nums[i]));
            } else {
                ranges.push_back(to_string(start));
            }
        }
        return ranges;
    }
};

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

Задача: 1233. Remove Sub-Folders from the Filesystem Сложность: medium Если дан список папок folder, верните папки после удаления всех вложенных папок в этих папках. Вы можете вернуть ответ в любом порядке. Если папка[i] находится внутри другой папки[j], она называется ее вложенной папкой. Формат пути - это одна или несколько скомбинированных строк вида: '/', за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" являются допустимыми путями, а пустая строка и "/" - нет. Пример:

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]

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

class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        sort(folder.begin(), folder.end());
        vector<string> result;
        string parent = "";
        
        for (const string& path : folder) {
            if (parent.empty() || path.find(parent + "/") != 0) {
                parent = path;
                result.push_back(path);
            }
        }
        
        return result;
    }
};

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

Задача: 984. String Without AAA or BBB Сложность: medium Даны два целых числа a и b, верните любую строку s, такую что: s имеет длину a + b и содержит ровно a букв 'a' и ровно b букв 'b'. Подстрока 'aaa' не встречается в s. Подстрока 'bbb' не встречается в s. Пример:

Input: a = 4, b = 1
Output: "aabaa"

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Завести пустую строку s и переменные a_count и b_count для отслеживания оставшихся 'a' и 'b' соответственно. 2⃣Создание строки: Добавляйте символы в строку s, попеременно добавляя 'a' и 'b', чтобы избегать подстрок 'aaa' и 'bbb'. Если в строке подряд уже два символа 'a' и осталось ещё 'b', добавьте 'b' и наоборот. Если оба символа возможны для добавления, выбирайте тот, которого осталось больше. 3⃣Добавление оставшихся символов: После основной логики добавления символов, добавьте оставшиеся 'a' или 'b' в конец строки, если они остались. 😎 Решение:

class Solution {
public:
    string strWithout3a3b(int a, int b) {
        string result;
        
        while (a > 0 || b > 0) {
            if (result.size() >= 2 && result[result.size() - 1] == result[result.size() - 2]) {
                if (result.back() == 'a') {
                    result.push_back('b');
                    b--;
                } else {
                    result.push_back('a');
                    a--;
                }
            } else {
                if (a >= b) {
                    result.push_back('a');
                    a--;
                } else {
                    result.push_back('b');
                    b--;
                }
            }
        }
        
        return result;
    }
};

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

Задача: 477. Total Hamming Distance Сложность: medium Хэммингово расстояние между двумя целыми числами — это количество позиций, в которых соответствующие биты отличаются. Дан целочисленный массив nums, верните сумму Хэмминговых расстояний между всеми парами чисел в nums. Пример:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

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

int totalHammingDistance(vector<int>& nums)
{
    int ans = 0;

    if (nums.empty())
        return ans;

    for (int i = 0; i < nums.size() - 1; i++)
        for (int j = i + 1; j < nums.size(); j++)
            ans += __builtin_popcount(nums[i] ^ nums[j]);

    return ans;
}

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

Задача: 732. My Calendar III Сложность: hard k-бронирование происходит, когда k событий имеют некоторое непустое пересечение (т.е, дано некоторое время, общее для всех k событий). Даны некоторые события [startTime, endTime), после каждого данного события верните целое число k, представляющее максимальное k-бронирование между всеми предыдущими событиями. Реализация класса MyCalendarThree: MyCalendarThree() Инициализирует объект. int book(int startTime, int endTime) Возвращает целое число k, представляющее наибольшее целое число, при котором в календаре существует k-бронирование. Пример:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

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

class MyCalendarThree {
public:
    MyCalendarThree() {}

    int book(int startTime, int endTime) {
        events[startTime]++;
        events[endTime]--;
        
        int active = 0;
        int maxActive = 0;
        for (const auto& [time, count] : events) {
            active += count;
            maxActive = max(maxActive, active);
        }
        
        return maxActive;
    }

private:
    map<int, int> events;
};

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

Задача: 1122. Relative Sort Array Сложность: easy Даны два массива arr1 и arr2, элементы arr2 уникальны, и все элементы arr2 также присутствуют в arr1. Отсортируйте элементы arr1 таким образом, чтобы относительный порядок элементов в arr1 был таким же, как в arr2. Элементы, которые не встречаются в arr2, должны быть размещены в конце arr1 в порядке возрастания. Пример:

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]

👨‍💻 Алгоритм: 1⃣Инициализация и подсчёт: Инициализируйте пустой массив result и массив remaining для хранения оставшихся элементов. Создайте хеш-таблицу countMap для хранения количества вхождений каждого элемента из arr2 в arr1. 2⃣Заполнение countMap и remaining: Пройдитесь по элементам arr1 и если элемент присутствует в countMap, увеличьте его счетчик. Если элемент не присутствует в arr2, добавьте его в remaining. 3⃣Формирование результирующего массива: Пройдитесь по arr2 и добавьте элементы в result в соответствии с их количеством в countMap. Отсортируйте массив remaining и добавьте его элементы в result. Верните result в виде массива. 😎 Решение:

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int, int> countMap;
        vector<int> remaining;
        vector<int> result;

        for (int value : arr2) {
            countMap[value] = 0;
        }

        for (int value : arr1) {
            if (countMap.count(value)) {
                countMap[value]++;
            } else {
                remaining.push_back(value);
            }
        }

        sort(remaining.begin(), remaining.end());

        for (int value : arr2) {
            for (int i = 0; i < countMap[value]; i++) {
                result.push_back(value);
            }
        }

        result.insert(result.end(), remaining.begin(), remaining.end());
        return result;
    }
};

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

Задача: 907. Sum of Subarray Minimums Сложность: medium Учитывая массив целых чисел arr, найдите сумму min(b), где b находится в каждом (смежном) подмассиве arr. Поскольку ответ может быть большим, верните ответ по модулю 109 + 7. Пример:

Input: arr = [3,1,2,4]
Output: 17

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

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        const int MOD = 1e9 + 7;
        int n = arr.size();
        vector<int> left(n), right(n);
        stack<int> st;

        for (int i = 0; i < n; ++i) {
            while (!st.empty() && arr[st.top()] > arr[i]) {
                st.pop();
            }
            left[i] = st.empty() ? i + 1 : i - st.top();
            st.push(i);
        }

        while (!st.empty()) st.pop();

        for (int i = n - 1; i >= 0; --i) {
            while (!st.empty() && arr[st.top()] >= arr[i]) {
                st.pop();
            }
            right[i] = st.empty() ? n - i : st.top() - i;
            st.push(i);
        }

        long long result = 0;
        for (int i = 0; i < n; ++i) {
            result = (result + (long long)arr[i] * left[i] * right[i]) % MOD;
        }

        return result;
    }
};

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

Задача: 507. Perfect Number Сложность: easy Совершенное число — это положительное целое число, которое равно сумме своих положительных делителей, исключая само число. Делитель целого числа x — это целое число, которое может делить x нацело. Дано целое число n, верните true, если n является совершенным числом, в противном случае верните false. Пример:

Input: num = 28
Output: true
Explanation: 28 = 1 + 2 + 4 + 7 + 14
1, 2, 4, 7, and 14 are all divisors of 28.

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

 class Solution {
public:
    bool checkPerfectNumber(int num) {
        if (num <= 0) return false;
        int sum = 0;
        for (int i = 1; i * i <= num; ++i) {
            if (num % i == 0) {
                sum += i;
                if (i * i != num) {
                    sum += num / i;
                }
            }
        }
        return sum - num == num;
    }
};

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

Задача: 229. Majority Element II Сложность: medium Дан массив целых чисел размера n, найдите все элементы, которые встречаются более ⌊ n/3 ⌋ раз. Пример:

Input: nums = [3,2,3]
Output: [3]

👨‍💻 Алгоритм: 1⃣Поиск кандидатов: Пройдите через массив, используя алгоритм Бойера-Мура для поиска двух потенциальных кандидатов, которые могут встречаться более ⌊ n/3 ⌋ раз. Поддерживайте два счётчика и двух кандидатов. Если текущий элемент равен одному из кандидатов, увеличьте соответствующий счётчик. Если счётчик равен нулю, установите текущий элемент как кандидата и установите счётчик в 1. Если текущий элемент не совпадает ни с одним из кандидатов, уменьшите оба счётчика. 2⃣Подсчёт голосов: После определения двух кандидатов, пройдите через массив снова, чтобы посчитать фактическое количество появлений каждого кандидата. 3⃣Проверка порога: Проверьте, превышает ли количество появлений каждого кандидата порог ⌊ n/3 ⌋. Если да, добавьте кандидата в результат. 😎 Решение:

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int count1 = 0, count2 = 0;
        int candidate1 = INT_MIN, candidate2 = INT_MIN;
        
        for (int n : nums) {
            if (candidate1 == n) {
                count1++;
            } else if (candidate2 == n) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = n;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = n;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        
        for (int n : nums) {
            if (candidate1 == n) count1++;
            if (candidate2 == n) count2++;
        }
        
        vector<int> result;
        int n = nums.size();
        if (count1 > n / 3) result.push_back(candidate1);
        if (count2 > n / 3) result.push_back(candidate2);
        
        return result;
    }
};

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

Задача: 956. Tallest Billboard Сложность: hard Вы устанавливаете рекламный щит и хотите, чтобы он имел наибольшую высоту. У рекламного щита будет две стальные опоры, по одной с каждой стороны. Каждая стальная опора должна быть одинаковой высоты. Вам дается набор стержней, которые можно сварить вместе. Например, если у вас есть стержни длиной 1, 2 и 3, вы можете сварить их вместе, чтобы получилась опора длиной 6. Верните наибольшую возможную высоту вашей рекламной установки. Если вы не можете установить рекламный щит, верните 0. Пример:

Input: rods = [1,2,3,6]
Output: 6

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

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int n = strs.size();
        int m = strs[0].length();
        vector<bool> deleteCount(m, false);
        
        auto isSorted = [&]() {
            for (int i = 0; i < n - 1; i++) {
                for (int j = 0; j < m; j++) {
                    if (deleteCount[j]) continue;
                    if (strs[i][j] > strs[i + 1][j]) return false;
                    if (strs[i][j] < strs[i + 1][j]) break;
                }
            }
            return true;
        };
        
        while (!isSorted()) {
            for (int j = 0; j < m; j++) {
                if (deleteCount[j]) continue;
                for (int i = 0; i < n - 1; i++) {
                    if (strs[i][j] > strs[i + 1][j]) {
                        deleteCount[j] = true;
                        break;
                    }
                }
                if (deleteCount[j]) break;
            }
        }
        
        return count(deleteCount.begin(), deleteCount.end(), true);
    }
};

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

Задача: 1099. Two Sum Less Than K Сложность: easy Дан массив целых чисел nums и целое число k. Верните максимальную сумму, такую что существуют i < j, при которых nums[i] + nums[j] = sum и sum < k. Если не существует таких i и j, удовлетворяющих этому условию, верните -1. Пример:

Input: nums = [34,23,1,24,75,33,54,8], k = 60
Output: 58
Explanation: We can use 34 and 24 to sum 58 which is less than 60.

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

class Solution {
public:
    int twoSumLessThanK(vector<int>& nums, int k) {
        int answer = -1;
        int count[1001] = {};
        for (int num : nums) {
            count[num]++;
        }
        int lo = 1;
        int hi = 1000;
        while (lo <= hi) {
            if (lo + hi >= k || count[hi] == 0) {
                hi--;
            } else {
                if (count[lo] > (lo < hi ? 0 : 1)) {
                    answer = max(answer, lo + hi);
                }
                lo++;
            }
        }
        return answer;
    }
};

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

Задача: 101. Symmetric Tree Сложность: easy Дан корень бинарного дерева. Проверьте, является ли это дерево зеркальным отражением самого себя (то есть симметричным относительно своего центра). Пример:

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

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

class Solution {
public:
    bool isSymmetric(TreeNode* root) { return isMirror(root, root); }
    bool isMirror(TreeNode* t1, TreeNode* t2) {
        if (t1 == nullptr && t2 == nullptr) return true;
        if (t1 == nullptr || t2 == nullptr) return false;
        return (t1->val == t2->val) && isMirror(t1->right, t2->left) &&
               isMirror(t1->left, t2->right);
    }
};

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

🔥Стажировки и вакансии для IT специалистов - Вакансии которых нет на джоб-агрегаторах - Только прямые контакты HR в Telegram 🤖 ML & DS 👩‍💻 DevOps 👨‍✈️ ИБ & OSINT 👣 Go 👩‍💻 Mobile 👩‍💻 C# 👩‍💻 Node.js 👩‍💻 Python 🔎 QA 👩‍💻 Java 👩‍💻 UX/UI 👩‍💻 Frontend 🖼️ PHP 📋 Analyst 💼 1C 🖥 SQL 👩‍💻 IT HR Пока другие листают джоб-сайты — ты уже пишешь HR в Telegram.

Задача: 127. Word Ladder Сложность: hard Дано: beginWord, endWord и wordList. Найдите длину кратчайшей цепочки преобразования из beginWord в endWord, где каждое слово отличается ровно одной буквой, и каждое промежуточное слово должно быть в wordList. Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: "hit" → "hot" → "dot" → "dog" → "cog" — цепочка из 5 слов

👨‍💻 Алгоритм: 1⃣Преобразование слов: Для каждого слова из wordList формируем промежуточные состояния, заменяя по одной букве на *. Например, "hot" → "*ot", "h*t", "ho*". Сохраняем в unordered_map<string, vector<string>> allComboDict. 2⃣BFS: Стартуем с beginWord, кладем в очередь (beginWord, 1) — слово и уровень. Храним visited, чтобы не зациклиться. На каждом шаге: генерируем все промежуточные состояния *ot, h*t, ... смотрим в allComboDict, какие слова подходят добавляем их в очередь с level + 1 если встречаем endWord — возвращаем level + 1 3⃣Если очередь опустела, а endWord не найден — возвращаем 0. 😎 Решение:

#include <unordered_map>
#include <vector>
#include <queue>
#include <string>
using namespace std;

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int L = beginWord.size();
        unordered_map<string, vector<string>> allComboDict;

        for (string word : wordList) {
            for (int i = 0; i < L; i++) {
                string newWord = word.substr(0, i) + '*' + word.substr(i + 1);
                allComboDict[newWord].push_back(word);
            }
        }

        queue<pair<string, int>> Q;
        Q.push({beginWord, 1});
        unordered_map<string, bool> visited;
        visited[beginWord] = true;

        while (!Q.empty()) {
            auto [word, level] = Q.front();
            Q.pop();

            for (int i = 0; i < L; i++) {
                string newWord = word.substr(0, i) + '*' + word.substr(i + 1);

                for (string& adjacentWord : allComboDict[newWord]) {
                    if (adjacentWord == endWord) return level + 1;
                    if (!visited[adjacentWord]) {
                        visited[adjacentWord] = true;
                        Q.push({adjacentWord, level + 1});
                    }
                }
            }
        }

        return 0;
    }
};

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

Задача: 897. Increasing Order Search Tree Сложность: easy Задав корень дерева двоичного поиска, перестройте дерево по порядку так, чтобы самый левый узел дерева теперь был корнем дерева, а каждый узел не имел левого и только одного правого дочернего узла. Пример:

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

👨‍💻 Алгоритм: 1⃣Выполнить обход дерева в порядке in-order, чтобы получить список узлов. 2⃣Перестроить дерево, устанавливая каждый узел из списка как правый дочерний элемент предыдущего узла и устанавливая левые дочерние элементы в null. 3⃣Вернуть новый корень дерева (первый элемент списка). 😎 Решение:

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

class Solution {
public:
    TreeNode* increasingBST(TreeNode* root) {
        vector<TreeNode*> nodes;
        
        inorder(root, nodes);
        
        for (int i = 0; i < nodes.size() - 1; ++i) {
            nodes[i]->left = nullptr;
            nodes[i]->right = nodes[i + 1];
        }
        
        nodes.back()->left = nullptr;
        nodes.back()->right = nullptr;
        return nodes.front();
    }
    
    void inorder(TreeNode* node, vector<TreeNode*>& nodes) {
        if (node == nullptr) return;
        inorder(node->left, nodes);
        nodes.push_back(node);
        inorder(node->right, nodes);
    }
};

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

Задача: 641. Design Circular Deque Сложность: medium Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае. Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

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

class MyCircularDeque {
public:
    MyCircularDeque(int k) : deque(k), front(0), rear(0), size(0), capacity(k) {}

    bool insertFront(int value) {
        if (isFull()) return false;
        front = (front - 1 + capacity) % capacity;
        deque[front] = value;
        size++;
        return true;
    }

    bool insertLast(int value) {
        if (isFull()) return false;
        deque[rear] = value;
        rear = (rear + 1) % capacity;
        size++;
        return true;
    }

    bool deleteFront() {
        if (isEmpty()) return false;
        front = (front + 1) % capacity;
        size--;
        return true;
    }

    bool deleteLast() {
        if (isEmpty()) return false;
        rear = (rear - 1 + capacity) % capacity;
        size--;
        return true;
    }

    int getFront() {
        if (isEmpty()) return -1;
        return deque[front];
    }

    int getRear() {
        if (isEmpty()) return -1;
        return deque[(rear - 1 + capacity) % capacity];
    }

    bool isEmpty() {
        return size == 0;
    }

    bool isFull() {
        return size == capacity;
    }

private:
    vector<int> deque;
    int front;
    int rear;
    int size;
    int capacity;
};

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

Задача: 954. Array of Doubled Pairs Сложность: medium Если задан целочисленный массив четной длины arr, верните true, если можно переупорядочить arr так, чтобы arr[2 * i + 1] = 2 * arr[2 * i] для каждого 0 <= i < len(arr) / 2, или false в противном случае. Пример:

Input: arr = [3,1,3,6]
Output: false

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

class Solution {
public:
    bool canReorderDoubled(vector<int>& arr) {
        unordered_map<int, int> count;
        for (int num : arr) {
            count[num]++;
        }
        sort(arr.begin(), arr.end(), [](int a, int b) { return abs(a) < abs(b); });
        for (int num : arr) {
            if (count[num] == 0) continue;
            if (count[2 * num] == 0) return false;
            count[num]--;
            count[2 * num]--;
        }
        return true;
    }
};

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

Задача: 433. Minimum Genetic Mutation Сложность: medium Пример:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

Алгоритм: 1⃣Инициализируем очередь и множество seen. Помещаем в них startGene. Начинаем BFS по возможным мутациям. 2⃣Для каждой строки из очереди проверяем, достигли ли endGene. Если нет, генерируем все возможные односимвольные мутации и добавляем допустимые в очередь. 3⃣Если очередь опустела, а endGene не найден — возвращаем -1. 😎 Решение:

class Solution {
public:
    int minMutation(string start, string end, vector<string>& bank) {
        queue<string> queue;
        unordered_set<string> seen;
        queue.push(start);
        seen.insert(start);
        
        int steps = 0;
        while (!queue.empty()) {
            int nodesInQueue = queue.size();
            
            for (int j = 0; j < nodesInQueue; j++) {
                string node = queue.front();
                queue.pop();

                if (node == end) {
                    return steps;
                }
                
                for (char c: "ACGT") {
                    for (int i = 0; i < node.size(); i++) {
                        string neighbor = node;
                        neighbor[i] = c;
                        if (!seen.count(neighbor) && find(bank.begin(), bank.end(), neighbor) != bank.end()) {
                            queue.push(neighbor);
                            seen.insert(neighbor);
                        }
                    }
                }
            }
            
            steps++;
        }
        
        return -1;
    }
};

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