#hard
Задача: 745. Prefix and Suffix Search

Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

👨‍💻 Алгоритм:

1⃣Сохраните слова и их индексы в словаре.

2⃣Создайте объединенные ключи, состоящие из префиксов и суффиксов для всех возможных комбинаций.

3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу.

😎 Решение:

class WordFilter {
public:
    WordFilter(vector<string>& words) {
        for (int index = 0; index < words.size(); ++index) {
            string word = words[index];
            int length = word.length();
            for (int prefixLength = 1; prefixLength <= length; ++prefixLength) {
                for (int suffixLength = 1; suffixLength <= length; ++suffixLength) {
                    string prefix = word.substr(0, prefixLength);
                    string suffix = word.substr(length - suffixLength);
                    string key = prefix + "#" + suffix;
                    prefixSuffixMap[key] = index;
                }
            }
        }
    }
    
    int f(string pref, string suff) {
        string key = pref + "#" + suff;
        return prefixSuffixMap.count(key) ? prefixSuffixMap[key] : -1;
    }

private:
    unordered_map<string, int> prefixSuffixMap;
};

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

#easy
Задача: 746. Min Cost Climbing Stairs

Вам дан целочисленный массив cost, где cost[i] - стоимость i-й ступеньки на лестнице. После оплаты стоимости вы можете подняться на одну или две ступеньки. Вы можете начать со ступеньки с индексом 0 или со ступеньки с индексом 1. Верните минимальную стоимость достижения вершины этажа.

Пример:

Input: cost = [10,15,20]
Output: 15

👨‍💻 Алгоритм:

1⃣Создать массив dp, где dp[i] хранит минимальную стоимость достижения i-й ступеньки.

2⃣Инициализировать dp[0] и dp[1] как cost[0] и cost[1] соответственно. Заполнить dp используя минимальную стоимость подъема с предыдущих ступенек.

3⃣Вернуть минимальную стоимость достижения вершины.

😎 Решение:

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        vector<int> dp = cost;
        for (int i = 2; i < n; i++) {
            dp[i] += min(dp[i - 1], dp[i - 2]);
        }
        return min(dp[n - 1], dp[n - 2]);
    }
};

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

#easy
Задача: 748. Shortest Completing Word

Вам дан целочисленный массив nums, в котором наибольшее целое число уникально. Определите, является ли наибольший элемент массива по крайней мере в два раза больше всех остальных чисел в массиве. Если да, то верните индекс самого большого элемента, в противном случае верните -1.

Пример:

Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"

👨‍💻 Алгоритм:

1⃣Извлечь все буквы из licensePlate, игнорируя цифры и пробелы, и создать словарь для подсчета частоты каждой буквы.

2⃣Пройти по массиву words, проверяя каждое слово на соответствие требованиям.

3⃣Найти самое короткое завершающее слово среди подходящих.

😎 Решение:

class Solution {
public:
    string shortestCompletingWord(string licensePlate, vector<string>& words) {
        unordered_map<char, int> licenseCount = getCharCount(licensePlate);
        
        string result;
        for (const string& word : words) {
            if (isCompletingWord(word, licenseCount)) {
                if (result.empty() || word.length() < result.length()) {
                    result = word;
                }
            }
        }
        return result;
    }
    
private:
    unordered_map<char, int> getCharCount(const string& s) {
        unordered_map<char, int> count;
        for (char c : s) {
            if (isalpha(c)) {
                count[tolower(c)]++;
            }
        }
        return count;
    }
    
    bool isCompletingWord(const string& word, const unordered_map<char, int>& licenseCount) {
        unordered_map<char, int> wordCount;
        for (char c : word) {
            wordCount[c]++;
        }
        for (const auto& entry : licenseCount) {
            if (wordCount[entry.first] < entry.second) {
                return false;
            }
        }
        return true;
    }
};

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

#hard
Задача: 1402. Reducing Dishes

Шеф-повар собрал данные об уровне удовлетворенности от своих n блюд. Шеф может приготовить любое блюдо за 1 единицу времени.

Коэффициент удовольствия от блюда определяется как время, затраченное на приготовление этого блюда вместе с предыдущими блюдами, умноженное на уровень удовлетворенности от этого блюда, то есть time[i] * satisfaction[i].

Верните максимальную сумму коэффициентов удовольствия, которую шеф-повар может получить после приготовления некоторого количества блюд.

