C# | LeetCode

Задача: 1207. Unique Number of Occurrences
Сложность: easy

Дан массив целых чисел arr. Верните true, если количество вхождений каждого значения в массиве уникально, или false в противном случае.

Пример:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

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

1⃣Сохраните частоты элементов массива arr в хэш-таблице freq.

2⃣Итерируйтесь по хэш-таблице freq и вставьте частоты всех уникальных элементов массива arr в хэш-набор freqSet.

3⃣Верните true, если размер хэш-набора freqSet равен размеру хэш-таблицы freq, иначе верните false.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public bool UniqueOccurrences(int[] arr) {
        Dictionary<int, int> freq = new Dictionary<int, int>();
        foreach (int num in arr) {
            if (freq.ContainsKey(num)) {
                freq[num]++;
            } else {
                freq[num] = 1;
            }
        }
        HashSet<int> freqSet = new HashSet<int>(freq.Values);
        return freq.Count == freqSet.Count;
    }
}

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

Задача: 892. Surface Area of 3D Shapes
Сложность: easy

Вам дана сетка n x n, на которой вы разместили несколько кубиков 1 x 1 x 1. Каждое значение v = grid[i][j] представляет собой башню из v кубиков, размещенных на вершине ячейки (i, j). После размещения кубиков вы решили склеить все непосредственно прилегающие кубики друг с другом, образовав несколько неправильных 3D-фигур. Верните общую площадь поверхности получившихся фигур. Примечание: нижняя грань каждой фигуры учитывается в площади ее поверхности.

Пример:

Input: grid = [[1,2],[3,4]]
Output: 34

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

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

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

3⃣Просуммировать все значения площадей для получения итоговой площади поверхности.

😎 Решение:

public int SurfaceArea(int[][] grid) {
    int n = grid.Length;
    int area = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] > 0) {
                area += (grid[i][j] * 4) + 2;
            }
            if (i > 0) {
                area -= Math.Min(grid[i][j], grid[i-1][j]) * 2;
            }
            if (j > 0) {
                area -= Math.Min(grid[i][j], grid[i][j-1]) * 2;
            }
        }
    }
    return area;
}

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

Задача: 605. Can Place Flowers
Сложность: Easy

У вас есть длинная клумба, на которой некоторые участки засажены, а некоторые нет. Однако цветы нельзя сажать на соседних участках.

Дан целочисленный массив flowerbed, содержащий 0 и 1, где 0 означает пустой участок, а 1 — занятый участок, и целое число n. Верните true, если n новых цветов можно посадить на клумбе, не нарушая правила о соседних цветах, и false в противном случае.

Пример:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

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

1⃣Решение очень простое. Мы можем определить максимальное количество дополнительных цветов, count, которые можно посадить для данного расположения клумбы. Для этого мы проходим по всем элементам массива flowerbed и находим те элементы, которые равны 0 (означает пустую позицию).

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

3⃣Если полученное количество count больше или равно n, требуемому количеству цветов для посадки, мы можем посадить n цветов на пустые места, иначе - нет.

😎 Решение:

public class Solution {
    public bool CanPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        for (int i = 0; i < flowerbed.Length; i++) {
            if (flowerbed[i] == 0) {
                bool emptyLeft = i == 0 || flowerbed[i - 1] == 0;
                bool emptyRight = i == flowerbed.Length - 1 || flowerbed[i + 1] == 0;
                if (emptyLeft && emptyRight) {
                    flowerbed[i] = 1;
                    count++;
                }
            }
        }
        return count >= n;
    }
}

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

Задача: 527. Word Abbreviation
Сложность: hard

Дано массив уникальных строк words, верните минимально возможные сокращения для каждого слова.

Правила сокращения строки следующие:
Первоначальное сокращение для каждого слова: первый символ, затем количество символов между первым и последним символом, затем последний символ.
Если более одного слова имеют одинаковое сокращение, выполните следующее:
Увеличьте префикс (символы в первой части) каждого из их сокращений на 1.
Например, начнем с слов ["abcdef", "abndef"], оба изначально сокращены как "a4f". Последовательность операций будет следующей: ["a4f", "a4f"] -> ["ab3f", "ab3f"] -> ["abc2f", "abn2f"].
Эта операция повторяется до тех пор, пока каждое сокращение не станет уникальным.
В конце, если сокращение не сделало слово короче, оставьте его в исходном виде.

Пример:

Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

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

1⃣ Инициализация и создание начальных сокращений:
Создайте массив для хранения сокращений и массив для отслеживания длины префикса каждого слова.
Для каждого слова создайте начальное сокращение с использованием первого символа, количества символов между первым и последним символом и последнего символа.

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

