C# | LeetCode

Задача: 1029. Two City Scheduling
Сложность: medium

Компания планирует провести интервью с 2n людьми. Учитывая массив costs, где costs[i] = [aCosti, bCosti], стоимость перелета i-го человека в город a равна aCosti, а стоимость перелета i-го человека в город b равна bCosti. Выведите минимальную стоимость перелета каждого человека в город, чтобы в каждый город прибыло ровно n человек.

Пример:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

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

1⃣Вычислить разницу стоимости:
Для каждого человека вычислите разницу в стоимости между перелетом в город A и город B.

2⃣Сортировать по разнице:
Отсортируйте людей по разнице в стоимости перелета в город A и B. Это поможет минимизировать общую стоимость, так как мы сначала будем отправлять тех, для кого разница минимальна.

3⃣Назначить города:
Первые n человек из отсортированного списка отправьте в город A.
Оставшихся n человек отправьте в город B.

😎 Решение:

public class Solution {
    public int TwoCitySchedCost(int[][] costs) {
        Array.Sort(costs, (a, b) => (a[0] - a[1]).CompareTo(b[0] - b[1]));
        int totalCost = 0;
        int n = costs.Length / 2;
        for (int i = 0; i < n; i++) {
            totalCost += costs[i][0];
            totalCost += costs[i + n][1];
        }
        return totalCost;
    }
}

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

Задача: 347. Top K Frequent Elements
Сложность: medium

Дан массив целых чисел nums и целое число k. Верните k самых частых элементов. Вы можете вернуть ответ в любом порядке.

Пример:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

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

1⃣Подсчет частоты:
Используйте хеш-таблицу или словарь для подсчета количества вхождений каждого элемента в массиве nums.

2⃣Создание кучи:
Создайте кучу, чтобы отсортировать элементы по их частоте и выбрать k самых частых элементов.

3⃣Возврат результата:
Верните k самых частых элементов.

😎 Решение:

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int[] TopKFrequent(int[] nums, int k) {
        var count = nums.GroupBy(n => n)
                        .ToDictionary(g => g.Key, g => g.Count());
        return count.OrderByDescending(x => x.Value)
                    .Take(k)
                    .Select(x => x.Key)
                    .ToArray();
    }
}

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

Задача: 207. Course Schedule
Сложность: medium

Всего у вас есть numCourses курсов, которые нужно пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.

Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните true, если вы можете завершить все курсы. В противном случае верните false.

Пример:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

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

1⃣Создайте массив indegree длины n, где indegree[x] хранит количество входящих рёбер в узел x. Создайте список смежности adj, в котором adj[x] содержит все узлы с входящим ребром от узла x, то есть соседей узла x. Создайте этот список смежности, итерируя prerequisites. Для каждого prerequisites добавьте ребро от prerequisites[1] к prerequisites[0] и увеличьте indegree prerequisites[0] на 1.

2⃣Инициализируйте очередь целых чисел q и начните алгоритм BFS, перемещаясь от листовых узлов к родительским узлам. Начните обход BFS, поместив все листовые узлы (indegree равное 0) в очередь. Создайте целочисленную переменную nodesVisited = 0 для подсчета количества посещенных узлов.

3⃣Пока очередь не пуста:
Извлеките первый узел из очереди.
Увеличьте nodesVisited на 1.
Для каждого соседа (узлы, которые имеют входящее ребро от узла) узла уменьшите indegree[neighbor] на 1, чтобы удалить ребро node -> neighbor.
Если indegree[neighbor] == 0, это означает, что neighbor ведет себя как листовой узел, поэтому добавьте neighbor в очередь.
Если количество посещенных узлов меньше общего количества узлов, то есть nodesVisited < n, верните false, так как должен быть цикл. В противном случае, если nodesVisited == numCourses, верните true. Можно сократить это до просто возвращения nodesVisited == numCourses.

😎 Решение:

public class Solution {
    public bool CanFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        List<int>[] adj = new List<int>[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            adj[i] = new List<int>();
        }
        
