C# | LeetCode

Задача: 143. Reorder List Сложность: medium Вам дана голова односвязного списка. Список можно представить в следующем виде: L0 → L1 → … → Ln - 1 → Ln Переупорядочите список так, чтобы он принял следующую форму: L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … Вы не можете изменять значения в узлах списка. Можно изменять только сами узлы. Пример:

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

👨‍💻 Алгоритм: 1⃣Нахождение середины списка и разделение его на две части: Используйте два указателя, slow и fast, для нахождения середины списка. Указатель slow движется на один узел за шаг, а fast — на два узла. Когда fast достигает конца списка, slow окажется в середине. Разделите список на две части. Первая часть начинается от головы списка до slow, вторая — с узла после slow до конца списка. 2⃣Реверс второй половины списка: Инициализируйте указатели prev как NULL и curr как slow. Перемещайтесь по второй половине списка и меняйте направление ссылок между узлами для реверсирования списка. Продолжайте, пока не перестроите весь второй сегмент, теперь последний элемент первой части списка будет указывать на NULL, а prev станет новой головой второй половины списка. 3⃣Слияние двух частей списка в заданном порядке: Начните с головы первой части списка (first) и головы реверсированной второй части (second). Перекрестно связывайте узлы из первой и второй части, вставляя узлы из второй части между узлами первой части. Передвигайте указатели first и second соответственно после каждой вставки. Продолжайте этот процесс до тех пор, пока узлы второй части не закончатся. 😎 Решение:

public class Solution {
    public void ReorderList(ListNode head) {
        if (head == null)
            return;

        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode prev = null, curr = slow, tmp;
        while (curr != null) {
            tmp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = tmp;
        }

        ListNode first = head, second = prev;
        while (second.next != null) {
            tmp = first.next;
            first.next = second;
            first = tmp;
            tmp = second.next;
            second.next = first;
            second = tmp;
        }
    }
}

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

Задача: 1010. Pairs of Songs With Total Durations Divisible by 60 Сложность: medium Вам дан список песен, в котором длительность i-й песни составляет time[i] секунд. Верните количество пар песен, для которых их общая длительность в секундах делится на 60. Формально, нам нужно количество индексов i, j таких, что i < j при (time[i] + time[j]) % 60 == 0. Пример:

Input: time = [30,20,150,100,40]
Output: 3

👨‍💻 Алгоритм: 1⃣Инициализация и вычисление остатков: Создайте массив для хранения количества остатков от деления на 60. Инициализируйте его нулями. 2⃣Подсчет пар: Пройдитесь по каждой песне в списке и для каждого элемента: Вычислите остаток от деления времени песни на 60. Если остаток равен 0, добавьте количество песен с остатком 0 к результату (поскольку (0 + 0) % 60 == 0). Иначе, добавьте количество песен с остатком (60 - текущий остаток) к результату (поскольку (текущий остаток + (60 - текущий остаток)) % 60 == 0). Обновите массив остатков, увеличивая количество песен с текущим остатком на 1. 3⃣Возврат результата: Верните общее количество пар. 😎 Решение:

public class Solution {
    public int NumPairsDivisibleBy60(int[] time) {
        int[] remainders = new int[60];
        int count = 0;
        
        foreach (int t in time) {
            if (t % 60 == 0) {
                count += remainders[0];
            } else {
                count += remainders[60 - t % 60];
            }
            remainders[t % 60]++;
        }
        
        return count;
    }
}

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

Задача: 774. Minimize Max Distance to Gas Station Сложность: hard Вам дан массив целых чисел stations, который представляет позиции автозаправочных станций на оси x. Вам также дано целое число k. Вы должны добавить k новых автозаправочных станций. Вы можете добавлять станции в любое место на оси x, необязательно в целочисленную позицию. Определим penalty() как максимальное расстояние между соседними автозаправочными станциями после добавления k новых станций. Верните наименьшее возможное значение penalty(). Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты. Пример:

Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000

