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

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

Задача: 499. The Maze III
Сложность: hard

В лабиринте есть мячик с пустыми пространствами (0) и стенами (1). Мячик может катиться вверх, вниз, влево или вправо, пока не столкнется со стеной, затем выбрать новое направление. В лабиринте также есть отверстие, куда мячик упадет, если закатится в него.

Дан лабиринт размером m x n, позиция мяча ball и отверстия hole, где ball = [ballrow, ballcol] и hole = [holerow, holecol]. Верните строку instructions с кратчайшим путем мячика к отверстию. Если существует несколько вариантов, верните лексикографически минимальный. Если путь невозможен, верните "impossible". Ответ должен содержать 'u' (вверх), 'd' (вниз), 'l' (влево) и 'r' (вправо).
Расстояние — это количество пройденных пустых пространств от начальной позиции (исключительно) до конечной (включительно).

Вы можете предположить, что границы лабиринта — это стены. В примере ниже они не указаны.

Пример:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], ball = [4,3], hole = [0,1]
Output: "lul"

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

1⃣Инициализация и вспомогательные функции
Создайте функцию valid для проверки, находится ли координата (row, col) в пределах лабиринта и является ли она пустым пространством. Создайте функцию getNeighbors для получения списка соседей для данной позиции. Двигайтесь в каждом направлении (вверх, вниз, влево, вправо) до встречи со стеной.

2⃣Запуск алгоритма Дейкстры
Инициализируйте очередь с начальной позицией мяча, где элементы с меньшим расстоянием имеют высокий приоритет, а при равных расстояниях выбирайте минимальную строку пути. Создайте структуру seen для отслеживания посещенных узлов.

3⃣Поиск кратчайшего пути
Пока очередь не пуста, извлекайте узел с наименьшим расстоянием. Если узел посещен, пропустите его. Если это отверстие, верните текущий путь. Отметьте узел как посещенный, добавьте его соседей в очередь, обновив расстояние и путь. Если пути нет, верните "impossible".

😎 Решение:

using System;
using System.Collections.Generic;

public class State : IComparable<State> {
    public int Row, Col, Dist;
    public string Path;
    public State(int r, int c, int d, string p) { Row = r; Col = c; Dist = d; Path = p; }
    public int CompareTo(State other) {
        return Dist == other.Dist ? string.Compare(Path, other.Path, StringComparison.Ordinal) : Dist - other.Dist;
    }
}

public class Solution {
    private static readonly int[][] Directions = { new[] {0, -1}, new[] {-1, 0}, new[] {0, 1}, new[] {1, 0} };
    private static readonly string[] TextDirections = { "l", "u", "r", "d" };

    public string FindShortestWay(int[][] maze, int[] ball, int[] hole) {
        int m = maze.Length, n = maze[0].Length;
        var heap = new PriorityQueue<State>();
        var seen = new bool[m, n];
        heap.Enqueue(new State(ball[0], ball[1], 0, ""));
        
        while (heap.Count > 0) {
            var curr = heap.Dequeue();
            if (seen[curr.Row, curr.Col]) continue;
            if (curr.Row == hole[0] && curr.Col == hole[1]) return curr.Path;
            seen[curr.Row, curr.Col] = true;
            
            foreach (var (dy, dx, direction) in Directions.Zip(TextDirections)) {
                int r = curr.Row, c = curr.Col, dist = 0;
                while (Valid(r + dy, c + dx, maze, m, n)) {
                    r += dy; c += dx; dist++;
                    if (r == hole[0] && c == hole[1]) break;
                }
                heap.Enqueue(new State(r, c, curr.Dist + dist, curr.Path + direction));
            }
        }
        return "impossible";
    }

    private bool Valid(int row, int col, int[][] maze, int m, int n) {
        return row >= 0 && row < m && col >= 0 && col < n && maze[row][col] == 0;
    }
}

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

Задача: 333. Largest BST Subtree
Сложность: medium

Дан корень бинарного дерева, найдите самое большое поддерево, которое также является деревом бинарного поиска (BST), где "самое большое" означает поддерево с наибольшим количеством узлов.

Дерево бинарного поиска (BST) — это дерево, в котором все узлы соблюдают следующие свойства:
Значения в левом поддереве меньше значения их родительского (корневого) узла.
Значения в правом поддереве больше значения их родительского (корневого) узла.
Примечание: Поддерево должно включать всех своих потомков.

Пример:

Input: root = [10,5,15,1,8,null,7]
Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.

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

