C/C++ | LeetCode

Задача: 363. Max Sum of Rectangle No Larger Than K Сложность: hard Дана матрица размером m x n и целое число k, вернуть максимальную сумму прямоугольника в матрице, такая что его сумма не превышает k. Гарантируется, что будет прямоугольник с суммой, не превышающей k. Пример:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).

👨‍💻 Алгоритм: 1⃣Создать вспомогательную функцию updateResult, которая будет находить максимальную сумму подмассива в одномерном массиве, не превышающую k. 2⃣Преобразовать каждую подматрицу в одномерный массив и применить к ней функцию updateResult. 3⃣Вернуть максимальную найденную сумму. 😎 Решение:

#include <vector>
#include <set>
#include <algorithm>
#include <climits>

class Solution {
public:
    int result = INT_MIN;

    void updateResult(std::vector<int>& nums, int k) {
        int sum = 0;
        std::set<int> sortedSum;
        sortedSum.insert(0);

        for (int num : nums) {
            sum += num;
            auto it = sortedSum.lower_bound(sum - k);
            if (it != sortedSum.end()) {
                result = std::max(result, sum - *it);
            }
            sortedSum.insert(sum);
        }
    }

    int maxSumSubmatrix(std::vector<std::vector<int>>& matrix, int k) {
        int rows = matrix.size();
        int cols = matrix[0].size();

        for (int i = 0; i < rows; ++i) {
            std::vector<int> rowSum(cols, 0);
            for (int row = i; row < rows; ++row) {
                for (int col = 0; col < cols; ++col) {
                    rowSum[col] += matrix[row][col];
                }
                updateResult(rowSum, k);
                if (result == k) {
                    return result;
                }
            }
        }
        return result;
    }
};

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

Задача: 46. Permutations Сложность: medium Дан массив nums, состоящий из различных целых чисел. Верните все возможные перестановки. Ответ может быть в любом порядке. Пример:

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

👨‍💻 Алгоритм: 1⃣Если размер текущей последовательности curr равен размеру nums, добавить копию curr в ans и выйти 2⃣Перебрать все числа из nums. Если число ещё не в curr, добавить его, вызвать рекурсию, затем удалить (backtrack) 3⃣Запустить backtrack с пустым curr. В конце вернуть ans 😎 Решение:

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> curr = {};
        backtrack(curr, ans, nums);
        return ans;
    }

    void backtrack(vector<int>& curr, vector<vector<int>>& ans,
                   vector<int>& nums) {
        if (curr.size() == nums.size()) {
            ans.push_back(curr);
            return;
        }

        for (int num : nums) {
            if (find(curr.begin(), curr.end(), num) == curr.end()) {
                curr.push_back(num);
                backtrack(curr, ans, nums);
                curr.pop_back();
            }
        }
    }
};

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

Задача: 541. Reverse String II Сложность: easy Дана строка s и целое число k, переверните первые k символов для каждых 2k символов, начиная с начала строки. Если осталось меньше k символов, переверните все. Если осталось меньше 2k, но больше или равно k символов, переверните первые k символов и оставьте остальные как есть. Пример:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

👨‍💻 Алгоритм: 1⃣Разворачиваем каждый блок из 2k символов непосредственно. Каждый блок начинается с кратного 2k: например, 0, 2k, 4k, 6k и так далее. 2⃣Будьте внимательны, если символов недостаточно, блок может не быть перевернут. 3⃣Для разворота блока символов с позиции i до j, меняем местами символы на позициях i++ и j--. 😎 Решение:

class Solution {
public:
    string reverseStr(string s, int k) {
        vector<char> a(s.begin(), s.end());
        for (int start = 0; start < a.size(); start += 2 * k) {
            int i = start, j = min(start + k - 1, (int)a.size() - 1);
            while (i < j) {
                char tmp = a[i];
                a[i++] = a[j];
                a[j--] = tmp;
            }
        }
        return string(a.begin(), a.end());
    }
};

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

