C/C++ | LeetCode

Задача: 293. Flip Game Сложность: easy Вам дана строка currentState, содержащая только символы '+' и '-'. Нужно вернуть все возможные состояния строки после одного допустимого хода, где один ход — это замена двух последовательных '++' на '--'. Пример:

    
        Input: currentState = "++++"
Output: ["--++", "+--+", "++--"]
{}
    

👨‍💻 Алгоритм 1⃣Создайте пустой список nextPossibleStates, в который будем добавлять новые состояния строки после одного хода. 2⃣Пройдитесь по строке от index = 0 до length - 2 На каждом шаге проверьте, есть ли пара ++ на позиции index и index + 1 Если да — создайте новую строку, заменив эту пару на -- и добавьте результат в список. 3⃣После завершения цикла верните список nextPossibleStates. 😎 Решение

    
        #include <vector>
#include <string>

using namespace std;

class Solution {
public:
    vector<string> generatePossibleNextMoves(string currentState) {
        vector<string> nextPossibleStates;

        for (int index = 0; index < currentState.length() - 1; ++index) {
            if (currentState[index] == '+' && currentState[index + 1] == '+') {
                string nextState = currentState.substr(0, index) + "--" + currentState.substr(index + 2);
                nextPossibleStates.push_back(nextState);
            }
        }

        return nextPossibleStates;
    }
};{}
    

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

Tanks Blitz — в RuStore, ты — на Финале Лиги Блиц Поинт! Проведи киберспортивные выходные с саундтреком от «ХЛЕБа», Oligarkh'а и FANKIN’а — скачай Tanks Blitz в RuStore, чтобы узнать больше о Финальном турнире Лиги Блиц Поинт, Часть 3 в Москве! ⚡ Узнать больше #реклама 16+ apps.rustore.ru О рекламодателе

Мы ищем людей, которые хотят работать турагентом из дома 💰Оплата от 150.000 рублей в месяц Образование, место жительства, трудовой стаж — не важны! Подходит, как для подработки / декретного отпуска, так и для полной занятости. Если заинтересовались, то для старта нужно: — зарегистрироваться на сайте — пройти трехдневный курс На что можно рассчитывать: ✅ удаленная работа ✅ зп от 150.000 рублей (потолка нет) ✅ стабильная подработка, если не хотите уходить с основной работы Количество бесплатных мест ограничено. Успейте пройти тест и оставить заявку. ⚡ Набор заканчивается в понедельник! Зарегистрироваться #реклама интревел.рф О рекламодателе

Задача: 1472. Design Browser History Сложность: medium У вас есть браузер с одной вкладкой, где вы начинаете на домашней странице и можете посетить другой URL, вернуться назад на определённое количество шагов в истории или переместиться вперёд на определённое количество шагов в истории. Реализуйте класс BrowserHistory: BrowserHistory(string homepage) Инициализирует объект с домашней страницей браузера. void visit(string url) Посещает URL с текущей страницы. Это очищает всю историю вперёд. string back(int steps) Перемещает на steps шагов назад в истории. Если вы можете вернуться только на x шагов в истории, а steps > x, вы вернётесь только на x шагов. Возвращает текущий URL после перемещения назад в истории на не более чем steps шагов. string forward(int steps) Перемещает на steps шагов вперёд в истории. Если вы можете переместиться только на x шагов вперёд в истории, а steps > x, вы переместитесь только на x шагов. Возвращает текущий URL после перемещения вперёд в истории на не более чем steps шагов. Пример:

    
        Input:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
Output:
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

Explanation:
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // You are in "leetcode.com". Visit "google.com"
browserHistory.visit("facebook.com");     // You are in "google.com". Visit "facebook.com"
browserHistory.visit("youtube.com");      // You are in "facebook.com". Visit "youtube.com"
browserHistory.back(1);                   // You are in "youtube.com", move back to "facebook.com" return "facebook.com"
browserHistory.back(1);                   // You are in "facebook.com", move back to "google.com" return "google.com"
browserHistory.forward(1);                // You are in "google.com", move forward to "facebook.com" return "facebook.com"
browserHistory.visit("linkedin.com");     // You are in "facebook.com". Visit "linkedin.com"
browserHistory.forward(2);                // You are in "linkedin.com", you cannot move forward any steps.{}
    

