C# | LeetCode

Задача: 938. Range Sum of BST Сложность: easy Учитывая корневой узел двоичного дерева поиска и два целых числа low и high, верните сумму значений всех узлов со значением в диапазоне [low, high]. Пример:

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32

👨‍💻 Алгоритм: 1⃣Если дерево пустое, вернуть 0. 2⃣Если значение текущего узла меньше low, рекурсивно искать в правом поддереве. Если значение текущего узла больше high, рекурсивно искать в левом поддереве. 3⃣Если значение текущего узла в диапазоне [low, high], включить значение узла в сумму и рекурсивно искать в обоих поддеревьях. 😎 Решение:

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 int RangeSumBST(TreeNode root, int low, int high) {
        if (root == null) return 0;
        if (root.val < low) return RangeSumBST(root.right, low, high);
        if (root.val > high) return RangeSumBST(root.left, low, high);
        return root.val + RangeSumBST(root.left, low, high) + RangeSumBST(root.right, low, high);
    }
}

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

Задача: 912. Sort an Array Сложность: medium Задав массив целых чисел nums, отсортируйте массив по возрастанию и верните его. Вы должны решить задачу без использования встроенных функций за время O(nlog(n)) и с минимально возможной пространственной сложностью. Пример:

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

👨‍💻 Алгоритм: 1⃣Используем алгоритм "Сортировка слиянием" (Merge Sort), который обеспечивает время выполнения O(n log n) и минимально возможную пространственную сложность для стабильного сортировочного алгоритма. 2⃣Разделить массив на две половины. Рекурсивно отсортировать каждую половину. 3⃣Слить две отсортированные половины. 😎 Решение:

using System;

class Program {
    static void MergeSort(int[] nums) {
        if (nums.Length > 1) {
            int mid = nums.Length / 2;
            int[] left_half = new int[mid];
            int[] right_half = new int[nums.Length - mid];

            Array.Copy(nums, 0, left_half, 0, mid);
            Array.Copy(nums, mid, right_half, 0, nums.Length - mid);

            MergeSort(left_half);
            MergeSort(right_half);

            int i = 0, j = 0, k = 0;
            while (i < left_half.Length && j < right_half.Length) {
                if (left_half[i] < right_half[j]) {
                    nums[k++] = left_half[i++];
                } else {
                    nums[k++] = right_half[j++];
                }
            }

            while (i < left_half.Length) {
                nums[k++] = left_half[i++];
            }

            while (j < right_half.Length) {
                nums[k++] = right_half[j++];
            }
        }
    }
}

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

Задача: 303. Range Sum Query - Immutable Сложность: easy Дан целочисленный массив nums. Обработайте несколько запросов следующего типа: Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right. Реализуйте класс NumArray: - NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums. - int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]). Пример:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

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

public class NumArray {
    private int[] sum;

