Задача: 474. Ones and Zeroes
Сложность: medium

Дан массив двоичных строк strs и два целых числа m и n.
Верните размер наибольшего подмножества strs, такого что в подмножестве содержится не более m нулей и n единиц.
Множество x является подмножеством множества y, если все элементы множества x также являются элементами множества y.

Пример:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.

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

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

2⃣Считаем количество нулей и единиц в каждом подмножестве.

3⃣Выбираем наибольшее подмножество, соответствующее условиям, и возвращаем его размер.

😎 Решение:

#include <vector>
#include <string>
#include <algorithm>

class Solution {
public:
    int findMaxForm(std::vector<std::string>& strs, int m, int n) {
        int maxlen = 0;
        for (int i = 0; i < (1 << strs.size()); ++i) {
            int zeroes = 0, ones = 0, len = 0;
            for (int j = 0; j < 32; ++j) {
                if ((i & (1 << j)) != 0) {
                    auto count = countZeroesOnes(strs[j]);
                    zeroes += count[0];
                    ones += count[1];
                    if (zeroes > m || ones > n)
                        break;
                    ++len;
                }
            }
            if (zeroes <= m && ones <= n)
                maxlen = std::max(maxlen, len);
        }
        return maxlen;
    }

    std::vector<int> countZeroesOnes(const std::string& s) {
        std::vector<int> c(2, 0);
        for (char ch : s) {
            ++c[ch - '0'];
        }
        return c;
    }
};

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

Задача: 952. Largest Component Size by Common Factor
Сложность: hard

Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае.

Пример:

Input: nums = [4,6,15,35]
Output: 4

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

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

2⃣Использовать алгоритм Union-Find для объединения узлов в связные компоненты.
Для каждого числа в массиве nums найти его простые делители и использовать их для объединения узлов.

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

😎 Решение:

class Solution {
public:
    int largestComponentSize(vector<int>& nums) {
        unordered_map<int, int> parent;
        unordered_map<int, int> rank;
        
        for (int num : nums) {
            parent[num] = num;
            rank[num] = 0;
        }
        
        function<int(int)> find = [&](int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        };
        
        auto unionFind = [&](int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                if (rank[rootX] > rank[rootY]) {
                    parent[rootY] = rootX;
                } else if (rank[rootX] < rank[rootY]) {
                    parent[rootX] = rootY;
                } else {
                    parent[rootY] = rootX;
                    rank[rootX]++;
                }
            }
        };
        
        auto primeFactors = [&](int n) {
            unordered_set<int> factors;
            int d = 2;
            while (d * d <= n) {
                while (n % d == 0) {
                    factors.insert(d);
                    n /= d;
                }
                d++;
            }
            if (n > 1) {
                factors.insert(n);
            }
            return factors;
        };
        
        unordered_map<int, vector<int>> primeToIndex;
        for (int num : nums) {
            auto primes = primeFactors(num);
            for (int prime : primes) {
                primeToIndex[prime].push_back(num);
            }
        }
        
        for (const auto& primes : primeToIndex) {
            for (int i = 1; i < primes.second.size(); i++) {
                unionFind(primes.second[0], primes.second[i]);
            }
        }
        
        unordered_map<int, int> size;
        for (int num : nums) {
            int root = find(num);
            size[root]++;
        }
        
        int maxSize = 0;
        for (const auto& [key, value] : size) {
            maxSize = max(maxSize, value);
        }
        
        return maxSize;
    }
};

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

Задача: 527. Word Abbreviation
Сложность: hard

Дано массив уникальных строк words, верните минимально возможные сокращения для каждого слова.
Правила сокращения строки следующие:
Первоначальное сокращение для каждого слова: первый символ, затем количество символов между первым и последним символом, затем последний символ.
Если более одного слова имеют одинаковое сокращение, выполните следующее:
Увеличьте префикс (символы в первой части) каждого из их сокращений на 1.
Например, начнем с слов ["abcdef", "abndef"], оба изначально сокращены как "a4f". Последовательность операций будет следующей: ["a4f", "a4f"] -> ["ab3f", "ab3f"] -> ["abc2f", "abn2f"].
Эта операция повторяется до тех пор, пока каждое сокращение не станет уникальным.
В конце, если сокращение не сделало слово короче, оставьте его в исходном виде.

Пример:

Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

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