Задача: 342. Power of Four Сложность: easy Дано целое число n. Верните true, если оно является степенью числа четыре. В противном случае верните false. Целое число n является степенью числа четыре, если существует целое число x такое, что n == 4^x. Пример:

Input: n = 16
Output: true

👨‍💻 Алгоритм: 1⃣Проверка неотрицательности: Убедитесь, что n больше нуля, так как степени числа четыре всегда положительны. 2⃣Проверка логарифмом: Используйте логарифм для проверки, является ли число степенью четырех. Число n является степенью четырех, если логарифм n по основанию 4 является целым числом. 3⃣Проверка побитовым оператором: Число является степенью четырех, если оно является степенью двух (только один бит установлен) и количество нулей после этого бита четно. 😎 Решение:

class Solution {
public:
    bool isPowerOfFour(int n) {
        if (n <= 0) return false;
        double log_n_base_4 = log(n) / log(4);
        return log_n_base_4 == floor(log_n_base_4);
    }
};

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

Задача: 436. Find Right Interval Сложность: medium Дан массив интервалов, где intervals[i] = [starti, endi] и каждый starti уникален. Правый интервал для интервала i - это интервал j, такой что startj >= endi и startj минимален. Обратите внимание, что i может быть равен j. Верните массив индексов правых интервалов для каждого интервала i. Если правого интервала для интервала i не существует, то поставьте -1 в индекс i. Пример:

Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

👨‍💻 Алгоритм: 1⃣Интуиция за этим подходом такова: если мы будем поддерживать два массива - intervals, который отсортирован по начальным точкам, и endIntervals, который отсортирован по конечным точкам. Когда мы выбираем первый интервал (или, скажем, i-ый интервал) из массива endIntervals, мы можем определить подходящий интервал, удовлетворяющий критериям правого интервала, просматривая интервалы в массиве intervals слева направо, так как массив intervals отсортирован по начальным точкам. Допустим, индекс выбранного элемента из массива intervals окажется j. 2⃣Теперь, когда мы выбираем следующий интервал (скажем, (i+1)-ый интервал) из массива endIntervals, нам не нужно начинать сканирование массива intervals с первого индекса. Вместо этого мы можем начать прямо с индекса j, где мы остановились в последний раз в массиве intervals. Это потому, что конечная точка, соответствующая endIntervals[i+1], больше, чем та, которая соответствует endIntervals[i], и ни один из интервалов из intervals[k], таких что 0 < k < j, не удовлетворяет критериям правого соседа с endIntervals[i], а значит, и с endIntervals[i+1] тоже. 3⃣Если в какой-то момент мы достигнем конца массива, т.е. j = intervals.length, и ни один элемент, удовлетворяющий критериям правого интервала, не будет доступен в массиве intervals, мы ставим -1 в соответствующую запись res. То же самое касается всех оставшихся элементов массива endIntervals, конечные точки которых даже больше, чем у предыдущего интервала. Также мы используем хеш-таблицу hash изначально, чтобы сохранить индексы, соответствующие интервалам, даже после сортировки. 😎 Решение:

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        vector<vector<int>> endIntervals = intervals;
        unordered_map<vector<int>, int> hash;
        for (int i = 0; i < intervals.size(); ++i) {
            hash[intervals[i]] = i;
        }
        sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b) { return a[0] < b[0]; });
        sort(endIntervals.begin(), endIntervals.end(), [](vector<int>& a, vector<int>& b) { return a[1] < b[1]; });
        int j = 0;
        vector<int> res(intervals.size());
        for (int i = 0; i < endIntervals.size(); ++i) {
            while (j < intervals.size() && intervals[j][0] < endIntervals[i][1]) {
                j++;
            }
            res[hash[endIntervals[i]]] = j == intervals.size() ? -1 : hash[intervals[j]];
        }
        return res;
    }
};

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