    public NumArray(int[] nums) {
        sum = new int[nums.Length + 1];
        for (int i = 0; i < nums.Length; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }

    public int SumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

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

Изиоффер переходит в публичное бета-тестирование! 🎉 Что нового: 🟢Анализ IT собеседований на основе 4500+ реальных интервью 🟢Вопросы из собеседований с вероятностью встречи 🟢Видео-примеры ответов на вопросы от Senior, Middle, Junior грейдов 🟢Пример лучшего ответа 🟢Задачи из собеседований 🟢Тестовые задания 🟢Примеры собеседований 🟢Фильтрация всего контента по грейдам, компаниям 🟢Тренажер подготовки к собеседованию на основе интервальных повторений и флеш карточек 🟢Тренажер "Реальное собеседование" с сценарием вопросов из реальных собеседований (скоро) 🟢Автоотклики на HeadHunter 🟢Закрытое сообщество easyoffer 💎 Акция в честь открытия для первых 500 покупателей: 🚀 Скидка 50% на PRO тариф на 1 год 🔥 Акция уже стартовала! 👉 https://easyoffer.ru/pro

Задача: 1437. Check If All 1's Are at Least Length K Places Away Сложность: easy Дан бинарный массив nums и целое число k. Вернуть true, если все единицы находятся на расстоянии не менее k позиций друг от друга, в противном случае вернуть false. Пример:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.

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

public class Solution {
    public bool KLengthApart(int[] nums, int k) {
        int count = k;
        foreach (int num in nums) {
            if (num == 1) {
                if (count < k) {
                    return false;
                }
                count = 0;
            } else {
                count++;
            }
        }
        return true;
    }
}

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

Задача: 1000. Minimum Cost to Merge Stones Сложность: hard Имеется n кучек камней, расположенных в ряд. В i-й куче находятся камни stones[i]. Ход состоит в объединении ровно k последовательных куч в одну кучу, и стоимость этого хода равна общему количеству камней в этих k кучах. Верните минимальную стоимость объединения всех куч камней в одну кучу. Если это невозможно, верните -1. Пример:

Input: stones = [3,2,4,1], k = 2
Output: 20

👨‍💻 Алгоритм: 1⃣Проверка на возможность объединения: Проверьте, можно ли объединить все кучи в одну, если количество куч n не равно 1 по модулю k-1. Если нет, верните -1. 2⃣Инициализация и динамическое программирование: Создайте таблицу dp для хранения минимальных затрат на объединение подмассивов камней. Используйте таблицу prefix для хранения префиксных сумм камней, чтобы быстро вычислять сумму камней в подмассиве. 3⃣Заполнение таблицы dp: Заполните таблицу dp минимальными затратами на объединение подмассивов камней, используя динамическое программирование. Для каждого подмассива длиной от k до n, найдите минимальную стоимость его объединения. 😎 Решение:

public class Solution {
    public int MergeStones(int[] stones, int k) {
        int n = stones.Length;
        if ((n - 1) % (k - 1) != 0) return -1;

        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + stones[i];
        }

        int[,] dp = new int[n, n];
        for (int m = k; m <= n; m++) {
            for (int i = 0; i <= n - m; i++) {
                int j = i + m - 1;
                dp[i, j] = int.MaxValue;
                for (int t = i; t < j; t += k - 1) {
                    dp[i, j] = Math.Min(dp[i, j], dp[i, t] + dp[t + 1, j]);
                }
                if ((j - i) % (k - 1) == 0) {
                    dp[i, j] += prefix[j + 1] - prefix[i];
                }
            }
        }

        return dp[0, n - 1];
    }
}

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

📺 База 1000+ реальных собеседований На программиста, тестировщика, аналитика, проджекта и другие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 568. Maximum Vacation Days Сложность: hard LeetCode хочет предоставить одному из своих лучших сотрудников возможность путешествовать по n городам для сбора задач по алгоритмам. Однако, как говорится, "делу время, потехе час". Вы можете брать отпуска в некоторых конкретных городах и неделях. Ваша задача — спланировать поездку, чтобы максимально увеличить количество дней отпуска, которые вы сможете взять, соблюдая при этом определенные правила и ограничения. Правила и ограничения: Вы можете путешествовать только между n городами, обозначенными индексами от 0 до n-1. Изначально вы находитесь в городе с индексом 0 в понедельник. Города связаны рейсами. Рейсы представлены матрицей n x n, называемой flights, представляющей статус авиалинии от города i до города j. Если рейса из города i в город j нет, flights[i][j] == 0; иначе flights[i][j] == 1. Также для всех i выполняется flights[i][i] == 0. У вас есть k недель (каждая неделя состоит из семи дней) для путешествий. Вы можете летать не более одного раза в день и можете летать только утром каждого понедельника. Время полета настолько короткое, что его влияние не учитывается. Для каждого города у вас есть ограниченные дни отпуска в разные недели, заданные матрицей n x k, называемой days. Значение days[i][j] представляет максимальное количество дней отпуска, которые вы можете взять в городе i на неделе j. Даны две матрицы flights и days, верните максимальное количество дней отпуска, которые вы можете взять в течение k недель. Пример:

Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
Output: 12
Explanation:
One of the best strategies is:
1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day.
(Although you start at city 0, we could also fly to and start at other cities since it is Monday.)
2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days.
3rd week : stay at city 2, and play 3 days and work 4 days.
Ans = 6 + 3 + 3 = 12.

👨‍💻 Алгоритм: 1⃣Использовать функцию dfs (поиск в глубину), которая возвращает количество отпускных дней, которые можно взять, начиная с текущего города cur_city и текущей недели weekno. В каждом вызове функции проходить по всем городам и находить все города, которые связаны с текущим городом. Такой город обозначен 1 в соответствующей позиции flights[cur_city][i]. 2⃣Для текущего города можно либо остаться в нем, либо поехать в связанный город. Обозначим город, в который меняется расположение, как j. После смены города нужно найти количество отпускных дней, которые можно взять, начиная с нового города и с новой недели. Это количество отпускных дней можно представить как: days[j][weekno] + dfs(flights, days, j, weekno + 1). 3⃣Для текущего города необходимо найти максимальное количество отпускных дней, выбирая различные города в качестве следующего местоположения. Из всех вариантов отпускных дней выбираем максимальное значение, которое и будет возвращено для каждого вызова функции dfs. 😎 Решение:

public class Solution {
    public int MaxVacationDays(int[][] flights, int[][] days) {
        int n = flights.Length, k = days[0].Length;
        int[][] memo = new int[n][];
        for (int i = 0; i < n; i++) {
            memo[i] = new int[k];
            Array.Fill(memo[i], -1);
        }
        return Dfs(flights, days, memo, 0, 0);
    }