Блюда можно готовить в любом порядке, и шеф может отказаться от некоторых блюд, чтобы достичь максимального значения.

Пример:

Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.

👨‍💻 Алгоритм:

1⃣Отсортируйте массив satisfaction в порядке возрастания.

2⃣Создайте таблицу мемоизации memo размером N x N и инициализируйте все значения -1, что будет означать, что ответ для всех состояний еще не рассчитан.

3⃣Реализуйте функцию, которая вызывается с параметрами index = 0 и time = 1, чтобы найти ответ: Если достигнут конец массива, т.е. index == satisfaction.length, верните 0, так как больше нет блюд для приготовления и нельзя получить дополнительное значение. Если значение в массиве memo для пары {index, time} не равно -1, верните это значение, так как это подразумевает, что данная подзадача уже была решена; поэтому рекурсивный вызов не требуется, и можно вернуть сохраненное значение из таблицы memo. Рассчитайте максимум из двух вариантов: добавьте значение коэффициента для данного блюда satisfaction[index] * time к рекурсивному результату с index = index + 1 и time = time + 1. Пропустите текущее блюдо и сделайте рекурсивный вызов для index = index + 1 и time = time.

😎 Решение:

class Solution {
public:
    int findMaxSatisfaction(vector<int>& satisfaction, vector<vector<int>>& memo, int index, int time) {
        if (index == satisfaction.size()) return 0;
        if (memo[index][time] != -1) return memo[index][time];

        return memo[index][time] = max(satisfaction[index] * time + findMaxSatisfaction(satisfaction, memo, index + 1, time + 1),
                                       findMaxSatisfaction(satisfaction, memo, index + 1, time));
    }

    int maxSatisfaction(vector<int>& satisfaction) {
        sort(satisfaction.begin(), satisfaction.end());
        vector<vector<int>> memo(satisfaction.size() + 1, vector<int>(satisfaction.size() + 1, -1));
        return findMaxSatisfaction(satisfaction, memo, 0, 1);
    }
};

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

#medium
Задача: 1404. Number of Steps to Reduce a Number in Binary Representation to One

Дано бинарное представление целого числа в виде строки s. Верните количество шагов, необходимых для его сокращения до 1 по следующим правилам:
Если текущее число четное, его нужно разделить на 2.
Если текущее число нечетное, нужно прибавить к нему 1.
Гарантируется, что для всех тестовых случаев всегда можно достичь единицы.

Пример:

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.  

👨‍💻 Алгоритм:

1⃣Инициализируйте переменную operations значением 0.

2⃣Повторяйте операции, пока длина строки s больше 1: Если последний бит строки s равен 0, это означает, что число четное; примените операцию деления на 2, удалив последний бит. В противном случае это означает, что число, представленное строкой, нечетное; добавьте 1 к числу, изменив строку, чтобы выполнить эту операцию.

3⃣Верните количество операций.

😎 Решение:

class Solution {
public:
    int numSteps(string s) {
        int operations = 0;
        while (s.size() > 1) {
            if (s.back() == '0') {
                s.pop_back();
            } else {
                int i = s.size() - 1;
                while (i >= 0 && s[i] == '1') {
                    s[i] = '0';
                    i--;
                }
                if (i < 0) {
                    s.insert(s.begin(), '1');
                } else {
                    s[i] = '1';
                }
            }
            operations++;
        }
        return operations;
    }
};

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

#medium
Задача: 750. Number Of Corner Rectangles

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

Input: grid = [[1,0,0,1,0],[0,0,1,0,1],[0,0,0,1,0],[1,0,1,0,1]]
Output: 1

👨‍💻 Алгоритм:

1⃣Пройдите по строкам матрицы. Для каждой пары строк, найдите все столбцы, где оба значения равны 1.

2⃣Подсчитайте количество таких столбцов. Если их больше одного, то они образуют прямоугольники.

3⃣Для каждой пары строк добавьте количество возможных прямоугольников в общий счетчик.

😎 Решение:

class Solution {
public:
    int countCornerRectangles(vector<vector<int>>& grid) {
        int count = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = i + 1; j < grid.size(); j++) {
                int numPairs = 0;
                for (int k = 0; k < grid[0].size(); k++) {
                    if (grid[i][k] == 1 && grid[j][k] == 1) {
                        numPairs++;
                    }
                }
                if (numPairs > 1) {
                    count += numPairs * (numPairs - 1) / 2;
                }
            }
        }
        return count;
    }
};

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