Задача: 112. Path Sum Сложность: easy Дан корень бинарного дерева и целое число targetSum. Верните true, если существует путь от корня до листового узла, сумма значений по которому равна targetSum. Пример:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true

👨‍💻 Алгоритм: 1⃣Инициализация: создаём два стека — один для узлов (node_stack), второй для текущей оставшейся суммы (sum_stack). Начинаем с корня и суммы sum - root->val. 2⃣Обход: в цикле извлекаем узел и соответствующую сумму. Если узел — лист, и сумма равна 0, возвращаем true. 3⃣Добавляем потомков узла в стек, уменьшая текущую сумму на их значения. 😎 Решение:

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (root == NULL) return false;

        std::stack<TreeNode*> node_stack;
        std::stack<int> sum_stack;

        node_stack.push(root);
        sum_stack.push(sum - root->val);

        while (!node_stack.empty()) {
            TreeNode* node = node_stack.top(); node_stack.pop();
            int curr_sum = sum_stack.top(); sum_stack.pop();

            if (!node->left && !node->right && curr_sum == 0) {
                return true;
            }

            if (node->right) {
                node_stack.push(node->right);
                sum_stack.push(curr_sum - node->right->val);
            }

            if (node->left) {
                node_stack.push(node->left);
                sum_stack.push(curr_sum - node->left->val);
            }
        }

        return false;
    }
};

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

Задача: 759. Employee Free Time Сложность: hard Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину. Пример:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]

👨‍💻 Алгоритм: 1⃣Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам. 2⃣Объедините пересекающиеся интервалы в один. 3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время. 😎 Решение:

class Interval {
public:
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};

class Solution {
public:
    vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {
        vector<Interval> intervals;
        for (const auto& employee : schedule) {
            intervals.insert(intervals.end(), employee.begin(), employee.end());
        }
        
        sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
            return a.start < b.start;
        });
        
        vector<Interval> merged;
        for (const auto& interval : intervals) {
            if (merged.empty() || merged.back().end < interval.start) {
                merged.push_back(interval);
            } else {
                merged.back().end = max(merged.back().end, interval.end);
            }
        }
        
        vector<Interval> freeTime;
        for (int i = 1; i < merged.size(); ++i) {
            if (merged[i].start > merged[i-1].end) {
                freeTime.push_back(Interval(merged[i-1].end, merged[i].start));
            }
        }
        
        return freeTime;
    }
};

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

Курс "Дизайн карточек для WB и Ozon". Бесплатно и с нуля Дизайнер карточек для маркетплейсов — востребованная и доходная профессия 💰 Научись ей бесплатно! - Бесплатный доступ - Разбор ДЗ от наставника - Мощные кейсы в портфолио Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

Задача: 718. Maximum Length of Repeated Subarray Сложность: medium Если даны два целочисленных массива nums1 и nums2, верните максимальную длину подмассива, который встречается в обоих массивах. Пример:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3

👨‍💻 Алгоритм: 1⃣Создайте двумерный массив для хранения длин общих подмассивов. 2⃣Используйте динамическое программирование для нахождения максимальной длины общего подмассива. 3⃣Итеративно обновляйте массив, сравнивая элементы обоих массивов и обновляя максимальную длину подмассива. 😎 Решение:

int findLength(vector<int>& nums1, vector<int>& nums2) {
    vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
    int maxLength = 0;
    for (int i = nums1.size() - 1; i >= 0; i--) {
        for (int j = nums2.size() - 1; j >= 0; j--) {
            if (nums1[i] == nums2[j]) {
                dp[i][j] = dp[i + 1][j + 1] + 1;
                maxLength = max(maxLength, dp[i][j]);
            }
        }
    }
    return maxLength;
}

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

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный курс по искусственному интеллекту! Мы подготовили для тебя 5 занятий по теме «Разработка нейро-сотрудников на GPT». Пройди регистрацию для получения полного бесплатного доступа к курсу. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 104. Maximum Depth of Binary Tree Сложность: easy Дан корень бинарного дерева, верните его максимальную глубину. Максимальная глубина бинарного дерева — это количество узлов вдоль самого длинного пути от корневого узла до самого удалённого листового узла. Пример:

