C# | LeetCode
Kanalga Telegram’da o‘tish
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Ko'proq ko'rsatish
Tarmoq:3 204
Obunachilar
-224 soatlar
-47 kunlar
-3430 kunlar
Postlar arxiv
3 204
Задача: 412. Fizz Buzz
Сложность: easy
Учитывая целое число n, верните строковый массив answer (с индексом 1), где: answer[i] == "FizzBuzz", если i делится на 3 и 5. answer[i] == "Fizz", если i делится на 3. answer[i] == "Buzz", если i делится на 5. answer[i] == i (как строка), если ни одно из перечисленных условий не верно.
Пример:
Input: nums = [1,2,2] Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]👨💻 Алгоритм: 1⃣Создайте пустой список для хранения результата. 2⃣Пройдите по всем числам от 1 до n и для каждого числа выполните проверку: Если число делится на 3 и на 5, добавьте "FizzBuzz". Если число делится на 3, добавьте "Fizz". Если число делится на 5, добавьте "Buzz". Если ни одно из условий не выполнено, добавьте само число как строку. 3⃣Верните полученный список. 😎 Решение:
using System;
using System.Collections.Generic;
public class Solution {
public IList<string> FizzBuzz(int n) {
List<string> answer = new List<string>();
for (int i = 1; i <= n; i++) {
if (i % 3 == 0 && i % 5 == 0) {
answer.Add("FizzBuzz");
} else if (i % 3 == 0) {
answer.Add("Fizz");
} else if (i % 5 == 0) {
answer.Add("Buzz");
} else {
answer.Add(i.ToString());
}
}
return answer;
}
}3 204
Задача: 945. Minimum Increment to Make Array Unique
Сложность: medium
Вам дан целочисленный массив nums. За один ход вы можете выбрать индекс i, где 0 <= i < nums.length, и увеличить nums[i] на 1. Верните минимальное количество ходов, чтобы каждое значение в nums было уникальным. Тестовые примеры генерируются так, чтобы ответ умещался в 32-битное целое число.
Пример:
Input: nums = [1,2,2] Output: 1👨💻 Алгоритм: 1⃣Отсортировать массив nums. Инициализировать переменную moves для подсчета количества ходов. 2⃣Пройти по массиву и для каждого элемента, начиная со второго: Если текущий элемент меньше или равен предыдущему элементу, увеличить текущий элемент до значения предыдущего элемента + 1 и обновить счетчик ходов. 3⃣Вернуть общее количество ходов. 😎 Решение:
public class Solution {
public int MinIncrementForUnique(int[] nums) {
Array.Sort(nums);
int moves = 0;
for (int i = 1; i < nums.Length; i++) {
if (nums[i] <= nums[i - 1]) {
moves += nums[i - 1] + 1 - nums[i];
nums[i] = nums[i - 1] + 1;
}
}
return moves;
}
}3 204
Задача: 1036. Escape a Large Maze
Сложность: hard
Имеется сетка размером 1 миллион на 1 миллион на плоскости XY, координаты каждого квадрата сетки - (x, y). Мы начинаем с исходного квадрата = [sx, sy] и хотим достичь цели = [tx, ty]. Существует также массив заблокированных квадратов, где каждый заблокированный[i] = [xi, yi] представляет собой заблокированный квадрат с координатами (xi, yi). Каждый ход мы можем пройти один квадрат на север, восток, юг или запад, если квадрат не находится в массиве заблокированных квадратов. Нам также не разрешается выходить за пределы сетки. Возвращается true тогда и только тогда, когда можно достичь целевого квадрата из исходного квадрата с помощью последовательности правильных ходов.
Пример:
Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2] Output: false👨💻 Алгоритм: 1⃣Обработка входных данных: Загрузите координаты исходного квадрата sx, sy, целевого квадрата tx, ty и список заблокированных квадратов blocked. 2⃣Проверка простого случая: Если список blocked пуст, верните true, так как путь не будет заблокирован. Проверка начальной или целевой клетки: Если исходная или целевая клетка заблокированы, верните false. 3⃣Поиск пути с использованием BFS или DFS: Используйте алгоритм поиска в ширину (BFS) или поиска в глубину (DFS) для поиска пути от sx, sy до tx, ty, избегая заблокированных клеток. Если обнаружен путь, верните true, в противном случае верните false. 😎 Решение:
public class Solution {
public bool IsEscapePossible(int[][] blocked, int[] source, int[] target) {
var blockedSet = new HashSet<(int, int)>(blocked.Select(b => (b[0], b[1])));
var src = (source[0], source[1]);
var tgt = (target[0], target[1]);
if (blockedSet.Contains(src) || blockedSet.Contains(tgt)) return false;
var directions = new (int, int)[] { (0, 1), (1, 0), (0, -1), (-1, 0) };
int maxArea = blocked.Length * (blocked.Length - 1) / 2;
bool Bfs((int, int) start, (int, int) end) {
var queue = new Queue<(int, int)>();
queue.Enqueue(start);
var visited = new HashSet<(int, int)> { start };
while (queue.Count > 0) {
if (visited.Count > maxArea) return true;
var (x, y) = queue.Dequeue();
foreach (var (dx, dy) in directions) {
var nx = x + dx;
var ny = y + dy;
var next = (nx, ny);
if (nx >= 0 && nx < 1_000_000 && ny >= 0 && ny < 1_000_000 && !visited.Contains(next) && !blockedSet.Contains(next)) {
if (next == end) return true;
queue.Enqueue(next);
visited.Add(next);
}
}
}
return false;
}
return Bfs(src, tgt) && Bfs(tgt, src);
}
}3 204
Задача: 438. Find All Anagrams in a String
Сложность: medium
Даны две строки s и p, вернуть массив всех начальных индексов анаграмм строки p в строке s. Ответ можно вернуть в любом порядке.
Анаграмма - это слово или фраза, образованные перестановкой букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.
Пример:
Input: s = "cbaebabacd", p = "abc" Output: [0,6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".👨💻 Алгоритм: 1⃣Построить эталонный счетчик pCount для строки p. 2⃣Передвигать скользящее окно по строке s: Пересчитывать счетчик скользящего окна sCount на каждом шаге, добавляя одну букву справа и удаляя одну букву слева. 3⃣Если sCount == pCount, обновить выходной список. Вернуть выходной список. 😎 Решение:
public class Solution {
public IList<int> FindAnagrams(string s, string p) {
int ns = s.Length, np = p.Length;
if (ns < np) return new List<int>();
var pCount = new Dictionary<char, int>();
var sCount = new Dictionary<char, int>();
foreach (char ch in p) {
if (pCount.ContainsKey(ch)) {
pCount[ch]++;
} else {
pCount[ch] = 1;
}
}
var output = new List<int>();
for (int i = 0; i < ns; ++i) {
char ch = s[i];
if (sCount.ContainsKey(ch)) {
sCount[ch]++;
} else {
sCount[ch] = 1;
}
if (i >= np) {
ch = s[i - np];
if (sCount[ch] == 1) {
sCount.Remove(ch);
} else {
sCount[ch]--;
}
}
if (pCount.SequenceEqual(sCount)) {
output.Add(i - np + 1);
}
}
return output;
}
}3 204
Задача: 935. Knight Dialer
Сложность: medium
Шахматный конь обладает уникальным движением: он может перемещаться на две клетки по вертикали и одну клетку по горизонтали, или на две клетки по горизонтали и одну клетку по вертикали (при этом обе клетки образуют форму буквы L). Возможные движения шахматного коня показаны на этой диаграмме: Шахматный конь может двигаться так, как показано на шахматной диаграмме ниже: У нас есть шахматный конь и телефонная панель, как показано ниже, конь может стоять только на числовой клетке (то есть на синей клетке).
Учитывая целое число n, верните, сколько различных телефонных номеров длины n мы можем набрать. Вам разрешается сначала поставить коня на любую цифровую клетку, а затем выполнить n - 1 прыжков, чтобы набрать номер длины n. Все прыжки должны быть правильными прыжками коня. Поскольку ответ может быть очень большим, верните ответ по модулю 10^9 + 7.
Пример:
Input: n = 1 Output: 10👨💻 Алгоритм: 1⃣Определить возможные движения коня с каждой цифровой клетки. Использовать динамическое программирование для хранения количества способов достижения каждой цифровой клетки на каждом шаге. 2⃣Инициализировать массив DP количеством способов набора телефонного номера длины 1 для каждой цифровой клетки (это просто 1). На каждом шаге обновлять массив DP, переходя по всем возможным движениям коня. 3⃣Вернуть сумму всех значений в массиве DP на последнем шаге. 😎 Решение:
public class Solution {
public int KnightDialer(int n) {
int MOD = 1000000007;
int[][] moves = new int[][] {
new int[] {4, 6},
new int[] {6, 8},
new int[] {7, 9},
new int[] {4, 8},
new int[] {0, 3, 9},
new int[0],
new int[] {0, 1, 7},
new int[] {2, 6},
new int[] {1, 3},
new int[] {2, 4}
};
int[] dp = new int[10];
Array.Fill(dp, 1);
for (int step = 1; step < n; step++) {
int[] newDp = new int[10];
for (int i = 0; i < 10; i++) {
foreach (int move in moves[i]) {
newDp[move] = (newDp[move] + dp[i]) % MOD;
}
}
dp = newDp;
}
int sum = 0;
foreach (int count in dp) {
sum = (sum + count) % MOD;
}
return sum;
}
}3 204
Осталось 3 часа до конца акции:
«Пожизненный PRO тариф — по цене 1 года»
Поиск работы отнимает силы, время и веру в себя, но не у тех кто использует easyoffer PRO. Успей сделать самую выгодную инвестицию в развитие своей карьеры.
Акция закончится уже сегодня 23 июня 23:59 по мск:
👉 https://easyoffer.ru/pro
3 204
Последний день акции:
«Пожизненный PRO тариф — по цене 1 года»
🚀 PRO включает:
– Полный доступ ко всем грейдам и профессиям
– База live-coding задач и вопросов из технических собеседований с вероятностью их встречи
– Примеры лучших ответов от Senior разработчиков
– 1100+ записи реальных собеседований, в том числе в топовые компании (Сбер, Авито, Яндекс, WB, OZON, МТС и др.)
– База 400+ тестовых заданий от компаний.
– Автоотклики на вакансии в хедхантер
– Аналитика ТОП-требований из вакансий для лучшего написания резюме и прохождения ATS систем рекрутеров
– Генератор уникального резюме и CV под каждую вакансию
– Тренажеры подготовки к собеседованию: «Реальное собеседование» и «Проработка вопросов» по методике интервальных повторений (как Anki)
– (скоро) Агрегатор вакансий
– (скоро) Сообщество
Акция закончится уже сегодня 23 июня 23:59 по мск:
👉 https://easyoffer.ru/pro
3 204
Задача: 684. Redundant Connection
Сложность: medium
В этой задаче дерево — это неориентированный граф, который является связным и не содержит циклов.
Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе.
Верните ребро, которое можно удалить, чтобы результирующий граф стал деревом из n узлов. Если существует несколько ответов, верните тот, который встречается последним в исходных данных.
Пример:
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]using System;
using System.Collections.Generic;
public class Solution {
HashSet<int> seen = new HashSet<int>();
const int MAX_EDGE_VAL = 1000;
public int[] FindRedundantConnection(int[][] edges) {
List<int>[] graph = new List<int>[MAX_EDGE_VAL + 1];
for (int i = 0; i <= MAX_EDGE_VAL; i++) {
graph[i] = new List<int>();
}
foreach (var edge in edges) {
seen.Clear();
if (graph[edge[0]].Count > 0 && graph[edge[1]].Count > 0 &&
Dfs(graph, edge[0], edge[1])) {
return edge;
}
graph[edge[0]].Add(edge[1]);
graph[edge[1]].Add(edge[0]);
}
throw new InvalidOperationException("No redundant connection found");
}
public bool Dfs(List<int>[] graph, int source, int target) {
if (!seen.Contains(source)) {
seen.Add(source);
if (source == target) return true;
foreach (int nei in graph[source]) {
if (Dfs(graph, nei, target)) return true;
}
}
return false;
}
}3 204
Пожизненный PRO тариф — по цене 1 года.
Покупаешь один раз — пользуешься всю жизнь:
👉 https://easyoffer.ru/pro
🚀 PRO-доступ закроет 99% проблем на пути к офферу:
1. Полный доступ ко всем грейдам и профессиям. Не важно, Junior вы или Senior, Тестировщик, Разработчик, Проджект — вы получите материалы под ваш текущий уровень и цели, без ограничений.
2. База live-coding задач и вопросов с реальных собесов с уникальной системой вероятности их встречи. Вы будете готовиться не вслепую, а точечно по тем темам, которые спрашивают чаще всего.
3. Эталонные ответы от Senior-разработчиков. Никакой воды и догадок — только четкие, структурированные решения, за которые дают «зеленый свет» к офферу
4. 1100+ записей реальных собеседований (включая топы: Сбер, Авито, Яндекс, WB, OZON, МТС). Вы увидите всё изнутри: как спрашивают, как отвечают сильные кандидаты и на каких ошибках проваливаются 80% проходящих.
5. База 400+ тестовых заданий. Если вы еще студент, то практикуйтесь на решении задач, которые помогут попасть на собес
6. Автоотклики на Хедхантере — пока вы спите, ваше резюме летит к рекрутерам автоматически. Это экономия сотен часов ручного кликанья.
7. Аналитика ТОП-требований из вакансий. Мы парсим рынок и показываем, какие скиллы сейчас в цене. Это позволит вам точечно апгрейдить резюме и проходить суровые ATS-фильтры (которые отсеивают до 75% резюме еще до просмотра рекрутером).
8. Генератор уникального резюме и CV под каждую вакансию. Забудьте про «универсальное» резюме — нейросеть адаптирует ваш опыт под конкретную позицию за минуту, повышая шансы на приглашение в разы.
9. Тренажеры подготовки к собеседованию:
«Реальное собеседование» — сценарий вопросов из реальных интервью
«Проработка вопросов» — флеш карточки с вопросами/ответами по методике интервальных повторений (как Anki)
10. (Скоро) Агрегатор вакансий — все вакансии из HH, Telegram, LinkedIn и других площадок в одной ленте.
11. (Скоро) Закрытое комьюнити — нетворкинг и помощь в сложных вопросах от таких же целеустремленных айтишников.
Завтра последний день акции:
👉 https://easyoffer.ru/pro
3 204
Задача: 944. Delete Columns to Make Sorted
Сложность: easy
Учитывая массив строк words, верните наименьшую строку, которая содержит каждую строку в words в качестве подстроки. Если существует несколько допустимых строк наименьшей длины, верните любую из них. Вы можете предположить, что ни одна строка в words не является подстрокой другой строки в words.
Пример:
Input: strs = ["cba","daf","ghi"] Output: 1👨💻 Алгоритм: 1⃣Инициализировать переменную count для отслеживания количества столбцов, которые нужно удалить. 2⃣Пройти по каждому столбцу от 0 до длины строки. Для каждого столбца проверить, отсортированы ли символы лексикографически. Если столбец не отсортирован, увеличить count. 3⃣Вернуть count. 😎 Решение:
public class Solution {
public int MinDeletionSize(string[] strs) {
int count = 0;
int rows = strs.Length;
int cols = strs[0].Length;
for (int col = 0; col < cols; col++) {
for (int row = 1; row < rows; row++) {
if (strs[row][col] < strs[row - 1][col]) {
count++;
break;
}
}
}
return count;
}
}3 204
Задача: 1260. Shift 2D Grid
Сложность: easy
Дана двумерная сетка размером m x n и целое число k. Требуется сдвинуть сетку k раз. За одну операцию сдвига: элемент в grid[i][j] перемещается в grid[i][j + 1]. Элемент в grid[i][n - 1] перемещается в grid[i + 1][0]. Элемент в grid[m - 1][n - 1] перемещается в grid[0][0]. Верните двумерную сетку после применения операции сдвига k раз.
Пример:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1 Output: [[9,1,2],[3,4,5],[6,7,8]]👨💻 Алгоритм: 1⃣Преобразовать двумерную сетку в одномерный массив. 2⃣Выполнить сдвиг элементов в одномерном массиве. 3⃣Преобразовать одномерный массив обратно в двумерную сетку. 😎 Решение:
public class Solution {
public IList<IList<int>> ShiftGrid(int[][] grid, int k) {
int m = grid.Length;
int n = grid[0].Length;
int total = m * n;
k = k % total;
if (k == 0) {
return grid;
}
int[] flatArray = new int[total];
for (int i = 0; i < total; i++) {
flatArray[i] = grid[i / n][i % n];
}
int[] newArray = new int[total];
for (int i = 0; i < total; i++) {
newArray[(i + k) % total] = flatArray[i];
}
var newGrid = new List<IList<int>>();
for (int i = 0; i < m; i++) {
var newRow = new List<int>();
for (int j = 0; j < n; j++) {
newRow.Add(newArray[i * n + j]);
}
newGrid.Add(newRow);
}
return newGrid;
}
}3 204
Привет, ребята!
У нас для вас отличные новости — на easyoffer вышло сразу несколько крупных обновлений:
1. Автоотклики на HeadHunter
Снова работают в полную силу — можно смело возвращаться к активному поиску.
2. Новый раздел «Резюмейкер»
Теперь вы можете быстро создавать уникальные резюме, адаптированные под каждую вакансию, и сразу добавлять сопроводительное письмо. Это заметно повышает шансы получить приглашение на собеседование.
3. База вопросов стала чище
Мы навели порядок и удалили около 30% дубликатов.
Ориентироваться стало проще.
––––––––––––––––––
🔥 Акция в честь обновления
Пожизненный тариф easyoffer PRO — по цене одного года.
Успейте до 23 июня:
👉 https://easyoffer.ru/pro
––––––––––––––––––
Что дальше?
В ближайшие пару недель добавим ещё два раздела:
1. Сообщество с чатами по всем профессиональным направлениям.
2. Агрегатор вакансий, чтобы поиск работы стал ещё удобнее.
3 204
Задача: 507. Perfect Number
Сложность: easy
Совершенное число — это положительное целое число, которое равно сумме своих положительных делителей, исключая само число. Делитель целого числа x — это целое число, которое может делить x нацело.
Дано целое число n, верните true, если n является совершенным числом, в противном случае верните false.
Пример:
Input: num = 28 Output: true Explanation: 28 = 1 + 2 + 4 + 7 + 14 1, 2, 4, 7, and 14 are all divisors of 28.👨💻 Алгоритм: 1⃣Инициализация Если число num меньше или равно 0, вернуть false. Инициализируйте переменную sum значением 0. 2⃣Поиск делителей и вычисление суммы Переберите числа от 1 до квадратного корня num. Если число является делителем num, добавьте его к sum. Если делитель не равен квадратному корню num, добавьте к sum также результат деления num на делитель. 3⃣Проверка на совершенное число Вычтите num из sum. Если результат равен num, вернуть true, иначе вернуть false. 😎 Решение:
public class Solution {
public bool CheckPerfectNumber(int num) {
if (num <= 0) return false;
int sum = 0;
for (int i = 1; i * i <= num; i++) {
if (num % i == 0) {
sum += i;
if (i * i != num) {
sum += num / i;
}
}
}
return sum - num == num;
}
}3 204
Задача: 815. Bus Routes
Сложность: hard
Дан массив routes, представляющий автобусные маршруты, где routes[i] - это автобусный маршрут, который i-й автобус повторяет бесконечно.
Например, если routes[0] = [1, 5, 7], это означает, что 0-й автобус путешествует в последовательности 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... бесконечно.
Вы начинаете на автобусной остановке source (вы изначально не находитесь в автобусе) и хотите добраться до автобусной остановки target. Перемещаться между автобусными остановками можно только на автобусах.
Верните наименьшее количество автобусов, которые вам нужно взять, чтобы доехать от source до target. Верните -1, если это невозможно.
Пример:
Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.public class Solution {
public int NumBusesToDestination(int[][] routes, int source, int target) {
if (source == target) return 0;
var adjList = new Dictionary<int, List<int>>();
for (int route = 0; route < routes.Length; route++) {
foreach (int stop in routes[route]) {
if (!adjList.ContainsKey(stop)) {
adjList[stop] = new List<int>();
}
adjList[stop].Add(route);
}
}
var q = new Queue<int>();
var vis = new HashSet<int>();
foreach (int route in adjList.GetValueOrDefault(source, new List<int>())) {
q.Enqueue(route);
vis.Add(route);
}
int busCount = 1;
while (q.Count > 0) {
int size = q.Count;
for (int i = 0; i < size; i++) {
int route = q.Dequeue();
foreach (int stop in routes[route]) {
if (stop == target) return busCount;
foreach (int nextRoute in adjList.GetValueOrDefault(stop, new List<int>())) {
if (!vis.Contains(nextRoute)) {
vis.Add(nextRoute);
q.Enqueue(nextRoute);
}
}
}
}
busCount++;
}
return -1;
}
}3 204
Задача: 258. Add Digits
Сложность: easy
Дано целое число num. Повторно складывайте все его цифры, пока результат не станет однозначным, и верните его.
Пример:
Input: num = 38 Output: 2 Explanation: The process is 38 --> 3 + 8 --> 11 11 --> 1 + 1 --> 2 Since 2 has only one digit, return it.👨💻 Алгоритм: 1⃣Инициализируйте переменную digital_root значением 0. 2⃣В цикле, пока num больше 0: Добавьте к digital_root последнюю цифру num. Уменьшите num, удалив последнюю цифру. Если num равно 0 и digital_root больше 9, присвойте num значение digital_root и сбросьте digital_root в 0. 3⃣Верните значение digital_root. 😎 Решение:
public class Solution {
public int AddDigits(int num) {
int digital_root = 0;
while (num > 0) {
digital_root += num % 10;
num /= 10;
if (num == 0 && digital_root > 9) {
num = digital_root;
digital_root = 0;
}
}
return digital_root;
}
}3 204
Задача: 868. Binary Gap
Сложность: easy
Дано положительное целое число n, найдите и верните наибольшее расстояние между любыми двумя соседними единицами в двоичном представлении числа n. Если нет двух соседних единиц, верните 0.
Две единицы считаются соседними, если их разделяют только нули (возможно, никаких нулей нет). Расстояние между двумя единицами — это абсолютная разница между их позициями в битовом представлении. Например, две единицы в "1001" имеют расстояние 3.
Пример:
Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.public class Solution {
public int BinaryGap(int N) {
int[] A = new int[32];
int t = 0;
for (int i = 0; i < 32; ++i)
if (((N >> i) & 1) != 0)
A[t++] = i;
int ans = 0;
for (int i = 0; i < t - 1; ++i)
ans = Math.Max(ans, A[i + 1] - A[i]);
return ans;
}
}3 204
Задача: 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.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;
}
}3 204
Задача: 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;
}3 204
Задача: 605. Can Place Flowers
Сложность: Easy
У вас есть длинная клумба, на которой некоторые участки засажены, а некоторые нет. Однако цветы нельзя сажать на соседних участках.
Дан целочисленный массив
flowerbed, содержащий 0 и 1, где 0 означает пустой участок, а 1 — занятый участок, и целое число n. Верните true, если n новых цветов можно посадить на клумбе, не нарушая правила о соседних цветах, и false в противном случае.
Пример:
Input: flowerbed = [1,0,0,0,1], n = 1
Output: truepublic 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;
}
}3 204
Задача: 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];
}
}