C/C++ | LeetCode

Задача: 849. Maximize Distance to Closest Person
Сложность: medium

Вам дан массив, представляющий ряд сидений, где seats[i] = 1 означает, что на i-м месте сидит человек, а seats[i] = 0 означает, что i-е место пусто (индексация с нуля).
Есть по крайней мере одно пустое место и по крайней мере один человек, сидящий на месте.
Алекс хочет сесть на такое место, чтобы расстояние между ним и ближайшим к нему человеком было максимальным.

Верните это максимальное расстояние до ближайшего человека.

Пример:

Input: seats = [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (i.e. seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.

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

1⃣Следите за prev, занятым местом слева или на текущей позиции i, и future, занятым местом справа или на текущей позиции i.

2⃣Для каждого пустого места i определите ближайшее занятие места как min(i - prev, future - i), с учетом, что i - prev считается бесконечностью, если слева нет занятого места, и future - i считается бесконечностью, если справа нет занятого места.

3⃣Найдите и верните максимальное расстояние до ближайшего занятого места.

😎 Решение:

class Solution {
public:
    int maxDistToClosest(vector<int>& seats) {
        int N = seats.size();
        int prev = -1, future = 0;
        int ans = 0;

        for (int i = 0; i < N; ++i) {
            if (seats[i] == 1) {
                prev = i;
            } else {
                while (future < N && (seats[future] == 0 || future < i)) {
                    future++;
                }
                int left = prev == -1 ? N : i - prev;
                int right = future == N ? N : future - i;
                ans = max(ans, min(left, right));
            }
        }

        return ans;
    }
};

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

Задача: 292. Nim Game
Сложность: easy

Вы играете в игру, где по очереди с другом берёте от 1 до 3 камней из кучи. Побеждает тот, кто берёт последний камень. Определите, можете ли вы выиграть, если ходите первым и оба играете оптимально.

Пример:

Input: n = 4
Output: false

👨‍💻 Алгоритм
1⃣Если n % 4 == 0, вы не можете выиграть. Независимо от вашего хода, друг сможет вернуть ситуацию к кратному 4 и в итоге победить.

2⃣Если n % 4 != 0, вы можете начать с такого хода, чтобы оставить другу 4, и после этого повторять стратегию.

3⃣Решение тривиальное: просто верните n % 4 != 0.

😎 Решение

class Solution {
public:
    bool canWinNim(int n) {
        return n % 4 != 0;
    }
};

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

Задача: 1259. Handshakes That Don't Cross
Сложность: hard

Вам дан список эквивалентных пар строк synonyms, где synonyms[i] = [si, ti] означает, что si и ti являются эквивалентными строками. Вам также дан текст предложения. Верните все возможные синонимичные предложения, отсортированные лексикографически.

Пример:

Input: numPeople = 4
Output: 2

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

1⃣Определим массив для хранения каталановых чисел.

2⃣Заполним массив каталановых чисел с помощью рекуррентной формулы.

3⃣Вернем 𝐶𝑛𝑢𝑚𝑃𝑒𝑜𝑝𝑙𝑒/2C.

😎 Решение:

class Solution {
public:
    int numHandshakes(int numPeople) {
        int n = numPeople / 2;
        vector<int> catalan(n + 1, 0);
        catalan[0] = 1;

        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                catalan[i] += catalan[j] * catalan[i - 1 - j];
            }
        }

        return catalan[n];
    }
};

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

Задача: 635. Design Log Storage System
Сложность: medium

Вам дается несколько журналов, где каждый журнал содержит уникальный идентификатор и временную метку. Временная метка - это строка, имеющая следующий формат: Год:Месяц:День:Час:Минута:Секунда, например, 2017:01:01:23:59:59. Все домены - десятичные числа с нулевым добавлением. Реализация класса LogSystem: LogSystem() Инициализирует объект LogSystem. void put(int id, string timestamp) Сохраняет заданный журнал (id, timestamp) в вашей системе хранения.
int[] retrieve(string start, string end, string granularity) Возвращает идентификаторы журналов, временные метки которых находятся в диапазоне от start до end включительно. start и end имеют тот же формат, что и timestamp, а granularity означает, насколько точным должен быть диапазон (т. е. с точностью до дня, минуты и т. д.). Например, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", а granularity = "Day" означает, что нам нужно найти журналы в диапазоне от 1 января 2017 года до 2 января 2017 года включительно, а час, минуту и секунду для каждой записи журнала можно игнорировать.