3⃣ Возврат результата:
Верните окончательные сокращения для каждого слова, убедившись, что они минимально возможны и уникальны.

😎 Решение:

public class Solution {
    public IList<string> WordsAbbreviation(IList<string> words) {
        int n = words.Count;
        string[] ans = new string[n];
        int[] prefix = new int[n];

        for (int i = 0; i < n; ++i)
            ans[i] = Abbrev(words[i], 0);

        for (int i = 0; i < n; ++i) {
            while (true) {
                HashSet<int> dupes = new HashSet<int>();
                for (int j = i + 1; j < n; ++j) {
                    if (ans[i] == ans[j])
                        dupes.Add(j);
                }

                if (dupes.Count == 0) break;
                dupes.Add(i);
                foreach (int k in dupes)
                    ans[k] = Abbrev(words[k], ++prefix[k]);
            }
        }

        return ans.ToList();
    }

    private string Abbrev(string word, int i) {
        int n = word.Length;
        if (n - i <= 3) return word;
        return word.Substring(0, i + 1) + (n - i - 2) + word[n - 1];
    }
}

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

Задача: 762. Prime Number of Set Bits in Binary Representation
Сложность: hard

Если даны два целых числа left и right, верните количество чисел в диапазоне [left, right], имеющих простое число битов в двоичном представлении. Напомним, что число битов в двоичном представлении - это количество единиц, присутствующих в числе 1. Например, 21 в двоичном представлении - это 10101, которое имеет 3 бита.

Пример:

Input: left = 10, right = 15
Output: 5

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

1⃣Создайте функцию для подсчета количества единиц в двоичном представлении числа.

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

3⃣Пройдите через все числа в диапазоне [left, right] и подсчитайте числа, у которых количество битов в двоичном представлении является простым числом.

😎 Решение:

public class Solution {
    public int CountPrimeSetBits(int left, int right) {
        int count = 0;
        for (int num = left; num <= right; num++) {
            if (IsPrime(BitCount(num))) {
                count++;
            }
        }
        return count;
    }
    
    private int BitCount(int x) {
        int count = 0;
        while (x > 0) {
            count += x & 1;
            x >>= 1;
        }
        return count;
    }
    
    private bool IsPrime(int x) {
        if (x < 2) return false;
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) return false;
        }
        return true;
    }
}

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

Задача: 1114. Print in Order
Сложность: easy

Предположим, у нас есть класс:

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

Один и тот же экземпляр Foo будет передан трем разным потокам. Поток A вызовет first(), поток B вызовет second(), и поток C вызовет third(). Спроектируйте механизм и модифицируйте программу, чтобы гарантировать, что second() выполняется после first(), а third() выполняется после second().

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

Пример:

Input: nums = [1,2,3]
Output: "firstsecondthird"
Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.

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

1⃣Инициализация переменных:
Инициализируйте координационные переменные firstJobDone и secondJobDone, чтобы указать, что задания еще не выполнены.

2⃣Функция first():
В этой функции нет зависимости, поэтому можно сразу приступить к выполнению задания. В конце функции обновите переменную firstJobDone, чтобы указать, что первое задание выполнено.

3⃣Функции second() и third():
В функции second() проверьте статус firstJobDone. Если она не обновлена, подождите, иначе переходите к выполнению второго задания. В конце функции обновите переменную secondJobDone, чтобы отметить завершение второго задания.
В функции third() проверьте статус secondJobDone. Аналогично функции second(), подождите сигнала secondJobDone перед тем, как приступить к выполнению третьего задания.

😎 Решение:

using System;
using System.Threading;

public class Foo {
    private SemaphoreSlim firstJobDone = new SemaphoreSlim(0, 1);
    private SemaphoreSlim secondJobDone = new SemaphoreSlim(0, 1);

    public void First(Action printFirst) {
        printFirst();
        firstJobDone.Release();
    }

    public void Second(Action printSecond) {
        firstJobDone.Wait();
        printSecond();
        secondJobDone.Release();
    }

    public void Third(Action printThird) {
        secondJobDone.Wait();
        printThird();
    }
}

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

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

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

Задача: 635. Design Log Storage System
Сложность: medium