👨‍💻 Алгоритм: 1⃣Пусть i-й интервал равен deltas[i] = stations[i+1] - stations[i]. Мы хотим найти dp[n+1][k] как рекурсию. Мы можем поставить x автозаправочных станций в интервал n+1 с наилучшим расстоянием deltas[n+1] / (x+1), затем оставшиеся интервалы можно решить с ответом dp[n][k-x]. Ответ — это минимум среди всех x. 2⃣Из этой рекурсии мы можем разработать решение с использованием динамического программирования. Инициализируем двумерный массив dp, где dp[i][j] будет хранить минимальное возможное значение penalty при добавлении j автозаправочных станций на первые i интервалов. 3⃣Заполняем dp таблицу начиная с базового случая, когда нет добавленных станций. Затем для каждого интервала и количества добавленных станций вычисляем минимальное значение penalty, используя вышеописанную рекурсию. Итоговый ответ будет находиться в dp[n][k], где n — количество интервалов, а k — количество добавляемых станций. 😎 Решение:

public class Solution {
    public double MinmaxGasDist(int[] stations, int K) {
        int N = stations.Length;
        double[] deltas = new double[N-1];
        for (int i = 0; i < N-1; ++i)
            deltas[i] = stations[i+1] - stations[i];

        double[][] dp = new double[N-1][];
        for (int i = 0; i < N-1; ++i)
            dp[i] = new double[K+1];

        for (int i = 0; i <= K; ++i)
            dp[0][i] = deltas[0] / (i+1);

        for (int p = 1; p < N-1; ++p)
            for (int k = 0; k <= K; ++k) {
                double bns = double.MaxValue;
                for (int x = 0; x <= k; ++x)
                    bns = Math.Min(bns, Math.Max(deltas[p] / (x+1), dp[p-1][k-x]));
                dp[p][k] = bns;
            }

        return dp[N-2][K];
    }
}

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

Задача: 960. Delete Columns to Make Sorted III Сложность: hard Вам дан массив из n строк strs, все одинаковой длины. Мы можем выбрать любые индексы для удаления, и мы удаляем все символы в этих индексах для каждой строки. Например, если у нас есть strs = ["abcdef","uvwxyz"] и индексы удаления {0, 2, 3}, то итоговый массив после удаления будет ["bef", "vyz"]. Предположим, мы выбрали набор индексов удаления answer таким образом, что после удаления итоговый массив имеет каждую строку (ряд) в лексикографическом порядке. (т.е. (strs[0][0] <= strs[0][1] <= ... <= strs[0][strs[0].length - 1]) и (strs[1][0] <= strs[1][1] <= ... <= strs[1][strs[1].length - 1]) и так далее). Верните минимально возможное значение answer.length. Пример:

Input: strs = ["babca","bbazb"]
Output: 3
Explanation: After deleting columns 0, 1, and 4, the final array is strs = ["bc", "az"].
Both these rows are individually in lexicographic order (ie. strs[0][0] <= strs[0][1] and strs[1][0] <= strs[1][1]).
Note that strs[0] > strs[1] - the array strs is not necessarily in lexicographic order.

👨‍💻 Алгоритм: 1⃣Вместо поиска количества удаляемых столбцов, найдем количество столбцов, которые нужно сохранить. В конце мы можем вычесть это значение, чтобы получить желаемый ответ. 2⃣Используйте динамическое программирование, чтобы решить проблему. Пусть dp[k] будет количеством столбцов, которые сохраняются, начиная с позиции k. Мы будем искать максимальное значение dp[k], чтобы найти количество столбцов, которые нужно сохранить. 3⃣Итоговое количество удаляемых столбцов будет равно общей длине строк минус количество сохраненных столбцов. 😎 Решение:

public class Solution {
    public int MinDeletionSize(string[] A) {
        int W = A[0].Length;
        int[] dp = new int[W];
        Array.Fill(dp, 1);

        for (int i = W - 2; i >= 0; --i) {
            for (int j = i + 1; j < W; ++j) {
                bool valid = true;
                foreach (string row in A) {
                    if (row[i] > row[j]) {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    dp[i] = Math.Max(dp[i], 1 + dp[j]);
                }
            }
        }

        return W - dp.Max();
    }
}

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

Задача: 1461. Check If a String Contains All Binary Codes of Size K Сложность: medium Дана бинарная строка s и целое число k, верните true, если каждый бинарный код длины k является подстрокой s. В противном случае верните false. Пример:

Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indices 0, 1, 3 and 2 respectively.

👨‍💻 Алгоритм: 1⃣Определите количество возможных двоичных кодов длины k. 2⃣Создайте массив для отслеживания, какие коды были найдены. Итерируйте по строке s, вычисляя хэш для текущего окна длины k и обновляя массив отслеживания. 3⃣Возвращайте true, если все возможные коды найдены, иначе false. 😎 Решение:

public class Solution {
    public bool HasAllCodes(string s, int k) {
        int need = 1 << k;
        bool[] got = new bool[need];
        int allOne = need - 1;
        int hashVal = 0;
        
        for (int i = 0; i < s.Length; i++) {
            hashVal = ((hashVal << 1) & allOne) | (s[i] - '0');
            if (i >= k - 1 && !got[hashVal]) {
                got[hashVal] = true;
                need--;
                if (need == 0) {
                    return true;
                }
            }
        }
        return false;
    }
}

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

Задача: 1312. Minimum Insertion Steps to Make a String Palindrome Сложность: hard Дана строка s. За один шаг вы можете вставить любой символ в любой индекс строки. Верните минимальное количество шагов, необходимых для превращения s в палиндром. Палиндром — это строка, которая читается одинаково как вперед, так и назад. Пример:

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we do not need any insertions.

👨‍💻 Алгоритм: 1⃣Создайте целочисленную переменную n и инициализируйте её размером строки s. Создайте строковую переменную sReverse и установите её значение как обратную строку s. 2⃣Создайте двумерный массив memo размером n + 1 на n + 1, где memo[i][j] будет содержать длину наибольшей общей подпоследовательности, учитывая первые i символов строки s и первые j символов строки sReverse. Инициализируйте массив значением -1. 3⃣Верните n - lcs(s, sReverse, n, n, memo), где lcs - это рекурсивный метод с четырьмя параметрами: первая строка s1, вторая строка s2, длина подстроки от начала s1, длина подстроки от начала s2 и memo. Метод возвращает длину наибольшей общей подпоследовательности в подстроках s1 и s2. В этом методе выполните следующее: Если m == 0 или n == 0, это означает, что одна из двух подстрок пуста, поэтому верните 0. Если memo[m][n] != -1, это означает, что мы уже решили эту подзадачу, поэтому верните memo[m][n]. Если последние символы подстрок совпадают, добавьте 1 и найдите длину наибольшей общей подпоследовательности, исключив последний символ обеих подстрок. Верните memo[i][j] = 1 + lcs(s1, s2, m - 1, n - 1, memo). В противном случае, если последние символы не совпадают, рекурсивно найдите наибольшую общую подпоследовательность в обеих подстроках, исключив их последние символы по одному. Верните memo[i][j] = max(lcs(s1, s2, m - 1, n, memo), lcs(s1, s2, m, n - 1, memo)). 😎 Решение:

public class Solution {
    private int Lcs(string s1, string s2, int m, int n, int[,] memo) {
        if (m == 0 || n == 0) {
            return 0;
        }
        if (memo[m, n] != -1) {
            return memo[m, n];
        }
        if (s1[m - 1] == s2[n - 1]) {
            return memo[m, n] = 1 + Lcs(s1, s2, m - 1, n - 1, memo);
        }
        return memo[m, n] = Math.Max(Lcs(s1, s2, m - 1, n, memo), Lcs(s1, s2, m, n - 1, memo));
    }

    public int MinInsertions(string s) {
        int n = s.Length;
        string sReverse = new string(s.Reverse().ToArray());
        int[,] memo = new int[n + 1, n + 1];
        
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                memo[i, j] = -1;
            }
        }

        return n - Lcs(s, sReverse, n, n, memo);
    }
}

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