    private int Dfs(int[][] flights, int[][] days, int[][] memo, int curCity, int weekNo) {
        int n = flights.Length, k = days[0].Length;
        if (weekNo == k) return 0;
        if (memo[curCity][weekNo] != -1) return memo[curCity][weekNo];
        int maxVac = 0;
        for (int nextCity = 0; nextCity < n; nextCity++) {
            if (curCity == nextCity || flights[curCity][nextCity] == 1) {
                maxVac = Math.Max(maxVac, days[nextCity][weekNo] + Dfs(flights, days, memo, nextCity, weekNo + 1));
            }
        }
        memo[curCity][weekNo] = maxVac;
        return maxVac;
    }
}

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

Задача: 625. Minimum Factorization Сложность: medium Если задано целое положительное число num, верните наименьшее целое положительное число x, умножение каждого разряда которого равно num. Если ответа нет или ответ не помещается в 32-битное знаковое целое число, возвращается 0. Пример:

Input: num = 48
Output: 68

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

public class Solution {
    public int SmallestFactorization(int num) {
        if (num == 1) return 1;
        
        List<int> factors = new List<int>();
        
        for (int i = 9; i >= 2; i--) {
            while (num % i == 0) {
                factors.Add(i);
                num /= i;
            }
        }
        
        if (num > 1) return 0;
        
        long result = 0;
        for (int i = factors.Count - 1; i >= 0; i--) {
            result = result * 10 + factors[i];
            if (result > int.MaxValue) return 0;
        }
        
        return (int) result;
    }
}

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

Задача: 1027. Longest Arithmetic Subsequence Сложность: medium Если задан массив nums целых чисел, верните длину самой длинной арифметической подпоследовательности в nums. Примечание: Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов. Последовательность seq является арифметической, если seq[i + 1] - seq[i] имеют одинаковое значение (для 0 <= i < seq.length - 1). Пример:

Input: nums = [3,6,9,12]
Output: 4

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Создайте массив словарей dp, где dp[i][d] будет хранить длину самой длинной арифметической подпоследовательности, заканчивающейся на элементе i с разностью d. 2⃣Заполнение массива dp: Пройдитесь по каждому элементу массива nums. Для каждого элемента nums[j] (где j идет от 0 до i-1), вычислите разность d = nums[i] - nums[j]. Обновите dp[i][d] на основе значения dp[j][d]. 3⃣Поиск максимальной длины: Пройдите по массиву dp и найдите максимальное значение среди всех значений dp[i][d]. 😎 Решение:

public class Solution {
    public int LongestArithSeqLength(int[] nums) {
        if (nums.Length == 0) return 0;
        
        var dp = new Dictionary<int, int>[nums.Length];
        for (int i = 0; i < nums.Length; i++) {
            dp[i] = new Dictionary<int, int>();
        }
        int maxLength = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j];
                if (dp[j].TryGetValue(diff, out int length)) {
                    dp[i][diff] = length + 1;
                } else {
                    dp[i][diff] = 2;
                }
                maxLength = Math.Max(maxLength, dp[i][diff]);
            }
        }
        
        return maxLength;
    }
}

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

Задача: 108. Convert Sorted Array to Binary Search Tree Сложность: easy Дан массив целых чисел nums, элементы которого отсортированы в порядке возрастания. Преобразуйте его в сбалансированное по высоте двоичное дерево поиска. Пример:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