Input: root = [3,9,20,null,null,15,7] Output: 3

👨‍💻 Алгоритм: 1⃣Можно обойти дерево, используя стратегию поиска в глубину (DFS) или поиска в ширину (BFS). 2⃣Для данной задачи подойдёт несколько способов. 3⃣Здесь мы демонстрируем решение, реализованное с использованием стратегии DFS и рекурсии. 😎 Решение:

class Solution {
  public:
    int maxDepth(TreeNode *root) {
      if (root == NULL) {
        return 0;
      }
      return max(1 + maxDepth(root -> left), 1 + maxDepth(root -> right));
    }
};

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

Задача: 1207. Unique Number of Occurrences Сложность: easy Дан массив целых чисел arr. Верните true, если количество вхождений каждого значения в массиве уникально, или false в противном случае. Пример:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

👨‍💻 Алгоритм: 1⃣Сохраните частоты элементов массива arr в хэш-таблице freq. 2⃣Итерируйтесь по хэш-таблице freq и вставьте частоты всех уникальных элементов массива arr в хэш-набор freqSet. 3⃣Верните true, если размер хэш-набора freqSet равен размеру хэш-таблицы freq, иначе верните false. 😎 Решение:

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

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        unordered_map<int, int> freq;
        for (int num : arr) {
            freq[num]++;
        }
        unordered_set<int> freqSet;
        for (auto& pair : freq) {
            freqSet.insert(pair.second);
        }
        return freq.size() == freqSet.size();
    }
};

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

Задача: 1037. Valid Boomerang Сложность: easy Если задан массив points, где points[i] = [xi, yi] представляет точку на плоскости X-Y, верните true, если эти точки являются бумерангом. Бумеранг - это набор из трех точек, которые отличаются друг от друга и не являются прямой линией. Пример:

Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false

👨‍💻 Алгоритм: 1⃣Проверка уникальности точек: Убедитесь, что все три точки уникальны. Если любые две точки совпадают, то это не бумеранг. 2⃣Проверка на коллинеарность: Используйте определитель (или площадь параллелограмма) для проверки, находятся ли три точки на одной прямой. Если площадь параллелограмма, образованного тремя точками, равна нулю, то точки коллинеарны. 3⃣Результат: Если точки уникальны и не коллинеарны, верните true. В противном случае, верните false. 😎 Решение:

class Solution {
public:
    bool isBoomerang(vector<vector<int>>& points) {
        int x1 = points[0][0], y1 = points[0][1];
        int x2 = points[1][0], y2 = points[1][1];
        int x3 = points[2][0], y3 = points[2][1];
        return (x1 != x2 || y1 != y2) && (x1 != x3 || y1 != y3) && (x2 != x3 || y2 != y3) && (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) != 0;
    }
};

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

Задача: 72. Edit Distance Сложность: medium Даны две строки word1 и word2. Нужно найти минимальное количество операций (вставка, удаление, замена), чтобы преобразовать word1 в word2. Пример:

Input: word1 = "horse", word2 = "ros"
Output: 3
Пояснение:
horse → rorse (замена h на r)
rorse → rose (удаление r)
rose → ros (удаление e)

👨‍💻 Алгоритм: 1⃣Используем рекурсивный подход с кэшированием: minDistance(i, j) — минимальная стоимость преобразования word1[0..i-1] в word2[0..j-1] 2⃣Базовые случаи: если i == 0, нужно вставить j символов если j == 0, нужно удалить i символов 3⃣Рекурсия: если символы совпадают → переходим к предыдущим иначе: вставка (i, j-1) удаление (i-1, j) замена (i-1, j-1) → берём минимум из трёх и добавляем 1 😎 Решение:

class Solution {
public:
    vector<vector<int>> memo;

