Задача: 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;
    }
}

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

Задача: 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;
    }
}

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

Задача: 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;
    }
}

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

Задача: 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);
    }
}

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

Задача: 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();
    }
}

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

Задача: 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
    }
}

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

Задача: 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;
    }
}

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

Задача: 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];
    }
}

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

Задача: 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;
    }
}

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

Задача: 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;
    }
}

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

Задача: 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;
    }
}

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

Задача: 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;
    }
}

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

Задача: 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();
    }
}

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

Задача: 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;
    }
}

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

Задача: 714. Best Time to Buy and Sell Stock with Transaction Fee
Сложность: medium

Вам дан массив prices, где prices[i] - это цена данной акции в i-й день, и целое число fee, представляющее собой комиссию за сделку. Найдите максимальную прибыль, которую вы можете получить. Вы можете совершить сколько угодно сделок, но за каждую сделку вам придется заплатить комиссию. Примечание: Вы не можете совершать несколько сделок одновременно (то есть вы должны продать акции, прежде чем купить их снова). Комиссия за сделку взимается только один раз за каждую покупку и продажу акций.

Пример:

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8

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

1⃣Инициализируйте две переменные: cash, представляющую максимальную прибыль без наличия акций, и hold, представляющую максимальную прибыль с наличием акций.

2⃣Пройдите по каждому элементу массива prices и обновите значения cash и hold, используя текущую цену и комиссию.

3⃣Верните значение cash, которое будет максимальной прибылью без наличия акций.

😎 Решение:

public class Solution {
    public int MaxProfit(int[] prices, int fee) {
        int cash = 0, hold = -prices[0];
        foreach (int price in prices) {
            cash = Math.Max(cash, hold + price - fee);
            hold = Math.Max(hold, cash - price);
        }
        return cash;
    }
}

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