        foreach (var prerequisite in prerequisites) {
            adj[prerequisite[1]].Add(prerequisite[0]);
            indegree[prerequisite[0]]++;
        }

        Queue<int> q = new Queue<int>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                q.Enqueue(i);
            }
        }

        int nodesVisited = 0;
        while (q.Count > 0) {
            int node = q.Dequeue();
            nodesVisited++;

            foreach (var neighbor in adj[node]) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    q.Enqueue(neighbor);
                }
            }
        }

        return nodesVisited == numCourses;
    }
}

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

Задача: 1482. Minimum Number of Days to Make m Bouquets
Сложность: medium

Вам дан массив целых чисел bloomDay, целое число m и целое число k.

Вам нужно сделать m букетов. Для создания букета необходимо использовать k соседних цветов из сада.
Сад состоит из n цветов, i-й цветок расцветет на bloomDay[i] и затем может быть использован ровно в одном букете.

Верните минимальное количество дней, которое нужно подождать, чтобы можно было сделать m букетов из сада. Если сделать m букетов невозможно, верните -1.

Пример:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let us see what happened in the first three days. x means flower bloomed and _ means flower did not bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.

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

1⃣Инициализация:
Инициализируйте start как 0 и end как максимальное значение в массиве bloomDay.
Введите вспомогательную функцию getNumOfBouquets для подсчета количества букетов, которые можно сделать на определенный день.

2⃣Поиск минимального числа дней:
Выполняйте бинарный поиск, пока start меньше или равен end:
- рассчитайте mid как среднее значение между start и end.
- используйте getNumOfBouquets, чтобы определить, сколько букетов можно сделать на mid день.
- если количество букетов больше или равно m, сохраните mid как возможное решение и переместите end влево.
- иначе переместите start вправо.

3⃣Возвращение результата:
Верните найденное минимальное количество дней или -1, если сделать m букетов невозможно.

😎 Решение:

public class Solution {
    private int GetNumOfBouquets(int[] bloomDay, int mid, int k) {
        int numOfBouquets = 0, count = 0;
        foreach (int day in bloomDay) {
            if (day <= mid) {
                count++;
            } else {
                count = 0;
            }
            if (count == k) {
                numOfBouquets++;
                count = 0;
            }
        }
        return numOfBouquets;
    }

    public int MinDays(int[] bloomDay, int m, int k) {
        if (bloomDay.Length < m * k) return -1;
        int start = 0, end = bloomDay.Max();
        int minDays = -1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (GetNumOfBouquets(bloomDay, mid, k) >= m) {
                minDays = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return minDays;
    }
}

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

Задача: 204. Count Primes
Сложность: medium

Дано целое число n, верните количество простых чисел, которые строго меньше n.

Пример:

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

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

1⃣Создайте список последовательных целых чисел от 2 до n: (2, 3, 4, ..., n). Пусть p будет переменной, используемой во внешнем цикле, проходящем от 2 до n. Изначально p равно 2, самому маленькому простому числу.

2⃣Перечислите кратные числа p, считая с шагом p от pp до n и отметьте их в списке (это будут pp, pp + p, pp + 2*p и т.д.; само число p должно быть простым). Найдите наименьшее число в списке, большее p, которое не отмечено. Если такого числа нет, остановитесь. В противном случае, пусть p теперь равно этому новому числу (следующее простое) и повторите шаг 2.

3⃣Когда алгоритм завершится, все оставшиеся числа, которые не отмечены, являются простыми.

😎 Решение:

public class Solution {
    public int CountPrimes(int n) {
        if (n <= 2) {
            return 0;
        }

        bool[] numbers = new bool[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = true;
        }

        for (int p = 2; p <= Math.Sqrt(n); ++p) {
            if (numbers[p]) {
                for (int j = p * p; j < n; j += p) {
                    numbers[j] = false;
                }
            }
        }

        int numberOfPrimes = 0;
        for (int i = 2; i < n; i++) {
            if (numbers[i]) {
                ++numberOfPrimes;
            }
        }

        return numberOfPrimes;
    }
}

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

Задача: 55. Jump Game
Сложность: medium

Дан массив nums, где nums[i] — максимальная длина прыжка из позиции i. Нужно определить, можно ли добраться до последнего индекса.

Пример:

Input: nums = [2,3,1,1,4]  
Output: true  
Explanation: Прыгаем 1 шаг с `0` на `1`, затем 3 шага на последний индекс.  

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

1⃣Завести переменную maxReach— максимальное положение, до которого можно допрыгнуть.

2⃣Идти по массиву, обновляясь maxReachна каждом шаге.

3⃣Если текущий индекс рассчитывается maxReach— путь прерывается, иначе возвращается true при выполнении конца.

😎 Решение:

public class Solution {
    public bool CanJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.Length; i++) {
            if (i > maxReach) return false;
            maxReach = Math.Max(maxReach, i + nums[i]);
            if (maxReach >= nums.Length - 1) return true;
        }
        return false;
    }
}

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

