Задача: 1151. Minimum Swaps to Group All 1's Together
Сложность: medium

Дан бинарный массив data, необходимо вернуть минимальное количество перестановок, чтобы сгруппировать все 1, присутствующие в массиве, вместе в любом месте массива.

Пример:

Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.

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

1⃣Используем два указателя, left и right, чтобы поддерживать скользящее окно длиной ones и проверяем каждый фрагмент массива data, подсчитывая количество единиц в нем (cnt_one) и запоминая максимальное значение max_one.

2⃣Пока окно скользит по массиву data, поддерживаем его длину равной ones.

3⃣Обновляем количество единиц в окне, добавляя новую границу data[right] и вычитая левую границу data[left].

😎 Решение:

class Solution {
public:
    int minSwaps(vector<int>& data) {
        int ones = accumulate(data.begin(), data.end(), 0);
        int cnt_one = 0, max_one = 0;
        int left = 0, right = 0;

        while (right < data.size()) {
            cnt_one += data[right++];
            if (right - left > ones) {
                cnt_one -= data[left++];
            }
            max_one = max(max_one, cnt_one);
        }
        return ones - max_one;
    }
};

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

Задача: 407. Trapping Rain Water II
Сложность: hard

Задав целочисленную матрицу heightMap размером m x n, представляющую высоту каждой ячейки на двумерной карте рельефа, верните объем воды, который она может задержать после дождя.

Пример:

Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output: 4

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

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

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

3⃣Повторите процесс, пока все ячейки не будут обработаны.

😎 Решение:

using namespace std;

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        if (heightMap.empty() || heightMap[0].empty()) return 0;
        int m = heightMap.size(), n = heightMap[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        auto cmp = [](const vector<int>& a, const vector<int>& b) { return a[0] > b[0]; };
        priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> heap(cmp);
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    heap.push({ heightMap[i][j], i, j });
                    visited[i][j] = true;
                }
            }
        }
        
        vector<vector<int>> directions = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
        int water = 0;
        
        while (!heap.empty()) {
            auto curr = heap.top(); heap.pop();
            int h = curr[0], x = curr[1], y = curr[2];
            for (auto& dir : directions) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && ny >= 0 && nx < m && ny < n && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    water += max(0, h - heightMap[nx][ny]);
                    heap.push({ max(h, heightMap[nx][ny]), nx, ny });
                }
            }
        }
        
        return water;
    }
};

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

Задача: 125. Valid Palindrome
Сложность: easy

Фраза является палиндромом, если после удаления всех неалфавитно-цифровых символов и приведения к нижнему регистру, она читается одинаково слева направо и справа налево.

Пример:

Input: s = "A man, a plan, a canal: Panama" Output: true
Explanation: "amanaplanacanalpanama" — палиндром

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

1⃣Установите два указателя: i в начале строки и j в конце.

2⃣Пропускайте все символы, которые не являются буквами или цифрами (isalnum), с обеих сторон.

3⃣Сравнивайте символы, приведённые к нижнему регистру (tolower). Если они не равны — строка не палиндром. Если равны — двигайтесь к центру.

😎 Решение:

class Solution {
public:
    bool isPalindrome(string s) {
        for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
            while (i < j && !isalnum(s[i])) i++;
            while (i < j && !isalnum(s[j])) j--;

            if (tolower(s[i]) != tolower(s[j])) return false;
        }

        return true;
    }
};

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

Задача: 1182. Shortest Distance to Target Color
Сложность: medium

Дан массив colors, содержащий три цвета: 1, 2 и 3.

Также даны несколько запросов. Каждый запрос состоит из двух целых чисел i и c. Верните наименьшее расстояние между заданным индексом i и целевым цветом c. Если решения нет, верните -1.

Пример:

Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation: 
The nearest 3 from index 1 is at index 4 (3 steps away).
The nearest 2 from index 2 is at index 2 itself (0 steps away).
The nearest 1 from index 6 is at index 3 (3 steps away).

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

1⃣Инициализируйте хэш-таблицу для отображения каждого цвета в список индексов. Итерируйте по массиву colors и добавляйте каждый индекс в соответствующий список хэш-таблицы.

2⃣Для каждого запроса, содержащего i и c, если c не является одним из ключей в хэш-таблице, то colors не содержит c, поэтому верните -1. Иначе, найдите позицию i в соответствующем списке индексов indexList для поддержания упорядоченного порядка.