На easyoffer 2.0 появится:
🎯 Тренажер "Проработка вопросов"

✅ Метод интервальных повторений и флеш-карточки
✅ Персональный подход изучения на основе ваших ответов
✅ Упор на самые частые вопросы

📌 Интервальные повторения по карточкам это научно доказанный метод эффективного обучения. Каждая карточка – это вопрос, который задают на собеседовании, вы можете выбрать "Не знаю", "Знаю", "Не спрашивать". После ответа вам показывается правильный ответ и возможность изучить вопрос подробнее (примеры ответов других людей). От ваших ответов зависит то, как часто карточки будут показываться на следующей тренировке. Трудные вопросы показываются чаще, простые – реже. Это позволяет бить в слабые места. Кроме того, изначальный порядок карточек зависит от частотности (вероятности встретить вопрос).

🚀 Благодаря этому тренажеру вы сможете очень быстро подготовиться к собеседованию, т.к. фокусируетесь отвечать на самые частые вопросы. Именно так готовился я сам, когда искал первую работу программистом.

Уже в течение недели я объявлю о старте краудфандинговой кампании на сбор финансирования, чтобы ускорить разработку сайта. Все кто поддержит проект до официального релиза получат самые выгодные условия пользования сервисом. А именно 1 год доступа к сайту по цене месячной подписки.

‼️ Очень важно, чтобы как можно больше людей поддержали проект в первые дни, по-этому те кто окажет поддержку первыми получат еще более выгодную стоимость на годовую подписку и существенный 💎 бонус о котором я позже расскажу в этом телеграм канале. Подписывайтесь, чтобы узнать о старте проекта раньше других и воспользоваться лимитированными вознаграждениями.

#medium
Задача: 751. IP to CIDR

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

Input: ip = "255.0.0.7", n = 10
Output: ["255.0.0.7/32","255.0.0.8/29","255.0.0.16/32"]

👨‍💻 Алгоритм:

1⃣Преобразовать начальный IP-адрес в целое число.

2⃣Пока количество оставшихся IP-адресов n больше нуля: Определить наибольший блок, который начинается с текущего IP-адреса и не превышает количество оставшихся IP-адресов. Добавить этот блок к результату. Увеличить текущий IP-адрес на размер блока. Уменьшить количество оставшихся IP-адресов n.

3⃣Преобразовать блоки обратно в формат CIDR и вернуть их.

😎 Решение:

class Solution {
public:
    vector<string> findCidrBlocks(string startIp, int n) {
        int start = ipToInt(startIp);
        vector<string> result;
        
        while (n > 0) {
            int maxSize = 1;
            while (maxSize <= start && maxSize <= n) {
                maxSize <<= 1;
            }
            maxSize >>= 1;
            
            while (start % maxSize != 0) {
                maxSize >>= 1;
            }
            
            result.push_back(cidr(intToIp(start), 32 - bitCount(maxSize - 1) + 1));
            start += maxSize;
            n -= maxSize;
        }
        
        return result;
    }
    
private:
    int ipToInt(const string& ip) {
        int result = 0;
        stringstream ss(ip);
        string segment;
        for (int i = 0; getline(ss, segment, '.'); ++i) {
            result = result * 256 + stoi(segment);
        }
        return result;
    }

    string intToIp(int num) {
        return to_string((num >> 24) & 255) + "." + to_string((num >> 16) & 255) + "." +
               to_string((num >> 8) & 255) + "." + to_string(num & 255);
    }

    string cidr(const string& ip, int prefixLength) {
        return ip + "/" + to_string(prefixLength);
    }

    int bitCount(int n) {
        return (int)log2(n) + 1;
    }
};

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

#medium
Задача: 752. Open the Lock

Перед вами замок с 4 круглыми колесами. Каждое колесо имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Колеса могут свободно вращаться и оборачиваться: например, мы можем повернуть "9" так, чтобы получился "0", или "0" так, чтобы получился "9". Каждый ход состоит из поворота одного колеса на один слот. Изначально замок начинается с '0000', строки, представляющей состояние 4 колес. Вам дан список тупиков, то есть если замок отобразит любой из этих кодов, колеса замка перестанут вращаться, и вы не сможете его открыть. Учитывая цель, представляющую значение колес, которое позволит отпереть замок, верните минимальное общее количество оборотов, необходимое для открытия замка, или -1, если это невозможно.