Задача: 64. Minimum Path Sum
Сложность: medium

На сетке размером m на n, заполненной неотрицательными числами, найдите путь от верхнего левого угла до нижнего правого, который минимизирует сумму всех чисел вдоль своего пути.

Примечание: Вы можете перемещаться только вниз или вправо в любой момент времени.

Пример:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

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

1⃣Инициализация дополнительной матрицы dp такого же размера, как и исходная матрица. В этой матрице dp(i, j) представляет минимальную сумму пути от индекса (i, j) до самого правого нижнего элемента. Начинаем с инициализации самого правого нижнего элемента dp как последнего элемента заданной матрицы.

2⃣Для каждого элемента, начиная с правого нижнего угла, мы обходим матрицу в обратном порядке и заполняем её требуемыми минимальными суммами. Важно отметить, что на каждом элементе мы можем перемещаться либо вправо, либо вниз.

3⃣Для заполнения минимальной суммы используется уравнение: dp(i, j) = grid(i, j) + min(dp(i+1, j), dp(i, j+1)), с учётом граничных условий.

😎 Решение:

public class Solution {
    public int MinPathSum(int[][] grid) {
        int[][] dp = new int [grid.Length][];
        for (int i = 0; i < grid.Length; i++) dp[i] = new int[grid[0].Length];
        for (int i = grid.Length - 1; i >= 0; i--) {
            for (int j = grid[0].Length - 1; j >= 0; j--) {
                if (i == grid.Length - 1 && j != grid[0].Length - 1)
                    dp[i][j] = grid[i][j] + dp[i][j + 1];
                else if (j == grid[0].Length - 1 && i != grid.Length - 1)
                    dp[i][j] = grid[i][j] + dp[i + 1][j];
                else if (j != grid[0].Length - 1 && i != grid.Length - 1)
                    dp[i][j] =
                        grid[i][j] + Math.Min(dp[i + 1][j], dp[i][j + 1]);
                else
                    dp[i][j] = grid[i][j];
            }
        }

        return dp[0][0];
    }
}

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

Задача: 1031. Maximum Sum of Two Non-Overlapping Subarrays
Сложность: medium

Если задан целочисленный массив nums и два целых числа firstLen и secondLen, верните максимальную сумму элементов в двух непересекающихся подмассивах с длинами firstLen и secondLen. Массив с длиной firstLen может находиться до или после массива с длиной secondLen, но они должны быть непересекающимися. Подмассив - это смежная часть массива.

Пример:

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20

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

1⃣Предварительные вычисления:
Вычислите сумму всех подмассивов длины firstLen и secondLen и сохраните их в списках.

2⃣Поиск максимальной суммы:
Переберите все возможные позиции для подмассива длины firstLen и для каждого такого подмассива найдите максимальную сумму для подмассива длины secondLen, который не пересекается с текущим подмассивом длины firstLen.

3⃣Сравнение двух случаев:
Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая.