    int minDistance(string word1, string word2) {
        memo.resize(word1.length() + 1, vector<int>(word2.length() + 1, -1));
        return minDistanceRecur(word1, word2, word1.size(), word2.size());
    }

    int minDistanceRecur(string &word1, string &word2, int word1Index, int word2Index) {
        if (word1Index == 0) return word2Index;
        if (word2Index == 0) return word1Index;

        if (memo[word1Index][word2Index] != -1)
            return memo[word1Index][word2Index];

        int minEditDistance = 0;

        if (word1[word1Index - 1] == word2[word2Index - 1]) {
            minEditDistance = minDistanceRecur(word1, word2, word1Index - 1, word2Index - 1);
        } else {
            int insertOp = minDistanceRecur(word1, word2, word1Index, word2Index - 1);
            int deleteOp = minDistanceRecur(word1, word2, word1Index - 1, word2Index);
            int replaceOp = minDistanceRecur(word1, word2, word1Index - 1, word2Index - 1);
            minEditDistance = 1 + min(insertOp, min(deleteOp, replaceOp));
        }

        memo[word1Index][word2Index] = minEditDistance;
        return minEditDistance;
    }
};

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

Задача: 1464. Maximum Product of Two Elements in an Array Сложность: easy Дан массив целых чисел nums, выберите два разных индекса i и j этого массива. Верните максимальное значение (nums[i]-1)*(nums[j]-1). Пример:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, 
that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12. 

👨‍💻 Алгоритм: 1⃣Инициализируйте biggest = 0 и secondBiggest = 0. 2⃣Итерируйте по каждому элементу массива nums: Если текущий элемент больше biggest, обновите secondBiggest = biggest и biggest = текущий элемент. Иначе обновите secondBiggest, если текущий элемент больше secondBiggest. 3⃣Верните (biggest - 1) * (secondBiggest - 1). 😎 Решение:

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int biggest = 0;
        int secondBiggest = 0;
        for (int num : nums) {
            if (num > biggest) {
                secondBiggest = biggest;
                biggest = num;
            } else if (num > secondBiggest) {
                secondBiggest = num;
            }
        }
        return (biggest - 1) * (secondBiggest - 1);
    }
};

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

Задача: 1232. Check If It Is a Straight Line Сложность: easy Вам дан массив координат, coordinates[i] = [x, y], где [x, y] - координаты точки. Проверьте, образуют ли эти точки прямую линию в плоскости XY. Пример:

Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
Output: true

👨‍💻 Алгоритм: 1⃣Определение наклона: Вычисляем наклон между первыми двумя точками и используем его как эталон. 2⃣Проверка других точек: Для всех остальных точек проверяем, совпадает ли наклон, образуемый этими точками с первой точкой, с эталонным наклоном. 3⃣Если все наклоны совпадают, то все точки лежат на одной прямой. 😎 Решение:

class Solution {
public:
    bool checkStraightLine(vector<vector<int>>& coordinates) {
        int x0 = coordinates[0][0], y0 = coordinates[0][1];
        int x1 = coordinates[1][0], y1 = coordinates[1][1];
        
        for (const auto& point : coordinates) {
            int x = point[0], y = point[1];
            if ((x1 - x0) * (y - y0) != (y1 - y0) * (x - x0)) {
                return false;
            }
        }
        return true;
    }
};

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

Задача: 970. Powerful Integers Сложность: medium Даны три целых числа x, y и bound. Верните список всех мощных чисел, которые имеют значение меньше или равное bound. Целое число является мощным, если оно может быть представлено как x^i + y^j для некоторых целых чисел i >= 0 и j >= 0. Вы можете вернуть ответ в любом порядке. В вашем ответе каждое значение должно встречаться не более одного раза. Пример:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation:
2 = 20 + 30
3 = 21 + 30
4 = 20 + 31
5 = 21 + 31
7 = 22 + 31
9 = 23 + 30
10 = 20 + 32

