Вам дан отсортированный по возрастанию массив целых чисел. Нужно создать новый массив, в котором содержатся квадраты этих чисел — и он тоже должен быть отсортирован по возрастанию.
Поскольку исходный массив отсортирован, отрицательные числа после возведения в квадрат могут стать больше положительных, поэтому нужно рассматривать оба края массива.
1. Обрабатываем два края массива (left и right), сравниваем их квадраты.
2. Наибольший квадрат записываем в конец результирующего массива.
3. Сдвигаем соответствующий указатель — либо left, либо right.
4. В конце получаем отсортированный массив квадратов.
Решение с двумя указателями:
public int[] SortedSquares(int[] nums) {
int n = nums.Length;
int[] result = new int[n];
int left = 0, right = n - 1, pos = n - 1;
while (left <= right) {
int leftSq = nums[left] * nums[left];
int rightSq = nums[right] * nums[right];
if (leftSq > rightSq) {
result[pos] = leftSq;
left++;
} else {
result[pos] = rightSq;
right--;
}
pos--;
}
return result;
}
#dotnet_challenge
Please open Telegram to view this post
VIEW IN TELEGRAM
❤7❤🔥6🥱2
Задача: дана строка
s
и строка p
. Необходимо найти все начальные индексы подстрок в s
, которые являются анаграммами строки p
.Анаграмма — это слово или фраза, образованная перестановкой букв другого слова, используя все исходные буквы ровно один раз.
Пример:
Input: s = "cbaebabacd", p = "abc"
Output: [0, 6]
Объяснение:
Подстрока с индекса 0 - "cba", анаграмма "abc".
Подстрока с индекса 6 - "bac", анаграмма "abc".
Оптимальное решение использует технику скользящего окна с подсчетом частот символов.
1. Подсчитываем количество и частоту всех символов в строке p
2. Создаем скользящее окно размером со строку
p
в строке s
3. Для каждой позиции окна сравниваем частоты символов с эталоном
4. При совпадении добавляем индекс в результат
Код:
public class Solution
{
public IList<int> FindAnagrams(string s, string p)
{
List<int> result = new List<int>();
if (s.Length < p.Length)
return result;
// Массивы для подсчета частот символов (26 букв английского алфавита)
int[] pCount = new int[26];
int[] windowCount = new int[26];
// Подсчитываем частоты в строке p и первом окне
for (int i = 0; i < p.Length; i++)
{
pCount[p[i] - 'a']++;
windowCount[s[i] - 'a']++;
}
// Проверяем первое окно
if (AreEqual(pCount, windowCount))
result.Add(0);
// Скользим окном по строке s
for (int i = p.Length; i < s.Length; i++)
{
// Добавляем новый символ справа
windowCount[s[i] - 'a']++;
// Удаляем старый символ слева
windowCount[s[i - p.Length] - 'a']--;
// Проверяем текущее окно
if (AreEqual(pCount, windowCount))
result.Add(i - p.Length + 1);
}
return result;
}
// Вспомогательный метод для сравнения массивов частот
private bool AreEqual(int[] arr1, int[] arr2)
{
for (int i = 0; i < 26; i++)
{
if (arr1[i] != arr2[i])
return false;
}
return true;
}
}
#dotnet_challenge
Please open Telegram to view this post
VIEW IN TELEGRAM
🤩3❤2🔥2💯2👾2
🔄 Как развернуть связный список
Дан связный список, нужно развернуть его задом наперёд. Разберём как решить задачу элегантно.
У вас есть цепочка узлов: 1 → 2 → 3 → 4 → 5. Каждый узел хранит значение и ссылку на следующий элемент. Задача — перевернуть все стрелки: 1 ← 2 ← 3 ← 4 ← 5.
Главная сложность здесь не в алгоритме, а в работе с указателями. Стоит перезаписать ссылку неправильно — и вы теряете доступ к остальной части списка. Именно поэтому многие решения проваливаются на первой попытке.
Итеративное решение: три указателя
Самый надёжный подход — использовать три указателя, которые двигаются по списку синхронно.
• prev отслеживает предыдущий узел
• curr указывает на текущий обрабатываемый узел
• next сохраняет следующий узел, чтобы не потерять его при развороте
Код:
Рекурсивное решение
Если вам нравятся рекурсивные решения, есть и такой вариант:
Попробуйте решить задачу сами, прежде чем смотреть готовый код. Нарисуйте список на бумаге, отследите движение указателей вручную. Это единственный способ понять, что происходит.
➡️ Решить задачу
🐸 Библиотека шарписта
#dotnet_challenge
Дан связный список, нужно развернуть его задом наперёд. Разберём как решить задачу элегантно.
У вас есть цепочка узлов: 1 → 2 → 3 → 4 → 5. Каждый узел хранит значение и ссылку на следующий элемент. Задача — перевернуть все стрелки: 1 ← 2 ← 3 ← 4 ← 5.
Главная сложность здесь не в алгоритме, а в работе с указателями. Стоит перезаписать ссылку неправильно — и вы теряете доступ к остальной части списка. Именно поэтому многие решения проваливаются на первой попытке.
Итеративное решение: три указателя
Самый надёжный подход — использовать три указателя, которые двигаются по списку синхронно.
• prev отслеживает предыдущий узел
• curr указывает на текущий обрабатываемый узел
• next сохраняет следующий узел, чтобы не потерять его при развороте
Код:
public ListNode ReverseList(ListNode head)
{
ListNode prev = null;
ListNode curr = head;
while (curr != null)
{
ListNode next = curr.next; // сохраняем следующий
curr.next = prev; // разворачиваем стрелку
prev = curr; // двигаем prev
curr = next; // двигаем curr
}
return prev;
}
Рекурсивное решение
Если вам нравятся рекурсивные решения, есть и такой вариант:
public ListNode ReverseList(ListNode head)
{
if (head == null || head.next == null)
return head;
ListNode newHead = ReverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
Попробуйте решить задачу сами, прежде чем смотреть готовый код. Нарисуйте список на бумаге, отследите движение указателей вручную. Это единственный способ понять, что происходит.
#dotnet_challenge
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥7🙏2👾1
Дан массив цен акций по дням. Нужно найти максимальную прибыль, совершая любое количество сделок купли-продажи. Одновременно можно держать только одну акцию.
Пример:
Цены: [7, 1, 5, 3, 6, 4]
Ответ: 7
Покупаем за 1, продаём за 5 (прибыль 4). Покупаем за 3, продаём за 6 (прибыль 3). Итого — 7.
Алгоритм
Самый простой подход — жадный алгоритм. Если завтра цена выше, чем сегодня — покупаем сегодня и продаём завтра. Собираем прибыль с каждого роста цены.
Представьте график цен: вам нужно получить прибыль со всех участков, где график идёт вверх. Неважно, сколько это будет сделок — каждый рост приносит деньги.
Почему это работает
Если цена растёт три дня подряд (например, 1 → 3 → 5), то неважно, продавать ли каждый день или держать до конца.
Код:
public class Solution
{
public int MaxProfit(int[] prices)
{
if (prices == null || prices.Length < 2)
return 0;
int totalProfit = 0;
for (int i = 1; i < prices.Length; i++)
{
// Если цена выросла — берём эту прибыль
if (prices[i] > prices[i - 1])
{
totalProfit += prices[i] - prices[i - 1];
}
}
return totalProfit;
}
}
Или ещё компактнее:
public class Solution
{
public int MaxProfit(int[] prices)
{
int profit = 0;
for (int i = 1; i < prices.Length; i++)
{
profit += Math.Max(0, prices[i] - prices[i - 1]);
}
return profit;
}
}
Жадный подход здесь безупречен: захватываем каждый рост, игнорируем падения. Никаких сложных расчётов оптимальных точек — только простая логика и максимальная прибыль.
Чтобы щёлкать такие задачи нужно знать алгоритмы. Подтянуть такую базу поможет наш курс по алгоритмам. До конца октября скидка 40%
#dotnet_challenge
Please open Telegram to view this post
VIEW IN TELEGRAM
😁6👍1