😎 Решение:

public class Solution {
    public int MaxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        return Math.Max(MaxSumNonOverlap(nums, firstLen, secondLen), MaxSumNonOverlap(nums.Reverse().ToArray(), secondLen, firstLen));
    }
    
    private int MaxSumNonOverlap(int[] nums, int firstLen, int secondLen) {
        int n = nums.Length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        int[] maxFirst = new int[n];
        for (int i = firstLen - 1; i < n; ++i) {
            maxFirst[i] = Math.Max((i > 0 ? maxFirst[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - firstLen]);
        }
        
        int[] maxSecond = new int[n];
        for (int i = secondLen - 1; i < n; ++i) {
            maxSecond[i] = Math.Max((i > 0 ? maxSecond[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - secondLen]);
        }
        
        int maxSum = 0;
        for (int i = firstLen + secondLen - 1; i < n; ++i) {
            maxSum = Math.Max(maxSum, maxFirst[i - secondLen] + (prefix[i + 1] - prefix[i + 1 - secondLen]));
        }
        
        return maxSum;
    }
}

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

Задача: 633. Sum of Square Numbers
Сложность: medium

Учитывая целое неотрицательное число c, решите, существуют ли два целых числа a и b такие, что a2 + b2 = c.

Пример:

Input: c = 5
Output: true

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

1⃣Проверка границ
Проверьте, если c меньше 0, немедленно верните false, так как сумма квадратов двух целых чисел не может быть отрицательной.

2⃣Инициализация указателей
Используйте два указателя a и b. Инициализируйте a на 0 и b на значение квадратного корня из c. Поиск решения: Используйте цикл для поиска a и b, таких что a^2 + b^2 == c: Если a^2 + b^2 равно c, верните true. Если a^2 + b^2 меньше c, увеличьте a на 1. Если a^2 + b^2 больше c, уменьшите b на 1.

3⃣Возвращение результата
Если цикл завершится без нахождения подходящих a и b, верните false.

😎 Решение:

import kotlin.math.sqrt

class Solution {
    fun judgeSquareSum(c: Int): Boolean {
        var a = 0
        var b = sqrt(c.toDouble()).toInt()
        while (a <= b) {
            val total = a * a + b * b
            if (total == c) {
                return true
            } else if (total < c) {
                a++
            } else {
                b--
            }
        }
        return false
    }
}

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

Задача: 917. Reverse Only Letters
Сложность: easy

Задав строку s, переверните ее в соответствии со следующими правилами: все символы, не являющиеся английскими буквами, остаются в той же позиции. Все английские буквы (строчные или прописные) должны быть перевернуты. Верните s после перевертывания.

Пример:

Input: s = "ab-cd"
Output: "dc-ba"

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

1⃣Создать массив для хранения только английских букв из строки s.

2⃣Перевернуть массив с английскими буквами.
Пройти по строке s и заменить каждую английскую букву на соответствующую из перевернутого массива.

3⃣Вернуть результат.

😎 Решение:

using System;
using System.Text;

public class Solution {
    public string ReverseOnlyLetters(string s) {
        var letters = new List<char>();
        foreach (char c in s) {
            if (char.IsLetter(c)) {
                letters.Add(c);
            }
        }
        letters.Reverse();
        var result = new StringBuilder();
        int idx = 0;
        foreach (char c in s) {
            if (char.IsLetter(c)) {
                result.Append(letters[idx++]);
            } else {
                result.Append(c);
            }
        }
        return result.ToString();
    }
}

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

Задача: 76. Minimum Window Substring
Сложность: hard

Даны две строки s и t длиной m и n соответственно. Верните наименьшую подстроку строки s так, чтобы каждый символ из строки t (включая дубликаты) входил в эту подстроку. Если такой подстроки не существует, верните пустую строку "".

Тестовые примеры будут сформированы таким образом, что ответ будет уникальным.

Пример:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

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

1⃣Мы начинаем с двух указателей, left и right, которые изначально указывают на первый элемент строки S.

2⃣Мы используем указатель right для расширения окна до тех пор, пока не получим желаемое окно, т.е. окно, которое содержит все символы из T.

3⃣Как только у нас есть окно со всеми символами, мы можем передвигать указатель left вперёд по одному. Если окно по-прежнему желаемое, мы продолжаем обновлять размер минимального окна. Если окно больше не желаемое, мы повторяем шаг 2 и далее.

😎 Решение:

public class Solution {
    public string MinWindow(string s, string t) {
        if (s.Length == 0 || t.Length == 0) {
            return "";
        }

        Dictionary<char, int> dictT = new Dictionary<char, int>();
        for (int i = 0; i < t.Length; i++) {
            if (dictT.ContainsKey(t[i])) {
                dictT[t[i]]++;
            } else {
                dictT[t[i]] = 1;
            }
        }

        int required = dictT.Count;
        int l = 0, r = 0;
        int formed = 0;
        Dictionary<char, int> windowCounts = new Dictionary<char, int>();
        int[] ans = { -1, 0, 0 };
        while (r < s.Length) {
            char c = s[r];
            if (windowCounts.ContainsKey(c)) {
                windowCounts[c]++;
            } else {
                windowCounts[c] = 1;
            }

            if (dictT.ContainsKey(c) && windowCounts[c] == dictT[c]) {
                formed++;
            }

            while (l <= r && formed == required) {
                c = s[l];
                if (ans[0] == -1 || r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }

                windowCounts[c]--;
                if (dictT.ContainsKey(c) && windowCounts[c] < dictT[c]) {
                    formed--;
                }

                l++;
            }

            r++;
        }

        return ans[0] == -1 ? "" : s.Substring(ans[1], ans[2] - ans[1] + 1);
    }
}

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

Задача: 160. Intersection of Two Linked Lists
Сложность: easy

Даны головы двух односвязных списков headA и headB. Верните узел, в котором эти два списка пересекаются. Если два связанных списка не имеют пересечений, верните null.

Например, следующие два связанных списка начинают пересекаться в узле c1.

Пример:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

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

1⃣Сохранение ссылок из списка B:
Проходим по всем узлам списка B и сохраняем ссылки (адреса) каждого узла в хеш-таблицу. Это позволит нам быстро проверять, содержится ли узел из списка A в списке B.

2⃣Проверка узлов списка A:
Далее, для каждого узла из списка A проверяем, существует ли такой узел в хеш-таблице, созданной на предыдущем шаге. Если такой узел найден, то он является точкой пересечения, и мы возвращаем этот узел.

3⃣Обработка отсутствия пересечения:
Если до конца списка A не найдено ни одного узла, который бы совпал с узлами из хеш-таблицы, возвращаем null, указывая на отсутствие пересечения между списками.

😎 Решение:

public class Solution {
    public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> nodesInB = new HashSet<ListNode>();

        while (headB != null) {
            nodesInB.Add(headB);
            headB = headB.next;
        }

        while (headA != null) {
            if (nodesInB.Contains(headA)) {
                return headA;
            }

            headA = headA.next;
        }

        return null;
    }
}

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