Пример:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6

👨‍💻 Алгоритм:

1⃣Используйте алгоритм BFS для поиска кратчайшего пути от начального состояния '0000' до целевого состояния, избегая тупиков. Инициализируйте очередь с начальным состоянием '0000' и начальным шагом 0. Используйте множество для отслеживания посещенных состояний, чтобы избежать повторного посещения одного и того же состояния.

2⃣Для каждого состояния в очереди: Проверьте все возможные переходы на следующий шаг, вращая каждое колесо на +1 и -1. Если найденное состояние является целевым, верните количество шагов. Если найденное состояние не является тупиком и не было посещено ранее, добавьте его в очередь и отметьте как посещенное.

3⃣Если очередь пуста и целевое состояние не найдено, верните -1.

😎 Решение:

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> dead(deadends.begin(), deadends.end());
        queue<pair<string, int>> queue;
        queue.push({"0000", 0});
        unordered_set<string> visited;
        visited.insert("0000");
        
        while (!queue.empty()) {
            auto [node, steps] = queue.front();
            queue.pop();
            if (node == target) {
                return steps;
            }
            if (dead.count(node)) {
                continue;
            }
            for (auto neighbor : neighbors(node)) {
                if (!visited.count(neighbor)) {
                    visited.insert(neighbor);
                    queue.push({neighbor, steps + 1});
                }
            }
        }
        
        return -1;
    }

private:
    vector<string> neighbors(const string& node) {
        vector<string> res;
        for (int i = 0; i < 4; i++) {
            string up = node;
            up[i] = (node[i] - '0' + 1) % 10 + '0';
            res.push_back(up);
            string down = node;
            down[i] = (node[i] - '0' - 1 + 10) % 10 + '0';
            res.push_back(down);
        }
        return res;
    }
};

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

#medium
Задача: 753. Cracking the Safe

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

👨‍💻 Алгоритм:

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

2⃣Используйте алгоритм Эйлерова пути или цикла для нахождения пути, который проходит через каждое ребро ровно один раз.

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

class Solution {
public:
    string crackSafe(int n, int k) {
        unordered_set<string> seen;
        string result;

        string startNode(n - 1, '0');
        dfs(startNode, k, seen, result);

        result += startNode;
        return result;
    }

private:
    void dfs(const string& node, int k, unordered_set<string>& seen, string& result) {
        for (int x = 0; x < k; ++x) {
            string neighbor = node + to_string(x);
            if (!seen.count(neighbor)) {
                seen.insert(neighbor);
                dfs(neighbor.substr(1), k, seen, result);
                result += to_string(x);
            }
        }
    }
};

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

#medium
Задача: 754. Reach a Number

Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения.

Пример:

Input: target = 2
Output: 3

👨‍💻 Алгоритм:

1⃣Инициализируйте переменную для текущей позиции (position) и счетчик шагов (steps).

2⃣Используйте цикл, чтобы добавлять к position текущее количество шагов и увеличивать steps.

3⃣Если position достигает или превышает target и разница между position и target четная, остановите цикл и верните steps.

😎 Решение:

class Solution {
public:
    int reachTarget(int target) {
        target = abs(target);
        int position = 0;
        int steps = 0;
        while (position < target || (position - target) % 2 != 0) {
            steps++;
            position += steps;
        }
        return steps;
    }
};

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

#medium
Задача: 755. Pour Water

Вам дана карта высот, представленная в виде целочисленного массива heights, где heights[i] - высота местности в точке i. Ширина в каждой точке равна 1. Вам также даны два целых числа volume и k. Единицы объема воды будут падать в точке k. Вода сначала падает в точке k и упирается в самую высокую местность или воду в этой точке. Затем она течет по следующим правилам: если капля в конечном итоге упадет, двигаясь влево, то двигайтесь влево. Иначе, если капля в конечном итоге упадет, двигаясь вправо, то двигайтесь вправо. Иначе поднимайтесь в текущее положение. Здесь "в конечном итоге упадет" означает, что капля в конечном итоге окажется на более низком уровне, если она будет двигаться в этом направлении. Кроме того, уровень означает высоту местности плюс вода в этом столбе. Мы можем предположить, что на двух сторонах, выходящих за пределы массива, есть бесконечно высокая местность. Также не может быть частичного равномерного распределения воды более чем на один блок сетки, и каждая единица воды должна находиться ровно в одном блоке.