Пример:

Input
["LogSystem", "put", "put", "put", "retrieve", "retrieve"]
[[], [1, "2017:01:01:23:59:59"], [2, "2017:01:01:22:59:59"], [3, "2016:01:01:00:00:00"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour"]]
Output
[null, null, null, null, [3, 2, 1], [2, 1]]

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

1⃣Инициализация и хранение журналов: Реализуйте метод put, который будет сохранять журнал с заданным id и timestamp в системе хранения.

2⃣Формирование диапазона: Реализуйте метод retrieve, который будет формировать диапазон временных меток на основе заданного start, end и granularity.

3⃣Фильтрация и возврат результатов: Используйте сформированный диапазон для фильтрации журналов и возврата идентификаторов тех журналов, чьи временные метки попадают в этот диапазон.

😎 Решение:

class LogSystem {
public:
    LogSystem() {
        granularity = {{"Year", 4}, {"Month", 7}, {"Day", 10}, {"Hour", 13}, {"Minute", 16}, {"Second", 19}};
    }

    void put(int id, string timestamp) {
        logs.push_back({id, timestamp});
    }

    vector<int> retrieve(string start, string end, string granularity) {
        int length = this->granularity[granularity];
        start = start.substr(0, length);
        end = end.substr(0, length);
        vector<int> result;
        for (const auto& log : logs) {
            string ts = log.timestamp.substr(0, length);
            if (start <= ts && ts <= end) {
                result.push_back(log.id);
            }
        }
        return result;
    }

private:
    struct Log {
        int id;
        string timestamp;
    };

    vector<Log> logs;
    unordered_map<string, int> granularity;
};

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

Задача: 916. Word Subsets
Сложность: medium

Вам даны два массива строк words1 и words2. Строка b является подмножеством строки a, если каждая буква в b встречается в ней, включая кратность. Например, "wrr" является подмножеством "warrior", но не является подмножеством "world". Строка a из words1 является универсальной, если для каждой строки b в words2, b является подмножеством a. Верните массив всех универсальных строк в words1. Вы можете вернуть ответ в любом порядке.

Пример:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]

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

1⃣Подсчитать максимальное количество каждой буквы в каждом слове из words2.

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

3⃣Вернуть массив слов из words1, которые удовлетворяют этому условию.

😎 Решение:

class Solution {
public:
    vector<string> wordSubsets(vector<string>& words1, vector<string>& words2) {
        vector<int> maxCount(26, 0);
        for (const string& word : words2) {
            vector<int> count = getCount(word);
            for (int i = 0; i < 26; ++i) {
                maxCount[i] = max(maxCount[i], count[i]);
            }
        }

        vector<string> result;
        for (const string& word : words1) {
            vector<int> count = getCount(word);
            if (isUniversal(count, maxCount)) {
                result.push_back(word);
            }
        }
        
        return result;
    }

private:
    vector<int> getCount(const string& word) {
        vector<int> count(26, 0);
        for (char c : word) {
            count[c - 'a']++;
        }
        return count;
    }

    bool isUniversal(const vector<int>& count, const vector<int>& maxCount) {
        for (int i = 0; i < 26; ++i) {
            if (count[i] < maxCount[i]) {
                return false;
            }
        }
        return true;
    }
};

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

Задача: 720. Longest Word in Dictionary
Сложность: medium

Если задан массив строк words, представляющих английский словарь, верните самое длинное слово из words, которое может быть построено по одному символу из других слов из words. Если существует более одного возможного ответа, верните самое длинное слово с наименьшим лексикографическим порядком. Если ответа нет, верните пустую строку. Обратите внимание, что слово должно строиться слева направо, причем каждый дополнительный символ добавляется в конец предыдущего слова.

Пример:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"

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

1⃣Отсортируйте массив слов по длине и лексикографическому порядку.

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

3⃣Пройдите по каждому слову в отсортированном массиве и добавьте его в множество, если все его префиксы уже существуют в множестве.

😎 Решение:

string longestWord(vector<string>& words) {
    sort(words.begin(), words.end());
    unordered_set<string> validWords;
    validWords.insert("");
    string longest = "";
    for (const string& word : words) {
        if (validWords.count(word.substr(0, word.size() - 1))) {
            validWords.insert(word);
            if (word.size() > longest.size()) {
                longest = word;
            }
        }
    }
    return longest;
}

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

Задача: 737. Sentence Similarity II
Сложность: medium

Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"].

Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c похожи.

Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
Output: true

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

1⃣Проверить, одинаковой ли длины предложения sentence1 и sentence2. Если нет, вернуть false.

2⃣Построить граф схожести слов с использованием словаря.

3⃣Использовать поиск в глубину (DFS) для проверки транзитивной схожести слов в предложениях.

😎 Решение:

class Solution {
public:
    bool areSentencesSimilar(vector<string>& sentence1, vector<string>& sentence2, vector<vector<string>>& similarPairs) {
        if (sentence1.size() != sentence2.size()) {
            return false;
        }

        unordered_map<string, vector<string>> graph;
        for (const auto& pair : similarPairs) {
            graph[pair[0]].push_back(pair[1]);
            graph[pair[1]].push_back(pair[0]);
        }

        for (size_t i = 0; i < sentence1.size(); ++i) {
            if (sentence1[i] != sentence2[i] && !dfs(sentence1[i], sentence2[i], graph, unordered_set<string>())) {
                return false;
            }
        }

        return true;
    }

private:
    bool dfs(const string& word1, const string& word2, unordered_map<string, vector<string>>& graph, unordered_set<string> visited) {
        if (word1 == word2) {
            return true;
        }
        visited.insert(word1);
        for (const string& neighbor : graph[word1]) {
            if (visited.find(neighbor) == visited.end() && dfs(neighbor, word2, graph, visited)) {
                return true;
            }
        }
        return false;
    }
};

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

Задача: 405. Convert a Number to Hexadecimal
Сложность: easy

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

Пример:

Input: num = 26
Output: "1a"

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

1⃣Определите, является ли число отрицательным. Если да, преобразуйте его в положительное число с помощью метода дополнения до двух. Для этого прибавьте к числу 2^32 и используйте битовую операцию И с маской 0xFFFFFFFF.

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

3⃣Переверните строку результата и удалите ведущие нули, если они есть. Если строка пустая, верните "0".

😎 Решение:

using namespace std;

class Solution {
public:
    string toHex(int num) {
        if (num == 0) return "0";
        string hexChars = "0123456789abcdef";
        unsigned int n = num;
        string result;
        while (n > 0) {
            result.push_back(hexChars[n % 16]);
            n /= 16;
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

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

Задача: 1252. Cells with Odd Values in a Matrix
Сложность: easy

Имеется матрица m x n, которая инициализирована всеми 0. Имеется двумерный массив indices, в котором каждый indices[i] = [ri, ci] представляет собой местоположение с индексом 0 для выполнения некоторых операций инкремента над матрицей. Для каждого местоположения indices[i] выполните оба следующих действия: увеличьте все ячейки в строке ri. Увеличьте все ячейки в столбце ci. Учитывая m, n и indices, верните количество нечетных ячеек в матрице после применения инкремента ко всем местоположениям в indices.

Пример:

Input: nums = [12,5,7,23]
Output: true

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

1⃣Инициализируйте два массива: один для подсчета количества инкрементов каждой строки, другой - каждого столбца.

2⃣Для каждого элемента в indices увеличьте счетчики соответствующих строк и столбцов.

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

😎 Решение:

class Solution {
public:
    int oddCells(int m, int n, vector<vector<int>>& indices) {
        vector<int> row_count(m, 0);
        vector<int> col_count(n, 0);

        for (auto& index : indices) {
            row_count[index[0]]++;
            col_count[index[1]]++;
        }

        int odd_count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((row_count[i] + col_count[j]) % 2 == 1) {
                    odd_count++;
                }
            }
        }

        return odd_count;
    }
};

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

Задача: 489. Robot Room Cleaner
Сложность: hard

Вы управляете роботом в комнате, представленной бинарной сеткой m x n, где 0 — стена, а 1 — пустая ячейка.
Робот начинает в неизвестном месте, гарантированно пустом. У вас нет доступа к сетке, но вы можете перемещать робота через предоставленный API Robot.
Роботу нужно очистить всю комнату (т.е. все пустые ячейки). Он может двигаться вперед, поворачивать налево или направо на 90 градусов.
Если робот наталкивается на стену, его датчик препятствия обнаруживает это, и он остается на текущей ячейке.

Разработайте алгоритм для очистки всей комнаты, используя следующие API:

interface Robot {
  // возвращает true, если следующая ячейка открыта и робот перемещается в эту ячейку.
  // возвращает false, если следующая ячейка является препятствием и робот остается на текущей ячейке.
  boolean move();

  // Робот останется на той же ячейке после вызова turnLeft/turnRight.
  // Каждый поворот составляет 90 градусов.
  void turnLeft();
  void turnRight();

  // Очистить текущую ячейку.
  void clean();
}

Пример:

Input: room = [[1,1,1,1,1,0,1,1],[1,1,1,1,1,0,1,1],[1,0,1,1,1,1,1,1],[0,0,0,1,0,0,0,0],[1,1,1,1,1,1,1,1]], row = 1, col = 3
Output: Robot cleaned all rooms.
Explanation: All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at the position of row=1, col=3.
From the top left corner, its position is one row below and three columns right.

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

1⃣Пометьте текущую ячейку как посещенную и очистите её.

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

3⃣Если движение невозможно (стена или посещенная ячейка), поверните направо и попробуйте снова, возвращаясь назад, если необходимо.

😎 Решение:

class Solution {
public:
    Robot* robot;
    set<pair<int, int>> visited;
    vector<pair<int, int>> directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    void goBack() {
        robot->turnRight();
        robot->turnRight();
        robot->move();
        robot->turnRight();
        robot->turnRight();
    }

    void backtrack(int row, int col, int d) {
        visited.insert({row, col});
        robot->clean();
        for (int i = 0; i < 4; ++i) {
            int newD = (d + i) % 4;
            int newRow = row + directions[newD].first;
            int newCol = col + directions[newD].second;
            if (visited.find({newRow, newCol}) == visited.end() && robot->move()) {
                backtrack(newRow, newCol, newD);
                goBack();
            }
            robot->turnRight();
        }
    }

    void cleanRoom(Robot* robot) {
        this->robot = robot;
        backtrack(0, 0, 0);
    }
};

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

Задача: 959. Regions Cut By Slashes
Сложность: medium

n x n сетка состоит из квадратов размером 1 x 1, где каждый квадрат 1 x 1 содержит '/', '', или пустое пространство ' '. Эти символы делят квадрат на смежные области.

Дана сетка grid, представленная в виде строкового массива. Верните количество областей.

Обратите внимание, что обратные слеши экранированы, поэтому '' представлен как '\'.

Пример:

Input: grid = [" /","/ "]
Output: 2

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

1⃣Создайте 4*N*N узлов для каждой ячейки сетки и соедините их в соответствии с описанием.

2⃣Используйте структуру объединения-поиска (DSU), чтобы найти количество связанных компонентов.

3⃣Пройдите по всем узлам и посчитайте количество корневых узлов, которые представляют количество областей.

😎 Решение:

class DSU {
public:
    vector<int> parent;
    DSU(int N) : parent(N) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    void unionSet(int x, int y) {
        parent[find(x)] = find(y);
    }
};

class Solution {
public:
    int regionsBySlashes(vector<string>& grid) {
        int N = grid.size();
        DSU dsu(4 * N * N);
        
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                int root = 4 * (r * N + c);
                char val = grid[r][c];
                
                if (val != '\\') {
                    dsu.unionSet(root + 0, root + 1);
                    dsu.unionSet(root + 2, root + 3);
                }
                if (val != '/') {
                    dsu.unionSet(root + 0, root + 2);
                    dsu.unionSet(root + 1, root + 3);
                }
                
                if (r + 1 < N) {
                    dsu.unionSet(root + 3, (root + 4 * N) + 0);
                }
                if (r - 1 >= 0) {
                    dsu.unionSet(root + 0, (root - 4 * N) + 3);
                }
                if (c + 1 < N) {
                    dsu.unionSet(root + 2, (root + 4) + 1);
                }
                if (c - 1 >= 0) {
                    dsu.unionSet(root + 1, (root - 4) + 2);
                }
            }
        }
        
        int ans = 0;
        for (int x = 0; x < 4 * N * N; ++x) {
            if (dsu.find(x) == x) {
                ++ans;
            }
        }
        
        return ans;
    }
};

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