👨‍💻 Алгоритм: 1⃣Инициализация функции помощника: Реализуйте функцию помощника helper(left, right), которая строит двоичное дерево поиска (BST) из элементов массива nums между индексами left и right. Если left > right, это означает, что элементов для построения поддерева нет, возвращаем None. 2⃣Выбор корня и разделение массива: Выберите элемент в середине для корня: p = (left + right) // 2. Инициализируйте корень: root = TreeNode(nums[p]). 3⃣Рекурсивное построение поддеревьев: Рекурсивно стройте левое поддерево: root.left = helper(left, p - 1). Рекурсивно стройте правое поддерево: root.right = helper(p + 1, right). В качестве результата возвращайте helper(0, len(nums) - 1), начиная с корня дерева. 😎 Решение:

public class Solution {
    public TreeNode SortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.Length - 1);
    }

    public TreeNode helper(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        int p = (left + right) / 2;
        TreeNode root = new TreeNode(nums[p]);
        root.left = helper(nums, left, p - 1);
        root.right = helper(nums, p + 1, right);
        return root;
    }
}

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

Задача: 229. Majority Element II Сложность: medium Дан массив целых чисел размера n, найдите все элементы, которые встречаются более ⌊ n/3 ⌋ раз. Пример:

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

👨‍💻 Алгоритм: 1⃣Поиск кандидатов: Пройдите через массив, используя алгоритм Бойера-Мура для поиска двух потенциальных кандидатов, которые могут встречаться более ⌊ n/3 ⌋ раз. Поддерживайте два счётчика и двух кандидатов. Если текущий элемент равен одному из кандидатов, увеличьте соответствующий счётчик. Если счётчик равен нулю, установите текущий элемент как кандидата и установите счётчик в 1. Если текущий элемент не совпадает ни с одним из кандидатов, уменьшите оба счётчика. 2⃣Подсчёт голосов: После определения двух кандидатов, пройдите через массив снова, чтобы посчитать фактическое количество появлений каждого кандидата. 3⃣Проверка порога: Проверьте, превышает ли количество появлений каждого кандидата порог ⌊ n/3 ⌋. Если да, добавьте кандидата в результат. 😎 Решение:

public class Solution {
    public IList<int> MajorityElement(int[] nums) {
        int count1 = 0, count2 = 0;
        int? candidate1 = null, candidate2 = null;
        
        foreach (int n in nums) {
            if (candidate1.HasValue && candidate1 == n) {
                count1++;
            } else if (candidate2.HasValue && candidate2 == n) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = n;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = n;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        
        foreach (int n in nums) {
            if (candidate1.HasValue && candidate1 == n) count1++;
            if (candidate2.HasValue && candidate2 == n) count2++;
        }
        
        IList<int> result = new List<int>();
        int nLength = nums.Length;
        if (count1 > nLength / 3) result.Add(candidate1.Value);
        if (count2 > nLength / 3) result.Add(candidate2.Value);
        
        return result;
    }
}

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

Задача: 128. Longest Consecutive Sequence Сложность: medium Дан несортированный массив целых чисел nums. Верните длину самой длинной последовательности последовательных элементов. Необходимо написать алгоритм, который работает за время O(n). Пример:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

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

public class Solution {
    private bool ArrayContains(int[] arr, int num) {
        for (int i = 0; i < arr.Length; i++) {
            if (arr[i] == num) {
                return true;
            }
        }

        return false;
    }

    public int LongestConsecutive(int[] nums) {
        int longestStreak = 0;
        for (int i = 0; i < nums.Length; i++) {
            int currentNum = nums[i];
            int currentStreak = 1;
            while (ArrayContains(nums, currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }

            longestStreak = Math.Max(longestStreak, currentStreak);
        }

        return longestStreak;
    }
}

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

Задача: 238. Product of Array Except Self Сложность: medium Дан массив целых чисел nums, верните массив answer такой, что answer[i] равен произведению всех элементов массива nums, кроме nums[i]. Произведение любого префикса или суффикса массива nums гарантированно помещается в 32-битное целое число. Вы должны написать алгоритм, который работает за время O(n) и не использует операцию деления. Пример:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

👨‍💻 Алгоритм: 1⃣Инициализация массивов L и R: Инициализируйте два пустых массива L и R. Массив L будет содержать произведение всех чисел слева от i, а массив R будет содержать произведение всех чисел справа от i. Заполните массив L, установив L[0] равным 1, а для остальных элементов используйте формулу L[i] = L[i-1] * nums[i-1]. Заполните массив R, установив R[length-1] равным 1, а для остальных элементов используйте формулу R[i] = R[i+1] * nums[i+1]. 2⃣Заполнение массивов L и R: Пройдите два цикла для заполнения массивов L и R. В первом цикле заполните массив L, начиная с L[0] и двигаясь вправо. Во втором цикле заполните массив R, начиная с R[length-1] и двигаясь влево. 3⃣Формирование результата: Пройдите по исходному массиву и для каждого элемента i вычислите произведение всех элементов, кроме nums[i], используя L[i] * R[i]. Сохраните результат в массиве answer и верните его. 😎 Решение:

public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        int length = nums.Length;
        int[] L = new int[length];
        int[] R = new int[length];
        int[] answer = new int[length];