Задача: 745. Prefix and Suffix Search
Сложность: hard

Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.

Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

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

1⃣Сохраните слова и их индексы в словаре.

2⃣Создайте объединенные ключи, состоящие из префиксов и суффиксов для всех возможных комбинаций.

3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу.

😎 Решение:

using System;
using System.Collections.Generic;

public class WordFilter {
    private Dictionary<string, int> prefixSuffixMap = new Dictionary<string, int>();
    
    public WordFilter(string[] words) {
        for (int index = 0; index < words.Length; index++) {
            string word = words[index];
            int length = word.Length;
            for (int prefixLength = 1; prefixLength <= length; prefixLength++) {
                for (int suffixLength = 1; suffixLength <= length; suffixLength++) {
                    string prefix = word.Substring(0, prefixLength);
                    string suffix = word.Substring(length - suffixLength);
                    string key = prefix + "#" + suffix;
                    prefixSuffixMap[key] = index;
                }
            }
        }
    }
    
    public int F(string pref, string suff) {
        string key = pref + "#" + suff;
        return prefixSuffixMap.ContainsKey(key) ? prefixSuffixMap[key] : -1;
    }
}

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

Задача: 392. Is Subsequence
Сложность: easy

Даны две строки s и t. Верните true, если s является подпоследовательностью t, иначе верните false.