Задача: 317. Shortest Distance from All Buildings
Сложность: hard

Дана сетка m x n, содержащая значения 0, 1 или 2, где:
каждое 0 обозначает пустую землю, по которой можно свободно проходить,
каждое 1 обозначает здание, через которое нельзя пройти,
каждое 2 обозначает препятствие, через которое нельзя пройти.
Вы хотите построить дом на пустой земле, чтобы он достиг всех зданий с минимальным суммарным расстоянием. Можно перемещаться только вверх, вниз, влево и вправо.
Верните минимальное суммарное расстояние для такого дома. Если построить такой дом невозможно согласно указанным правилам, верните -1.
Суммарное расстояние — это сумма расстояний между домами друзей и точкой встречи.

Пример:

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

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

1⃣Инициализация и запуск BFS
Для каждой пустой ячейки (0) в сетке grid запустите BFS, обходя все соседние ячейки в 4 направлениях, которые не заблокированы и не посещены, отслеживая расстояние от начальной ячейки.

2⃣Обработка BFS и обновление расстояний
При достижении здания (1) увеличьте счетчик достигнутых домов housesReached и суммарное расстояние distanceSum на текущее расстояние. Если housesReached равно общему количеству зданий, верните суммарное расстояние. Если BFS не может достигнуть всех домов, установите значение каждой посещенной пустой ячейки в 2, чтобы не запускать новый BFS из этих ячеек, и верните INT_MAX.