Задача: 588. Design In-Memory File System Сложность: hard Спроектируйте структуру данных, которая симулирует файловую систему в памяти. Реализуйте класс FileSystem: FileSystem() Инициализирует объект системы. List<String> ls(String path) Если path является путем к файлу, возвращает список, содержащий только имя этого файла. Если path является путем к директории, возвращает список имен файлов и директорий в этой директории. Ответ должен быть в лексикографическом порядке. void mkdir(String path) Создает новую директорию согласно заданному пути. Заданная директория не существует. Если промежуточные директории в пути не существуют, вы также должны создать их. void addContentToFile(String filePath, String content) Если filePath не существует, создает файл, содержащий заданный контент. Если filePath уже существует, добавляет заданный контент к исходному содержимому. String readContentFromFile(String filePath) Возвращает содержимое файла по пути filePath. Пример:

Input
["FileSystem", "ls", "mkdir", "addContentToFile", "ls", "readContentFromFile"]
[[], ["/"], ["/a/b/c"], ["/a/b/c/d", "hello"], ["/"], ["/a/b/c/d"]]
Output
[null, [], null, null, ["a"], "hello"]

Explanation
FileSystem fileSystem = new FileSystem();
fileSystem.ls("/");                         // return []
fileSystem.mkdir("/a/b/c");
fileSystem.addContentToFile("/a/b/c/d", "hello");
fileSystem.ls("/");                         // return ["a"]
fileSystem.readContentFromFile("/a/b/c/d"); // return "hello"

👨‍💻 Алгоритм: 1⃣ Инициализация файловой системы: Создайте класс FileSystem, который будет содержать вложенный класс File. Класс File будет представлять либо файл, либо директорию, содержать флаг isfile, словарь files и строку content. 2⃣ Обработка команд: Реализуйте метод ls, который возвращает список файлов и директорий в указанном пути, либо имя файла, если указанный путь является файлом. Реализуйте метод mkdir, который создаёт директории по указанному пути. Если промежуточные директории не существуют, создайте их. Реализуйте метод addContentToFile, который добавляет содержимое в файл по указанному пути. Если файл не существует, создайте его. Реализуйте метод readContentFromFile, который возвращает содержимое файла по указанному пути. 3⃣ Обработка путей и работа с файлами/директориями: Используйте метод split для разделения пути на составляющие и навигации по дереву директорий и файлов. Для каждой команды выполняйте соответствующие операции по созданию, чтению или записи содержимого файлов и директорий. 😎 Решение:

public class FileSystem {
    class File {
        public bool isFile = false;
        public Dictionary<string, File> files = new Dictionary<string, File>();
        public string content = "";
    }

    File root = new File();

    private File Navigate(string path) {
        File t = root;
        if (path != "/") {
            var dirs = path.Split('/');
            foreach (var dir in dirs) {
                if (!string.IsNullOrEmpty(dir)) {
                    if (!t.files.ContainsKey(dir)) {
                        t.files[dir] = new File();
                    }
                    t = t.files[dir];
                }
            }
        }
        return t;
    }

    public IList<string> Ls(string path) {
        var t = Navigate(path);
        if (t.isFile) return new List<string> { path.Substring(path.LastIndexOf("/") + 1) };
        var res = new List<string>(t.files.Keys);
        res.Sort();
        return res;
    }

    public void Mkdir(string path) {
        Navigate(path);
    }

    public void AddContentToFile(string filePath, string content) {
        var t = Navigate(filePath);
        t.isFile = true;
        t.content += content;
    }

    public string ReadContentFromFile(string filePath) {
        return Navigate(filePath).content;
    }
}

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

Задача: 746. Min Cost Climbing Stairs Сложность: easy Вам дан целочисленный массив cost, где cost[i] - стоимость i-й ступеньки на лестнице. После оплаты стоимости вы можете подняться на одну или две ступеньки. Вы можете начать со ступеньки с индексом 0 или со ступеньки с индексом 1. Верните минимальную стоимость достижения вершины этажа. Пример:

Input: cost = [10,15,20]
Output: 15

👨‍💻 Алгоритм: 1⃣Создать массив dp, где dp[i] хранит минимальную стоимость достижения i-й ступеньки. 2⃣Инициализировать dp[0] и dp[1] как cost[0] и cost[1] соответственно. Заполнить dp используя минимальную стоимость подъема с предыдущих ступенек. 3⃣Вернуть минимальную стоимость достижения вершины. 😎 Решение:

public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        int n = cost.Length;
        int[] dp = new int[n];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < n; i++) {
            dp[i] = cost[i] + Math.Min(dp[i - 1], dp[i - 2]);
        }
        return Math.Min(dp[n - 1], dp[n - 2]);
    }
}

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

Задача: 998. Maximum Binary Tree II Сложность: medium Максимальное дерево - это дерево, в котором каждый узел имеет значение большее, чем любое другое значение в его поддереве. Вам дан корень максимального двоичного дерева и целое число val. Как и в предыдущей задаче, данное дерево было построено из списка a (root = Construct(a)) рекурсивно с помощью следующей процедуры Construct(a): Если a пусто, верните null. В противном случае пусть a[i] - наибольший элемент a. Создайте корневой узел со значением a[i]. Левым ребенком root будет Construct([a[0], a[1], ..., a[i - 1]]). Правым ребенком root будет Construct([a[i + 1], a[i + 2], ..., a[a.length])...., a[a.length - 1]]). Возвращаем root. Обратите внимание, что нам не было дано непосредственно a, а только корневой узел root = Construct(a). Предположим, что b - это копия a с добавленным к ней значением val. Гарантируется, что b имеет уникальные значения. Возвращаем Construct(b). Пример:

Input: root = [5,2,4,null,1], val = 3
Output: [5,2,4,null,1,null,3]

👨‍💻 Алгоритм: 1⃣Поиск места вставки: Итерируйте через дерево, начиная с корня. Найдите место для вставки нового значения val так, чтобы дерево оставалось максимальным деревом. Если значение val больше, чем значение текущего узла, создайте новый узел с val и сделайте текущий узел его левым ребенком. 2⃣Вставка нового узла: Если значение val меньше, чем значение текущего узла, продолжайте спускаться по правому поддереву, пока не найдете место для вставки. 3⃣Создание нового дерева: После вставки нового узла убедитесь, что дерево сохраняет свои свойства максимального дерева. 😎 Решение:

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

public class Solution {
    public TreeNode InsertIntoMaxTree(TreeNode root, int val) {
        if (root == null || val > root.val) {
            TreeNode newNode = new TreeNode(val);
            newNode.left = root;
            return newNode;
        }
        root.right = InsertIntoMaxTree(root.right, val);
        return root;
    }
}

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

Получи грант на обучение в Центральном университете Центральный университет выдает гранты на 4 года обучения в бакалавриате. Грант покрывает до 100% стоимости обучения. Участвуй в отборе, чтобы получить грант. Получи доступ к уникальным активностям для абитуриентов. Для выпускников 10-х, 11-х классов и колледжей. Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Задача: 954. Array of Doubled Pairs Сложность: medium Если задан целочисленный массив четной длины arr, верните true, если можно переупорядочить arr так, чтобы arr[2 * i + 1] = 2 * arr[2 * i] для каждого 0 <= i < len(arr) / 2, или false в противном случае. Пример:

Input: arr = [3,1,3,6]
Output: false

👨‍💻 Алгоритм: 1⃣Подсчитать частоту каждого элемента в массиве. Отсортировать массив по абсолютным значениям элементов. 2⃣Для каждого элемента в отсортированном массиве: Проверить, можно ли сопоставить его с элементом, равным его удвоенному значению. Уменьшить счетчик обоих элементов в словаре частот. 3⃣Если для каждого элемента можно найти пару, вернуть true, иначе вернуть false. 😎 Решение:

using System;
using System.Collections.Generic;

public class Solution {
    public bool CanReorderDoubled(int[] arr) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        foreach (int num in arr) {
            if (count.ContainsKey(num)) {
                count[num]++;
            } else {
                count[num] = 1;
            }
        }
        Array.Sort(arr, (a, b) => Math.Abs(a).CompareTo(Math.Abs(b)));
        foreach (int num in arr) {
            if (count[num] == 0) continue;
            if (!count.ContainsKey(2 * num) || count[2 * num] == 0) return false;
            count[num]--;
            count[2 * num]--;
        }
        return true;
    }
}

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