1⃣Пост-упорядоченный обход дерева:
Обходите каждую ноду дерева в пост-упорядоченном порядке (left-right-root). Это позволит гарантировать, что обе поддеревья ноды уже проверены на соответствие критериям BST перед проверкой самой ноды.

2⃣Проверка условий BST для каждой ноды:
Для каждой ноды определите минимальное и максимальное значения в её левом и правом поддеревьях. Проверьте, удовлетворяет ли текущее поддерево условиям BST:
- значение текущей ноды должно быть больше максимального значения в левом поддереве.
- значение текущей ноды должно быть меньше минимального значения в правом поддереве.
Если условия выполняются, вычислите размер текущего поддерева как сумму размеров левого и правого поддеревьев плюс 1 (для текущей ноды).

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

😎 Решение:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class NodeValue {
    public int minNode, maxNode, maxSize;
    
    public NodeValue(int minNode, int maxNode, int maxSize) {
        this.minNode = minNode;
        this.maxNode = maxNode;
        this.maxSize = maxSize;
    }
}

public class Solution {
    private NodeValue largestBSTSubtreeHelper(TreeNode root) {
        if (root == null) {
            return new NodeValue(int.MaxValue, int.MinValue, 0);
        }
        
        NodeValue left = largestBSTSubtreeHelper(root.left);
        NodeValue right = largestBSTSubtreeHelper(root.right);
        
        if (left.maxNode < root.val && root.val < right.minNode) {
            return new NodeValue(Math.Min(root.val, left.minNode), Math.Max(root.val, right.maxNode), 
                                 left.maxSize + right.maxSize + 1);
        }
        
        return new NodeValue(int.MinValue, int.MaxValue, Math.Max(left.maxSize, right.maxSize));
    }
    
    public int LargestBSTSubtree(TreeNode root) {
        return largestBSTSubtreeHelper(root).maxSize;
    }
}

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

Задача: 683. K Empty Slots
Сложность: hard

У вас есть n лампочек, расположенных в ряд и пронумерованных от 1 до n. Изначально все лампочки выключены. Каждый день мы включаем ровно одну лампочку, и через n дней все лампочки будут включены.

Вам дан массив bulbs длины n, где bulbs[i] = x означает, что в (i+1)-й день мы включим лампочку в позиции x, где i индексируется с 0, а x индексируется с 1.

Дано целое число k, верните минимальный номер дня, такой что существует две включенные лампочки, между которыми ровно k выключенных лампочек. Если такого дня не существует, верните -1.

Пример:

Input: bulbs = [1,3,2], k = 1
Output: 2
Explanation:
On the first day: bulbs[0] = 1, first bulb is turned on: [1,0,0]
On the second day: bulbs[1] = 3, third bulb is turned on: [1,0,1]
On the third day: bulbs[2] = 2, second bulb is turned on: [1,1,1]
We return 2 because on the second day, there were two on bulbs with one off bulb between them.

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

1⃣Поддерживайте active, отсортированную структуру данных, содержащую каждую лампочку, которая в данный момент включена. Это позволит быстро находить соседей для вновь добавленных лампочек и проверять условия задачи.

2⃣Когда вы добавляете лампочку в active, проверьте ее нижних и верхних соседей. Для этого найдите ближайшие включенные лампочки с обеих сторон и проверьте количество выключенных лампочек между ними.

3⃣Если какой-то сосед удовлетворяет условию (ровно k выключенных лампочек между двумя включенными), значит, условие впервые произошло в этот день, и вы можете вернуть номер этого дня. Если такого дня не существует после включения всех лампочек, верните -1.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int KEmptySlots(int[] bulbs, int k) {
        SortedSet<int> active = new SortedSet<int>();
        int day = 0;
        
        foreach (int bulb in bulbs) {
            day++;
            active.Add(bulb);
            var lower = active.GetViewBetween(0, bulb - 1).Max;
            var higher = active.GetViewBetween(bulb + 1, int.MaxValue).Min;
            
            if ((lower != null && bulb - lower - 1 == k) ||
                (higher != null && higher - bulb - 1 == k)) {
                return day;
            }
        }
        return -1;
    }
}

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

Задача: 270. Closest Binary Search Tree Value
Сложность: easy

Дано корень бинарного дерева поиска и целевое значение. Верните значение в дереве, которое ближе всего к целевому. Если существует несколько ответов, выведите наименьшее.

Пример:

Input: root = [4,2,5,1,3], target = 3.714286
Output: 4

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