3⃣Если i меньше всех элементов в indexList, то i - indexList[0] является кратчайшим расстоянием. Если i больше всех элементов в indexList, то indexList[indexList.size() - 1] - i является кратчайшим расстоянием. Иначе, ближайшее появление c к i либо на индексе вставки, либо перед ним, поэтому рассчитайте расстояние от i до каждого из них и верните наименьшее.

😎 Решение:

class Solution {
public:
    vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
        vector<int> queryResults;
        unordered_map<int, vector<int>> hashmap;

        for (int i = 0; i < colors.size(); i++) {
            hashmap[colors[i]].push_back(i);
        }

        for (const auto& query : queries) {
            int target = query[0], color = query[1];
            if (hashmap.find(color) == hashmap.end()) {
                queryResults.push_back(-1);
                continue;
            }

            const auto& indexList = hashmap[color];
            auto insert = lower_bound(indexList.begin(), indexList.end(), target);

            if (insert == indexList.begin()) {
                queryResults.push_back(*insert - target);
            } else if (insert == indexList.end()) {
                queryResults.push_back(target - indexList.back());
            } else {
                int leftNearest = target - *(insert - 1);
                int rightNearest = *insert - target;
                queryResults.push_back(min(leftNearest, rightNearest));
            }
        }
        return queryResults;
    }
};

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

Задача: 851. Loud and Rich
Сложность: medium

Есть группа из n человек, пронумерованных от 0 до n - 1, где у каждого человека разное количество денег и разный уровень спокойствия.

Вам дан массив richer, где richer[i] = [ai, bi] указывает на то, что ai имеет больше денег, чем bi, и целочисленный массив quiet, где quiet[i] — это уровень спокойствия i-го человека. Все данные в richer логически корректны (т.е. данные не приведут к ситуации, где x богаче y и y богаче x одновременно).

Верните целочисленный массив answer, где answer[x] = y, если y — это самый спокойный человек (то есть человек y с наименьшим значением quiet[y]) среди всех людей, которые однозначно имеют столько же или больше денег, чем человек x.

Пример:

Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output: [5,5,2,5,4,5,6,7]
Explanation: 
answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but it is not clear if they have more money than person 0.
answer[7] = 7.
Among all people that definitely have equal to or more money than person 7 (which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x]) is person 7.
The other answers can be filled out with similar reasoning.

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

1⃣Постройте граф, описанный выше, и пусть dfs(person) будет самым спокойным человеком в поддереве person. Обратите внимание, что из-за логической последовательности утверждений граф должен быть DAG — ориентированным графом без циклов.

2⃣Теперь dfs(person) — это либо сам person, либо min(dfs(child) для каждого child из person). То есть, самый спокойный человек в поддереве — это либо сам person, либо самый спокойный человек в каком-то поддереве потомка person.

3⃣Мы можем кэшировать значения dfs(person) в answer[person], выполняя обход графа в пост-обходе. Таким образом, мы не повторяем работу. Этот метод уменьшает квадратичное время выполнения алгоритма до линейного.

😎 Решение:

class Solution {
public:
    vector<vector<int>> graph;
    vector<int> answer;
    vector<int> quiet;

    vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
        int N = quiet.size();
        graph.resize(N);
        answer.resize(N, -1);
        this->quiet = quiet;

        for (const auto& edge : richer) {
            graph[edge[1]].push_back(edge[0]);
        }

        for (int node = 0; node < N; ++node) {
            dfs(node);
        }
        return answer;
    }

    int dfs(int node) {
        if (answer[node] == -1) {
            answer[node] = node;
            for (int child : graph[node]) {
                int cand = dfs(child);
                if (quiet[cand] < quiet[answer[node]]) {
                    answer[node] = cand;
                }
            }
        }
        return answer[node];
    }
};

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

Задача: 361. Bomb Enemy
Сложность: medium

Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке.

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

Пример:

Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3

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

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

2⃣Реализовать функцию killEnemies(row, col), которая считает количество врагов, убитых бомбой, установленных в пустой ячейке (row, col), проверяя все четыре направления (влево, вправо, вверх, вниз) до стены или границы сетки.

3⃣Вернуть максимальное количество врагов, убитых среди всех пустых ячеек.

😎 Решение:

class Solution {
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;

        int rows = grid.size();
        int cols = grid[0].size();
        int maxCount = 0;

        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                if (grid[row][col] == '0') {
                    int hits = killEnemies(row, col, grid);
                    maxCount = max(maxCount, hits);
                }
            }
        }

        return maxCount;
    }

