Задача: 728. Self Dividing Numbers
Сложность: hard
Например, 128 является саморазделяющимся числом, потому что 128 % 1 == 0, 128 % 2 == 0 и 128 % 8 == 0. Саморазделяющееся число не может содержать цифру ноль. Если даны два целых числа left и right, верните список всех саморазделяющихся чисел в диапазоне [left, right].
Пример:
👨💻 Алгоритм:
1⃣Переберите все числа в диапазоне от left до right.
2⃣Для каждого числа проверьте, является ли оно саморазделяющимся: Разделите число на его цифры. Убедитесь, что ни одна цифра не равна нулю и число делится на каждую из своих цифр без остатка.
3⃣Добавьте саморазделяющиеся числа в результативный список и верните его.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Например, 128 является саморазделяющимся числом, потому что 128 % 1 == 0, 128 % 2 == 0 и 128 % 8 == 0. Саморазделяющееся число не может содержать цифру ноль. Если даны два целых числа left и right, верните список всех саморазделяющихся чисел в диапазоне [left, right].
Пример:
Input: left = 1, right = 22
Output: [1,2,3,4,5,6,7,8,9,11,12,15,22]
👨💻 Алгоритм:
1⃣Переберите все числа в диапазоне от left до right.
2⃣Для каждого числа проверьте, является ли оно саморазделяющимся: Разделите число на его цифры. Убедитесь, что ни одна цифра не равна нулю и число делится на каждую из своих цифр без остатка.
3⃣Добавьте саморазделяющиеся числа в результативный список и верните его.
😎 Решение:
public class Solution {
public IList<int> SelfDividingNumbers(int left, int right) {
List<int> result = new List<int>();
for (int num = left; num <= right; num++) {
if (IsSelfDividing(num)) {
result.Add(num);
}
}
return result;
}
private bool IsSelfDividing(int num) {
int n = num;
while (n > 0) {
int digit = n % 10;
if (digit == 0 || num % digit != 0) {
return false;
}
n /= 10;
}
return true;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1203. Sort Items by Groups Respecting Dependencies
Сложность: hard
Есть n предметов, каждый из которых принадлежит нулевой или одной из m групп, где group[i] — это группа, к которой принадлежит i-й предмет, и равно -1, если i-й предмет не принадлежит никакой группе. Предметы и группы имеют индексацию с нуля. Группа может не иметь ни одного предмета.
Верните отсортированный список предметов таким образом:
Предметы, принадлежащие одной группе, расположены рядом друг с другом в отсортированном списке.
Существуют некоторые отношения между этими предметами, где beforeItems[i] — это список, содержащий все предметы, которые должны быть перед i-м предметом в отсортированном массиве (слева от i-го предмета).
Верните любое решение, если существует более одного решения, и верните пустой список, если решения не существует.
Пример:
👨💻 Алгоритм:
1⃣Инициализация и создание графов:
Присвоить уникальные идентификаторы группам для элементов без группы.
Создать два графа: item_graph для элементов и group_graph для групп. Также создать два массива для учета входящих рёбер для элементов и групп.
2⃣Построение графов:
Пройти по массиву beforeItems и добавить зависимости между элементами в item_graph, увеличивая счётчик входящих рёбер.
Если элементы принадлежат разным группам, добавить зависимость между группами в group_graph, увеличивая счётчик входящих рёбер.
3⃣Топологическая сортировка и создание итогового списка:
Выполнить топологическую сортировку для элементов и групп. Если есть цикл, вернуть пустой список.
Создать итоговый список, добавляя отсортированные элементы каждой группы.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Есть n предметов, каждый из которых принадлежит нулевой или одной из m групп, где group[i] — это группа, к которой принадлежит i-й предмет, и равно -1, если i-й предмет не принадлежит никакой группе. Предметы и группы имеют индексацию с нуля. Группа может не иметь ни одного предмета.
Верните отсортированный список предметов таким образом:
Предметы, принадлежащие одной группе, расположены рядом друг с другом в отсортированном списке.
Существуют некоторые отношения между этими предметами, где beforeItems[i] — это список, содержащий все предметы, которые должны быть перед i-м предметом в отсортированном массиве (слева от i-го предмета).
Верните любое решение, если существует более одного решения, и верните пустой список, если решения не существует.
Пример:
Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]
👨💻 Алгоритм:
1⃣Инициализация и создание графов:
Присвоить уникальные идентификаторы группам для элементов без группы.
Создать два графа: item_graph для элементов и group_graph для групп. Также создать два массива для учета входящих рёбер для элементов и групп.
2⃣Построение графов:
Пройти по массиву beforeItems и добавить зависимости между элементами в item_graph, увеличивая счётчик входящих рёбер.
Если элементы принадлежат разным группам, добавить зависимость между группами в group_graph, увеличивая счётчик входящих рёбер.
3⃣Топологическая сортировка и создание итогового списка:
Выполнить топологическую сортировку для элементов и групп. Если есть цикл, вернуть пустой список.
Создать итоговый список, добавляя отсортированные элементы каждой группы.
😎 Решение:
public class Solution {
public int[] SortItems(int n, int m, int[] group, IList<IList<int>> beforeItems) {
int groupId = m;
for (int i = 0; i < n; i++) if (group[i] == -1) group[i] = groupId++;
var itemGraph = new Dictionary<int, List<int>>();
var groupGraph = new Dictionary<int, List<int>>();
int[] itemIndegree = new int[n], groupIndegree = new int[groupId];
for (int i = 0; i < n; i++) itemGraph[i] = new List<int>();
for (int i = 0; i < groupId; i++) groupGraph[i] = new List<int>();
for (int curr = 0; curr < n; curr++) {
foreach (var prev in beforeItems[curr]) {
itemGraph[prev].Add(curr);
itemIndegree[curr]++;
if (group[curr] != group[prev]) {
groupGraph[group[prev]].Add(group[curr]);
groupIndegree[group[curr]]++;
}
}
}
var itemOrder = TopologicalSort(itemGraph, itemIndegree);
var groupOrder = TopologicalSort(groupGraph, groupIndegree);
if (itemOrder.Count == 0 || groupOrder.Count == 0) return new int[0];
var orderedGroups = new Dictionary<int, List<int>>();
foreach (var item in itemOrder) {
if (!orderedGroups.ContainsKey(group[item])) orderedGroups[group[item]] = new List<int>();
orderedGroups[group[item]].Add(item);
}
var answerList = new List<int>();
foreach (var groupIndex in groupOrder) {
if (orderedGroups.ContainsKey(groupIndex)) answerList.AddRange(orderedGroups[groupIndex]);
}
return answerList.ToArray();
}
private List<int> TopologicalSort(Dictionary<int, List<int>> graph, int[] indegree) {
var visited = new List<int>();
var stack = new Stack<int>();
foreach (var key in graph.Keys) if (indegree[key] == 0) stack.Push(key);
while (stack.Count > 0) {
var curr = stack.Pop();
visited.Add(curr);
foreach (var next in graph[curr]) if (--indegree[next] == 0) stack.Push(next);
}
return visited.Count == graph.Keys.Count ? visited : new List<int>();
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 462. Minimum Moves to Equal Array Elements II
Сложность: medium
Дан массив целых чисел nums размера n, вернуть минимальное количество ходов, необходимых для того, чтобы сделать все элементы массива равными.
В одном ходе вы можете увеличить или уменьшить элемент массива на 1.
Тестовые случаи составлены так, что ответ поместится в 32-битное целое число.
Пример:
👨💻 Алгоритм:
1⃣Найти минимальный и максимальный элементы в массиве. Пусть k будет числом, к которому должны быть приведены все элементы массива.
2⃣Перебирать значения k в диапазоне между минимальным и максимальным элементами, вычисляя количество ходов, необходимых для каждого k.
3⃣Определить минимальное количество ходов среди всех возможных k, что и будет конечным результатом.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан массив целых чисел nums размера n, вернуть минимальное количество ходов, необходимых для того, чтобы сделать все элементы массива равными.
В одном ходе вы можете увеличить или уменьшить элемент массива на 1.
Тестовые случаи составлены так, что ответ поместится в 32-битное целое число.
Пример:
Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3] => [2,2,3] => [2,2,2]
👨💻 Алгоритм:
1⃣Найти минимальный и максимальный элементы в массиве. Пусть k будет числом, к которому должны быть приведены все элементы массива.
2⃣Перебирать значения k в диапазоне между минимальным и максимальным элементами, вычисляя количество ходов, необходимых для каждого k.
3⃣Определить минимальное количество ходов среди всех возможных k, что и будет конечным результатом.
😎 Решение:
public class Solution {
public int MinMoves2(int[] nums) {
long ans = long.MaxValue;
int minval = int.MaxValue;
int maxval = int.MinValue;
foreach (int num in nums) {
minval = Math.Min(minval, num);
maxval = Math.Max(maxval, num);
}
for (int i = minval; i <= maxval; i++) {
long sum = 0;
foreach (int num in nums) {
sum += Math.Abs(num - i);
}
ans = Math.Min(ans, sum);
}
return (int) ans;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1071. Greatest Common Divisor of Strings
Сложность: easy
Для двух строк s и t мы говорим, что "t делит s", если и только если s = t + t + t + ... + t (т.е. t соединена сама с собой один или более раз).
Даны две строки str1 и str2, верните наибольшую строку x, такую что x делит и str1, и str2.
Пример:
👨💻 Алгоритм:
1⃣Найдите более короткую строку среди str1 и str2, для простоты пусть это будет str1.
2⃣Начните с base = str1 и проверьте, состоят ли обе строки str1 и str2 из множителей строки base. Если это так, верните base. В противном случае, попробуйте более короткую строку, удалив последний символ из base.
3⃣Если вы проверили все префиксные строки и не нашли строку GCD, верните "".
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Для двух строк s и t мы говорим, что "t делит s", если и только если s = t + t + t + ... + t (т.е. t соединена сама с собой один или более раз).
Даны две строки str1 и str2, верните наибольшую строку x, такую что x делит и str1, и str2.
Пример:
Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"
👨💻 Алгоритм:
1⃣Найдите более короткую строку среди str1 и str2, для простоты пусть это будет str1.
2⃣Начните с base = str1 и проверьте, состоят ли обе строки str1 и str2 из множителей строки base. Если это так, верните base. В противном случае, попробуйте более короткую строку, удалив последний символ из base.
3⃣Если вы проверили все префиксные строки и не нашли строку GCD, верните "".
😎 Решение:
public class Solution {
public bool Valid(string str1, string str2, int k) {
int len1 = str1.Length, len2 = str2.Length;
if (len1 % k > 0 || len2 % k > 0) {
return false;
} else {
string baseStr = str1.Substring(0, k);
int n1 = len1 / k, n2 = len2 / k;
return str1 == JoinWords(baseStr, n1) && str2 == JoinWords(baseStr, n2);
}
}
public string JoinWords(string str, int k) {
var sb = new StringBuilder();
for (int i = 0; i < k; i++) {
sb.Append(str);
}
return sb.ToString();
}
public string GcdOfStrings(string str1, string str2) {
int len1 = str1.Length, len2 = str2.Length;
for (int i = Math.Min(len1, len2); i >= 1; i--) {
if (Valid(str1, str2, i)) {
return str1.Substring(0, i);
}
}
return "";
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1150. Check If a Number Is Majority Element in a Sorted Array
Сложность: easy
Дан целочисленный массив nums, отсортированный в неубывающем порядке, и целое число target. Верните true, если target является элементом большинства, или false в противном случае.
Элемент большинства в массиве nums — это элемент, который встречается в массиве более чем nums.length / 2 раз.
Пример:
👨💻 Алгоритм:
1⃣Инициализация переменной count:
Инициализируйте переменную count значением 0..
2⃣Итерация по списку nums:
Пройдите по каждому элементу списка nums.
Если элемент num равен target, увеличьте значение переменной count.
3⃣Проверка условия мажоритарного элемента:
Если count больше чем половина длины списка nums, верните true.
В противном случае верните false.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дан целочисленный массив nums, отсортированный в неубывающем порядке, и целое число target. Верните true, если target является элементом большинства, или false в противном случае.
Элемент большинства в массиве nums — это элемент, который встречается в массиве более чем nums.length / 2 раз.
Пример:
Input: nums = [2,4,5,5,5,5,5,6,6], target = 5
Output: true
Explanation: The value 5 appears 5 times and the length of the array is 9.
Thus, 5 is a majority element because 5 > 9/2 is true.
👨💻 Алгоритм:
1⃣Инициализация переменной count:
Инициализируйте переменную count значением 0..
2⃣Итерация по списку nums:
Пройдите по каждому элементу списка nums.
Если элемент num равен target, увеличьте значение переменной count.
3⃣Проверка условия мажоритарного элемента:
Если count больше чем половина длины списка nums, верните true.
В противном случае верните false.
😎 Решение:
public class Solution {
public bool IsMajorityElement(int[] nums, int target) {
int count = 0;
foreach (int num in nums) {
if (num == target) {
count++;
}
}
return count > nums.Length / 2;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 908. Smallest Range I
Сложность: easy
Вам дан целочисленный массив nums и целое число k. За одну операцию вы можете выбрать любой индекс i, где 0 <= i < nums.length, и изменить nums[i] на nums[i] + x, где x - целое число из диапазона [-k, k]. Эту операцию можно применять не более одного раза для каждого индекса i. Оценка nums - это разница между максимальным и минимальным элементами в nums. Верните минимальную оценку nums после применения указанной операции не более одного раза для каждого индекса в нем.
Пример:
👨💻 Алгоритм:
1⃣Найти минимальное и максимальное значения массива nums.
2⃣Рассчитать потенциальные новые минимальные и максимальные значения после применения операции.
3⃣Вычислить минимальную оценку, сравнивая разницу между всеми возможными новыми минимальными и максимальными значениями.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Вам дан целочисленный массив nums и целое число k. За одну операцию вы можете выбрать любой индекс i, где 0 <= i < nums.length, и изменить nums[i] на nums[i] + x, где x - целое число из диапазона [-k, k]. Эту операцию можно применять не более одного раза для каждого индекса i. Оценка nums - это разница между максимальным и минимальным элементами в nums. Верните минимальную оценку nums после применения указанной операции не более одного раза для каждого индекса в нем.
Пример:
Input: nums = [1], k = 0
Output: 0
👨💻 Алгоритм:
1⃣Найти минимальное и максимальное значения массива nums.
2⃣Рассчитать потенциальные новые минимальные и максимальные значения после применения операции.
3⃣Вычислить минимальную оценку, сравнивая разницу между всеми возможными новыми минимальными и максимальными значениями.
😎 Решение:
public class Solution {
public int SmallestRangeI(int[] nums, int k) {
int minVal = int.MaxValue;
int maxVal = int.MinValue;
foreach (int num in nums) {
if (num < minVal) minVal = num;
if (num > maxVal) maxVal = num;
}
return Math.Max(0, (maxVal - k) - (minVal + k));
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 520. Detect Capital
Сложность: easy
Мы определяем правильное использование заглавных букв в слове, когда выполняется одно из следующих условий:
Все буквы в этом слове заглавные, как "USA".
Все буквы в этом слове строчные, как "leetcode".
Только первая буква в этом слове заглавная, как "Google".
Дана строка word. Верните true, если использование заглавных букв в ней правильное.
Пример:
👨💻 Алгоритм:
1⃣Шаблон для первого случая в регулярном выражении: [A-Z]*, где [A-Z] соответствует одной заглавной букве от 'A' до 'Z', а * означает повторение предыдущего шаблона 0 или более раз. Этот шаблон представляет "Все заглавные буквы".
2⃣Шаблон для второго случая в регулярном выражении: [a-z]*, где [a-z] соответствует одной строчной букве от 'a' до 'z'. Этот шаблон представляет "Все строчные буквы". Шаблон для третьего случая в регулярном выражении: [A-Z][a-z]*, где первая буква заглавная, а остальные строчные.
3⃣Объедините эти три шаблона: [A-Z]*|[a-z]*|[A-Z][a-z]*, где | означает "или". Мы можем объединить второй и третий случай, получив . [a-z]*, где . соответствует любому символу. Итоговый шаблон: [A-Z]*|.[a-z]*.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Мы определяем правильное использование заглавных букв в слове, когда выполняется одно из следующих условий:
Все буквы в этом слове заглавные, как "USA".
Все буквы в этом слове строчные, как "leetcode".
Только первая буква в этом слове заглавная, как "Google".
Дана строка word. Верните true, если использование заглавных букв в ней правильное.
Пример:
Input: word = "USA"
Output: true
👨💻 Алгоритм:
1⃣Шаблон для первого случая в регулярном выражении: [A-Z]*, где [A-Z] соответствует одной заглавной букве от 'A' до 'Z', а * означает повторение предыдущего шаблона 0 или более раз. Этот шаблон представляет "Все заглавные буквы".
2⃣Шаблон для второго случая в регулярном выражении: [a-z]*, где [a-z] соответствует одной строчной букве от 'a' до 'z'. Этот шаблон представляет "Все строчные буквы". Шаблон для третьего случая в регулярном выражении: [A-Z][a-z]*, где первая буква заглавная, а остальные строчные.
3⃣Объедините эти три шаблона: [A-Z]*|[a-z]*|[A-Z][a-z]*, где | означает "или". Мы можем объединить второй и третий случай, получив . [a-z]*, где . соответствует любому символу. Итоговый шаблон: [A-Z]*|.[a-z]*.
😎 Решение:
using System.Text.RegularExpressions;
public class Solution {
public bool DetectCapitalUse(string word) {
string pattern = @"[A-Z]*|.[a-z]*";
return Regex.IsMatch(word, pattern);
}
}
Ставь 👍 и забирай 📚 Базу знаний
Задача: 188. Best Time to Buy and Sell Stock IV
Сложность: hard
Дан массив целых чисел prices, где prices[i] - это цена данной акции в i-й день, и целое число k.
Найдите максимальную прибыль, которую вы можете получить. Вы можете завершить не более чем k транзакций, т.е. вы можете купить не более k раз и продать не более k раз.
Обратите внимание: Вы не можете участвовать в нескольких транзакциях одновременно (т.е., вы должны продать акцию, прежде чем снова купить).
Пример:
👨💻 Алгоритм:
1⃣Инициализация DP массива: Инициализируйте трехмерный массив dp, где dp[i][j][l] представляет максимальную прибыль на конец i-го дня с j оставшимися транзакциями и l акциями в портфеле. Начните с dp[0][0][0] = 0 (нет прибыли без акций и транзакций) и dp[0][1][1] = -prices[0] (покупка первой акции).
2⃣Вычисление переходов: Для каждого дня и каждого возможного количества транзакций вычислите возможные действия: держать акцию, не держать акцию, купить акцию, если j > 0, или продать акцию. Обновляйте dp с использованием:
dp[i][j][1] = max(dp[i−1][j][1], dp[i−1][j−1][0] - prices[i]) (максимум между удержанием акции и покупкой новой).
dp[i][j][0] = max(dp[i−1][j][0], dp[i−1][j][1] + prices[i]) (максимум между неудержанием акции и продажей).
3⃣Расчет результатов: По завершении всех дней, возвращайте максимальное значение dp[n-1][j][0] для всех j от 0 до k, что представляет максимальную прибыль без удержания акций на последний день. Обработайте специальный случай, когда 𝑘×2≥𝑛, чтобы избежать лишних расчетов.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Дан массив целых чисел prices, где prices[i] - это цена данной акции в i-й день, и целое число k.
Найдите максимальную прибыль, которую вы можете получить. Вы можете завершить не более чем k транзакций, т.е. вы можете купить не более k раз и продать не более k раз.
Обратите внимание: Вы не можете участвовать в нескольких транзакциях одновременно (т.е., вы должны продать акцию, прежде чем снова купить).
Пример:
Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
👨💻 Алгоритм:
1⃣Инициализация DP массива: Инициализируйте трехмерный массив dp, где dp[i][j][l] представляет максимальную прибыль на конец i-го дня с j оставшимися транзакциями и l акциями в портфеле. Начните с dp[0][0][0] = 0 (нет прибыли без акций и транзакций) и dp[0][1][1] = -prices[0] (покупка первой акции).
2⃣Вычисление переходов: Для каждого дня и каждого возможного количества транзакций вычислите возможные действия: держать акцию, не держать акцию, купить акцию, если j > 0, или продать акцию. Обновляйте dp с использованием:
dp[i][j][1] = max(dp[i−1][j][1], dp[i−1][j−1][0] - prices[i]) (максимум между удержанием акции и покупкой новой).
dp[i][j][0] = max(dp[i−1][j][0], dp[i−1][j][1] + prices[i]) (максимум между неудержанием акции и продажей).
3⃣Расчет результатов: По завершении всех дней, возвращайте максимальное значение dp[n-1][j][0] для всех j от 0 до k, что представляет максимальную прибыль без удержания акций на последний день. Обработайте специальный случай, когда 𝑘×2≥𝑛, чтобы избежать лишних расчетов.
😎 Решение:
public class Solution {
public int MaxProfit(int k, int[] prices) {
int n = prices.Length;
if (n == 0 || k == 0) return 0;
if (k * 2 >= n) {
int res = 0;
for (int i = 1; i < n; i++)
res += Math.Max(0, prices[i] - prices[i - 1]);
return res;
}
var dp = new int[n, k + 1, 2];
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k; j++) {
dp[i, j, 0] = Int32.MinValue / 2;
dp[i, j, 1] = Int32.MinValue / 2;
}
}
dp[0, 0, 0] = 0;
dp[0, 1, 1] = -prices[0];
for (int i = 1; i < n; i++) {
for (int j = 0; j <= k; j++) {
dp[i, j, 0] = Math.Max(dp[i - 1, j, 0], dp[i - 1, j, 1] + prices[i]);
if (j > 0)
dp[i, j, 1] = Math.Max(dp[i - 1, j, 1], dp[i - 1, j - 1, 0] - prices[i]);
}
}
int res = 0;
for (int j = 0; j <= k; j++)
res = Math.Max(res, dp[n - 1, j, 0]);
return res;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 647. Palindromic Substrings
Сложность: medium
Если задана строка s, верните количество палиндромных подстрок в ней. Строка является палиндромом, если она читается так же, как задом наперед. Подстрока - это непрерывная последовательность символов в строке.
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте счетчик для подсчета палиндромных подстрок.
2⃣Для каждой позиции в строке используйте два метода расширения: один для палиндромов нечетной длины и один для палиндромов четной длины.
3⃣Расширяйте от центра, проверяя, является ли подстрока палиндромом, и увеличивайте счетчик, если условие выполняется.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Если задана строка s, верните количество палиндромных подстрок в ней. Строка является палиндромом, если она читается так же, как задом наперед. Подстрока - это непрерывная последовательность символов в строке.
Пример:
Input: s = "abc"
Output: 3
👨💻 Алгоритм:
1⃣Инициализируйте счетчик для подсчета палиндромных подстрок.
2⃣Для каждой позиции в строке используйте два метода расширения: один для палиндромов нечетной длины и один для палиндромов четной длины.
3⃣Расширяйте от центра, проверяя, является ли подстрока палиндромом, и увеличивайте счетчик, если условие выполняется.
😎 Решение:
public class Solution {
public 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;
}
private int ExpandAroundCenter(string s, int left, int right) {
int count = 0;
while (left >= 0 && right < s.Length && s[left] == s[right]) {
count++;
left--;
right++;
}
return count;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 131. Palindrome Partitioning
Сложность: medium
Дана строка s. Разделите строку таким образом, чтобы каждая подстрока разделения была палиндромом. Верните все возможные варианты разделения строки s на палиндромы.
Пример:
👨💻 Алгоритм:
1⃣Инициация рекурсивного обхода:
В алгоритме обратного отслеживания (backtracking) мы рекурсивно пробегаем по строке, используя метод поиска в глубину (depth-first search). Для каждого рекурсивного вызова задаётся начальный индекс строки start.
Итеративно генерируем все возможные подстроки, начиная с индекса start. Индекс end увеличивается от start до конца строки.
2⃣Проверка на палиндром и продолжение поиска:
Для каждой сгенерированной подстроки проверяем, является ли она палиндромом.
Если подстрока оказывается палиндромом, она становится потенциальным кандидатом. Добавляем подстроку в currentList и выполняем поиск в глубину для оставшейся части строки. Если текущая подстрока заканчивается на индексе end, то end+1 становится начальным индексом для следующего рекурсивного вызова.
3⃣Возврат (Backtracking) и сохранение результатов:
Возвращаемся, если начальный индекс start больше или равен длине строки, и добавляем currentList в результат.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дана строка s. Разделите строку таким образом, чтобы каждая подстрока разделения была палиндромом. Верните все возможные варианты разделения строки s на палиндромы.
Пример:
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
👨💻 Алгоритм:
1⃣Инициация рекурсивного обхода:
В алгоритме обратного отслеживания (backtracking) мы рекурсивно пробегаем по строке, используя метод поиска в глубину (depth-first search). Для каждого рекурсивного вызова задаётся начальный индекс строки start.
Итеративно генерируем все возможные подстроки, начиная с индекса start. Индекс end увеличивается от start до конца строки.
2⃣Проверка на палиндром и продолжение поиска:
Для каждой сгенерированной подстроки проверяем, является ли она палиндромом.
Если подстрока оказывается палиндромом, она становится потенциальным кандидатом. Добавляем подстроку в currentList и выполняем поиск в глубину для оставшейся части строки. Если текущая подстрока заканчивается на индексе end, то end+1 становится начальным индексом для следующего рекурсивного вызова.
3⃣Возврат (Backtracking) и сохранение результатов:
Возвращаемся, если начальный индекс start больше или равен длине строки, и добавляем currentList в результат.
😎 Решение:
public class Solution {
public IList<IList<string>> Partition(string s) {
var ans = new List<IList<string>>();
Dfs(0, new List<string>(), s, ans);
return ans;
}
private void Dfs(int start, List<string> currentList, string s,
List<IList<string>> result) {
if (start >= s.Length)
result.Add(new List<string>(currentList));
else {
for (int end = start; end < s.Length; end++) {
if (IsPalindrome(s, start, end)) {
currentList.Add(s.Substring(start, end - start + 1));
Dfs(end + 1, currentList, s, result);
currentList.RemoveAt(currentList.Count - 1);
}
}
}
}
bool IsPalindrome(string s, int low, int high) {
while (low < high)
if (s[low++] != s[high--])
return false;
return true;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 409. Longest Palindrome
Сложность: easy
Если задана строка s, состоящая из строчных или прописных букв, верните длину самого длинного палиндрома, который можно построить из этих букв. Буквы чувствительны к регистру, например, "Aa" не считается палиндромом.
Пример:
👨💻 Алгоритм:
1⃣Создайте словарь для подсчета количества каждого символа в строке.
2⃣Пройдитесь по словарю и добавьте четное количество каждого символа к длине палиндрома. Если встречается нечетное количество символа, добавьте (count - 1) к длине палиндрома.
3⃣Если есть хотя бы один символ с нечетным количеством, добавьте 1 к длине палиндрома для центрального символа.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Если задана строка s, состоящая из строчных или прописных букв, верните длину самого длинного палиндрома, который можно построить из этих букв. Буквы чувствительны к регистру, например, "Aa" не считается палиндромом.
Пример:
Input: s = "abccccdd"
Output: 7
👨💻 Алгоритм:
1⃣Создайте словарь для подсчета количества каждого символа в строке.
2⃣Пройдитесь по словарю и добавьте четное количество каждого символа к длине палиндрома. Если встречается нечетное количество символа, добавьте (count - 1) к длине палиндрома.
3⃣Если есть хотя бы один символ с нечетным количеством, добавьте 1 к длине палиндрома для центрального символа.
😎 Решение:
using System.Collections.Generic;
public class Solution {
public int LongestPalindrome(string s) {
Dictionary<char, int> charCount = new Dictionary<char, int>();
foreach (char c in s) {
if (charCount.ContainsKey(c)) {
charCount[c]++;
} else {
charCount[c] = 1;
}
}
int length = 0;
bool oddFound = false;
foreach (int count in charCount.Values) {
if (count % 2 == 0) {
length += count;
} else {
length += count - 1;
oddFound = true;
}
}
return oddFound ? length + 1 : length;
}
}
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1051. Height Checker
Сложность: easy
Школа пытается сделать ежегодную фотографию всех учеников. Учеников просят встать в одну шеренгу в неубывающем порядке по росту. Пусть этот порядок представлен целочисленным массивом expected, где expected[i] - ожидаемый рост i-го студента в очереди. Вам дан целочисленный массив heights, представляющий текущий порядок, в котором стоят студенты. Каждый heights[i] - это высота i-го студента в очереди (с индексом 0). Верните количество индексов, в которых heights[i] != expected[i].
Пример:
👨💻 Алгоритм:
1⃣Создай отсортированную копию массива heights, чтобы получить ожидаемый порядок высот.
2⃣Пройди по обоим массивам и сравни элементы.
3⃣Подсчитай количество индексов, где элементы двух массивов не равны
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Школа пытается сделать ежегодную фотографию всех учеников. Учеников просят встать в одну шеренгу в неубывающем порядке по росту. Пусть этот порядок представлен целочисленным массивом expected, где expected[i] - ожидаемый рост i-го студента в очереди. Вам дан целочисленный массив heights, представляющий текущий порядок, в котором стоят студенты. Каждый heights[i] - это высота i-го студента в очереди (с индексом 0). Верните количество индексов, в которых heights[i] != expected[i].
Пример:
Input: heights = [1,1,4,2,1,3]
Output: 3
👨💻 Алгоритм:
1⃣Создай отсортированную копию массива heights, чтобы получить ожидаемый порядок высот.
2⃣Пройди по обоим массивам и сравни элементы.
3⃣Подсчитай количество индексов, где элементы двух массивов не равны
😎 Решение:
public class Solution {
public int HeightChecker(int[] heights) {
int[] expected = (int[])heights.Clone();
Array.Sort(expected);
int count = 0;
for (int i = 0; i < heights.Length; i++) {
if (heights[i] != expected[i]) {
count++;
}
}
return count;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1518. Water Bottles
Сложность: easy
Есть numBottles бутылок с водой, которые изначально наполнены водой. Вы можете обменять numExchange пустых бутылок на одну полную бутылку воды на рынке.
Операция питья полной бутылки воды превращает её в пустую бутылку.
Даны два целых числа numBottles и numExchange. Верните максимальное количество бутылок с водой, которые вы можете выпить.
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте переменную ответа consumedBottles значением 0.
2⃣Продолжайте выполнять следующие действия, пока количество numBottles больше или равно numExchange:
— Выпейте numExchange количество полных бутылок, т.е. добавьте numExchange к consumedBottles.
— Уменьшите numExchange от доступных полных бутылок numBottles.
— Обменяйте пустые бутылки на одну полную бутылку, т.е. увеличьте numBottles на одну.
3⃣Верните consumedBottles + numBottles.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Есть numBottles бутылок с водой, которые изначально наполнены водой. Вы можете обменять numExchange пустых бутылок на одну полную бутылку воды на рынке.
Операция питья полной бутылки воды превращает её в пустую бутылку.
Даны два целых числа numBottles и numExchange. Верните максимальное количество бутылок с водой, которые вы можете выпить.
Пример:
Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.
👨💻 Алгоритм:
1⃣Инициализируйте переменную ответа consumedBottles значением 0.
2⃣Продолжайте выполнять следующие действия, пока количество numBottles больше или равно numExchange:
— Выпейте numExchange количество полных бутылок, т.е. добавьте numExchange к consumedBottles.
— Уменьшите numExchange от доступных полных бутылок numBottles.
— Обменяйте пустые бутылки на одну полную бутылку, т.е. увеличьте numBottles на одну.
3⃣Верните consumedBottles + numBottles.
😎 Решение:
public class Solution {
public int NumWaterBottles(int numBottles, int numExchange) {
int consumedBottles = 0;
while (numBottles >= numExchange) {
consumedBottles += numExchange;
numBottles -= numExchange;
numBottles++;
}
return consumedBottles + numBottles;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 945. Minimum Increment to Make Array Unique
Сложность: medium
Вам дан целочисленный массив nums. За один ход вы можете выбрать индекс i, где 0 <= i < nums.length, и увеличить nums[i] на 1. Верните минимальное количество ходов, чтобы каждое значение в nums было уникальным. Тестовые примеры генерируются так, чтобы ответ умещался в 32-битное целое число.
Пример:
👨💻 Алгоритм:
1⃣Отсортировать массив nums.
Инициализировать переменную moves для подсчета количества ходов.
2⃣Пройти по массиву и для каждого элемента, начиная со второго:
Если текущий элемент меньше или равен предыдущему элементу, увеличить текущий элемент до значения предыдущего элемента + 1 и обновить счетчик ходов.
3⃣Вернуть общее количество ходов.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам дан целочисленный массив nums. За один ход вы можете выбрать индекс i, где 0 <= i < nums.length, и увеличить nums[i] на 1. Верните минимальное количество ходов, чтобы каждое значение в nums было уникальным. Тестовые примеры генерируются так, чтобы ответ умещался в 32-битное целое число.
Пример:
Input: nums = [1,2,2]
Output: 1
👨💻 Алгоритм:
1⃣Отсортировать массив nums.
Инициализировать переменную moves для подсчета количества ходов.
2⃣Пройти по массиву и для каждого элемента, начиная со второго:
Если текущий элемент меньше или равен предыдущему элементу, увеличить текущий элемент до значения предыдущего элемента + 1 и обновить счетчик ходов.
3⃣Вернуть общее количество ходов.
😎 Решение:
public class Solution {
public int MinIncrementForUnique(int[] nums) {
Array.Sort(nums);
int moves = 0;
for (int i = 1; i < nums.Length; i++) {
if (nums[i] <= nums[i - 1]) {
moves += nums[i - 1] + 1 - nums[i];
nums[i] = nums[i - 1] + 1;
}
}
return moves;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Сложность: medium
Дан массив целых чисел nums и целое число limit. Вернуть размер самой длинной непустой подстроки, такая что абсолютная разница между любыми двумя элементами этой подстроки меньше или равна limit.
Пример:
👨💻 Алгоритм:
1⃣Инициализировать два дека (minDeque и maxDeque) для хранения минимальных и максимальных значений в текущем окне и переменную left для начала окна.
2⃣Итеративно добавлять элементы в дек, поддерживая условие абсолютной разницы между максимальным и минимальным элементом в окне, чтобы она была не больше limit, при необходимости сдвигая left.
3⃣Обновлять maxLength, проверяя максимальную длину текущего окна, и возвращать maxLength как результат.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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 как результат.
😎 Решение:
using System;
using System.Collections.Generic;
public class Solution {
public int LongestSubarray(int[] nums, int limit) {
var maxHeap = new SortedSet<(int Value, int Index)>(Comparer<(int, int)>.Create((a, b) => a.Value == b.Value ? a.Index.CompareTo(b.Index) : b.Value.CompareTo(a.Value)));
var minHeap = new SortedSet<(int Value, int Index)>(Comparer<(int, int)>.Create((a, b) => a.Value == b.Value ? a.Index.CompareTo(b.Index) : a.Value.CompareTo(b.Value)));
int left = 0, maxLength = 0;
for (int right = 0; right < nums.Length; ++right) {
maxHeap.Add((nums[right], right));
minHeap.Add((nums[right], right));
while (maxHeap.Min.Value - minHeap.Max.Value > limit) {
left = Math.Min(maxHeap.Min.Index, minHeap.Max.Index) + 1;
while (maxHeap.Min.Index < left) {
maxHeap.Remove(maxHeap.Min);
}
while (minHeap.Max.Index < left) {
minHeap.Remove(minHeap.Max);
}
}
maxLength = Math.Max(maxLength, right - left + 1);
}
return maxLength;
}
}
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1032. Stream of Characters
Сложность: hard
Разработайте алгоритм, который принимает поток символов и проверяет, является ли суффикс этих символов строкой заданного массива строк words. Например, если words = ["abc", "xyz"] и в поток добавлены четыре символа (один за другим) 'a', 'x', 'y' и 'z', ваш алгоритм должен определить, что суффикс "xyz" символов "axyz" соответствует "xyz" из words.
Реализуйте класс StreamChecker: StreamChecker(String[] words) Инициализирует объект с массивом строк words. boolean query(char letter) Принимает новый символ из потока и возвращает true, если любой непустой суффикс из потока образует слово, которое есть в words.
Пример:
👨💻 Алгоритм:
1⃣Построение суффиксного Trie:
Создайте суффиксный Trie (префиксное дерево) для хранения всех слов из массива words в обратном порядке. Это позволяет эффективно искать слова, которые являются суффиксами потока символов.
2⃣Проверка суффиксов:
Для каждого нового символа, проходите по текущему списку символов и проверяйте, образуют ли они какой-либо суффикс, присутствующий в Trie. Если найдено совпадение, возвращайте true, иначе продолжайте добавлять новые символы и проверять суффиксы.
3⃣Сравнение двух случаев:
Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: hard
Разработайте алгоритм, который принимает поток символов и проверяет, является ли суффикс этих символов строкой заданного массива строк words. Например, если words = ["abc", "xyz"] и в поток добавлены четыре символа (один за другим) 'a', 'x', 'y' и 'z', ваш алгоритм должен определить, что суффикс "xyz" символов "axyz" соответствует "xyz" из words.
Реализуйте класс StreamChecker: StreamChecker(String[] words) Инициализирует объект с массивом строк words. boolean query(char letter) Принимает новый символ из потока и возвращает true, если любой непустой суффикс из потока образует слово, которое есть в words.
Пример:
Input
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
Output
[null, false, false, false, true, false, true, false, false, false, false, false, true]
👨💻 Алгоритм:
1⃣Построение суффиксного Trie:
Создайте суффиксный Trie (префиксное дерево) для хранения всех слов из массива words в обратном порядке. Это позволяет эффективно искать слова, которые являются суффиксами потока символов.
2⃣Проверка суффиксов:
Для каждого нового символа, проходите по текущему списку символов и проверяйте, образуют ли они какой-либо суффикс, присутствующий в Trie. Если найдено совпадение, возвращайте true, иначе продолжайте добавлять новые символы и проверять суффиксы.
3⃣Сравнение двух случаев:
Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая.
😎 Решение:
public class TrieNode {
public Dictionary<char, TrieNode> Children = new Dictionary<char, TrieNode>();
public bool IsEndOfWord = false;
}
public class StreamChecker {
private TrieNode root;
private LinkedList<char> stream;
public StreamChecker(string[] words) {
root = new TrieNode();
stream = new LinkedList<char>();
foreach (var word in words) {
var node = root;
for (int i = word.Length - 1; i >= 0; i--) {
if (!node.Children.ContainsKey(word[i])) {
node.Children[word[i]] = new TrieNode();
}
node = node.Children[word[i]];
}
node.IsEndOfWord = true;
}
}
public bool Query(char letter) {
stream.AddFirst(letter);
var node = root;
foreach (var char in stream) {
if (!node.Children.ContainsKey(char)) return false;
node = node.Children[char];
if (node.IsEndOfWord) return true;
}
return false;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 179. Largest Number
Сложность: medium
Дан список неотрицательных целых чисел nums. Организуйте их таким образом, чтобы они составляли наибольшее число и верните его.
Поскольку результат может быть очень большим, вам необходимо вернуть строку вместо целого числа.
Пример:
👨💻 Алгоритм:
1⃣Преобразование и сортировка: Преобразовать каждое число в строку и отсортировать массив строк с использованием специального компаратора, который для двух строк 𝑎 и b сравнивает результаты конкатенации 𝑎+𝑏 и 𝑏+𝑎.
2⃣Проверка на нули: Если после сортировки первый элемент массива равен "0", вернуть "0", так как все числа в массиве нули.
3⃣Формирование результата: Конкатенировать отсортированные строки для формирования наибольшего числа и вернуть это число в виде строки.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Дан список неотрицательных целых чисел nums. Организуйте их таким образом, чтобы они составляли наибольшее число и верните его.
Поскольку результат может быть очень большим, вам необходимо вернуть строку вместо целого числа.
Пример:
Input: nums = [10,2]
Output: "210"
👨💻 Алгоритм:
1⃣Преобразование и сортировка: Преобразовать каждое число в строку и отсортировать массив строк с использованием специального компаратора, который для двух строк 𝑎 и b сравнивает результаты конкатенации 𝑎+𝑏 и 𝑏+𝑎.
2⃣Проверка на нули: Если после сортировки первый элемент массива равен "0", вернуть "0", так как все числа в массиве нули.
3⃣Формирование результата: Конкатенировать отсортированные строки для формирования наибольшего числа и вернуть это число в виде строки.
😎 Решение:
public class Solution {
public string LargestNumber(int[] nums) {
string[] strNums = nums.Select(num => num.ToString()).ToArray();
Array.Sort(strNums, (a, b) => (b + a).CompareTo(a + b));
if (strNums[0] == "0") {
return "0";
}
return string.Concat(strNums);
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 717. 1-bit and 2-bit Characters
Сложность: easy
У нас есть два специальных символа: первый символ может быть представлен одним битом 0. Второй символ может быть представлен двумя битами (10 или 11). Если задан двоичный массив bits, который заканчивается 0, верните true, если последний символ должен быть однобитным.
Пример:
👨💻 Алгоритм:
1⃣Инициализируйте индекс для итерации по массиву.
2⃣Пройдите по массиву, увеличивая индекс на 1, если текущий бит равен 0, и на 2, если текущий бит равен 1.
3⃣Проверьте, достиг ли индекс последнего элемента массива, и верните результат.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
У нас есть два специальных символа: первый символ может быть представлен одним битом 0. Второй символ может быть представлен двумя битами (10 или 11). Если задан двоичный массив bits, который заканчивается 0, верните true, если последний символ должен быть однобитным.
Пример:
Input: bits = [1,0,0]
Output: true
👨💻 Алгоритм:
1⃣Инициализируйте индекс для итерации по массиву.
2⃣Пройдите по массиву, увеличивая индекс на 1, если текущий бит равен 0, и на 2, если текущий бит равен 1.
3⃣Проверьте, достиг ли индекс последнего элемента массива, и верните результат.
😎 Решение:
public class Solution {
public bool IsOneBitCharacter(int[] bits) {
int i = 0;
while (i < bits.Length - 1) {
i += bits[i] + 1;
}
return i == bits.Length - 1;
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 594. Longest Harmonious Subsequence
Сложность: easy
Мы определяем гармоничный массив как массив, в котором разница между его максимальным и минимальным значением составляет ровно 1.
Дан целочисленный массив nums, верните длину его самой длинной гармоничной подпоследовательности среди всех возможных подпоследовательностей.
Подпоследовательность массива - это последовательность, которую можно получить из массива, удалив некоторые или никакие элементы, не изменяя порядок оставшихся элементов.
Пример:
👨💻 Алгоритм:
1⃣Пройдитесь по массиву, создавая словарь для подсчета частоты каждого элемента.
2⃣На каждой итерации проверьте, существуют ли в словаре элементы, отличающиеся на 1 от текущего, и обновите максимальную длину гармоничной подпоследовательности.
3⃣Верните максимальную длину гармоничной подпоследовательности.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Мы определяем гармоничный массив как массив, в котором разница между его максимальным и минимальным значением составляет ровно 1.
Дан целочисленный массив nums, верните длину его самой длинной гармоничной подпоследовательности среди всех возможных подпоследовательностей.
Подпоследовательность массива - это последовательность, которую можно получить из массива, удалив некоторые или никакие элементы, не изменяя порядок оставшихся элементов.
Пример:
Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].
👨💻 Алгоритм:
1⃣Пройдитесь по массиву, создавая словарь для подсчета частоты каждого элемента.
2⃣На каждой итерации проверьте, существуют ли в словаре элементы, отличающиеся на 1 от текущего, и обновите максимальную длину гармоничной подпоследовательности.
3⃣Верните максимальную длину гармоничной подпоследовательности.
😎 Решение:
using System;
using System.Collections.Generic;
public class Solution {
public int FindLHS(int[] nums) {
var count = new Dictionary<int, int>();
int res = 0;
foreach (var num in nums) {
if (count.ContainsKey(num)) {
count[num]++;
} else {
count[num] = 1;
}
if (count.ContainsKey(num + 1)) {
res = Math.Max(res, count[num] + count[num + 1]);
}
if (count.ContainsKey(num - 1)) {
res = Math.Max(res, count[num] + count[num - 1]);
}
}
return res;
}
}
Ставь 👍 и забирай 📚 Базу знаний
Задача: 1119. Remove Vowels from a String
Сложность: easy
Дана строка s, удалите из нее гласные 'a', 'e', 'i', 'o' и 'u' и верните новую строку.
Пример:
👨💻 Алгоритм:
1⃣Создайте метод isVowel(), который возвращает true, если переданный символ является одной из гласных [a, e, i, o, u], и false в противном случае.
2⃣Инициализируйте пустую строку ans.
3⃣Пройдитесь по каждому символу в строке s, и для каждого символа c проверьте, является ли он гласной, используя isVowel(c). Если нет, добавьте символ в строку ans. В конце верните строку ans.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: easy
Дана строка s, удалите из нее гласные 'a', 'e', 'i', 'o' и 'u' и верните новую строку.
Пример:
Input: s = "leetcodeisacommunityforcoders"
Output: "ltcdscmmntyfrcdrs"
👨💻 Алгоритм:
1⃣Создайте метод isVowel(), который возвращает true, если переданный символ является одной из гласных [a, e, i, o, u], и false в противном случае.
2⃣Инициализируйте пустую строку ans.
3⃣Пройдитесь по каждому символу в строке s, и для каждого символа c проверьте, является ли он гласной, используя isVowel(c). Если нет, добавьте символ в строку ans. В конце верните строку ans.
😎 Решение:
public class Solution {
public string RemoveVowels(string s) {
var ans = new StringBuilder();
foreach (char c in s) {
if (!IsVowel(c)) {
ans.Append(c);
}
}
return ans.ToString();
}
private bool IsVowel(char c) {
return c == 'a' || c == 'i' || c == 'e' || c == 'o' || c == 'u';
}
}Ставь 👍 и забирай 📚 Базу знаний
Задача: 937. Reorder Data in Log Files
Сложность: medium
Вам дается массив журналов. Каждый журнал представляет собой строку слов, ограниченную пробелами, где первое слово является идентификатором. Существует два типа журналов: Буквенные журналы: Все слова (кроме идентификатора) состоят из строчных английских букв. Цифровые журналы: Все слова (кроме идентификатора) состоят из цифр. Упорядочите эти журналы таким образом: буквенные журналы идут перед всеми цифровыми журналами. Буквенные журналы сортируются лексикографически по их содержанию. Если их содержимое одинаково, то отсортируйте их лексикографически по их идентификаторам. Цифровые журналы сохраняют свой относительный порядок. Верните окончательный порядок журналов.
Пример:
👨💻 Алгоритм:
1⃣Разделить журналы на буквенные и цифровые.
2⃣Отсортировать буквенные журналы:
Лексикографически по содержимому.
Если содержимое одинаково, отсортировать по идентификатору.
Объединить отсортированные буквенные журналы и цифровые журналы в исходном порядке.
3⃣Вернуть окончательный результат.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: medium
Вам дается массив журналов. Каждый журнал представляет собой строку слов, ограниченную пробелами, где первое слово является идентификатором. Существует два типа журналов: Буквенные журналы: Все слова (кроме идентификатора) состоят из строчных английских букв. Цифровые журналы: Все слова (кроме идентификатора) состоят из цифр. Упорядочите эти журналы таким образом: буквенные журналы идут перед всеми цифровыми журналами. Буквенные журналы сортируются лексикографически по их содержанию. Если их содержимое одинаково, то отсортируйте их лексикографически по их идентификаторам. Цифровые журналы сохраняют свой относительный порядок. Верните окончательный порядок журналов.
Пример:
Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]
👨💻 Алгоритм:
1⃣Разделить журналы на буквенные и цифровые.
2⃣Отсортировать буквенные журналы:
Лексикографически по содержимому.
Если содержимое одинаково, отсортировать по идентификатору.
Объединить отсортированные буквенные журналы и цифровые журналы в исходном порядке.
3⃣Вернуть окончательный результат.
😎 Решение:
using System;
using System.Linq;
public class Solution {
public string[] ReorderLogFiles(string[] logs) {
return logs.OrderBy(log => log, Comparer<string>.Create((log1, log2) => {
var split1 = log1.Split(new char[] { ' ' }, 2);
var split2 = log2.Split(new char[] { ' ' }, 2);
bool isDigit1 = char.IsDigit(split1[1][0]);
bool isDigit2 = char.IsDigit(split2[1][0]);
if (!isDigit1 && !isDigit2) {
int cmp = string.Compare(split1[1], split2[1]);
if (cmp != 0) return cmp;
return string.Compare(split1[0], split2[0]);
}
return isDigit1 ? 1 : -1;
})).ToArray();
}
}
Ставь 👍 и забирай 📚 Базу знаний