Вам дается несколько журналов, где каждый журнал содержит уникальный идентификатор и временную метку. Временная метка - это строка, имеющая следующий формат: Год:Месяц:День:Час:Минута:Секунда, например, 2017:01:01:23:59:59. Все домены - десятичные числа с нулевым добавлением. Реализация класса LogSystem: LogSystem() Инициализирует объект LogSystem. void put(int id, string timestamp) Сохраняет заданный журнал (id, timestamp) в вашей системе хранения.
int[] retrieve(string start, string end, string granularity) Возвращает идентификаторы журналов, временные метки которых находятся в диапазоне от start до end включительно. start и end имеют тот же формат, что и timestamp, а granularity означает, насколько точным должен быть диапазон (т. е. с точностью до дня, минуты и т. д.). Например, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", а granularity = "Day" означает, что нам нужно найти журналы в диапазоне от 1 января 2017 года до 2 января 2017 года включительно, а час, минуту и секунду для каждой записи журнала можно игнорировать.

Пример:

Input
["LogSystem", "put", "put", "put", "retrieve", "retrieve"]
[[], [1, "2017:01:01:23:59:59"], [2, "2017:01:01:22:59:59"], [3, "2016:01:01:00:00:00"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour"]]
Output
[null, null, null, null, [3, 2, 1], [2, 1]]

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

1⃣Инициализация и хранение журналов
Реализуйте метод put, который будет сохранять журнал с заданным id и timestamp в системе хранения.

2⃣Формирование диапазона
Реализуйте метод retrieve, который будет формировать диапазон временных меток на основе заданного start, end и granularity.

3⃣Фильтрация и возврат результатов
Используйте сформированный диапазон для фильтрации журналов и возврата идентификаторов тех журналов, чьи временные метки попадают в этот диапазон.

😎 Решение:

using System;
using System.Collections.Generic;

public class LogSystem {
    private List<LogEntry> logs;

    public LogSystem() {
        logs = new List<LogEntry>();
    }

    public void Put(int id, string timestamp) {
        logs.Add(new LogEntry(id, timestamp));
    }

    public IList<int> Retrieve(string start, string end, string granularity) {
        int index = GetGranularityIndex(granularity);
        string startPrefix = start.Substring(0, index);
        string endPrefix = end.Substring(0, index);

        List<int> result = new List<int>();
        foreach (var log in logs) {
            string timestampPrefix = log.Timestamp.Substring(0, index);
            if (startPrefix.CompareTo(timestampPrefix) <= 0 && timestampPrefix.CompareTo(endPrefix) <= 0) {
                result.Add(log.Id);
            }
        }
        return result;
    }

    private int GetGranularityIndex(string granularity) {
        switch (granularity) {
            case "Year": return 4;
            case "Month": return 7;
            case "Day": return 10;
            case "Hour": return 13;
            case "Minute": return 16;
            case "Second": return 19;
            default: return 19;
        }
    }

    private class LogEntry {
        public int Id { get; }
        public string Timestamp { get; }

        public LogEntry(int id, string timestamp) {
            Id = id;
            Timestamp = timestamp;
        }
    }
}

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

Задача: 1268. Search Suggestions System
Сложность: medium

Вам дан массив строк products и строка searchWord. Разработайте систему, которая предлагает не более трех названий продуктов после ввода каждого символа searchWord. Предлагаемые товары должны иметь общий префикс с searchWord. Если есть более трех продуктов с общим префиксом, возвращаются три лексикографически минимальных продукта. Возвращается список списков предложенных продуктов после ввода каждого символа searchWord.

Пример:

Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

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

1⃣Отсортируйте массив продуктов.

2⃣Итерируйтесь по каждому символу в searchWord, находите все продукты, которые соответствуют текущему префиксу.

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

😎 Решение:

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

public class Solution {
    public IList<IList<string>> SuggestedProducts(string[] products, string searchWord) {
        Array.Sort(products);
        var result = new List<IList<string>>();
        var prefix = "";
        foreach (var c in searchWord) {
            prefix += c;
            var suggestions = products.Where(p => p.StartsWith(prefix)).Take(3).ToList();
            result.Add(suggestions);
        }
        return result;
    }
}

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

Задача: 928. Minimize Malware Spread II
Сложность: hard

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.

Пример:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

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

1⃣Определить компоненты связности в графе.
Для каждой компоненты связности определить количество зараженных узлов и общее количество узлов.

2⃣Для каждого узла в initial удалить его и пересчитать количество зараженных узлов.

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

😎 Решение:

public class Solution {
    public int MinMalwareSpread(int[][] graph, int[] initial) {
        int n = graph.Length;
        var visited = new HashSet<int>();
        var components = new List<HashSet<int>>();
        
        void Dfs(int node) {
            var stack = new Stack<int>();
            stack.Push(node);
            var component = new HashSet<int>();
            while (stack.Count > 0) {
                int u = stack.Pop();
                if (!visited.Contains(u)) {
                    visited.Add(u);
                    component.Add(u);
                    for (int v = 0; v < n; v++) {
                        if (graph[u][v] == 1 && !visited.Contains(v)) {
                            stack.Push(v);
                        }
                    }
                }
            }
            components.Add(component);
        }
        
        for (int i = 0; i < n; i++) {
            if (!visited.Contains(i)) {
                Dfs(i);
            }
        }
        
        int[] infectedInComponent = new int[components.Count];
        int[] nodeToComponent = new int[n];
        Array.Fill(nodeToComponent, -1);
        
        for (int idx = 0; idx < components.Count; idx++) {
            var component = components[idx];
            foreach (int node in component) {
                nodeToComponent[node] = idx;
                if (Array.IndexOf(initial, node) >= 0) {
                    infectedInComponent[idx]++;
                }
            }
        }
        
        int minInfected = int.MaxValue;
        int resultNode = initial.Min();
        
        foreach (int node in initial) {
            int componentIdx = nodeToComponent[node];
            if (infectedInComponent[componentIdx] == 1) {
                int componentSize = components[componentIdx].Count;
                if (componentSize < minInfected || (componentSize == minInfected && node < resultNode)) {
                    minInfected = componentSize;
                    resultNode = node;
                }
            }
        }
        
        return resultNode;
    }
}

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

Задача: 959. Regions Cut By Slashes
Сложность: medium

n x n сетка состоит из квадратов размером 1 x 1, где каждый квадрат 1 x 1 содержит '/', '', или пустое пространство ' '. Эти символы делят квадрат на смежные области.

Дана сетка grid, представленная в виде строкового массива. Верните количество областей.

Обратите внимание, что обратные слеши экранированы, поэтому '' представлен как '\'.

Пример:

Input: grid = [" /","/ "]
Output: 2

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

1⃣Создайте 4*N*N узлов для каждой ячейки сетки и соедините их в соответствии с описанием.

2⃣Используйте структуру объединения-поиска (DSU), чтобы найти количество связанных компонентов.

3⃣Пройдите по всем узлам и посчитайте количество корневых узлов, которые представляют количество областей.

😎 Решение:

public class DSU {
    int[] parent;
    public DSU(int N) {
        parent = new int[N];
        for (int i = 0; i < N; ++i)
            parent[i] = i;
    }
    public int Find(int x) {
        if (parent[x] != x) parent[x] = Find(parent[x]);
        return parent[x];
    }
    public void Union(int x, int y) {
        parent[Find(x)] = Find(y);
    }
}

public class Solution {
    public int RegionsBySlashes(string[] grid) {
        int N = grid.Length;
        DSU dsu = new DSU(4 * N * N);
        
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                int root = 4 * (r * N + c);
                char val = grid[r][c];
                
                if (val != '\\') {
                    dsu.Union(root + 0, root + 1);
                    dsu.Union(root + 2, root + 3);
                }
                if (val != '/') {
                    dsu.Union(root + 0, root + 2);
                    dsu.Union(root + 1, root + 3);
                }
                
                if (r + 1 < N) {
                    dsu.Union(root + 3, (root + 4 * N) + 0);
                }
                if (r - 1 >= 0) {
                    dsu.Union(root + 0, (root - 4 * N) + 3);
                }
                if (c + 1 < N) {
                    dsu.Union(root + 2, (root + 4) + 1);
                }
                if (c - 1 >= 0) {
                    dsu.Union(root + 1, (root - 4) + 2);
                }
            }
        }
        
        int ans = 0;
        for (int x = 0; x < 4 * N * N; ++x) {
            if (dsu.Find(x) == x) {
                ++ans;
            }
        }
        
        return ans;
    }
}

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

