🚩 Задача с собеса

Задача: дана строка 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

🔄 Как развернуть связный список

Дан связный список, нужно развернуть его задом наперёд. Разберём как решить задачу элегантно.

У вас есть цепочка узлов: 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

✏️ Как заработать на всех взлётах цены акций

Дан массив цен акций по дням. Нужно найти максимальную прибыль, совершая любое количество сделок купли-продажи. Одновременно можно держать только одну акцию.

Пример:

Цены: [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

✏️ Задача с собеса: кинотеатр и лучшие места

В кинотеатр пришли люди, и часть мест уже занята.
Места описаны массивом из нулей и единиц:

1 — место занято
0 — место свободно

Нужно найти такое место, чтобы сидящий оказался как можно дальше от ближайшего соседа.

Разбор решения

Нужно рассмотреть три типа промежутков свободных мест:

• Начало ряда — расстояние до ближайшего соседа = количество нулей
• Конец ряда — расстояние = количество нулей
• Середина — расстояние = количество нулей / 2. Целочисленное деление.

Алгоритм

1. Проходим по массиву один раз
2. Отслеживаем индекс последнего человека, которого мы встретили
3. При встрече человека вычисляем расстояние:

• Если это первый человек → берём его индекс (левый край)
• Если не первый → вычисляем (текущий_индекс - прошлый_индекс) / 2

3. После цикла проверяем правый край: n - 1 - последний_индекс
4. Возвращаем максимум из всех расстояний.

Код:

public class Solution {
    public int MaxDistToClosest(int[] seats) {
        int n = seats.Length;
        int maxDist = 0;
        int lastPerson = -1;
        
        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                if (lastPerson == -1) {
                    // Левый край
                    maxDist = i;
                } else {
                    // Середина
                    maxDist = Math.Max(maxDist, (i - lastPerson) / 2);
                }
                lastPerson = i;
            }
        }
        
        // Правый край
        maxDist = Math.Max(maxDist, n - 1 - lastPerson);
        
        return maxDist;
    }
}

Задача решается одним проходом за линейное время. Главное — правильно обработать три случая: левый край, середину и правый край.

➡️ Попробовать решить

Чтобы щёлкать такие задачи нужно знать алгоритмы. Подтянуть такую базу поможет наш курс по алгоритмам. До конца октября скидка 40%

🐸 Библиотека шарписта

#dotnet_challenge