        L[0] = 1;
        for (int i = 1; i < length; i++) {
            L[i] = nums[i - 1] * L[i - 1];
        }

        R[length - 1] = 1;
        for (int i = length - 2; i >= 0; i--) {
            R[i] = nums[i + 1] * R[i + 1];
        }

        for (int i = 0; i < length; i++) {
            answer[i] = L[i] * R[i];
        }

        return answer;
    }
}

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

Задача: 1006. Clumsy Factorial Сложность: medium Факториал целого положительного числа n - это произведение всех целых положительных чисел, меньших или равных n. Например, факториал(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1. Мы составляем неуклюжий факториал, используя целые числа в порядке убывания, заменяя операции умножения на фиксированную последовательность операций с умножением "*", делением "/", сложением "+" и вычитанием "-" в этом порядке. Например, clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1. Однако эти операции по-прежнему применяются с использованием обычного порядка операций арифметики. Мы выполняем все шаги умножения и деления перед шагами сложения и вычитания, а шаги умножения и деления выполняются слева направо. Кроме того, деление, которое мы используем, является делением с полом, так что 10 * 9 / 8 = 90 / 8 = 11. Учитывая целое число n, верните неуклюжий факториал n. Пример:

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

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

public class Solution {
    public int Clumsy(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2 * 1;
        if (n == 3) return 3 * 2 / 1;
        
        int res = n * (n - 1) / (n - 2);
        n -= 3;
        if (n > 0) res += n--;
        
        while (n > 0) {
            res -= n * (n - 1) / (n - 2);
            n -= 3;
            if (n > 0) res += n--;
        }
        
        return res;
    }
}

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

Задача: 1493. Longest Subarray of 1's After Deleting One Element Сложность: medium Дан бинарный массив nums, из которого следует удалить один элемент. Верните размер самой длинной непустой подмассивы, содержащей только 1, в результирующем массиве. Верните 0, если такого подмассива не существует. Пример:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].

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

public class Solution {
    public int LongestSubarray(int[] nums) {
        int zeroCount = 0;
        int longestWindow = 0;
        int start = 0;

        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] == 0) {
                zeroCount++;
            }

            while (zeroCount > 1) {
                if (nums[start] == 0) {
                    zeroCount--;
                }
                start++;
            }

            longestWindow = Math.Max(longestWindow, i - start);
        }

        return longestWindow;
    }
}

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

Задача: 94. Binary Tree Inorder Traversal Сложность: easy Дан корень бинарного дерева. Верните обход значений его узлов в симметричном порядке. Пример:

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

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

public class Solution {
    List<int> res = new List<int>();

    public IList<int> InorderTraversal(TreeNode root) {
        Helper(root);
        return res;
    }

    public void Helper(TreeNode root) {
        if (root != null) {
            Helper(root.left);
            res.Add(root.val);
            Helper(root.right);
        }
    }
}

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

Задача: 198. House Robber Сложность: medium Вы — профессиональный грабитель, планирующий ограбление домов вдоль улицы. В каждом доме спрятана определённая сумма денег, единственное ограничение, мешающее ограбить каждый из них, заключается в том, что соседние дома оснащены охранными системами, которые автоматически свяжутся с полицией, если в одну и ту же ночь будут взломаны два соседних дома. Учитывая целочисленный массив nums, представляющий сумму денег в каждом доме, верните максимальную сумму денег, которую вы можете ограбить этой ночью, не подняв тревогу. Пример:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

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

class Solution {
    private int[] memo;