Пример:

Input: heights = [2,1,1,2,1,2,2], volume = 4, k = 3
Output: [2,2,2,3,2,2,2]

👨‍💻 Алгоритм:

1⃣Инициализируйте цикл для добавления объема воды.

2⃣Для каждой единицы воды: Проверьте, может ли вода двигаться влево и упасть на более низкий уровень. Если нет, проверьте, может ли вода двигаться вправо и упасть на более низкий уровень. Если нет, добавьте воду в текущую позицию.

3⃣Повторите шаг 2, пока не будет добавлен весь объем воды.

😎 Решение:

class Solution {
public:
    vector<int> pourWater(vector<int>& heights, int volume, int k) {
        for (int v = 0; v < volume; v++) {
            int dropIndex = k;
            for (int d : {-1, 1}) {
                int i = k;
                while (i + d >= 0 && i + d < heights.size() && heights[i + d] <= heights[i]) {
                    if (heights[i + d] < heights[i]) {
                        dropIndex = i + d;
                    }
                    i += d;
                }
                if (dropIndex != k) {
                    break;
                }
            }
            heights[dropIndex]++;
        }
        return heights;
    }
};

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

#medium
Задача: 756. Pyramid Transition Matrix

Вы складываете блоки так, чтобы получилась пирамида. Каждый блок имеет цвет, который представлен одной буквой. Каждый ряд блоков содержит на один блок меньше, чем ряд под ним, и располагается по центру сверху. Чтобы пирамида выглядела эстетично, допускаются только определенные треугольные узоры. Треугольный узор состоит из одного блока, уложенного поверх двух блоков. Шаблоны задаются в виде списка допустимых трехбуквенных строк, где первые два символа шаблона представляют левый и правый нижние блоки соответственно, а третий символ - верхний блок. Например, "ABC" представляет треугольный шаблон с блоком 'C', уложенным поверх блоков 'A' (слева) и 'B' (справа). Обратите внимание, что это отличается от "BAC", где "B" находится слева внизу, а "A" - справа внизу. Вы начинаете с нижнего ряда блоков bottom, заданного в виде одной строки, который вы должны использовать в качестве основания пирамиды. Учитывая bottom и allowed, верните true, если вы можете построить пирамиду до самой вершины так, чтобы каждый треугольный узор в пирамиде был в allowed, или false в противном случае.

Пример:

Input: bottom = "BCD", allowed = ["BCC","CDE","CEA","FFF"]
Output: true

👨‍💻 Алгоритм:

1⃣Создайте структуру данных для хранения допустимых треугольных узоров.

2⃣Напишите рекурсивную функцию, которая проверяет возможность построения следующего уровня пирамиды.

3⃣Начните с нижнего уровня пирамиды и используйте рекурсию для построения каждого следующего уровня, проверяя каждый треугольный узор на допустимость.

😎 Решение:

class Solution {
public:
    bool pyramidTransition(string bottom, vector<string>& allowed) {
        unordered_map<string, vector<char>> allowedDict;

        for (const string& pattern : allowed) {
            string key = pattern.substr(0, 2);
            char value = pattern[2];
            allowedDict[key].push_back(value);
        }

        return canBuild(bottom, allowedDict);
    }

private:
    bool canBuild(string currentLevel, unordered_map<string, vector<char>>& allowedDict) {
        if (currentLevel.size() == 1) return true;

        vector<vector<char>> nextLevelOptions;
        for (size_t i = 0; i < currentLevel.size() - 1; ++i) {
            string key = currentLevel.substr(i, 2);
            if (!allowedDict.count(key)) return false;
            nextLevelOptions.push_back(allowedDict[key]);
        }

        return canBuildNextLevel(nextLevelOptions, 0, "", allowedDict);
    }

    bool canBuildNextLevel(vector<vector<char>>& options, size_t index, string nextLevel, unordered_map<string, vector<char>>& allowedDict) {
        if (index == options.size()) return canBuild(nextLevel, allowedDict);
        for (char option : options[index]) {
            if (canBuildNextLevel(options, index + 1, nextLevel + option, allowedDict)) return true;
        }
        return false;
    }
};

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

На easyoffer 2.0 появится новый раздел:
Задачи с собеседований

🟠Задачи на Алгоритмические, Live-coding и System Design из реальных собеседований
🟠Вероятность встретить ту или иную задачу
🟠Возможность подготовиться к задачам конкретной компании