3⃣Обновление и возврат минимального расстояния
Обновите минимальное расстояние (minDistance) после каждого вызова BFS. Если возможно достигнуть все дома из любой пустой ячейки, верните найденное минимальное расстояние. В противном случае, верните -1.

😎 Решение:

#include <vector>
#include <queue>
#include <climits>
using namespace std;

class Solution {
private:
    int bfs(vector<vector<int>>& grid, int row, int col, int totalHouses) {
        int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int rows = grid.size(), cols = grid[0].size();
        int distanceSum = 0, housesReached = 0, steps = 0;
        queue<pair<int, int>> q;
        q.push({row, col});
        vector<vector<bool>> vis(rows, vector<bool>(cols, false));
        vis[row][col] = true;

        while (!q.empty() && housesReached != totalHouses) {
            int size = q.size();
            while (size-- > 0) {
                auto curr = q.front();
                q.pop();
                int r = curr.first, c = curr.second;
                if (grid[r][c] == 1) {
                    distanceSum += steps;
                    housesReached++;
                    continue;
                }
                for (auto& dir : dirs) {
                    int nr = r + dir[0], nc = c + dir[1];
                    if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && !vis[nr][nc] && grid[nr][nc] != 2) {
                        vis[nr][nc] = true;
                        q.push({nr, nc});
                    }
                }
            }
            steps++;
        }