Задача: 1165. Single-Row Keyboard
Сложность: easy

Есть специальная клавиатура, на которой все клавиши расположены в один ряд.

Дана строка keyboard длиной 26, указывающая на раскладку клавиатуры (индексирована от 0 до 25). Изначально ваш палец находится на индексе 0. Чтобы напечатать символ, нужно переместить палец на индекс нужного символа. Время, затраченное на перемещение пальца с индекса i на индекс j, равно |i - j|.

Вам нужно напечатать строку word. Напишите функцию для расчета времени, необходимого для её набора одним пальцем.

Пример:

Input: keyboard = "abcdefghijklmnopqrstuvwxyz", word = "cba"
Output: 4
Explanation: The index moves from 0 to 2 to write 'c' then to 1 to write 'b' then to 0 again to write 'a'.
Total time = 2 + 1 + 1 = 4.

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

1⃣Клавиатура содержит уникальные строчные английские буквы, поэтому мы можем сопоставить её с массивом размера 26. Создадим массив размера 26, назовём его keyIndices. Сохраните индекс каждой буквы в этом массиве, проходя по строке keyboard. Инициализируйте переменную result значением 0, которая будет хранить сумму всех расстояний. Объявите переменную prev, которая будет хранить индекс предыдущей клавиши. Поскольку начальная позиция равна 0, инициализируйте её значением 0.