Есть много сайтов, на которых можно тренироваться решать задачи, но у них у всех одна проблема – сами задачи люди просто выдумывают. На easyoffer 2.0 вы сможете готовиться к live-coding и system design секциям на основе задач из реальных собеседований. Вы можете найдете самые частые задачи и сделаете упор на их решение.

Считаные дни остались до старта краудфандинговой кампании, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки, а те кто поддержат проект раньше других ито дешевле + получат существенный бонус. Следите за стартом 👉 в этом телеграм канале.

Задача: 1354. Construct Target Array With Multiple Sums
Сложность: hard

Дан массив целых чисел target длины n. Начав с массива arr, состоящего из n единиц, вы можете выполнить следующую процедуру:

Пусть x будет суммой всех элементов, находящихся в вашем массиве.
Выберите индекс i так, чтобы 0 <= i < n, и установите значение arr в индексе i равным x.
Вы можете повторять эту процедуру столько раз, сколько потребуется.
Верните true, если возможно построить массив target из arr, в противном случае верните false.

Пример:

Input: target = [8,5]
Output: true

👨‍💻 Алгоритм:

1⃣Использование максимальной кучи (Max Heap) для отслеживания максимальных значений в target:
Сначала необходимо инициализировать кучу с максимальным приоритетом, чтобы всегда иметь доступ к наибольшему элементу в массиве target.
Вычислить сумму всех элементов в target и сохранить ее.

2⃣Повторение процесса переворота:
Извлечь наибольшее значение из кучи. Вычесть это значение из общей суммы.
Проверить несколько условий:
Если извлеченное значение равно 1 или общая сумма равна 1, вернуть true.
Если извлеченное значение меньше общей суммы, общая сумма равна 0, или извлеченное значение делится на общую сумму без остатка, вернуть false.
Остаток от деления наибольшего значения на общую сумму является новым значением, которое нужно вставить обратно в кучу. Обновить общую сумму.

3⃣Повторение цикла до достижения результата:
Повторять шаг 2 до тех пор, пока не будут выполнены условия выхода из цикла (возврат true или false).

😎 Решение:

#include <vector>
#include <queue>

class Solution {
public:
    bool isPossible(std::vector<int>& target) {
        std::priority_queue<int> pq(target.begin(), target.end());
        long total = std::accumulate(target.begin(), target.end(), 0L);
        
        while (pq.top() > 1) {
            int maxVal = pq.top(); pq.pop();
            total -= maxVal;
            if (maxVal < total || total == 0 || maxVal % total == 0) return false;
            pq.push(maxVal % total);
            total += pq.top();
        }
        return true;
    }
};

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

Задача: 1171. Remove Zero Sum Consecutive Nodes from Linked List
Сложность: medium

Дан указатель на голову связанного списка. Мы многократно удаляем последовательные последовательности узлов, сумма которых равна 0, до тех пор, пока такие последовательности не исчезнут.

После этого верните голову конечного связанного списка. Вы можете вернуть любой такой ответ.

Пример:

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.

👨‍💻 Алгоритм:

1⃣Инициализируйте новый узел ListNode с именем front со значением 0, у которого поле next указывает на head, и узел start, указывающий на front.

2⃣Обрабатывайте все узлы в связанном списке, пока start != null. Инициализируйте переменную prefixSum значением 0 и узел ListNode с именем end, указывающий на start.next. Обрабатывайте остальные узлы в связанном списке, пока end != null: добавьте значение узла end к prefixSum. Если prefixSum равен 0, установите соединение от узла start к последнему узлу после последовательности с суммой ноль, установив start.next равным end.next. Установите end равным end.next.

3⃣Установите start равным start.next. Верните front.next. Узел front указывает на голову конечного связанного списка.

😎 Решение:

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

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        ListNode* front = new ListNode(0, head);
        ListNode* start = front;

        while (start != nullptr) {
            int prefixSum = 0;
            ListNode* end = start->next;

            while (end != nullptr) {
                prefixSum += end->val;
                if (prefixSum == 0) {
                    start->next = end->next;
                }
                end = end->next;
            }

            start = start->next;
        }
        return front->next;
    }
};

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

На easyoffer 2.0 появится:
Тренажер "Реальное собеседование"

🟠 Сценарии вопросов из реального собеседования
🟠Возможность подготовиться к собеседованию в конкретную компанию
🟠Итоговая статистика (прошёл/не прошёл)