👨‍💻 Алгоритм: 1⃣Инициализация: Создайте класс BrowserHistory с двумя стеками (history и future) и строковой переменной current для хранения текущего URL. Инициализируйте current с домашней страницей. 2⃣Посещение URL: Метод visit(url) сохраняет текущий URL в стеке history, устанавливает url как текущий и очищает стек future. 3⃣Навигация назад и вперед: Метод back(steps) перемещает текущий URL в стек future и извлекает URL из стека history, пока шаги не будут исчерпаны или стек history не станет пустым. Метод forward(steps) перемещает текущий URL в стек history и извлекает URL из стека future, пока шаги не будут исчерпаны или стек future не станет пустым. 😎 Решение:

    
        #include <stack>
#include <string>
using namespace std;

class BrowserHistory {
private:
    stack<string> history;
    stack<string> future;
    string current;

public:
    BrowserHistory(string homepage) {
        current = homepage;
    }
    
    void visit(string url) {
        history.push(current);
        current = url;
        while (!future.empty()) {
            future.pop();
        }
    }
    
    string back(int steps) {
        while (steps > 0 && !history.empty()) {
            future.push(current);
            current = history.top();
            history.pop();
            steps--;
        }
        return current;
    }
    
    string forward(int steps) {
        while (steps > 0 && !future.empty()) {
            history.push(current);
            current = future.top();
            future.pop();
            steps--;
        }
        return current;
    }
};{}
    

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

Задача: 1166. Design File System Сложность: medium Вам нужно разработать файловую систему, которая позволяет создавать новые пути и связывать их с различными значениями. Формат пути - это одна или несколько конкатенированных строк в форме: /, за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" - допустимые пути, в то время как пустая строка "" и "/" не допустимы. Реализуйте класс FileSystem: - bool createPath(string path, int value) создает новый путь и связывает с ним значение, если это возможно, и возвращает true. Возвращает false, если путь уже существует или его родительский путь не существует. - int get(string path) возвращает значение, связанное с путем, или возвращает -1, если путь не существует. Пример:

    
        Input: 
["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]
Output: 
[null,true,1]
Explanation: 
FileSystem fileSystem = new FileSystem();

fileSystem.createPath("/a", 1); // return true
fileSystem.get("/a"); // return 1{}
    

👨‍💻 Алгоритм: 1⃣Инициализируйте словарь или HashMap под названием paths, который будет использовать ключ в виде пути, переданного в нашу функцию create, и значение, переданное этой функции. 2⃣Для функции create выполняем три шага. Сначала выполняем базовую проверку валидности пути. Проверяем, является ли путь пустым, "/" или если путь уже существует в нашем словаре. Если любое из этих условий выполнено, просто возвращаем false. Затем получаем родительский путь предоставленного пути и проверяем его наличие в словаре. Если родительский путь не существует, возвращаем false, иначе продолжаем. 3⃣Наконец, вставляем предоставленный путь и значение в словарь и возвращаем true. Для функции get просто возвращаем значение по умолчанию -1, если путь не существует в словаре. В противном случае возвращаем фактическое значение. 😎 Решение:

    
        class FileSystem {
public:
    unordered_map<string, int> paths;

    FileSystem() {
        paths = unordered_map<string, int>();
    }

    bool createPath(string path, int value) {
        if (path.empty() || (path.length() == 1 && path == "/") || paths.count(path)) {
            return false;
        }

        int delimIndex = path.rfind("/");
        string parent = path.substr(0, delimIndex);

        if (parent.length() > 1 && !paths.count(parent)) {
            return false;
        }

        paths[path] = value;
        return true;
    }

    int get(string path) {
        return paths.count(path) ? paths[path] : -1;
    }
};{}
    

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

Задача: 57. Insert Interval Сложность: medium Дан отсортированный массив непересекающихся интервалов intervals, и новый интервал newInterval. Вставьте newInterval, объединив перекрывающиеся интервалы, и сохраните сортировку по возрастанию. Пример:

    
        Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]
{}
    

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

    
        class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size(), i = 0;
        vector<vector<int>> res;

        while (i < n && intervals[i][1] < newInterval[0]) {
            res.push_back(intervals[i]);
            i++;
        }

        while (i < n && newInterval[1] >= intervals[i][0]) {
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            i++;
        }
        res.push_back(newInterval);

        while (i < n) {
            res.push_back(intervals[i]);
            i++;
        }
        return res;
    }
};{}
    

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

Задача: 752. Open the Lock Сложность: medium Перед вами замок с 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;
    }
};{}
    

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