2⃣Проходите по строке word буква за буквой. Для каждой буквы c добавьте ∣prev−indexOf(c)∣ к result. Обновите prev до индекса c.

3⃣Повторите шаги 6 и 7 для всех букв. В конце прохода result будет содержать итоговое время, необходимое для набора слова.

😎 Решение:

public class Solution {
    public int CalculateTime(string keyboard, string word) {
        int[] keyIndices = new int[26];
        for (int i = 0; i < keyboard.Length; i++) {
            keyIndices[keyboard[i] - 'a'] = i;
        }
        
        int prev = 0;
        int result = 0;
        
        foreach (char c in word) {
            int index = keyIndices[c - 'a'];
            result += Math.Abs(prev - index);
            prev = index;
        }
        
        return result;
    }
}

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

Задача: 153. Find Minimum in Rotated Sorted Array
Сложность: medium

Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,2,4,5,6,7] может стать:

[4,5,6,7,0,1,2], если он был повернут 4 раза.
[0,1,2,4,5,6,7], если он был повернут 7 раз.
Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Для данного отсортированного и повернутого массива nums с уникальными элементами верните минимальный элемент этого массива.

Вы должны написать алгоритм, который работает за время O(log n).

Пример:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

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

1⃣Нахождение середины массива:
Определите элемент, находящийся посередине массива.

2⃣Определение направления поиска:
Если элемент в середине больше первого элемента массива, это означает, что точка перегиба (минимальный элемент) находится справа от середины.
Если элемент в середине меньше первого элемента массива, это указывает на то, что точка перегиба находится слева от середины.

3⃣Остановка поиска при нахождении точки перегиба:
Поиск прекращается, когда найдена точка перегиба, когда выполняется одно из двух условий:
nums[mid] > nums[mid + 1] – следовательно, mid+1 является наименьшим элементом.
nums[mid - 1] > nums[mid] – следовательно, mid является наименьшим элементом.

😎 Решение:

public class Solution {
    public int FindMin(int[] nums) {
        if (nums.Length == 1) {
            return nums[0];
        }
        int left = 0, right = nums.Length - 1;

        if (nums[right] > nums[0]) {
            return nums[0];
        }

        while (right >= left) {
          
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                return nums[mid + 1];
            }

            if (nums[mid - 1] > nums[mid]) {
                return nums[mid];
            }
            if (nums[mid] > nums[0]) {
                left = mid + 1;
            } else {
                               right = mid - 1;
            }
        }

        return Int32.MaxValue;
    }
}

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

Задача: 1244. Design A Leaderboard
Сложность: medium

Разработайте класс Leaderboard, который содержит 3 функции: addScore(playerId, score): Обновляет таблицу лидеров, добавляя счет к счету данного игрока. Если в таблице лидеров нет игрока с таким id, добавьте его в таблицу лидеров с заданным счетом. top(K): Возвращает сумму очков K лучших игроков. reset(playerId): Сбрасывает счет игрока с заданным идентификатором в 0 (другими словами, стирает его из таблицы лидеров). Гарантируется, что игрок был добавлен в таблицу лидеров до вызова этой функции. Изначально таблица лидеров пуста.

Пример:

Input: 
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output: 
[null,null,null,null,null,null,73,null,null,null,141]

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

1⃣addScore(playerId, score):
Если игрок уже существует в таблице лидеров, добавляем к его текущему счету новое значение.
Если игрок не существует, добавляем его с заданным счетом.

2⃣top(K):
Сортируем игроков по их счету в порядке убывания.
Возвращаем сумму очков K лучших игроков.

3⃣reset(playerId):
Устанавливаем счет игрока в 0.

😎 Решение:

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

public class Leaderboard {
    private Dictionary<int, int> scores;

    public Leaderboard() {
        scores = new Dictionary<int, int>();
    }

    public void AddScore(int playerId, int score) {
        if (scores.ContainsKey(playerId)) {
            scores[playerId] += score;
        } else {
            scores[playerId] = score;
        }
    }