Сценарий вопросов взят из реального собеседования. То есть вы тренируетесь на тех вопросах, которые действительно задавались в компании X.

Уже в начале следующей недели стартует краудфандинг кампания, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки. Первые 150 донатеров получать особо-выгодную цену и бонус. Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.

Задача: 1337. The K Weakest Rows in a Matrix
Сложность: easy

Вам дана бинарная матрица размером m x n mat, состоящая из 1 (представляющих солдат) и 0 (представляющих гражданских лиц). Солдаты расположены перед гражданскими лицами. То есть, все 1 будут расположены слева от всех 0 в каждой строке.

Строка i слабее строки j, если выполнено одно из следующих условий:

Количество солдат в строке i меньше, чем в строке j.
Обе строки имеют одинаковое количество солдат, но i < j.
Верните индексы k самых слабых строк в матрице, упорядоченных от самой слабой к самой сильной.

Пример:

Input: mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
Output: [2,0,3]
Explanation: 
The number of soldiers in each row is: 
- Row 0: 2 
- Row 1: 4 
- Row 2: 1 
- Row 3: 2 
- Row 4: 5 
The rows ordered from weakest to strongest are [2,0,3,1,4].

👨‍💻 Алгоритм:

1⃣Вычислите силу каждой строки матрицы и поместите пары сила/индекс в массив. Для каждой строки подсчитайте количество единиц (солдат) до первой нуля (гражданского), чтобы определить силу строки.

2⃣Отсортируйте массив пар по возрастанию силы, а в случае равенства силы — по возрастанию индекса. Для этого потребуется реализовать компаратор, который сравнивает сначала силу, а затем индекс.

3⃣Извлеките первые k индексов из отсортированного массива и верните их. Эти индексы будут соответствовать k самым слабым строкам в порядке от самой слабой к самой сильной.

😎 Решение:

class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        int m = mat.size();
        int n = mat[0].size();

        vector<pair<int, int>> pairs(m);

        for (int i = 0; i < m; i++) {
            int strength = 0;
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) break;
                strength++;
            }
            pairs[i] = {strength, i};
        }

        sort(pairs.begin(), pairs.end());
        vector<int> indexes(k);
        for (int i = 0; i < k; i++) {
            indexes[i] = pairs[i].second;
        }
        return indexes;
    }
};

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

Задача: 1370. Increasing Decreasing String
Сложность: easy

Дана строка s. Переставьте символы строки, используя следующий алгоритм:

Выберите наименьший символ из s и добавьте его к результату.
Выберите наименьший символ из s, который больше последнего добавленного символа, и добавьте его.
Повторяйте шаг 2, пока не сможете выбрать больше символов.
Выберите наибольший символ из s и добавьте его к результату.
Выберите наибольший символ из s, который меньше последнего добавленного символа, и добавьте его.
Повторяйте шаг 5, пока не сможете выбрать больше символов.
Повторяйте шаги с 1 по 6, пока не выберете все символы из s.
На каждом этапе, если наименьший или наибольший символ появляется более одного раза, вы можете выбрать любое его вхождение и добавить его к результату.

Верните результирующую строку после сортировки s с помощью этого алгоритма.

Пример:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

👨‍💻 Алгоритм:

1⃣Инициализация и сортировка:
Создайте словарь для подсчета количества каждого символа в строке s. Создайте результирующую строку result.

2⃣Перебор и добавление символов:
Используйте два цикла: первый для добавления символов в возрастающем порядке, второй — в убывающем. В каждом цикле добавляйте символы к результату, обновляя их количество в словаре.

3⃣Проверка завершения:
Повторяйте шаги 2 и 3, пока не будут добавлены все символы из строки s в result.

😎 Решение:

#include <string>
#include <vector>

class Solution {
public:
    std::string sortString(std::string s) {
        std::vector<int> charCount(26, 0);
        for (char c : s) {
            charCount[c - 'a']++;
        }
        
        std::string result;
        while (result.size() < s.size()) {
            for (char c = 'a'; c <= 'z'; c++) {
                if (charCount[c - 'a'] > 0) {
                    result += c;
                    charCount[c - 'a']--;
                }
            }
            for (char c = 'z'; c >= 'a'; c--) {
                if (charCount[c - 'a'] > 0) {
                    result += c;
                    charCount[c - 'a']--;
                }
            }
        }
        
        return result;
    }
};

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