1⃣Построить массив с помощью inorder обхода:
Выполнить inorder обход дерева и собрать элементы в отсортированный массив.

2⃣Найти ближайший элемент:
Пройти по массиву и определить элемент, наиболее близкий к целевому значению.

3⃣Выбрать наименьший из ближайших элементов:
Если несколько элементов одинаково близки к целевому значению, выбрать наименьший из них.

😎 Решение:

public class Solution {
    public int ClosestValue(TreeNode root, double target) {
        int closest = root.val;
        while (root != null) {
            if (Math.Abs(root.val - target) < Math.Abs(closest - target)) {
                closest = root.val;
            } else if (Math.Abs(root.val - target) == Math.Abs(closest - target)) {
                closest = Math.Min(root.val, closest);
            }
            root = target < root.val ? root.left : root.right;
        }
        return closest;
    }
}

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

Задача: 973. K Closest Points to Origin
Сложность: medium

Дан массив точек, где points[i] = [xi, yi] представляет собой точку на плоскости X-Y, и целое число k. Верните k точек, ближайших к началу координат (0, 0).

Расстояние между двумя точками на плоскости X-Y является евклидовым расстоянием (то есть √((x1 - x2)² + (y1 - y2)²)).

Вы можете вернуть ответ в любом порядке. Гарантируется, что ответ будет уникальным (за исключением порядка).

Пример:

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

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

1⃣Отсортируйте массив с помощью функции компаратора.

2⃣Функция компаратора будет использовать уравнение квадратного евклидова расстояния для сравнения двух точек.

3⃣Верните первые k элементов массива.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public int[][] KClosest(int[][] points, int k) {
        Array.Sort(points, (a, b) => SquaredDistance(a).CompareTo(SquaredDistance(b)));
        var result = new int[k][];
        Array.Copy(points, result, k);
        return result;
    }

    private int SquaredDistance(int[] point) {
        return point[0] * point[0] + point[1] * point[1];
    }
}

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

Задача: 405. Convert a Number to Hexadecimal
Сложность: easy

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

Пример:

Input: num = 26
Output: "1a"

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

1⃣Определите, является ли число отрицательным. Если да, преобразуйте его в положительное число с помощью метода дополнения до двух. Для этого прибавьте к числу 2^32 и используйте битовую операцию И с маской 0xFFFFFFFF.

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

3⃣Переверните строку результата и удалите ведущие нули, если они есть. Если строка пустая, верните "0".

😎 Решение:

public class Solution {
    public string ToHex(int num) {
        if (num == 0) return "0";
        char[] hexChars = "0123456789abcdef".ToCharArray();
        uint n = (uint)num;
        StringBuilder result = new StringBuilder();
        while (n > 0) {
            result.Append(hexChars[n % 16]);
            n /= 16;
        }
        char[] charArray = result.ToString().ToCharArray();
        Array.Reverse(charArray);
        return new string(charArray);
    }
}

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

Задача: 28. Find the Index of the First Occurrence in a String
Сложность: easy

Учитывая две строки needle и haystack, верните индекс первого вхождения needle в haystack или -1, если needle не является частью haystack.

Пример:

Input: haystack = "sadbutsad", needle = "sad"  
Output: 0  

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

1⃣Использовать два указателя i и j для прохода по haystack и needle.

2⃣Применить алгоритм KMP с использованием массива LPS (longest prefix suffix) для оптимального поиска.

3⃣Вернуть индекс первого вхождения needle или -1, если needle не найден.

😎 Решение:

public class Solution {
    public int StrStr(string haystack, string needle) {
        int i = 0, j = 0;
        int[] lps = BuildLPS(needle);
        
        while (i < haystack.Length) {
            if (haystack[i] == needle[j]) {
                i++;
                j++;
                if (j == needle.Length) return i - j;
            } else {
                if (j > 0) j = lps[j - 1];
                else i++;
            }
        }
        
        return -1;
    }
    
    private int[] BuildLPS(string needle) {
        int[] lps = new int[needle.Length];
        int i = 0;

        for (int j = 1; j < needle.Length;) {
            if (needle[i] == needle[j]) {
                lps[j++] = ++i;
            } else {
                if (i > 0) i = lps[i - 1];
                else j++;
            }
        }

        return lps;
    }
}

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

Задача: 922. Sort Array By Parity II
Сложность: medium

Дан массив целых чисел nums, половина целых чисел в нем нечетные, а другая половина - четные. Отсортируйте массив так, чтобы во всех случаях, когда nums[i] нечетный, i был нечетным, а во всех случаях, когда nums[i] четный, i был четным. Верните любой массив ответов, удовлетворяющий этому условию.