1⃣ Инициализация и создание начальных сокращений:
Создайте массив для хранения сокращений и массив для отслеживания длины префикса каждого слова.
Для каждого слова создайте начальное сокращение с использованием первого символа, количества символов между первым и последним символом и последнего символа.

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

3⃣ Возврат результата:
Верните окончательные сокращения для каждого слова, убедившись, что они минимально возможны и уникальны.

😎 Решение:

class Solution {
public:
    vector<string> wordsAbbreviation(vector<string>& words) {
        int n = words.size();
        vector<string> ans(n);
        vector<int> prefix(n, 0);

        for (int i = 0; i < n; ++i)
            ans[i] = abbrev(words[i], 0);

        for (int i = 0; i < n; ++i) {
            while (true) {
                unordered_set<int> dupes;
                for (int j = i + 1; j < n; ++j) {
                    if (ans[i] == ans[j])
                        dupes.insert(j);
                }

                if (dupes.empty()) break;
                dupes.insert(i);
                for (int k : dupes) {
                    ans[k] = abbrev(words[k], ++prefix[k]);
                }
            }
        }

        return ans;
    }

private:
    string abbrev(const string& word, int i) {
        int n = word.size();
        if (n - i <= 3) return word;
        return word.substr(0, i + 1) + to_string(n - i - 2) + word.back();
    }
};

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

Задача: 1034. Coloring A Border
Сложность: medium

Вам дана целочисленная матричная сетка m x n и три целых числа row, col и color. Каждое значение в сетке представляет собой цвет квадрата сетки в данном месте. Два квадрата называются смежными, если они находятся рядом друг с другом в любом из 4 направлений. Два квадрата принадлежат одному связанному компоненту, если они имеют одинаковый цвет и являются смежными.

Граница связанного компонента - это все квадраты в связанном компоненте, которые либо смежны (по крайней мере) с квадратом, не входящим в компонент, либо находятся на границе сетки (в первой или последней строке или столбце). Вы должны окрасить границу связанного компонента, содержащего квадрат grid[row][col], в цвет. Верните конечную сетку.

Пример:

Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]

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

1⃣Поиск связанного компонента:
Используйте поиск в глубину (DFS) или поиск в ширину (BFS), чтобы найти все клетки, принадлежащие связанному компоненту, содержащему клетку grid[row][col].
Запомните все клетки, которые принадлежат этому компоненту.

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

3⃣Окрашивание границы:
Измените цвет всех клеток, являющихся границами, на заданный цвет.

😎 Решение:

class Solution {
public:
    vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
        int m = grid.size(), n = grid[0].size();
        int original_color = grid[row][col];
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        vector<pair<int, int>> borders;

        function<void(int, int)> dfs = [&](int r, int c) {
            visited[r][c] = true;
            bool is_border = false;
            for (auto [dr, dc] : vector<pair<int, int>>{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
                int nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                    if (!visited[nr][nc]) {
                        if (grid[nr][nc] == original_color) {
                            dfs(nr, nc);
                        } else {
                            is_border = true;
                        }
                    }
                } else {
                    is_border = true;
                }
            }
            if (is_border || r == 0 || r == m - 1 || c == 0 || c == n - 1) {
                borders.emplace_back(r, c);
            }
        };

        dfs(row, col);
        for (auto [r, c] : borders) {
            grid[r][c] = color;
        }

        return grid;
    }
};

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

Задача: 1014. Best Sightseeing Pair
Сложность: easy

Вам дан целочисленный массив values, в котором values[i] представляет собой значение i-й достопримечательности. Две достопримечательности i и j имеют расстояние j - i между собой. Оценка пары (i < j) достопримечательностей равна values[i] + values[j] + i - j: сумма значений достопримечательностей минус расстояние между ними. Возвращается максимальная оценка пары достопримечательностей.

Пример:

Input: values = [8,1,5,2,6]
Output: 11

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

1⃣Инициализация переменных:
Инициализируйте переменную max_score для хранения максимальной оценки пары.
Инициализируйте переменную max_i_plus_value для хранения максимального значения выражения values[i] + i при проходе по массиву.

2⃣Проход по массиву:
Пройдитесь по массиву начиная с первого элемента и для каждого элемента values[j] вычислите текущую оценку пары как values[j] - j + max_i_plus_value.
Обновите значение max_score, если текущая оценка больше.
Обновите значение max_i_plus_value, если текущий элемент values[j] + j больше предыдущего max_i_plus_value.