Задача: 1100. Find K-Length Substrings With No Repeated Characters
Сложность: medium

Дана строка s и целое число k. Верните количество подстрок в s длиной k, которые не содержат повторяющихся символов.

Пример:

Input: s = "havefunonleetcode", k = 5
Output: 6
Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'.

👨‍💻 Алгоритм:

1⃣Если k > 26, верните 0, так как не может быть строки длиной более 26 символов с уникальными символами. Для остальных случаев, где k <= 26, проверьте каждую подстроку длиной k на наличие повторяющихся символов.

2⃣Итерация по строке s от индекса 0 до n - k (включительно), где n - длина строки s:
Для каждого индекса i:
Инициализируйте флаг isUnique как true и массив частот размером 26 для подсчета частот каждого символа.
Итерируйте следующие k символов и увеличивайте частоту каждого встреченного символа в массиве частот.
Если частота любого символа становится больше 1, установите isUnique в false и прекратите итерацию.
Если после итерации по k символам флаг isUnique все еще равен true, увеличьте счетчик ответов на 1.

3⃣Верните количество подстрок без повторяющихся символов после итерации по всем индексам от 0 до n - k.

😎 Решение:

class Solution {
public:
    int numKLenSubstrNoRepeats(string s, int k) {
        if (k > 26) return 0;
        
        int answer = 0;
        int n = s.size();
        
        for (int i = 0; i <= n - k; i++) {
            int freq[26] = {0};
            bool isUnique = true;
            
            for (int j = i; j < i + k; j++) {
                freq[s[j] - 'a']++;
                
                if (freq[s[j] - 'a'] > 1) {
                    isUnique = false;
                    break;
                }
            }
            
            if (isUnique) answer++;
        }
        
        return answer;
    }
};

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

Задача: 1040. Moving Stones Until Consecutive II
Сложность: medium

Есть несколько камней, расположенных в разных позициях на оси X. Вам дан целочисленный массив stones - позиции камней. Назовите камень конечным, если он имеет наименьшую или наибольшую позицию. За один ход вы берете конечный камень и перемещаете его в незанятую позицию так, чтобы он перестал быть конечным. В частности, если камни находятся, скажем, в позиции stones = [1,2,5], вы не можете переместить конечный камень в позицию 5, поскольку перемещение его в любую позицию (например, 0 или 3) сохранит этот камень в качестве конечного. Игра заканчивается, когда вы не можете сделать больше ни одного хода (т.е, камни находятся в трех последовательных позициях). Возвращает целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сделать, а answer[1] - максимальное количество ходов, которое вы можете сделать.

Пример:

Input: stones = [7,4,9]
Output: [1,2]

👨‍💻 Алгоритм:

1⃣Сортировка:
Сначала отсортируем массив камней.

2⃣Максимальное количество ходов:
Максимальное количество ходов равно (последняя позиция - первая позиция + 1) - количество камней, исключая случаи, когда уже имеются три последовательных камня.

3⃣Минимальное количество ходов:
Минимальное количество ходов можно определить следующим образом:
Если первый или последний камень уже находится на своем месте, необходимо проверить остальные камни.
Если расстояние между первым и последним камнем равно 2 (то есть, всего три камня и они расположены последовательно), то минимальное количество ходов равно 0.
В других случаях минимальное количество ходов равно либо 2 (если среди первых или последних трех камней есть два подряд и одно пропущенное), либо 1 (если можно переместить один камень в нужное место).

😎 Решение:

using namespace std;

class Solution {
public:
    vector<int> numMovesStonesII(vector<int>& stones) {
        sort(stones.begin(), stones.end());
        int n = stones.size();
        
        int max_moves = stones[n-1] - stones[0] + 1 - n;
        max_moves -= min(stones[1] - stones[0] - 1, stones[n-1] - stones[n-2] - 1);

        int min_moves = INT_MAX;
        int j = 0;

        for (int i = 0; i < n; ++i) {
            while (j < n && stones[j] - stones[i] + 1 <= n) {
                ++j;
            }
            int already_in_window = j - i;
            if (already_in_window == n - 1 && stones[j-1] - stones[i] + 1 == n - 1) {
                min_moves = min(min_moves, 2);
            } else {
                min_moves = min(min_moves, n - already_in_window);
            }
        }

        return {min_moves, max_moves};
    }
};

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