Крупнейший университет искусственного интеллекта Учим использовать ChatGPT в профессиональных целях, создавать нейро-сотрудников и зарабатывать на искусственном интеллекте. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 414. Third Maximum Number Сложность: easy Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число. Пример:

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

👨‍💻 Алгоритм: 1⃣Инициализируйте три переменные для хранения первого, второго и третьего максимальных чисел, используя значения None или аналогичные значения. 2⃣Пройдитесь по массиву, обновляя переменные первого, второго и третьего максимальных чисел, избегая дубликатов. 3⃣Если третье максимальное число существует, верните его. В противном случае, верните первое максимальное число. 😎 Решение:

public class Solution {
    public int ThirdMax(int[] nums) {
        int? first = null;
        int? second = null;
        int? third = null;
        
        foreach (int num in nums) {
            if (num == first || num == second || num == third) {
                continue;
            }
            if (first == null || num > first) {
                third = second;
                second = first;
                first = num;
            } else if (second == null || num > second) {
                third = second;
                second = num;
            } else if (third == null || num > third) {
                third = num;
            }
        }
        
        return third ?? first.Value;
    }
}

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

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по AI! Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: №26. Remove Duplicates from Sorted Array Сложность: easy Учитывая целочисленный массив чисел, отсортированный в неубывающем порядке, удалите дубликаты на месте так, чтобы каждый уникальный элемент появлялся только один раз. Относительный порядок элементов должен оставаться неизменным. Затем верните количество уникальных элементов. Пример:

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

👨‍💻 Алгоритм: 1⃣Использовать два указателя: i для записи уникальных элементов и j для перебора массива. 2⃣Перемещать j вперед, если текущий элемент равен предыдущему. 3⃣Если найден новый уникальный элемент, записывать его в i-ю позицию. 😎 Решение:

public class Solution {
    public int RemoveDuplicates(int[] nums) {
        if (nums.Length == 0) return 0;
        
        int i = 0;
        for (int j = 1; j < nums.Length; j++) {
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }
        
        return i + 1;
    }
}

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

Ищешь высокооплачиваемые проекты? Попробуй SkillStaff SkillStaff — это платформа для ИТ-специалистов, менеджеров и креаторов, которым мало одного оклада. Здесь можно найти клиентов, выполнять их проекты и увеличивать свой доход. - Проекты с гибким графиком: part time, full time, удаленка и гибрид - Ставка за час работы — та, что ты сам выбрал - Клиенты — ведущие бренды, проверенные с юридической точки зрения при регистрации на платформе - Оплата поступает ежемесячно на расчетный счет исполнителя - Удобный личный кабинет и функционал, автоматизирующий документооборот Все, что нужно для работы — иметь статус самозанятого или ИП, а платформа поможет со всеми нюансами. Регистрируйся прямо сейчас Зарегистрироваться #реклама 16+ skillstaff.ru О рекламодателе

Задача: 252. Meeting Rooms Сложность: easy Дан массив интервалов времени встреч, где intervals[i] = [starti, endi]. Определите, может ли человек посетить все встречи. Пример:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

👨‍💻 Алгоритм: 1⃣Создайте функцию для проверки перекрытия двух интервалов: Возвращайте true, если начало одного интервала находится внутри другого интервала. 2⃣Проверьте каждый интервал с каждым другим интервалом: Если найдено перекрытие, верните false. 3⃣Если все интервалы проверены и перекрытий не найдено, верните true. 😎 Решение:

class Solution {
    public bool Overlap(int[] interval1, int[] interval2) {
        return (interval1[0] >= interval2[0] && interval1[0] < interval2[1]) ||
               (interval2[0] >= interval1[0] && interval2[0] < interval1[1]);
    }
    
    public bool CanAttendMeetings(int[][] intervals) {
        for (int i = 0; i < intervals.Length; i++) {
            for (int j = i + 1; j < intervals.Length; j++) {
                if (Overlap(intervals[i], intervals[j])) {
                    return false;
                }
            }
        }
        return true;
    }
}

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