private:
    int killEnemies(int row, int col, vector<vector<char>>& grid) {
        int enemyCount = 0;
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for (const auto& dir : directions) {
            int r = row + dir.first;
            int c = col + dir.second;
            
            while (r >= 0 && r < grid.size() && c >= 0 && c < grid[0].size()) {
                if (grid[r][c] == 'W') break;
                if (grid[r][c] == 'E') ++enemyCount;
                r += dir.first;
                c += dir.second;
            }
        }

        return enemyCount;
    }
};

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

Задача: 932. Beautiful Array
Сложность: medium

Массив nums длины n красив, если: nums является перестановкой целых чисел в диапазоне [1, n]. Для каждого 0 <= i < j < n не существует индекса k с i < k < j, где 2 * nums[k] == nums[i] + nums[j]. Задано целое число n, верните любой красивый массив nums длины n. Для заданного n будет хотя бы один правильный ответ.

Пример:

Input: n = 4
Output: [2,1,4,3]

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

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

2⃣Если длина массива равна 1, вернуть массив [1].
Разделить n на четные и нечетные индексы и создать массивы для них.

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

😎 Решение:

class Solution {
public:
    vector<int> beautifulArray(int n) {
        return construct(n);
    }
    
private:
    vector<int> construct(int n) {
        if (n == 1) return {1};
        vector<int> odd = construct((n + 1) / 2);
        vector<int> even = construct(n / 2);
        vector<int> result;
        for (int x : odd) result.push_back(2 * x - 1);
        for (int x : even) result.push_back(2 * x);
        return result;
    }
};

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

Задача: 1436. Destination City
Сложность: easy

Дан массив paths, где paths[i] = [cityAi, cityBi] означает, что существует прямой путь из cityAi в cityBi. Вернуть конечный город, то есть город, из которого нет пути в другой город.

Гарантируется, что граф путей образует линию без циклов, поэтому будет ровно один конечный город.

Пример:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo" 
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

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

1⃣Для каждого города cityBi в paths проверьте, является ли он кандидатом на конечный город.

2⃣Для каждого кандидата проверьте, нет ли пути, ведущего из него (cityAi == candidate).

3⃣Верните город, который не имеет исходящих путей.

😎 Решение:

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        for (auto& path : paths) {
            string candidate = path[1];
            bool good = true;
            for (auto& p : paths) {
                if (p[0] == candidate) {
                    good = false;
                    break;
                }
            }
            if (good) {
                return candidate;
            }
        }
        return "";
    }
};

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

Задача: 202. Happy Number
Сложность: easy

Напишите алгоритм, определяющий, является ли число n счастливым.
Счастливое число — это такое число, которое в результате повторяющейся замены на сумму квадратов его цифр в конечном счёте становится равным 1.
Если процесс зацикливается и никогда не приводит к 1, число не является счастливым.

Пример:

Input: n = 19 Output: true
Пояснение:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1 ✅

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

1⃣Определяем функцию getNext(n), которая находит сумму квадратов всех цифр числа n.

2⃣Используем HashSet, чтобы отслеживать уже встреченные числа. Если мы снова увидим уже встреченное число — значит, попали в цикл.

3⃣Если на каком-то шаге число стало равным 1 — это счастливое число.

😎 Решение:

class Solution {
public:
    int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int digit = n % 10;
            n = n / 10;
            totalSum += digit * digit;
        }
        return totalSum;
    }

    bool isHappy(int n) {
        unordered_set<int> seen;
        while (n != 1 && seen.find(n) == seen.end()) {
            seen.insert(n);
            n = getNext(n);
        }
        return n == 1;
    }
};

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

Задача: 19. Remove Nth Node From End of List
Сложность: medium

Учитывая заголовок связанного списка, удалите n-й узел с конца списка и верните его заголовок.

Пример:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

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

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

2⃣Сдвигаем fast на n шагов вперёд, чтобы создать нужную дистанцию.

3⃣Затем двигаем fast и slow вместе до конца списка. Удаляем нужный узел, обновляя prev->next.

😎 Решение:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *slow = head, *fast = head;
        ListNode *prev = new ListNode(0, head);
        ListNode *answer = prev;

        while (n > 1) {
            fast = fast->next;
            n--;
        }

        while (fast->next) {
            fast = fast->next;
            slow = slow->next;
            prev = prev->next;
        }

        prev->next = slow->next;
        return answer->next;
    }
};

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