    public int Top(int K) {
        return scores.Values.OrderByDescending(x => x).Take(K).Sum();
    }

    public void Reset(int playerId) {
        if (scores.ContainsKey(playerId)) {
            scores[playerId] = 0;
        }
    }
}

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

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

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

Сотни представляют глубину d этого узла, где 1 <= d <= 4.
Десятки представляют позицию p этого узла на уровне, которому он принадлежит, где 1 <= p <= 8. Позиция соответствует позиции в полном бинарном дереве.
Единицы представляют значение v этого узла, где 0 <= v <= 9.
Дан массив возрастающих трехзначных чисел nums, представляющих бинарное дерево с глубиной меньше 5. Верните сумму всех путей от корня к листьям.

Гарантируется, что данный массив представляет собой валидное связанное бинарное дерево.

Пример:

Input: nums = [113,215,221]
Output: 12
Explanation: The tree that the list represents is shown.
The path sum is (3 + 5) + (3 + 1) = 12.

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

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

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

3⃣Подсчет суммы путей:
Выполните обход дерева (например, используя DFS) и подсчитайте сумму всех путей от корня к листьям.

😎 Решение:

public class Solution {
    public int PathSum(int[] nums) {
        var tree = new Dictionary<int, int>();
        
        foreach (int num in nums) {
            int depth = num / 100;
            int pos = (num / 10) % 10;
            int val = num % 10;
            tree[depth * 10 + pos] = val;
        }
        
        return Dfs(tree, 1, 1, 0);
    }
    
    private int Dfs(Dictionary<int, int> tree, int depth, int pos, int currentSum) {
        int key = depth * 10 + pos;
        if (!tree.ContainsKey(key)) {
            return 0;
        }
        currentSum += tree[key];
        int leftChild = (depth + 1) * 10 + 2 * pos - 1;
        int rightChild = (depth + 1) * 10 + 2 * pos;
        if (!tree.ContainsKey(leftChild) && !tree.ContainsKey(rightChild)) {
            return currentSum;
        }
        return Dfs(tree, depth + 1, 2 * pos - 1, currentSum) + Dfs(tree, depth + 1, 2 * pos, currentSum);
    }
}

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

Задача: 318. Maximum Product of Word Lengths
Сложность: medium

Дан массив строк words, верните максимальное значение произведения длины word[i] на длину word[j], где два слова не имеют общих букв. Если таких двух слов не существует, верните 0.

Пример:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

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

1⃣Предварительная обработка масок и длин
Вычислите битовые маски для всех слов и сохраните их в массиве masks. Сохраните длины всех слов в массиве lens.

2⃣Сравнение слов и проверка общих букв
Сравните каждое слово с каждым последующим словом. Если два слова не имеют общих букв (проверка с использованием масок: (masks[i] & masks[j]) == 0), обновите максимальное произведение maxProd.

3⃣Возврат результата
Верните максимальное значение произведения maxProd.

😎 Решение:

public class Solution {
    public int MaxProduct(string[] words) {
        int n = words.Length;
        int[] masks = new int[n];
        int[] lens = new int[n];
        
        for (int i = 0; i < n; i++) {
            int bitmask = 0;
            foreach (char ch in words[i]) {
                bitmask |= 1 << (ch - 'a');
            }
            masks[i] = bitmask;
            lens[i] = words[i].Length;
        }
        
        int maxVal = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    maxVal = Math.Max(maxVal, lens[i] * lens[j]);
                }
            }
        }
        return maxVal;
    }
}

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

Задача: 678. Valid Parenthesis String
Сложность: medium

Создайте карту, которая позволяет выполнять следующие действия:

Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:

Дана строка s, содержащая только три типа символов: '(', ')' и '*'. Вернуть true, если s является допустимой.

Следующие правила определяют допустимую строку:

Любая открывающая скобка '(' должна иметь соответствующую закрывающую скобку ')'.
Любая закрывающая скобка ')' должна иметь соответствующую открывающую скобку '('.
Открывающая скобка '(' должна идти перед соответствующей закрывающей скобкой ')'.
'*' может рассматриваться как одна закрывающая скобка ')', одна открывающая скобка '(' или пустая строка "".

Пример:

Input: s = "()"
Output: true
Example 2:

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

1⃣Инициализировать 2D вектор memo размером s.size() x s.size() - 1, представляющий неинициализированное состояние. Вызвать вспомогательную функцию isValidString с начальными параметрами index = 0, openCount = 0 и строкой s. Вернуть результат isValidString.