Подпоследовательность строки — это новая строка, которая формируется из исходной строки путем удаления некоторых (возможно, ни одного) символов без нарушения относительных позиций оставшихся символов. (например, "ace" является подпоследовательностью "abcde", тогда как "aec" не является).

Пример:

Input: s = "abc", t = "ahbgdc"
Output: true

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

1⃣Назначьте два указателя: левый для исходной строки и правый для целевой строки. Эти указатели будут использоваться для итерации по строкам и сравнения их символов.

2⃣Перемещайте указатели в зависимости от совпадения символов. Если символы на текущих позициях указателей совпадают, переместите оба указателя на один шаг вперед. Если символы не совпадают, переместите только правый указатель целевой строки.

3⃣Итерация завершается, когда один из указателей выходит за пределы своей строки. Если в конце итерации все символы исходной строки были найдены в целевой строке, исходная строка является подпоследовательностью целевой строки.

😎 Решение:

public class Solution {
    public bool IsSubsequence(string s, string t) {
        int leftBound = s.Length, rightBound = t.Length;
        int pLeft = 0, pRight = 0;

        while (pLeft < leftBound && pRight < rightBound) {
            if (s[pLeft] == t[pRight]) {
                pLeft += 1;
            }
            pRight += 1;
        }
        return pLeft == leftBound;
    }
}

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

Задача: 111. Minimum Depth of Binary Tree
Сложность: easy

Дано бинарное дерево, найдите его минимальную глубину.

Минимальная глубина - это количество узлов вдоль самого короткого пути от корневого узла до ближайшего листового узла.

Пример:

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

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

1⃣Мы будем использовать метод обхода в глубину (dfs) с корнем в качестве аргумента.
Базовое условие рекурсии: это для узла NULL, в этом случае мы должны вернуть 0.

2⃣Если левый ребенок корня является NULL: тогда мы должны вернуть 1 + минимальную глубину для правого ребенка корневого узла, что равно 1 + dfs(root.right).

3⃣Если правый ребенок корня является NULL: тогда мы должны вернуть 1 + минимальную глубину для левого ребенка корневого узла, что равно 1 + dfs(root.left). Если оба ребенка не являются NULL, тогда вернуть 1 + min(dfs(root.left), dfs(root.right)).

😎 Решение:

public class Solution {
    private int Dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null) {
            return 1 + Dfs(root.right);
        } else if (root.right == null) {
            return 1 + Dfs(root.left);
        }
        return 1 + Math.Min(Dfs(root.left), Dfs(root.right));
    }

    public int MinDepth(TreeNode root) {
        return Dfs(root);
    }
}

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

Задача: 215. Kth Largest Element in an Array
Сложность: medium

Дан целочисленный массив nums и целое число k. Верните k-й наибольший элемент в массиве.

Обратите внимание, что это k-й наибольший элемент в отсортированном порядке, а не k-й уникальный элемент.

Пример:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

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

1⃣Отсортируйте массив в порядке убывания:
Используйте стандартную функцию сортировки для сортировки элементов массива nums в порядке убывания. В этом случае самый большой элемент будет первым в массиве, второй по величине - вторым и так далее.

2⃣Найдите k-й по величине элемент:
После сортировки просто верните элемент, который стоит на позиции k-1 (учитывая, что индексация в массиве начинается с 0).

3⃣Верните результат:
Возвратите найденное значение как результат.

😎 Решение:

public class Solution {
    public string ShortestPalindrome(string s) {
        int n = s.Length;
        char[] revArray = s.ToCharArray();
        Array.Reverse(revArray);
        string rev = new string(revArray);

        for (int i = 0; i < n; i++) {
            if (s.Substring(0, n - i) == rev.Substring(i)) {
                return rev.Substring(0, i) + s;
            }
        }

        return "";
    }
}

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

Задача: 1134. Armstrong Number
Сложность: easy

Дано целое число n, верните true, если и только если оно является числом Армстронга.

k-значное число n является числом Армстронга, если сумма k-й степени каждой его цифры равна n.

Пример:

Input: n = 153
Output: true
Explanation: 153 is a 3-digit number, and 153 = 1^3 + 5^3 + 3^3.

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

1⃣Получите количество цифр в n, преобразовав его в строку и найдя длину.

2⃣Создайте функцию getSumOfKthPowerOfDigits(n, k), которая возвращает сумму k-й степени каждой цифры числа n.
Инициализируйте переменную result для хранения результата.
Пока n не равно 0, добавляйте k-ю степень последней цифры n к result и удаляйте последнюю цифру.

3⃣Верните true, если результат равен исходному числу n.

😎 Решение:

public class Solution {
    public int GetSumOfKthPowerOfDigits(int n, int k) {
        int result = 0;
        while (n != 0) {
            int digit = n % 10;
            result += (int)Math.Pow(digit, k);
            n /= 10;
        }
        return result;
    }

    public bool IsArmstrong(int n) {
        int length = n.ToString().Length;
        return GetSumOfKthPowerOfDigits(n, length) == n;
    }
}

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

Задача: 535. Encode and Decode TinyURL
Сложность: medium

Спроектируйте класс для кодирования URL и декодирования короткого URL.
Нет ограничений на то, как ваш алгоритм кодирования/декодирования должен работать. Вам просто нужно убедиться, что URL может быть закодирован в короткий URL, а короткий URL может быть декодирован в исходный URL.

Реализуйте класс Solution:
Solution() Инициализирует объект системы.
String encode(String longUrl) Возвращает короткий URL для данного longUrl.
String decode(String shortUrl) Возвращает исходный длинный URL для данного shortUrl. Гарантируется, что данный shortUrl был закодирован тем же объектом.

Пример:

Input: url = "https://leetcode.com/problems/design-tinyurl"
Output: "https://leetcode.com/problems/design-tinyurl"

Explanation:
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after decoding it.

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

1⃣ Инициализация:
Создайте строку, содержащую все возможные символы (цифры и буквы), которые могут быть использованы для генерации кода.
Создайте хэш-таблицу для хранения соответствий коротких и длинных URL-адресов.
Создайте объект для генерации случайных чисел.

2⃣ Кодирование:
Сгенерируйте случайный 6-символьный код.
Если такой код уже существует в хэш-таблице, повторите генерацию.
Сохраните соответствие длинного URL и сгенерированного кода в хэш-таблице.
Верните полный короткий URL.

3⃣ Декодирование:
Удалите префикс короткого URL, чтобы получить код.
Используйте код для поиска длинного URL в хэш-таблице.
Верните длинный URL.

😎 Решение:

public class Codec {
    private static string alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    private Dictionary<string, string> map = new Dictionary<string, string>();
    private Random rand = new Random();
    
    private string GetRand() {
        var sb = new StringBuilder();
        for (int i = 0; i < 6; i++) {
            sb.Append(alphabet[rand.Next(62)]);
        }
        return sb.ToString();
    }

    public string Encode(string longUrl) {
        string key = GetRand();
        while (map.ContainsKey(key)) {
            key = GetRand();
        }
        map[key] = longUrl;
        return "http://tinyurl.com/" + key;
    }

    public string Decode(string shortUrl) {
        string key = shortUrl.Replace("http://tinyurl.com/", "");
        return map[key];
    }
}

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

Задача: 57. Insert Interval
Сложность: medium

Дан массив intervals, содержащий непересекающиеся интервалы, отсортированные по start. Дано newInterval = [start, end].