    public int Rob(int[] nums) {
        memo = new int[100];
        for (int i = 0; i < memo.Length; i++) {
            memo[i] = -1;
        }
        return RobFrom(0, nums);
    }

    private int RobFrom(int i, int[] nums) {
        if (i >= nums.Length) {
            return 0;
        }
        if (memo[i] > -1) {
            return memo[i];
        }
        int ans = Math.Max(RobFrom(i + 1, nums), RobFrom(i + 2, nums) + nums[i]);
        memo[i] = ans;
        return ans;
    }
}

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

Задача: 943. Find the Shortest Superstring Сложность: hard Учитывая массив строк words, верните наименьшую строку, которая содержит каждую строку в words в качестве подстроки. Если существует несколько допустимых строк наименьшей длины, верните любую из них. Вы можете предположить, что ни одна строка в words не является подстрокой другой строки в words. Пример:

Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"

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

public class Solution {
    public string ShortestSuperstring(string[] words) {
        while (words.Length > 1) {
            int maxOverlap = -1;
            int l = 0, r = 0;
            string merged = "";
            for (int i = 0; i < words.Length; i++) {
                for (int j = 0; j < words.Length; j++) {
                    if (i != j) {
                        int ovlp = Overlap(words[i], words[j]);
                        if (ovlp > maxOverlap) {
                            maxOverlap = ovlp;
                            l = i;
                            r = j;
                            merged = Merge(words[i], words[j], ovlp);
                        }
                    }
                }
            }
            words[l] = merged;
            words = words.Where((val, idx) => idx != r).ToArray();
        }
        return words[0];
    }

    private int Overlap(string a, string b) {
        int maxOverlap = 0;
        for (int i = 1; i <= Math.Min(a.Length, b.Length); i++) {
            if (a.Substring(a.Length - i) == b.Substring(0, i)) {
                maxOverlap = i;
            }
        }
        return maxOverlap;
    }

    private string Merge(string a, string b, int overlapLen) {
        return a + b.Substring(overlapLen);
    }
}

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

Задача: 764. Largest Plus Sign Сложность: medium Вам дано целое число n. У вас есть бинарная сетка размером n x n, в которой все значения изначально равны 1, за исключением некоторых индексов, указанных в массиве mines. Элемент массива mines с индексом i определяется как mines[i] = [xi, yi], где grid[xi][yi] == 0. Верните порядок самого большого крестообразного знака из 1, выровненного по осям, который содержится в сетке. Если такого знака нет, верните 0. Крестообразный знак из 1 порядка k имеет некоторый центр grid[r][c] == 1, а также четыре луча длиной k - 1, идущих вверх, вниз, влево и вправо, состоящие из 1. Обратите внимание, что за пределами лучей креста могут быть 0 или 1, проверяется только соответствующая область крестообразного знака на наличие 1. Пример:

Input: n = 5, mines = [[4,2]]
Output: 2
Explanation: In the above grid, the largest plus sign can only be of order 2. One of them is shown.

👨‍💻 Алгоритм: 1⃣Создайте сетку размером n x n, заполненную единицами. Затем используйте массив mines, чтобы установить значения нулей в соответствующих ячейках сетки. 2⃣Для каждой ячейки в сетке создайте четыре дополнительных сетки: left, right, up и down, которые будут хранить длину непрерывных единиц, простирающихся в соответствующем направлении от каждой ячейки. 3⃣Пройдите по всей сетке и для каждой ячейки определите минимальную длину луча среди четырех направлений. Эта минимальная длина будет определять порядок крестообразного знака с центром в данной ячейке. Обновите максимальный порядок крестообразного знака и верните его после завершения обхода всей сетки. Если такого знака нет, верните 0. 😎 Решение:

public class Solution {
    public int OrderOfLargestPlusSign(int N, int[][] mines) {
        var banned = new HashSet<int>();
        foreach (var mine in mines) {
            banned.Add(mine[0] * N + mine[1]);
        }
        
        int ans = 0;
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                int k = 0;
                while (k <= r && r < N - k && k <= c && c < N - k &&
                      !banned.Contains((r - k) * N + c) &&
                      !banned.Contains((r + k) * N + c) &&
                      !banned.Contains(r * N + c - k) &&
                      !banned.Contains(r * N + c + k)) {
                    k++;
                }
                ans = Math.Max(ans, k);
            }
        }
        return ans;
    }
}

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