👨‍💻 Алгоритм: 1⃣Вычислите степени a и b как логарифмы bound по основаниям x и y соответственно. Создайте множество powerfulIntegers для хранения результатов. 2⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers. 3⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers. 😎 Решение:

class Solution {
public:
    vector<int> powerfulIntegers(int x, int y, int bound) {
        int a = x == 1 ? bound : log(bound) / log(x);
        int b = y == 1 ? bound : log(bound) / log(y);
        unordered_set<int> powerfulIntegers;

        for (int i = 0; i <= a; i++) {
            for (int j = 0; j <= b; j++) {
                int value = pow(x, i) + pow(y, j);
                if (value <= bound) {
                    powerfulIntegers.insert(value);
                }
                if (y == 1) {
                    break;
                }
            }
            if (x == 1) {
                break;
            }
        }

        return vector<int>(powerfulIntegers.begin(), powerfulIntegers.end());
    }
};

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

Задача: 651. 4 Keys Keyboard Сложность: medium Представьте, что у вас есть специальная клавиатура со следующими клавишами: A: Напечатать одну букву "A" на экране. Ctrl-A: Выделить весь экран. Ctrl-C: Скопировать выделение в буфер. Ctrl-V: Печать буфера на экране с добавлением его после того, что уже было напечатано. Учитывая целое число n, верните максимальное количество букв 'A', которые можно напечатать на экране при нажатии не более n клавиш. Пример:

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

👨‍💻 Алгоритм: 1⃣Используйте динамическое программирование для отслеживания максимального количества букв 'A' на экране после каждого числа нажатий клавиш. 2⃣Итерируйтесь от 1 до n, вычисляя максимальное количество 'A' для каждой позиции, учитывая возможность вставки скопированного текста. 3⃣Возвращайте значение из таблицы динамического программирования для n нажатий клавиш. 😎 Решение:

public class Solution {
    public int MaxA(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + 1;
            for (int j = 2; j < i; j++) {
                dp[i] = Math.Max(dp[i], dp[j - 2] * (i - j + 1));
            }
        }
        return dp[n];
    }
}

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

Задача: 677. Map Sum Pairs Сложность: medium Создайте карту, которая позволяет выполнять следующие действия: Отображает строковый ключ на заданное значение. Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке. Реализуйте класс MapSum: MapSum() Инициализирует объект MapSum. void insert(String key, int val) Вставляет пару ключ-значение в карту. Если ключ уже существовал, исходная пара ключ-значение будет заменена на новую. int sum(string prefix) Возвращает сумму всех значений пар, у которых ключ начинается с данного префикса. Пример:

Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]

Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

👨‍💻 Алгоритм: 1⃣Для каждого ключа в карте проверить, начинается ли этот ключ с данного префикса. 2⃣Если ключ начинается с префикса, добавить его значение к ответу. 3⃣Вернуть полученную сумму как результат. 😎 Решение:

#include <unordered_map>
#include <string>

class MapSum {
    std::unordered_map<std::string, int> map;
public:
    MapSum() {}
    void insert(std::string key, int val) {
        map[key] = val;
    }
    int sum(std::string prefix) {
        int ans = 0;
        for (const auto& pair : map) {
            if (pair.first.find(prefix) == 0) {
                ans += pair.second;
            }
        }
        return ans;
    }
};

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

Ищу желающих выполнять задачи с помощью ИИ! Работа полностью на удаленке с зп до 150 000 рублей в месяц. Без опыта, нужен только телефон, занятость 3-6 часов в день. Всему обучат на бесплатном курсе и после возьму на работу: ✅ 3 дня уроков по 30 минут ✅ Домашки с проверкой и оплатой бонусами ✅ Плачу 10 тыс за каждую выполненную домашку Все кто пройдет курс, получат сертификат от школы с образовательной лицензией. ⚡ Набор заканчивается завтра. 👍 Для регистрации жмите кнопку "Зарегистрироваться": Зарегистрироваться #реклама 16+ ganstaagency.com О рекламодателе