        if (housesReached != totalHouses) {
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (grid[r][c] == 0 && vis[r][c]) grid[r][c] = 2;
                }
            }
            return INT_MAX;
        }
        return distanceSum;
    }

public:
    int shortestDistance(vector<vector<int>>& grid) {
        int minDistance = INT_MAX, rows = grid.size(), cols = grid[0].size(), totalHouses = 0;
        for (const auto& row : grid) for (const auto& cell : row) if (cell == 1) totalHouses++;
        for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (grid[r][c] == 0) minDistance = min(minDistance, bfs(grid, r, c, totalHouses));
        return minDistance == INT_MAX ? -1 : minDistance;
    }
};

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

Задача: 1025. Divisor Game
Сложность: easy

Алиса и Боб играют в игру по очереди, причем Алиса начинает первой. Изначально на доске мелом написано число n. В свой ход каждый игрок делает ход, состоящий из: выбора любого x при 0 < x < n и n % x == 0. Замены числа n на доске на n - x. Также, если игрок не может сделать ход, он проигрывает игру. Возвращается true тогда и только тогда, когда Алиса выигрывает игру, предполагая, что оба игрока играют оптимально.

Пример:

Input: n = 2
Output: true

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

1⃣Определение выигрыша:
Заметим, что если число n четное, Алиса всегда выигрывает, потому что она может уменьшить n на 1, и оставить Боба с нечетным числом.
Если число n нечетное, Алиса всегда проигрывает, потому что Боб может уменьшить n на 1, и оставить Алису с четным числом.