Задача: 325. Maximum Size Subarray Sum Equals k Сложность: medium Дан целочисленный массив nums и целое число k. Верните максимальную длину подмассива, сумма которого равна k. Если такого подмассива не существует, верните 0. Пример:

Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

👨‍💻 Алгоритм: 1⃣Инициализация переменных Инициализируйте prefixSum как 0 для отслеживания префиксной суммы nums. Инициализируйте longestSubarray как 0 для отслеживания самой длинной подмассы с суммой k. Инициализируйте хеш-карту indices для хранения префиксных сумм и их индексов. 2⃣Итерация по массиву На каждом индексе i, добавляйте nums[i] к prefixSum. Проверьте следующие условия: Если prefixSum == k, обновите longestSubarray как i + 1. Если prefixSum - k существует в indices, обновите longestSubarray, если текущая длина подмассива больше. Если текущий prefixSum еще не существует в indices, добавьте indices[prefixSum] = i. 3⃣Возврат результата Верните значение longestSubarray. 😎 Решение:

public class Solution {
    public int MaxSubArrayLen(int[] nums, int k) {
        int prefixSum = 0;
        int longestSubarray = 0;
        Dictionary<int, int> indices = new Dictionary<int, int>();
        
        for (int i = 0; i < nums.Length; i++) {
            prefixSum += nums[i];
            
            if (prefixSum == k) {
                longestSubarray = i + 1;
            }
            if (indices.ContainsKey(prefixSum - k)) {
                longestSubarray = Math.Max(longestSubarray, i - indices[prefixSum - k]);
            }
            if (!indices.ContainsKey(prefixSum)) {
                indices[prefixSum] = i;
            }
        }
        
        return longestSubarray;
    }
}

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

Бесплатный курс по 3D-моделированию с нуля Начни карьеру в дизайне и получи первую зарплату! Вас ждет реальный рабочий процесс: ✅ разные задачи по 3D Blander ✅ опыт общения с клиентами ✅ оплата за проект Освойте Blender и создайте работу для портфолио Обучение полностью бесплатное для первых 70 участников. Осталось 28 мест. В конце курса мы откроем для вас доступ к звездной распродаже Там вы сможете обменять звездочки на ценные бонусы: 1. Гайд по выходу на биржу UpWork 2. Курс «Заработок на дизайне» 3. Анимированный концепт Samsung True для портфолио 4. Бессрочный грант на обучение: 15 000 ₽ 5. Гайд «Горячие клавиши в Blender» Записывайтесь сейчас! Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

Задача: 223. Rectangle Area Сложность: medium Даны координаты двух прямоугольных прямоугольников на двумерной плоскости, верните общую площадь, покрытую этими двумя прямоугольниками. Первый прямоугольник определяется его нижним левым углом (ax1, ay1) и верхним правым углом (ax2, ay2). Второй прямоугольник определяется его нижним левым углом (bx1, by1) и верхним правым углом (bx2, by2). Пример:

Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45

👨‍💻 Алгоритм: 1⃣Вычислить площади двух прямоугольников: Рассчитайте площади прямоугольников A и B, умножив их ширину на высоту. 2⃣Вычислить перекрытие: Найдите перекрытие по оси X и оси Y. Если перекрытие существует, вычислите площадь перекрытия. 3⃣Вычислить и вернуть общую площадь: Вычтите площадь перекрытия из суммы площадей двух прямоугольников и верните результат. 😎 Решение:

public class Solution {
    public int ComputeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
        int areaOfA = (ay2 - ay1) * (ax2 - ax1);
        int areaOfB = (by2 - by1) * (bx2 - bx1);

        int left = Math.Max(ax1, bx1);
        int right = Math.Min(ax2, bx2);
        int xOverlap = right - left;

        int top = Math.Min(ay2, by2);
        int bottom = Math.Max(ay1, by1);
        int yOverlap = top - bottom;

        int areaOfOverlap = 0;
        if (xOverlap > 0 && yOverlap > 0) {
            areaOfOverlap = xOverlap * yOverlap;
        }

        int totalArea = areaOfA + areaOfB - areaOfOverlap;
        return totalArea;
    }
}

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