Нужно вставить newInterval так, чтобы intervals оставался отсортированным и не имел пересекающихся интервалов.

Пример:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]  
Output: [[1,5],[6,9]]  

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

1⃣Добавить в результат все интервалы, которые переходят к новому интервалу и не пересекаются с ними.

2⃣Объединить все пересекающиеся интервалы с newInterval в один.

3⃣Добавить функциональные интервалы без изменений.

😎 Решение:

public class Solution {
    public int[][] Insert(int[][] intervals, int[] newInterval) {
        int n = intervals.Length, i = 0;
        List<int[]> res = new List<int[]>();

        while (i < n && intervals[i][1] < newInterval[0]) {
            res.Add(intervals[i]);
            i++;
        }

        while (i < n && newInterval[1] >= intervals[i][0]) {
            newInterval[0] = Math.Min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.Max(newInterval[1], intervals[i][1]);
            i++;
        }

        res.Add(newInterval);

        while (i < n) {
            res.Add(intervals[i]);
            i++;
        }

        return res.ToArray();
    }
}

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

Задача: 1061. Lexicographically Smallest Equivalent String
Сложность: medium

Даны две строки одинаковой длины s1 и s2, а также строка baseStr.

Мы говорим, что символы s1[i] и s2[i] эквивалентны.

Например, если s1 = "abc" и s2 = "cde", то 'a' == 'c', 'b' == 'd' и 'c' == 'e'. Эквивалентные символы следуют правилам рефлексивности, симметрии и транзитивности.

Верните лексикографически наименьшую эквивалентную строку baseStr, используя информацию об эквивалентности из s1 и s2.

Пример:

Input: s1 = "parker", s2 = "morris", baseStr = "parser"
Output: "makkek"
Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [m,p], [a,o], [k,r,s], [e,i].
The characters in each group are equivalent and sorted in lexicographical order.
So the answer is "makkek".

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

1⃣Создайте матрицу смежности adjMatrix размером 26x26 для хранения рёбер и массив visited для отслеживания посещённых символов.

2⃣Итеративно обрабатывайте каждый символ от 0 до 25:

Если символ ещё не посещён, выполните DFS, начиная с этого символа, и сохраните все пройденные символы в векторе component, а минимальный из этих символов в переменной minChar.
Обновите все символы из component до minChar в векторе mappingChar, который хранит окончательное сопоставление символов baseStr.

3⃣Пройдите по baseStr и создайте итоговую строку ans, используя символы из mappingChar.

😎 Решение:

class Solution {
    void DFS(int src, int[,] adjMatrix, int[] visited, List<int> component, ref int minChar) {
        visited[src] = 1;
        component.Add(src);
        minChar = Math.Min(minChar, src);
        for (int i = 0; i < 26; i++) {
            if (adjMatrix[src, i] != 0 && visited[i] == 0) {
                DFS(i, adjMatrix, visited, component, ref minChar);
            }
        }
    }

    public string SmallestEquivalentString(string s1, string s2, string baseStr) {
        int[,] adjMatrix = new int[26, 26];
        for (int i = 0; i < s1.Length; i++) {
            adjMatrix[s1[i] - 'a', s2[i] - 'a'] = 1;
            adjMatrix[s2[i] - 'a', s1[i] - 'a'] = 1;
        }
        int[] mappingChar = new int[26];
        for (int i = 0; i < 26; i++) {
            mappingChar[i] = i;
        }
        int[] visited = new int[26];
        for (int c = 0; c < 26; c++) {
            if (visited[c] == 0) {
                List<int> component = new List<int>();
                int minChar = 27;
                DFS(c, adjMatrix, visited, component, ref minChar);
                foreach (int vertex in component) {
                    mappingChar[vertex] = minChar;
                }
            }
        }
        StringBuilder ans = new StringBuilder();
        foreach (char c in baseStr) {
            ans.Append((char)(mappingChar[c - 'a'] + 'a'));
        }
        return ans.ToString();
    }
}

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