C# | LeetCode
Kanalga Telegram’da o‘tish
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Ko'proq ko'rsatish
Tarmoq:3 157
Obunachilar
+124 soatlar
-127 kun
-3430 kun
Postlar arxiv
3 157
#medium
Задача: 720. Longest Word in Dictionary
Если задан массив строк words, представляющих английский словарь, верните самое длинное слово из words, которое может быть построено по одному символу из других слов из words. Если существует более одного возможного ответа, верните самое длинное слово с наименьшим лексикографическим порядком. Если ответа нет, верните пустую строку. Обратите внимание, что слово должно строиться слева направо, причем каждый дополнительный символ добавляется в конец предыдущего слова.
Пример:
Input: words = ["w","wo","wor","worl","world"] Output: "world"👨💻 Алгоритм: 1⃣Отсортируйте массив слов по длине и лексикографическому порядку. 2⃣Используйте множество для отслеживания слов, которые можно построить. 3⃣Пройдите по каждому слову в отсортированном массиве и добавьте его в множество, если все его префиксы уже существуют в множестве. 😎 Решение:
using System;
using System.Collections.Generic;
public class Solution {
public string LongestWord(string[] words) {
Array.Sort(words);
HashSet<string> validWords = new HashSet<string>();
validWords.Add("");
string longest = "";
foreach (string word in words) {
if (validWords.Contains(word.Substring(0, word.Length - 1))) {
validWords.Add(word);
if (word.Length > longest.Length) {
longest = word;
}
}
}
return longest;
}
}3 157
Repost from easyoffer
– Помощь с pet-проектом
– Составление roadmap
– Общая консультация
– Проведение код-ревью и mock-собеседования
– Помощь с трудоустройством
Все это и многое другое может Ментор. Он обеспечит вам необходимый boost, ускорит и упростит вход в IT.
🔥 Узнай список топовых менторов
✴ Многие из них предлагают бесплатную первую консультацию
3 157
#hard
Задача: 719. Find K-th Smallest Pair Distance
Расстояние между парой целых чисел a и b определяется как абсолютная разность между a и b. Учитывая целочисленный массив nums и целое число k, верните k-е наименьшее расстояние среди всех пар nums[i] и nums[j], где 0 <= i < j < nums.length.
Пример:
Input: nums = [1,3,1], k = 1 Output: 0👨💻 Алгоритм: 1⃣Отсортируйте массив nums. 2⃣Определите минимальное и максимальное возможные расстояния. 3⃣Используйте бинарный поиск, чтобы найти k-е наименьшее расстояние, проверяя количество пар с расстоянием меньше или равно текущему среднему значению. 😎 Решение:
public class Solution {
public int SmallestDistancePair(int[] nums, int k) {
Array.Sort(nums);
int left = 0, right = nums[nums.Length - 1] - nums[0];
while (left < right) {
int mid = (left + right) / 2;
if (CountPairs(nums, mid) < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
private int CountPairs(int[] nums, int mid) {
int count = 0, j = 0;
for (int i = 0; i < nums.Length; i++) {
while (j < nums.Length && nums[j] - nums[i] <= mid) {
j++;
}
count += j - i - 1;
}
return count;
}
}3 157
#medium
Задача: 718. Maximum Length of Repeated Subarray
Если даны два целочисленных массива nums1 и nums2, верните максимальную длину подмассива, который встречается в обоих массивах.
Пример:
Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] Output: 3👨💻 Алгоритм: 1⃣Создайте двумерный массив для хранения длин общих подмассивов. 2⃣Используйте динамическое программирование для нахождения максимальной длины общего подмассива. 3⃣Итеративно обновляйте массив, сравнивая элементы обоих массивов и обновляя максимальную длину подмассива. 😎 Решение:
public class Solution {
public int FindLength(int[] nums1, int[] nums2) {
int[,] dp = new int[nums1.Length + 1, nums2.Length + 1];
int maxLength = 0;
for (int i = nums1.Length - 1; i >= 0; i--) {
for (int j = nums2.Length - 1; j >= 0; j--) {
if (nums1[i] == nums2[j]) {
dp[i, j] = dp[i + 1, j + 1] + 1;
maxLength = Math.Max(maxLength, dp[i, j]);
}
}
}
return maxLength;
}
}3 157
#easy
Задача: 717. 1-bit and 2-bit Characters
У нас есть два специальных символа: первый символ может быть представлен одним битом 0. Второй символ может быть представлен двумя битами (10 или 11). Если задан двоичный массив bits, который заканчивается 0, верните true, если последний символ должен быть однобитным.
Пример:
Input: bits = [1,0,0] Output: true👨💻 Алгоритм: 1⃣Инициализируйте индекс для итерации по массиву. 2⃣Пройдите по массиву, увеличивая индекс на 1, если текущий бит равен 0, и на 2, если текущий бит равен 1. 3⃣Проверьте, достиг ли индекс последнего элемента массива, и верните результат. 😎 Решение:
public class Solution {
public bool IsOneBitCharacter(int[] bits) {
int i = 0;
while (i < bits.Length - 1) {
i += bits[i] + 1;
}
return i == bits.Length - 1;
}
}3 157
ТОП 2 канала для тех кто увлекатеся хакингом и кибербезопасностью:
Этичный Хакер — крупнейший в СНГ канал по информационной безопасности. OSINT, анонимность, пентест, социальная инженерия.
Лаборатория Хакера — авторский канал от специалиста по ИБ. Новости даркнета, сетевая разведка, обзоры инструментов с github, полезные подборки.
3 157
Нужен человек, для сбора вопросов из собеседований на должность C# разработчик.
Что надо делать:
1. Смотреть записи собеседований (список будет дан)
2. Выписывать вопросы, которые задают кандидату
Ставка: 450 руб. / час
Примерная ЗП: 54 000 руб. / месяц (4 часа в день)
Если интересно и можешь уделять работе от 4 часов / день, то отправь сообщение https://t.me/niniafd и сразу напиши какие языки программирования знаешь и какие лучше всего?
3 157
#medium
Задача: 776. Split BST
Дан корень бинарного дерева поиска (BST) и целое число target, разделите дерево на два поддерева, где первое поддерево содержит узлы, которые меньше или равны значению target, а второе поддерево содержит узлы, которые больше значения target. Не обязательно, чтобы дерево содержало узел со значением target.
Кроме того, большая часть структуры исходного дерева должна сохраниться. Формально, для любого потомка c с родителем p в исходном дереве, если они оба находятся в одном поддереве после разделения, то узел c все еще должен иметь родителя p.
Верните массив из двух корней двух поддеревьев в порядке.
Пример:
Input: root = [4,2,6,1,3,5,7], target = 2
Output: [[2,1],[4,3,6,null,null,5,7]]public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode[] SplitBST(TreeNode root, int target) {
if (root == null) {
return new TreeNode[]{null, null};
}
if (root.val > target) {
TreeNode[] left = SplitBST(root.left, target);
root.left = left[1];
return new TreeNode[]{left[0], root};
} else {
TreeNode[] right = SplitBST(root.right, target);
root.right = right[0];
return new TreeNode[]{root, right[1]};
}
}
}3 157
#hard
Задача: 716. Max Stack
Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова.
Пример:
Input ["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"] [[], [5], [1], [5], [], [], [], [], [], []] Output [null, null, null, null, 5, 5, 1, 5, 1, 5]👨💻 Алгоритм: 1⃣Инициализируйте MaxStack с двумя стеками: один для хранения всех элементов, другой для отслеживания максимальных элементов. 2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека. 3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно. 😎 Решение:
public class MaxStack {
private Stack<int> stack;
private Stack<int> maxStack;
public MaxStack() {
stack = new Stack<int>();
maxStack = new Stack<int>();
}
public void Push(int x) {
stack.Push(x);
if (maxStack.Count == 0 || x >= maxStack.Peek()) {
maxStack.Push(x);
}
}
public int Pop() {
int x = stack.Pop();
if (x == maxStack.Peek()) {
maxStack.Pop();
}
return x;
}
public int Top() {
return stack.Peek();
}
public int PeekMax() {
return maxStack.Peek();
}
public int PopMax() {
int maxVal = maxStack.Pop();
Stack<int> buffer = new Stack<int>();
while (stack.Peek() != maxVal) {
buffer.Push(stack.Pop());
}
stack.Pop();
while (buffer.Count > 0) {
Push(buffer.Pop());
}
return maxVal;
}
}3 157
#medium
Задача: 775. Global and Local Inversions
Дан массив целых чисел nums длиной n, который представляет собой перестановку всех чисел в диапазоне [0, n - 1].
Число глобальных инверсий — это количество различных пар (i, j), где:
0 <= i < j < n
nums[i] > nums[j]
Число локальных инверсий — это количество индексов i, где:
0 <= i < n - 1
nums[i] > nums[i + 1]
Верните true, если количество глобальных инверсий равно количеству локальных инверсий.
Пример:
Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.public class Solution {
public bool IsIdealPermutation(int[] A) {
int N = A.Length;
for (int i = 0; i < N; ++i)
for (int j = i + 2; j < N; ++j)
if (A[i] > A[j]) return false;
return true;
}
}3 157
📺 Уникальная база IT собеседований
456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы.
Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.
🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!
3 157
#hard
Задача: 774. Minimize Max Distance to Gas Station
Вам дан массив целых чисел 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.50000public 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];
}
}3 157
#hard
Задача: 715. Range Module
Модуль Range - это модуль, который отслеживает диапазоны чисел. Создайте структуру данных для отслеживания диапазонов, представленных в виде полуоткрытых интервалов, и запросов к ним. Полуоткрытый интервал [left, right) обозначает все вещественные числа x, где left <= x < right. Реализуйте класс RangeModule: RangeModule() Инициализирует объект структуры данных. void addRange(int left, int right) Добавляет полуоткрытый интервал [left, right), отслеживая каждое вещественное число в этом интервале. Добавление интервала, который частично перекрывает отслеживаемые в данный момент числа, должно добавить все числа в интервале [left, right), которые еще не отслеживаются. boolean queryRange(int left, int right) Возвращает true, если каждое действительное число в интервале [left, right) отслеживается в данный момент, и false в противном случае. void removeRange(int left, int right) Прекращает отслеживание каждого действительного числа, отслеживаемого в данный момент в полуоткрытом интервале [left, right).
Пример:
Input
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Output
[null, null, null, true, false, true]public class RangeModule {
private List<(int, int)> ranges;
public RangeModule() {
ranges = new List<(int, int)>();
}
public void AddRange(int left, int right) {
var newRanges = new List<(int, int)>();
int i = 0;
while (i < ranges.Count && ranges[i].Item2 < left) {
newRanges.Add(ranges[i]);
i++;
}
while (i < ranges.Count && ranges[i].Item1 <= right) {
left = Math.Min(left, ranges[i].Item1);
right = Math.Max(right, ranges[i].Item2);
i++;
}
newRanges.Add((left, right));
while (i < ranges.Count) {
newRanges.Add(ranges[i]);
i++;
}
ranges = newRanges;
}
public bool QueryRange(int left, int right) {
foreach (var range in ranges) {
if (range.Item1 <= left && right <= range.Item2) {
return true;
}
}
return false;
}
public void RemoveRange(int left, int right) {
var newRanges = new List<(int, int)>();
foreach (var range in ranges) {
if (range.Item1 < left) {
newRanges.Add((range.Item1, Math.Min(range.Item2, left)));
}
if (right < range.Item2) {
newRanges.Add((Math.Max(range.Item1, right), range.Item2)));
}
}
ranges = newRanges;
}
}3 157
#medium
Задача: 772. Basic Calculator III
Реализуйте базовый калькулятор для вычисления простого строкового выражения.
Строка выражения содержит только неотрицательные целые числа, операторы '+', '-', '*', '/' и открывающие '(' и закрывающие скобки ')'. Целочисленное деление должно округляться к нулю.
Предполагается, что данное выражение всегда корректно. Все промежуточные результаты будут находиться в диапазоне [-2^31, 2^31 - 1].
Примечание: нельзя использовать встроенные функции для вычисления строк как математических выражений, такие как eval().
Пример:
Input: s = "1+1"
Output: 2public class Solution {
private string Evaluate(char operator, string first, string second) {
int x = int.Parse(first);
int y = int.Parse(second);
int res = 0;
if (operator == '+') {
res = x;
} else if (operator == '-') {
res = -x;
} else if (operator == '*') {
res = x * y;
} else {
res = x / y;
}
return res.ToString();
}
public int Calculate(string s) {
Stack<string> stack = new Stack<string>();
string curr = "";
char previousOperator = '+';
s += "@";
HashSet<string> operators = new HashSet<string>(new string[] {"+", "-", "*", "/"});
foreach (char c in s) {
if (char.IsDigit(c)) {
curr += c;
} else if (c == '(') {
stack.Push(previousOperator.ToString());
previousOperator = '+';
} else {
if (previousOperator == '*' || previousOperator == '/') {
stack.Push(Evaluate(previousOperator, stack.Pop(), curr));
} else {
stack.Push(Evaluate(previousOperator, curr, "0"));
}
curr = "";
previousOperator = c;
if (c == ')') {
int currentTerm = 0;
while (!operators.Contains(stack.Peek())) {
currentTerm += int.Parse(stack.Pop());
}
curr = currentTerm.ToString();
previousOperator = stack.Pop()[0];
}
}
}
int ans = 0;
foreach (string num in stack) {
ans += int.Parse(num);
}
return ans;
}
}3 157
⚡️Вся База по IT в одном месте!
Надоело читать мусорные статьи и бред из ChatGPT? Нам тоже, поэтому мы создали IT Базу Знаний, где вручную отбираем всё самое вкусное из мира IT 🧑💻
🖥 Python: @python_baza
👩💻 Frontend: @frontend_baza
👩💻 Backend: @backend_baza
🎨 Дизайн: @design_baza
📚 Книги: @archive_baza
👩💻 Топ GitHub: @main_it_baza
⏲️ Ссылки на каналы будут доступны ещё 48 часов, успей забрать лучшее из мира IT в Телеге 👌
3 157
#medium
Задача: 714. Best Time to Buy and Sell Stock with Transaction Fee
Вам дан массив prices, где prices[i] - это цена данной акции в i-й день, и целое число fee, представляющее собой комиссию за сделку. Найдите максимальную прибыль, которую вы можете получить. Вы можете совершить сколько угодно сделок, но за каждую сделку вам придется заплатить комиссию. Примечание: Вы не можете совершать несколько сделок одновременно (то есть вы должны продать акции, прежде чем купить их снова). Комиссия за сделку взимается только один раз за каждую покупку и продажу акций.
Пример:
Input: prices = [1,3,2,8,4,9], fee = 2 Output: 8👨💻 Алгоритм: 1⃣Инициализируйте две переменные: cash, представляющую максимальную прибыль без наличия акций, и hold, представляющую максимальную прибыль с наличием акций. 2⃣Пройдите по каждому элементу массива prices и обновите значения cash и hold, используя текущую цену и комиссию. 3⃣Верните значение cash, которое будет максимальной прибылью без наличия акций. 😎 Решение:
public class Solution {
public int MaxProfit(int[] prices, int fee) {
int cash = 0, hold = -prices[0];
foreach (int price in prices) {
cash = Math.Max(cash, hold + price - fee);
hold = Math.Max(hold, cash - price);
}
return cash;
}
}3 157
#medium
Задача: 487. Max Consecutive Ones II
Дан бинарный массив nums, верните максимальное количество последовательных единиц в массиве, если можно перевернуть не более одного нуля.
Пример:
Input: nums = [1,0,1,1,0] Output: 4 Explanation: - If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones. - If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones. The max number of consecutive ones is 4.👨💻 Алгоритм: 1⃣Для каждого возможного начала последовательности в массиве nums начните считать количество нулей. 2⃣Для каждой последовательности проверяйте, сколько нулей содержится в ней. Если количество нулей не превышает одного, обновите максимальную длину последовательности единиц. 3⃣Продолжайте проверять все возможные последовательности в массиве, и верните максимальную длину последовательности единиц, удовлетворяющую условию. 😎 Решение:
public class Solution {
public int FindMaxConsecutiveOnes(int[] nums) {
int longestSequence = 0;
for (int left = 0; left < nums.Length; left++) {
int numZeroes = 0;
for (int right = left; right < nums.Length; right++) {
if (nums[right] == 0) {
numZeroes++;
}
if (numZeroes <= 1) {
longestSequence = Math.Max(longestSequence, right - left + 1);
}
}
}
return longestSequence;
}
}3 157
#medium
Задача: 771. Jewels and Stones
Вам даны строки jewels, представляющие типы камней, которые являются драгоценностями, и stones, представляющие камни, которые у вас есть. Каждый символ в stones является типом камня, который у вас есть. Вы хотите узнать, сколько из камней, которые у вас есть, также являются драгоценностями.
Буквы чувствительны к регистру, поэтому "a" считается другим типом камня, чем "A".
Пример:
Input: jewels = "aA", stones = "aAAbbbb"
Output: 3public class Solution {
public int NumJewelsInStones(string J, string S) {
int ans = 0;
foreach (char s in S)
foreach (char j in J)
if (j == s) {
ans++;
break;
}
return ans;
}
}3 157
#medium
Задача: 713. Subarray Product Less Than K
Если задан массив целых чисел nums и целое число k, верните количество смежных подмассивов, в которых произведение всех элементов в подмассиве строго меньше k.
Пример:
Input: nums = [10,5,2,6], k = 100 Output: 8👨💻 Алгоритм: 1⃣Инициализируйте переменные для отслеживания текущего произведения и количества допустимых подмассивов. Используйте два указателя для границ подмассива. 2⃣Перемещайте правый указатель по массиву и умножайте текущий элемент на текущее произведение. Если произведение становится больше или равно k, перемещайте левый указатель, уменьшая произведение до тех пор, пока оно снова не станет меньше k. 3⃣Подсчитайте количество подмассивов с текущим правым указателем, добавив к общему количеству допустимых подмассивов разницу между правым и левым указателями. 😎 Решение:
public class Solution {
public int NumSubarrayProductLessThanK(int[] nums, int k) {
if (k <= 1) return 0;
int product = 1, count = 0, left = 0;
for (int right = 0; right < nums.Length; right++) {
product *= nums[right];
while (product >= k) {
product /= nums[left];
left++;
}
count += right - left + 1;
}
return count;
}
}3 157
Все новости из мира программирования на этом канале @umnyiprogrammist
Подписывайтесь, чтобы не упустите ничего важного
Ставь 👍 и забирай 📚 Базу знаний