3⃣Возврат результата:
Верните значение max_score как максимальную оценку пары достопримечательностей.

😎 Решение:

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int max_score = 0;
        int max_i_plus_value = values[0];
        
        for (int j = 1; j < values.size(); ++j) {
            max_score = max(max_score, max_i_plus_value + values[j] - j);
            max_i_plus_value = max(max_i_plus_value, values[j] + j);
        }
        
        return max_score;
    }
};

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

Задача: 40. Combination Sum II
Сложность: medium

Дан массив candidates и число target. Найдите все уникальные комбинации, где сумма элементов равна target. Каждое число можно использовать только один раз.

Пример:

Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [[1,1,6],[1,2,5],[1,7],[2,6]]

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

1⃣Отсортировать и подсчитать количество каждого уникального элемента, чтобы избежать дубликатов.

2⃣Запустить рекурсивный backtrack, на каждом шаге выбирая доступный элемент, уменьшая его частоту и остаток target.

3⃣Если remain == 0 — сохранить комбинацию; иначе — откатить шаг (уменьшение глубины, восстановление частоты и удаление элемента из комбинации).

😎 Решение:

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> results;
        vector<int> comb;
        map<int, int> counter;
        for (int candidate : candidates) {
            counter[candidate]++;
        }
        vector<pair<int, int>> counterList(counter.begin(), counter.end());
        backtrack(comb, target, 0, counterList, results);
        return results;
    }

private:
    void backtrack(vector<int>& comb, int remain, int curr,
                   vector<pair<int, int>>& counter,
                   vector<vector<int>>& results) {
        if (remain == 0) {
            results.push_back(comb);
            return;
        } else if (remain < 0) {
            return;
        }

        for (int nextCurr = curr; nextCurr < counter.size(); ++nextCurr) {
            auto& [candidate, freq] = counter[nextCurr];
            if (freq == 0) continue;

            comb.push_back(candidate);
            --freq;

            backtrack(comb, remain - candidate, nextCurr, counter, results);

            ++freq;
            comb.pop_back();
        }
    }
};

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

🔥 Скрытые вакансии с удаленной работой для C/C++ разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.

🔹 C/C++ Jobs | Вакансии

🔸 Все каналы с вакансиями

Задача: 33. Search in Rotated Sorted Array
Сложность: medium

Дан массив nums, отсортированный по возрастанию и повернутый на некотором неизвестном индексе. Необходимо найти индекс элемента target. Если он не найден — вернуть -1. Решение должно работать за O(log n).

Пример:

Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4

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

1⃣Инициализируем границы бинарного поиска: left = 0, right = n-1.

2⃣В цикле проверяем значение в середине. Если совпадает с target — возвращаем индекс.

3⃣Определяем, какая половина массива отсортирована, и сужаем поиск к той части, где может находиться target.

😎 Решение:

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int m = (left + right) / 2;
            if (nums[m] == target) {
                return m;
            }
            if (nums[left] <= nums[m]) { // левая часть отсортирована
                if (nums[left] <= target && target < nums[m]) {
                    right = m - 1;
                } else {
                    left = m + 1;
                }
            } else { // правая часть отсортирована
                if (nums[m] < target && target <= nums[right]) {
                    left = m + 1;
                } else {
                    right = m - 1;
                }
            }
        }
        return -1;
    }
};

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

Задача: 37. Sudoku Solver
Сложность: hard

Напишите программу, которая решает судоку, заполняя пустые клетки, соблюдая правила: цифры от 1 до 9 должны встречаться ровно один раз в каждой строке, столбце и каждом из девяти 3×3 блоков.

Пример:

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

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

1⃣Создаем матрицы для отслеживания наличия цифр 1–9 в строках, столбцах и блоках 3×3. Заполняем их по уже заданным цифрам на доске.

2⃣Запускаем рекурсивную функцию backtrack, которая ищет пустые клетки и пытается поместить туда цифры от 1 до 9, проверяя допустимость по строке, столбцу и блоку.

3⃣Если дошли до конца доски — судоку решено. Иначе откатываемся (backtrack) и пробуем другие варианты.

😎 Решение:

class Solution {
    int n = 3;
    int N = n * n;
    std::vector<std::vector<int>> rows, cols, boxes;
    std::vector<std::vector<char>> board;
    bool sudoku_solved = false;

public:
    Solution() : rows(N, std::vector<int>(N + 1, 0)), cols(N, std::vector<int>(N + 1, 0)), boxes(N, std::vector<int>(N + 1, 0)) {}

    bool could_place(int d, int row, int col) {
        int idx = (row / n) * n + col / n;
        return rows[row][d] == 0 && cols[col][d] == 0 && boxes[idx][d] == 0;
    }

    void place_or_remove(int d, int row, int col, bool place) {
        int idx = (row / n) * n + col / n;
        int delta = place ? 1 : -1;
        rows[row][d] += delta;
        cols[col][d] += delta;
        boxes[idx][d] += delta;
        board[row][col] = place ? d + '0' : '.';
    }

    void backtrack(int row = 0, int col = 0) {
        if (col == N) col = 0, row++;
        if (row == N) {
            sudoku_solved = true;
            return;
        }

        if (board[row][col] == '.') {
            for (int d = 1; d <= 9 && !sudoku_solved; d++) {
                if (could_place(d, row, col)) {
                    place_or_remove(d, row, col, true);
                    backtrack(row, col + 1);
                    if (!sudoku_solved) place_or_remove(d, row, col, false);
                }
            }
        } else
            backtrack(row, col + 1);
    }

    void solveSudoku(std::vector<std::vector<char>>& in_board) {
        board = in_board;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] != '.') {
                    int d = board[i][j] - '0';
                    place_or_remove(d, i, j, true);
                }
            }
        }
        backtrack();
        in_board = board;
    }
};

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

Задача: 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;
}

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

Задача: 834. Sum of Distances in Tree
Сложность: hard

Есть неориентированное связное дерево с n узлами, пронумерованными от 0 до n - 1, и n - 1 ребрами.

Вам даны целое число n и массив edges, где edges[i] = [ai, bi] указывает, что существует ребро между узлами ai и bi в дереве.

Верните массив answer длиной n, где answer[i] — это сумма расстояний между i-м узлом в дереве и всеми другими узлами.

Пример:

Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: The tree is shown above.
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.
Hence, answer[0] = 8, and so on.

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

1⃣Постройте дерево и выполните обход в глубину (DFS) для расчета количества узлов в поддереве и суммы расстояний до всех узлов поддерева.

2⃣На основе полученных данных рассчитайте сумму расстояний для корня дерева.

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

😎 Решение:

#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    vector<int> ans, count;
    vector<unordered_set<int>> graph;
    int N;

    vector<int> sumOfDistancesInTree(int N, vector<vector<int>>& edges) {
        this->N = N;
        graph.resize(N);
        ans.resize(N);
        count.resize(N, 1);

        for (auto& edge : edges) {
            graph[edge[0]].insert(edge[1]);
            graph[edge[1]].insert(edge[0]);
        }

        dfs(0, -1);
        dfs2(0, -1);
        return ans;
    }

    void dfs(int node, int parent) {
        for (int child : graph[node]) {
            if (child != parent) {
                dfs(child, node);
                count[node] += count[child];
                ans[node] += ans[child] + count[child];
            }
        }
    }

    void dfs2(int node, int parent) {
        for (int child : graph[node]) {
            if (child != parent) {
                ans[child] = ans[node] - count[child] + N - count[child];
                dfs2(child, node);
            }
        }
    }
};

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

Задача: 1137. N-th Tribonacci Number
Сложность: easy

Трибоначчи последовательность Tn определяется следующим образом:

T0 = 0, T1 = 1, T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 для n >= 0.

Дано n, вернуть значение Tn.

Пример:

Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

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

1⃣Если n < 3, вернуть значение n-го терма, как указано в описании задачи.

2⃣Инициализировать a, b и c как базовые случаи. Установить a = 0, b = 1, c = 1.

3⃣Для следующих n - 2 шагов обновлять a, b, c следующим образом: a = b, b = c, c = a + b + c. Вернуть c.

😎 Решение:

class Solution {
public:
    int tribonacci(int n) {
        if (n < 3) {
            return n > 0 ? 1 : 0;
        }
        
        int a = 0, b = 1, c = 1;
        for (int i = 0; i < n - 2; ++i) {
            int tmp = a + b + c;
            a = b;
            b = c;
            c = tmp;
        }
        
        return c;
    }
};

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