2⃣Проверка четности числа:
Проверяем, четное ли число n. Если n четное, возвращаем true, если нечетное, возвращаем false.

3⃣Возврат результата:
Возвращаем результат в зависимости от четности числа n.

😎 Решение:

class Solution {
public:
    bool divisorGame(int n) {
        return n % 2 == 0;
    }
};

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

Задача: 1272. Remove Interval
Сложность: medium

Множество вещественных чисел можно представить как объединение нескольких несовпадающих интервалов, где каждый интервал имеет вид [a, b). Вещественное число x входит в множество, если один из его интервалов [a, b) содержит x (то есть a <= x < b). Вам дан отсортированный список непересекающихся интервалов, представляющих множество вещественных чисел, как описано выше, где intervals[i] = [ai, bi] представляет интервал [ai, bi). Вам также дан еще один интервал toBeRemoved. Верните набор вещественных чисел с интервалом toBeRemoved, удаленным из intervals. Другими словами, верните набор вещественных чисел, каждый x в котором находится в интервале, но не в toBeRemoved. Вашим ответом должен быть отсортированный список непересекающихся интервалов, как описано выше.

Пример:

Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]

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

1⃣Итерируйтесь по каждому интервалу в списке intervals.

2⃣Для каждого интервала, проверяйте пересечения с toBeRemoved и обновляйте список результатов.

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

😎 Решение:

class Solution {
public:
    vector<vector<double>> removeInterval(vector<vector<double>>& intervals, vector<double>& toBeRemoved) {
        vector<vector<double>> result;
        for (auto& interval : intervals) {
            if (interval[0] < toBeRemoved[0]) {
                result.push_back({interval[0], min(interval[1], toBeRemoved[0])});
            }
            if (interval[1] > toBeRemoved[1]) {
                result.push_back({max(interval[0], toBeRemoved[1]), interval[1]});
            }
        }
        return result;
    }
};

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

Задача: 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Сложность: medium

Дан массив целых чисел nums и целое число limit. Вернуть размер самой длинной непустой подстроки, такая что абсолютная разница между любыми двумя элементами этой подстроки меньше или равна limit.

Пример:

Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

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

1⃣Инициализировать два дека (minDeque и maxDeque) для хранения минимальных и максимальных значений в текущем окне и переменную left для начала окна.

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

3⃣Обновлять maxLength, проверяя максимальную длину текущего окна, и возвращать maxLength как результат.

😎 Решение:

#include <queue>
#include <vector>

class Solution {
public:
    int longestSubarray(std::vector<int>& nums, int limit) {
        std::priority_queue<std::pair<int, int>> maxHeap;
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> minHeap;
        int left = 0, maxLength = 0;

        for (int right = 0; right < nums.size(); ++right) {
            maxHeap.push({nums[right], right});
            minHeap.push({nums[right], right});

            while (maxHeap.top().first - minHeap.top().first > limit) {
                left = std::min(maxHeap.top().second, minHeap.top().second) + 1;
                while (maxHeap.top().second < left) {
                    maxHeap.pop();
                }
                while (minHeap.top().second < left) {
                    minHeap.pop();
                }
            }

            maxLength = std::max(maxLength, right - left + 1);
        }

        return maxLength;
    }
};

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

Задача: 647. Palindromic Substrings
Сложность: medium

Если задана строка s, верните количество палиндромных подстрок в ней. Строка является палиндромом, если она читается так же, как задом наперед. Подстрока - это непрерывная последовательность символов в строке.

Пример:

Input: s = "abc"
Output: 3

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

1⃣Инициализируйте счетчик для подсчета палиндромных подстрок.

2⃣Для каждой позиции в строке используйте два метода расширения: один для палиндромов нечетной длины и один для палиндромов четной длины.

3⃣Расширяйте от центра, проверяя, является ли подстрока палиндромом, и увеличивайте счетчик, если условие выполняется.

😎 Решение:

int expandAroundCenter(const string& s, int left, int right) {
    int count = 0;
    while (left >= 0 && right < s.length() && s[left] == s[right]) {
        count++;
        left--;
        right++;
    }
    return count;
}

int countSubstrings(string s) {
    int totalCount = 0;
    for (int i = 0; i < s.length(); i++) {
        totalCount += expandAroundCenter(s, i, i);
        totalCount += expandAroundCenter(s, i, i + 1);
    }
    return totalCount;
}

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