Пример:

Input: nums = [4,2,5,7]
Output: [4,5,2,7]

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

1⃣Инициализировать два указателя even_idx и odd_idx для отслеживания позиций четных и нечетных индексов соответственно.

2⃣Пройти по массиву nums и для каждого элемента:
Если элемент четный, поместить его на позицию even_idx и увеличить even_idx на 2.
Если элемент нечетный, поместить его на позицию odd_idx и увеличить odd_idx на 2.

3⃣Вернуть отсортированный массив.

😎 Решение:

public class Solution {
    public int[] SortArrayByParityII(int[] nums) {
        int[] result = new int[nums.Length];
        int evenIdx = 0;
        int oddIdx = 1;
        
        foreach (int num in nums) {
            if (num % 2 == 0) {
                result[evenIdx] = num;
                evenIdx += 2;
            } else {
                result[oddIdx] = num;
                oddIdx += 2;
            }
        }
        
        return result;
    }
}

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

Задача: 413. Arithmetic Slices
Сложность: medium

Целочисленный массив называется арифметическим, если он состоит не менее чем из трех элементов и если разность между любыми двумя последовательными элементами одинакова. Например, [1,3,5,7,9], [7,7,7] и [3,-1,-5,-9] являются арифметическими последовательностями. Если задан целочисленный массив nums, верните количество арифметических подмассивов массива nums. Подмассив - это непрерывная подпоследовательность массива.

Пример:

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

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

1⃣Пройдите по массиву, инициализируя два указателя: начальный и текущий. Начните с первой пары элементов.

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

3⃣Суммируйте количество найденных арифметических подмассивов, учитывая, что для каждого арифметического подмассива длины len, количество таких подмассивов равно (len - 2).

😎 Решение:

public class Solution {
    public int NumberOfArithmeticSlices(int[] nums) {
        if (nums.Length < 3) return 0;
        int count = 0;
        int currentLength = 0;
        for (int i = 2; i < nums.Length; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                currentLength++;
                count += currentLength;
            } else {
                currentLength = 0;
            }
        }
        return count;
    }
}

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

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

Множество вещественных чисел можно представить как объединение нескольких несовпадающих интервалов, где каждый интервал имеет вид [a, b). Вещественное число x входит в множество, если один из его интервалов [a, b) содержит x (то есть a <= x < b). Вам дан отсортированный список непересекающихся интервалов, представляющих множество вещественных чисел, как описано выше, где intervals[i] = [ai, bi] представляет интервал [ai, bi). Вам также дан еще один интервал toBeRemoved. Верните набор вещественных чисел с интервалом toBeRemoved, удаленным из intervals. Другими словами, верните набор вещественных чисел, каждый x в котором находится в интервале, но не в toBeRemoved. Вашим ответом должен быть отсортированный список непересекающихся интервалов, как описано выше.

Пример:

Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]

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

1⃣Интерируйтесь по каждому интервалу в списке intervals.

2⃣Для каждого интервала, проверяйте пересечения с toBeRemoved и обновляйте список результатов.

3⃣Добавляйте непересекающиеся части текущего интервала в результат.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public IList<IList<double>> RemoveInterval(IList<IList<double>> intervals, IList<double> toBeRemoved) {
        var result = new List<IList<double>>();
        foreach (var interval in intervals) {
            if (interval[0] < toBeRemoved[0]) {
                result.Add(new List<double> { interval[0], Math.Min(interval[1], toBeRemoved[0]) });
            }
            if (interval[1] > toBeRemoved[1]) {
                result.Add(new List<double> { Math.Max(interval[0], toBeRemoved[1]), interval[1] });
            }
        }
        return result;
    }
}

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

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

Дан непустой массив целых чисел nums, в котором каждый элемент встречается дважды, кроме одного. Найдите этот единственный элемент.

Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство.

Пример:

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

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

1⃣Переберите все элементы в массиве nums.

2⃣Если какое-то число в nums новое для массива, добавьте его.

3⃣Если какое-то число уже есть в массиве, удалите его.

😎 Решение:

public class Solution {
    public int SingleNumber(int[] nums) {
        List<int> no_duplicate_list = new List<int>();
        foreach (int i in nums) {
            if (!no_duplicate_list.Contains(i)) {
                no_duplicate_list.Add(i);
            } else {
                no_duplicate_list.Remove(i);
            }
        }

        return no_duplicate_list[0];
    }
}

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