2⃣Вспомогательная функция isValidString. Базовый случай: если index достиг конца строки (index == s.size.), вернуть true, если openCount равен 0 (все скобки сбалансированы), и false в противном случае. Проверить, был ли результат для текущего index и openCount уже вычислен (мемоизирован) в memo. Если да, вернуть мемоизированный результат. Инициализировать isValid как false. Если текущий символ s[index] равен '*': Попробовать трактовать '*' как '(' и вызвать isValidString рекурсивно с index + 1 и openCount + 1. Если рекурсивный вызов вернет true, обновить isValid на true. Если openCount не равен нулю, попробовать трактовать '*' как ')' и вызвать isValidString рекурсивно с index + 1 и openCount - 1. Если рекурсивный вызов вернет true, обновить isValid на true. Попробовать трактовать '*' как пустой символ и вызвать isValidString рекурсивно с index + 1 и тем же openCount. Если рекурсивный вызов вернет true, обновить isValid на true.

3⃣Продолжение функции isValidString. Если текущий символ s[index] равен '(': Вызвать isValidString рекурсивно с index + 1 и openCount + 1. Обновить isValid с результатом рекурсивного вызова. Если текущий символ s[index] равен ')': Если openCount не равен нулю (есть открытые скобки), вызвать isValidString рекурсивно с index + 1 и openCount - 1. Обновить isValid с результатом рекурсивного вызова. Мемоизировать результат isValid в memo[index][openCount]. Вернуть isValid.

😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public bool CheckValidString(string s) {
        int n = s.Length;
        int[][] memo = new int[n][];
        for (int i = 0; i < n; i++) {
            memo[i] = new int[n];
            Array.Fill(memo[i], -1);
        }
        return IsValidString(0, 0, s, memo);
    }

    private bool IsValidString(int index, int openCount, string str, int[][] memo) {
        if (index == str.Length) {
            return openCount == 0;
        }

        if (memo[index][openCount] != -1) {
            return memo[index][openCount] == 1;
        }

        bool isValid = false;

        if (str[index] == '*') {
            isValid = IsValidString(index + 1, openCount + 1, str, memo);
            if (openCount > 0) {
                isValid = isValid || IsValidString(index + 1, openCount - 1, str, memo);
            }
            isValid = isValid || IsValidString(index + 1, openCount, str, memo);
        } else if (str[index] == '(') {
            isValid = IsValidString(index + 1, openCount + 1, str, memo);
        } else if (openCount > 0) {
            isValid = IsValidString(index + 1, openCount - 1, str, memo);
        }

        memo[index][openCount] = isValid ? 1 : 0;
        return isValid;
    }
}

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

Задача: 1469. Find All The Lonely Nodes
Сложность: easy

В бинарном дереве одиночный узел — это узел, который является единственным ребёнком своего родительского узла. Корень дерева не является одиночным, так как у него нет родительского узла.

Дано корневое значение бинарного дерева. Верните массив, содержащий значения всех одиночных узлов в дереве. Верните список в любом порядке.

Пример:

Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
Output: [6,2]
Explanation: Light blue nodes are lonely nodes.
Please remember that order doesn't matter, [2,6] is also an acceptable answer.

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

1⃣Определите рекурсивную функцию DFS, которая принимает корень дерева, булеву переменную isLonely и список одиночных узлов ans в качестве аргументов. Если корень равен NULL, завершите выполнение функции.

2⃣Если isLonely равен true, добавьте значение корня в список ans. Рекурсивно обрабатывайте левого потомка корня, устанавливая флаг isLonely в true, если правый потомок равен NULL, и правого потомка, устанавливая флаг isLonely в true, если левый потомок равен NULL.

3⃣Вызовите DFS с корнем и false в качестве значения isLonely. Верните ans.

😎 Решение:

using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public void DFS(TreeNode root, bool isLonely, List<int> ans) {
        if (root == null) {
            return;
        }
        
        if (isLonely) {
            ans.Add(root.val);
        }
        
        DFS(root.left, root.right == null, ans);
        DFS(root.right, root.left == null, ans);
    }
    
    public IList<int> GetLonelyNodes(TreeNode root) {
        List<int> ans = new List<int>();
        DFS(root, false, ans);
        return ans;
    }
}

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

Задача: 765. Couples Holding Hands
Сложность: hard

Есть n пар, сидящих на 2n местах, расположенных в ряд, и они хотят держаться за руки.

Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1).

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

Пример:

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

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

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

2⃣При таком предположении, для какого-то дивана с несчастливыми людьми X и Y, мы либо заменяем Y на партнера X, либо заменяем X на партнера Y. Для каждой из двух возможностей мы можем попробовать оба варианта, используя подход с возвратом.