Задача: 813. Largest Sum of Averages
Сложность: medium

Вам дан целочисленный массив nums и целое число k. Вы можете разбить массив на не более чем k непустых смежных подмассивов. Оценка разбиения равна сумме средних значений каждого подмассива.

Обратите внимание, что при разбиении должны быть использованы все целые числа из nums, и что оценка не обязательно является целым числом.

Верните максимальную оценку, которую можно достичь среди всех возможных разбиений. Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты.

Пример:

Input: nums = [9,1,2,3,9], k = 3
Output: 20.00000
Explanation: 
The best choice is to partition nums into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned nums into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.

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

1⃣Пусть dp(i, k) будет лучшей оценкой для разбиения массива A[i:] на не более чем k частей. Если первая группа, в которую мы разбиваем A[i:], заканчивается перед j, тогда наше разбиение-кандидат имеет оценку average(i, j) + dp(j, k-1), где average(i, j) = (A[i] + A[i+1] + ... + A[j-1]) / (j - i) (деление с плавающей запятой). Мы берем наивысшую оценку из этих вариантов, помня, что разбиение необязательно - dp(i, k) также может быть просто average(i, N).

2⃣В общем случае наша рекурсия выглядит так: dp(i, k) = max(average(i, N), max_{j > i}(average(i, j) + dp(j, k-1))). Мы можем рассчитывать average немного быстрее, используя префиксные суммы. Если P[x+1] = A[0] + A[1] + ... + A[x], тогда average(i, j) = (P[j] - P[i]) / (j - i).

3⃣Наша реализация демонстрирует подход "снизу вверх" для динамического программирования. На шаге k во внешнем цикле, dp[i] представляет собой dp(i, k) из обсуждения выше, и мы рассчитываем следующий слой dp(i, k+1). Завершение второго цикла для i = 0..N-1 означает завершение расчета правильного значения для dp(i, t), а внутренний цикл выполняет расчет max_{j > i}(average(i, j) + dp(j, k)).

😎 Решение:

class Solution {
public:
    double largestSumOfAverages(vector<int>& A, int K) {
        int N = A.size();
        vector<double> P(N + 1);
        for (int i = 0; i < N; ++i)
            P[i + 1] = P[i] + A[i];
        
        vector<double> dp(N);
        for (int i = 0; i < N; ++i)
            dp[i] = (P[N] - P[i]) / (N - i);
        
        for (int k = 0; k < K - 1; ++k) {
            for (int i = 0; i < N; ++i) {
                for (int j = i + 1; j < N; ++j) {
                    dp[i] = max(dp[i], (P[j] - P[i]) / (j - i) + dp[j]);
                }
            }
        }
        
        return dp[0];
    }
};

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

Задача: 1357. Apply Discount Every n Orders
Сложность: medium

В супермаркете, который посещает множество покупателей, товары представлены двумя параллельными массивами целых чисел products и prices, где i-й товар имеет идентификатор products[i] и цену prices[i].

Когда покупатель оплачивает товар, его счет представлен двумя параллельными массивами целых чисел product и amount, где j-й приобретенный товар имеет идентификатор product[j], а amount[j] - количество купленного товара. Их промежуточный итог рассчитывается как сумма каждого amount[j] * (цена j-го товара).

Супермаркет решил провести распродажу. Каждому n-му покупателю, оплачивающему свои покупки, будет предоставлена скидка в процентах. Сумма скидки задается параметром discount, и покупатель получит скидку в discount процентов от своего промежуточного итога. Формально, если их промежуточный итог составляет bill, то они фактически заплатят bill * ((100 - discount) / 100).

Реализуйте класс Cashier:

Cashier(int n, int discount, int[] products, int[] prices): инициализирует объект с параметрами n, discount, а также массивами товаров и их цен.
double getBill(int[] product, int[] amount): возвращает итоговую сумму счета с примененной скидкой (если применима). Ответы, отличающиеся от фактического значения не более чем на 10^-5, будут приняты.

Пример:

Input
["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]
Output
[null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]

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

1⃣Инициализация объекта:
Создайте класс Cashier с конструктором, который принимает параметры n, discount, products и prices. В конструкторе инициализируйте необходимые переменные и создайте словарь для сопоставления идентификаторов продуктов с их ценами.

2⃣Обработка каждого счета:
Создайте метод getBill, который принимает массивы product и amount.
Вычислите промежуточный итог счета, умножая количество каждого продукта на его цену и суммируя результаты.
Увеличьте счетчик клиентов. Если клиент является n-м по счету, примените скидку к промежуточному итогу.

3⃣Верните итоговую сумму счета.

😎 Решение:

#include <unordered_map>
#include <vector>

class Cashier {
public:
    Cashier(int n, int discount, std::vector<int>& products, std::vector<int>& prices) 
        : n(n), discount(discount), customerCount(0) {
        for (size_t i = 0; i < products.size(); ++i) {
            productsPrices[products[i]] = prices[i];
        }
    }

    double getBill(std::vector<int>& product, std::vector<int>& amount) {
        customerCount++;
        double bill = 0.0;
        
        for (size_t i = 0; i < product.size(); ++i) {
            bill += productsPrices[product[i]] * amount[i];
        }
        
        if (customerCount % n == 0) {
            bill *= (100.0 - discount) / 100.0;
        }
        
        return bill;
    }

private:
    int n;
    int discount;
    int customerCount;
    std::unordered_map<int, int> productsPrices;
};

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

Задача: 109. Convert Sorted List to Binary Search Tree
Сложность: medium

Дана голова односвязного списка, элементы которого отсортированы в порядке возрастания. Преобразуйте его в сбалансированное по высоте бинарное дерево поиска.

Пример:

Input: head = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5]

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

1⃣Так как список односвязный, для нахождения середины используем два указателя: slow_ptr (двигается на 1 узел) и fast_ptr (на 2 узла). Когда fast_ptr дойдёт до конца, slow_ptr будет в середине.

2⃣Для отделения левой части от средней сохраняем prev_ptr, который указывает на узел перед slow_ptr. Затем делаем prev_ptr->next = nullptr, чтобы отсоединить левую часть списка.

3⃣Рекурсивно строим левое поддерево из головы списка, правое — из mid->next. Базовый случай — если head == mid, это лист, возвращаем его как TreeNode.

😎 Решение:

class Solution {
public:
    ListNode* findMiddleElement(ListNode* head) {
        ListNode* prevPtr = nullptr;
        ListNode* slowPtr = head;
        ListNode* fastPtr = head;

        while (fastPtr != nullptr && fastPtr->next != nullptr) {
            prevPtr = slowPtr;
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;
        }

        if (prevPtr != nullptr) {
            prevPtr->next = nullptr;
        }
        return slowPtr;
    }

    TreeNode* sortedListToBST(ListNode* head) {
        if (head == nullptr) {
            return nullptr;
        }

        ListNode* mid = this->findMiddleElement(head);
        TreeNode* node = new TreeNode(mid->val);

        if (head == mid) {
            return node;
        }

        node->left = this->sortedListToBST(head);
        node->right = this->sortedListToBST(mid->next);
        return node;
    }
};

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

Задача: 64. Minimum Path Sum
Сложность: medium

На сетке m x n, заполненной неотрицательными числами, найдите путь от (0, 0) до (m - 1, n - 1) с минимальной суммой.
Можно двигаться только вправо или вниз.

Пример:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]] Output: 7

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

1⃣Инициализировать матрицу dp такого же размера, где dp[i][j] будет хранить минимальную сумму пути до конца из позиции (i, j)

2⃣Заполнить dp в обратном порядке, начиная с правого нижнего угла.
Для каждой ячейки:
dp[i][j] = grid[i][j] + min(dp[i+1][j], dp[i][j+1]) — если оба пути доступны
Учитывать границы (последняя строка и столбец) отдельно

3⃣Вернуть dp[0][0] — минимальную сумму пути из начала в конец

😎 Решение:

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i == m - 1 && j != n - 1)
                    dp[i][j] = grid[i][j] + dp[i][j + 1];
                else if (j == n - 1 && i != m - 1)
                    dp[i][j] = grid[i][j] + dp[i + 1][j];
                else if (j != n - 1 && i != m - 1)
                    dp[i][j] = grid[i][j] + min(dp[i + 1][j], dp[i][j + 1]);
                else
                    dp[i][j] = grid[i][j];
            }
        }
        return dp[0][0];
    }
};

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