3⃣Для каждого дивана с двумя возможностями (т.е. оба человека на диване несчастливы) мы попробуем первый вариант, найдем ответ как ans1, затем отменим наш ход и попробуем второй вариант, найдем связанный ответ как ans2, отменим наш ход и затем вернем наименьший ответ.

😎 Решение:

public class Solution {
    int N;
    int[][] pairs;

    public int MinSwapsCouples(int[] row) {
        N = row.Length / 2;
        pairs = new int[N][];
        for (int i = 0; i < N; ++i) {
            pairs[i] = new int[2];
            pairs[i][0] = row[2 * i] / 2;
            pairs[i][1] = row[2 * i + 1] / 2;
        }
        return Solve(0);
    }

    public void Swap(int a, int b, int c, int d) {
        int t = pairs[a][b];
        pairs[a][b] = pairs[c][d];
        pairs[c][d] = t;
    }

    public int Solve(int i) {
        if (i == N) return 0;
        int x = pairs[i][0], y = pairs[i][1];
        if (x == y) return Solve(i + 1);

        int jx = 0, kx = 0, jy = 0, ky = 0;
        for (int j = i + 1; j < N; ++j) {
            for (int k = 0; k <= 1; ++k) {
                if (pairs[j][k] == x) { jx = j; kx = k; }
                if (pairs[j][k] == y) { jy = j; ky = k; }
            }
        }

        Swap(i, 1, jx, kx);
        int ans1 = 1 + Solve(i + 1);
        Swap(i, 1, jx, kx);

        Swap(i, 0, jy, ky);
        int ans2 = 1 + Solve(i + 1);
        Swap(i, 0, jy, ky);

        return Math.Min(ans1, ans2);
    }
}

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

Задача: 267. Palindrome Permutation II
Сложность: medium

Дана строка s, верните все палиндромные перестановки (без дубликатов) этой строки.

Вы можете вернуть ответ в любом порядке. Если у строки s нет палиндромных перестановок, верните пустой список.

Пример:

Input: s = "aabb"
Output: ["abba","baab"]

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

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

2⃣Генерация первой половины палиндромной строки:
Создаем строку st, которая содержит все символы строки s с количеством вхождений, уменьшенным до половины от их первоначального количества.
Если длина строки s нечетная, сохраняем символ, который встречается нечетное количество раз, отдельно.

3⃣Генерация всех перестановок первой половины и создание палиндромов:
Генерируем все перестановки строки st.
Для каждой перестановки добавляем её обратную строку к самой себе, создавая тем самым полную палиндромную строку.
Если длина строки s нечетная, добавляем сохраненный символ в середину каждого палиндрома.
Чтобы избежать дубликатов, проверяем, равны ли элементы перед свапом. Если да, то пропускаем данную перестановку.

😎 Решение:

using System;
using System.Collections.Generic;
using System.Text;

public class Solution {
    private HashSet<string> set;

    public Solution() {
        set = new HashSet<string>();
    }

    public IList<string> GeneratePalindromes(string s) {
        int[] map = new int[128];
        char[] st = new char[s.Length / 2];
        if (!CanPermutePalindrome(s, map)) {
            return new List<string>();
        }

        char ch = '\0';
        int k = 0;
        for (int i = 0; i < map.Length; i++) {
            if (map[i] % 2 == 1) {
                ch = (char)i;
            }
            for (int j = 0; j < map[i] / 2; j++) {
                st[k++] = (char)i;
            }
        }
        Permute(st, 0, ch);
        return new List<string>(set);
    }

    private bool CanPermutePalindrome(string s, int[] map) {
        int count = 0;
        foreach (char c in s) {
            int index = (int)c;
            map[index]++;
            if (map[index] % 2 == 0) {
                count--;
            } else {
                count++;
            }
        }
        return count <= 1;
    }

    private void Swap(ref char[] s, int i, int j) {
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }

    private void Permute(char[] s, int l, char ch) {
        if (l == s.Length) {
            StringBuilder sb = new StringBuilder();
            sb.Append(s);
            if (ch != '\0') {
                sb.Append(ch);
            }
            Array.Reverse(s);
            sb.Append(s);
            set.Add(sb.ToString());
            Array.Reverse(s);
        } else {
            for (int i = l; i < s.Length; i++) {
                if (s[l] != s[i] || l == i) {
                    Swap(ref s, l, i);
                    Permute(s, l + 1, ch);
                    Swap(ref s, l, i);
                }
            }
        }
    }
}

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