C# | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
نمایش بیشتر
شبکه:3 201
مشترکین
اطلاعاتی وجود ندارد24 ساعت
-57 روز
-3230 روز
آرشیو پست ها
3 201
#medium
Задача: 142. Linked List Cycle II
Дана голова связного списка. Верните узел, с которого начинается цикл. Если цикла нет, верните null.
Цикл в связном списке существует, если есть такой узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла (индексация с нуля). Она равна -1, если цикла нет. Обратите внимание, что pos не передается в качестве параметра.
Не модифицируйте связный список.
Пример:
Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node.👨💻 Алгоритм: 1️⃣Инициализация и начало обхода: Инициализируйте узел указателем на голову связного списка и создайте пустое множество nodes_seen для отслеживания посещенных узлов. Начните обход со связного списка, перемещая узел на один шаг за раз. 2️⃣Проверка на наличие узла в множестве: Для каждого посещенного узла проверьте, содержится ли он уже в множестве nodes_seen. Если узел найден в множестве, это означает, что был найден цикл. Верните текущий узел как точку входа в цикл. 3️⃣Добавление узла в множество или завершение обхода: Если узел не найден в nodes_seen, добавьте его в множество и перейдите к следующему узлу. Если узел становится равным null (конец списка), верните null. В списке нет цикла, так как в случае наличия цикла вы бы застряли в петле и не достигли бы конца списка. 😎 Решение:
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode DetectCycle(ListNode head) {
HashSet<ListNode> nodesSeen = new HashSet<ListNode>();
ListNode node = head;
while (node != null) {
if (nodesSeen.Contains(node)) {
return node;
} else {
nodesSeen.Add(node);
node = node.next;
}
}
return null;
}
}3 201
👨💻 Джун: Слушай, вот стажировку я прошел, где теперь можно чекнуть вакансии на работу?
🍷 Мидл: Ооо, тебе помогут ребята с канала Джун работает
💯 Карьеру нужно начинать с хорошими работодателями. Твое резюме будет ликовать, ведь контент выходит каждый день, работа ждет тебя, мой друг!
😏 Не упускай возможность и подписывайся, чтобы не потерять
3 201
#easy
Задача: 141. Linked List Cycle
Дана переменная head, которая является началом связного списка. Определите, содержит ли связный список цикл.
Цикл в связном списке существует, если существует узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла. Обратите внимание, что pos не передается в качестве параметра.
Верните true, если в связном списке есть цикл. В противном случае верните false.
Пример:
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).👨💻 Алгоритм: 1️⃣Инициализация структуры данных: Создайте хеш-таблицу (или множество) для хранения ссылок на узлы, чтобы отслеживать уже посещённые узлы. 2️⃣Обход списка: Перемещайтесь по связному списку, начиная с головы (head), и проверяйте каждый узел по очереди. 3️⃣Проверка на цикл: Если текущий узел равен null, это означает, что вы достигли конца списка, и список не имеет циклов. В этом случае верните false. Если текущий узел уже содержится в хеш-таблице, это означает, что вы вернулись к ранее посещённому узлу, и, следовательно, в списке присутствует цикл. Верните true. Если ни одно из этих условий не выполнено, добавьте текущий узел в хеш-таблицу и продолжите обход списка. 😎 Решение:
public class Solution {
public bool HasCycle(ListNode head) {
HashSet<ListNode> nodesSeen = new HashSet<ListNode>();
ListNode current = head;
while (current != null) {
if (nodesSeen.Contains(current)) {
return true;
}
nodesSeen.Add(current);
current = current.next;
}
return false;
}
}3 201
📕 Прогер, как ты расширяешь свой кругозор в сфере IT?
Не достаточно знать что-то одно, мысля глобально и изучая смежные отрасли, ты не только становишься умнее, но и увеличиваешь свою востребованность и свой заработок.
🗿 Не обязательно читать заумные книги и смотреть подкасты - это долго.
У нас есть решение:
🔥 Полезные статьи - концентрат знаний.
🔥 Советы - короткие сообщения, которые будут увеличивать твою эффективность.
🔥 Инструменты - tool-сайты в разы упростят и ускорят твою работу.
🧑💻 Время, силы, желание - ресурсы, которые нужно использовать с умом. Подпишись на канал Заметки прогера, IT ниша скажет "спасибо" за такого специалиста.
3 201
#hard
Задача: 140. Word Break II
Дана строка s и словарь строк wordDict. Добавьте пробелы в строку s, чтобы построить предложение, в котором каждое слово является допустимым словом из словаря. Верните все такие возможные предложения в любом порядке.
Обратите внимание, что одно и то же слово из словаря может использоваться несколько раз при разделении.
Пример:
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"] Output: ["cats and dog","cat sand dog"]👨💻 Алгоритм: 1️⃣Инициализация и начальный вызов: Преобразуйте массив wordDict в множество wordSet для эффективного поиска. Инициализируйте пустой массив results для хранения допустимых предложений. Инициализируйте пустую строку currentSentence для отслеживания конструируемого предложения. Вызовите функцию backtrack с исходной строкой s, множеством wordSet, текущим предложением currentSentence, массивом результатов results и начальным индексом, установленным в 0 — начало входной строки. Верните results после завершения работы backtrack. 2️⃣Функция backtrack: Базовый случай: Если startIndex равен длине строки, добавьте currentSentence в results и вернитесь, так как это означает, что currentSentence представляет собой допустимое предложение. Итерация по возможным значениям endIndex от startIndex + 1 до конца строки. 3️⃣Обработка и рекурсия: Извлеките подстроку word от startIndex до endIndex - 1. Если word найдено в wordSet: Сохраните текущее значение currentSentence в originalSentence. Добавьте word к currentSentence (с пробелом, если это необходимо). Рекурсивно вызовите backtrack с обновленным currentSentence и endIndex. Сбросьте currentSentence к его исходному значению (originalSentence) для отката и попробуйте следующий endIndex. Вернитесь из функции backtrack. 😎 Решение:
using System.Collections.Generic;
public class Solution {
public IList<string> WordBreak(string s, IList<string> wordDict) {
HashSet<string> wordSet = new HashSet<string>(wordDict);
List<string> results = new List<string>();
string currentSentence = string.Empty;
Backtrack(s, wordSet, currentSentence, results, 0);
return results;
}
private void Backtrack(string s, HashSet<string> wordSet,
string currentSentence, IList<string> results,
int startIndex) {
if (startIndex == s.Length) {
results.Add(currentSentence);
return;
}
for (int endIndex = startIndex + 1; endIndex <= s.Length; endIndex++) {
string word = s.Substring(startIndex, endIndex - startIndex);
if (wordSet.Contains(word)) {
string originalSentence = currentSentence;
if (!string.IsNullOrEmpty(currentSentence)) currentSentence += " ";
currentSentence += word;
Backtrack(s, wordSet, currentSentence, results, endIndex);
currentSentence = originalSentence;
}
}
}
}3 201
😭 Джун: Как мне найти работу в IT, если опыта нет?
🧑💻 Мидл: Просто зайди на канал Джун стажер и подбери стажировку по душе.
📕 Админы отбирают самые сочные вакансии от ведущих компаний, к тому же контент выходит каждый день.
🔥 Не упускай возможность и подписывайся, чтобы не потерять
3 201
#medium
Задача: 139. Word Break
Дана строка s и словарь строк wordDict. Верните true, если строку s можно разделить на последовательность одного или нескольких слов из словаря, разделённых пробелами.
Обратите внимание, что одно и то же слово из словаря может использоваться несколько раз при разделении.
Пример:
Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".👨💻 Алгоритм: 1️⃣Инициализация структур данных: Преобразуйте wordDict в множество words для быстрой проверки вхождения. Инициализируйте очередь queue начальным значением 0 (индекс начала строки) и множество seen для отслеживания посещённых индексов. 2️⃣Обход в ширину (BFS): Пока очередь не пуста, извлекайте первый элемент из очереди, обозначающий начальную позицию start. Если start равен длине строки s, возвращайте true, так как достигнут конец строки, и строку можно разделить на слова из словаря. Итерируйте end от start + 1 до s.length включительно. Для каждого end, проверьте, посещён ли он уже. 3️⃣Проверка подстроки и обновление структур: Проверьте подстроку начиная с start и заканчивая перед end. Если подстрока находится в множестве words, добавьте end в очередь и отметьте его в seen как посещённый. Если BFS завершается и конечный узел не достигнут, возвращайте false. 😎 Решение:
public class Solution {
public bool WordBreak(string s, IList<string> wordDict) {
HashSet<string> words = new HashSet<string>(wordDict);
Queue<int> queue = new Queue<int>();
bool[] seen = new bool[s.Length + 1];
queue.Enqueue(0);
while (queue.Count != 0) {
int start = queue.Dequeue();
if (start == s.Length) {
return true;
}
for (int end = start + 1; end <= s.Length; end++) {
if (seen[end]) {
continue;
}
if (words.Contains(s.Substring(start, end - start))) {
queue.Enqueue(end);
seen[end] = true;
}
}
}
return false;
}
}3 201
👨💻 Будущий специалист, ты знаешь, какая самая частая ошибка новичка в сфере IT?
Отсутствие практики убивает в тебе потенциал
✈️ Как с этим бороться, мой друг?
Найди работу и прокачивай свои скилы на конкретных задачах
🔥 У нас ты будешь находить большое количество вакансий каждый день. Понятие работы перестанет быть для тебя размытым.
Подпишись на канал и не откладывай свой прогресс в долгий ящик.
3 201
#medium
Задача: 138. Copy List with Random Pointer
Дан связный список длиной n, в котором каждый узел содержит дополнительный случайный указатель (random pointer), который может указывать на любой узел в списке или быть равным null.
Создайте глубокую копию списка. Глубокая копия должна состоять из ровно n совершенно новых узлов, где каждый новый узел имеет значение, равное значению соответствующего оригинального узла. Указатели next и random новых узлов должны указывать на новые узлы в скопированном списке таким образом, чтобы указатели в оригинальном и скопированном списке представляли одно и то же состояние списка. Ни один из указателей в новом списке не должен указывать на узлы в оригинальном списке.
Например, если в оригинальном списке есть два узла X и Y, где X.random --> Y, то для соответствующих узлов x и y в скопированном списке, x.random должен указывать на y.
Верните голову скопированного связного списка.
Связный список представлен во входных/выходных данных как список из n узлов. Каждый узел представлен парой [val, random_index], где:
val: целое число, представляющее Node.val
random_index: индекс узла (в диапазоне от 0 до n-1), на который указывает случайный указатель, или null, если он не указывает ни на какой узел.
Вашему коду будет дана только голова оригинального связного списка.
Пример:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]👨💻 Алгоритм: 1️⃣Инициализация и начало обхода: Начните обход графа со стартового узла (head). Создайте словарь visited_dictionary для отслеживания посещенных и клонированных узлов. 2️⃣Проверка и клонирование узлов: Для каждого текущего узла (current_node) проверьте, есть ли уже клонированная копия в visited_dictionary. Если клонированная копия существует, используйте ссылку на этот клонированный узел. Если клонированной копии нет, создайте новый узел (cloned_node_for_current_node), инициализируйте его и добавьте в visited_dictionary, где ключом будет current_node, а значением — созданный клон. 3️⃣Рекурсивные вызовы для обработки связей: Сделайте два рекурсивных вызова для каждого узла: один используя указатель random, другой — указатель next. Эти вызовы отражают обработку "детей" текущего узла в терминах графа, где детьми являются узлы, на которые указывают указатели random и next. 😎 Решение:
public class Node {
public int val;
public Node next;
public Node random;
public Node(int _val, Node _next, Node _random) {
val = _val;
next = _next;
random = _random;
}
}
public class Solution {
private Dictionary<Node, Node> visitedHash = new Dictionary<Node, Node>();
public Node CopyRandomList(Node head) {
if (head == null) {
return null;
}
if (this.visitedHash.ContainsKey(head)) {
return this.visitedHash[head];
}
Node node = new Node(head.val, null, null);
this.visitedHash[head] = node;
node.next = this.CopyRandomList(head.next);
node.random = this.CopyRandomList(head.random);
return node;
}
}3 201
🧑💻 Если твой английский позволяет ответить только на вопрос "Do you speak English", то с этим нужно что-то делать, будучи программистом.
🫤 Ты в курсе, что ...
- говорят по-английски — 20% из всех людей.
- Большое кол-во IT документации написано на английском.
Хочешь понимать код лучше? Изучи язык, который используется в его основе.
📕 На нашем канале ты постепенно будешь набираться опыта, в этом тебе помогут:
- Тесты для изучения английского: проверьте свои знания на практике.
- Английский через мемы: учите язык весело и с интересом.
- Шпаргалки для повторения: закрепите знания быстро и эффективно.
- Английский сленг программиста: станьте настоящим профи в коммуникации.
🔥 Маленький шаг в изучении иностранного откроет перед тобой большие возможности будущего специалиста и значительно повысит твое зп.
🌸 Подпишись, do it!
3 201
#medium
Задача: 137. Single Number II
Дан массив целых чисел nums, в котором каждый элемент встречается три раза, кроме одного, который встречается ровно один раз. Найдите этот единственный элемент и верните его.
Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство.
Пример:
Input: nums = [2,2,3,2] Output: 3👨💻 Алгоритм: 1️⃣Сортировка массива: Отсортируйте массив nums. Это упорядочит все элементы так, чтобы одинаковые числа находились рядом. 2️⃣Итерация с проверкой: Используйте цикл for для перебора элементов массива от начала до nums.size() - 2 с шагом 3. Таким образом, каждый проверяемый индекс будет иметь следующий за ним индекс в пределах массива. Если элемент на текущем индексе совпадает с элементом на следующем индексе (проверка nums[i] == nums[i + 1]), продолжайте следующую итерацию цикла. 3️⃣Возврат уникального элемента: Если элемент на текущем индексе не совпадает с следующим, значит, это искомый уникальный элемент, который встречается только один раз. В этом случае возвращайте элемент на текущем индексе. Если до последнего элемента цикл не нашёл уникального элемента, возвращайте последний элемент массива nums[nums.size() - 1], поскольку он, очевидно, будет уникальным, если предыдущие проверки не выявили уникального элемента раньше. 😎 Решение:
public class Solution {
public int SingleNumber(int[] nums) {
Array.Sort(nums);
for (int i = 0; i < nums.Length - 1; i += 3) {
if (nums[i] == nums[i + 1]) {
continue;
} else {
return nums[i];
}
}
return nums[nums.Length - 1];
}
}3 201
#easy
Задача: 136. Single Number
Дан непустой массив целых чисел nums, в котором каждый элемент встречается дважды, кроме одного. Найдите этот единственный элемент.
Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство.
Пример:
Input: nums = [2,2,1] Output: 1👨💻 Алгоритм: 1️⃣Переберите все элементы в массиве nums. 2️⃣Если какое-то число в nums новое для массива, добавьте его. 3️⃣Если какое-то число уже есть в массиве, удалите его. 😎 Решение:
public class Solution {
public int SingleNumber(int[] nums) {
List<int> no_duplicate_list = new List<int>();
foreach (int i in nums) {
if (!no_duplicate_list.Contains(i)) {
no_duplicate_list.Add(i);
} else {
no_duplicate_list.Remove(i);
}
}
return no_duplicate_list[0];
}
}3 201
#hard
Задача: 135. Candy
В очереди стоят n детей. Каждому ребенку присвоено значение рейтинга, указанное в массиве целых чисел ratings.
Вы раздаете конфеты этим детям с соблюдением следующих требований:
Каждый ребенок должен получить как минимум одну конфету.
Дети с более высоким рейтингом должны получать больше конфет, чем их соседи.
Верните минимальное количество конфет, которое вам нужно иметь, чтобы распределить их среди детей.
Пример:
Input: ratings = [1,0,2] Output: 5 Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.👨💻 Алгоритм: 1️⃣Инициализация и первичное заполнение массивов: Создайте два массива: left2right для расчета конфет с учетом только левых соседей и right2left для расчета с учетом только правых соседей. Изначально каждому ученику в обоих массивах присваивается по одной конфете. 2️⃣Обход и обновление значений в массивах: Проходите массив ratings слева направо, увеличивая значение в left2right для каждого ученика, чей рейтинг выше рейтинга его левого соседа. Затем проходите массив справа налево, увеличивая значение в right2left для каждого ученика, чей рейтинг выше рейтинга его правого соседа. 3️⃣Расчет минимального количества конфет: Для каждого ученика определите максимальное значение конфет между left2right[i] и right2left[i], чтобы соответствовать требованиям к распределению конфет. Суммируйте полученные значения для всех учеников, чтобы найти минимальное количество конфет, необходимое для соблюдения всех правил. 😎 Решение:
public class Solution {
public int Candy(int[] ratings) {
int sum = 0;
int length = ratings.Length;
int[] left2right = Enumerable.Repeat(1, length).ToArray();
int[] right2left = Enumerable.Repeat(1, length).ToArray();
for (int i = 1; i < length; i++) {
if (ratings[i] > ratings[i - 1]) {
left2right[i] = left2right[i - 1] + 1;
}
}
for (int i = length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
right2left[i] = right2left[i + 1] + 1;
}
}
for (int i = 0; i < length; i++) {
sum += Math.Max(left2right[i], right2left[i]);
}
return sum;
}
}3 201
#medium
Задача: 134. Gas Station
Вдоль кругового маршрута расположены n заправочных станций, на каждой из которых находится определённое количество топлива gas[i].
У вас есть автомобиль с неограниченным топливным баком, и для проезда от i-й станции к следующей (i + 1)-й станции требуется cost[i] топлива. Путешествие начинается с пустым баком на одной из заправочных станций.
Учитывая два массива целых чисел gas и cost, верните индекс начальной заправочной станции, если вы можете проехать вокруг цепи один раз по часовой стрелке, в противном случае верните -1. Если решение существует, оно гарантированно будет уникальным.
Пример:
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2] Output: 3 Explanation: Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 4. Your tank = 4 - 1 + 5 = 8 Travel to station 0. Your tank = 8 - 2 + 1 = 7 Travel to station 1. Your tank = 7 - 3 + 2 = 6 Travel to station 2. Your tank = 6 - 4 + 3 = 5 Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3. Therefore, return 3 as the starting index.👨💻 Алгоритм: 1️⃣Инициализируйте переменные curr_gain, total_gain и answer значением 0. 2️⃣Пройдите по массивам gas и cost. Для каждого индекса i увеличивайте total_gain и curr_gain на gas[i] - cost[i]. Если curr_gain меньше 0, проверьте, может ли станция i + 1 быть начальной станцией: установите answer как i + 1, сбросьте curr_gain до 0 и повторите шаг 2. 3️⃣По завершении итерации, если total_gain меньше 0, верните -1. В противном случае верните answer. 😎 Решение:
public class Solution {
public int CanCompleteCircuit(int[] gas, int[] cost) {
int currGain = 0, totalGain = 0, answer = 0;
for (int i = 0; i < gas.Length; ++i) {
totalGain += gas[i] - cost[i];
currGain += gas[i] - cost[i];
if (currGain < 0) {
answer = i + 1;
currGain = 0;
}
}
return totalGain >= 0 ? answer : -1;
}
}3 201
#medium
Задача: 133. Clone Graph
Дана ссылка на узел в связанном неориентированном графе.
Верните глубокую копию (клон) графа.
Каждый узел в графе содержит значение (целое число) и список (List[Node]) своих соседей.
Пример:
Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]] Explanation: There are 4 nodes in the graph. 1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3). 3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).👨💻 Алгоритм: 1️⃣Используйте хеш-таблицу для хранения ссылок на копии всех уже посещенных и скопированных узлов. Ключом будет узел оригинального графа, а значением — соответствующий клонированный узел клонированного графа. Хеш-таблица посещенных узлов также используется для предотвращения циклов. 2️⃣Добавьте первый узел в очередь, клонируйте его и добавьте в хеш-таблицу посещенных. 3️⃣Выполните обход в ширину (BFS): извлеките узел из начала очереди, посетите всех соседей этого узла. Если какой-либо сосед уже был посещен, получите его клон из хеш-таблицы посещенных; если нет, создайте клон и добавьте его в хеш-таблицу. Добавьте клоны соседей в список соседей клонированного узла. 😎 Решение:
using System.Collections.Generic;
public class Node {
public int val;
public IList<Node> neighbors;
public Node() {
val = 0;
neighbors = new List<Node>();
}
public Node(int _val) {
val = _val;
neighbors = new List<Node>();
}
public Node(int _val, List<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
public class Solution {
public Node CloneGraph(Node node) {
if (node == null) {
return node;
}
Dictionary<Node, Node> visited = new Dictionary<Node, Node>();
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(node);
visited[node] = new Node(node.val, new List<Node>());
while (queue.Count > 0) {
Node n = queue.Dequeue();
foreach (Node neighbor in n.neighbors) {
if (!visited.ContainsKey(neighbor)) {
visited[neighbor] = new Node(neighbor.val, new List<Node>());
queue.Enqueue(neighbor);
}
visited[n].neighbors.Add(visited[neighbor]);
}
}
return visited[node];
}
}3 201
Как запустить собственный пет-проект и зарабатывать на нём зарплату senior-разработчика?
На этом канале мы решаем сложные задачи, которые часто попадаются на собеседованиях. Но что, если перевернуть игру и вместо работы на кого-то запустить собственный пет-проект, который будет приносить деньги?
Александр Рогачев запустил телеграм-канал Indie Hackers, где рассказывает про пет-проекты, которые приносят стабильный доход своим создателям.
Без венчурных инвестиций, без бизнес-планов и команды.
Разве такое возможно?
Да!
Несколько примеров:
Агрегатор вакансий c доходом в 4000$ / месяц
Плагин для Chrome с доходом 20000₽ / месяц
Если вы в поиске свежих идей, которые могут обеспечить стабильный пассивных доход, подписывайтесь на канал Indie Hackers.
Уверен, что там вы найдёте то самое, что зажжёт огонь в вашем сердце ❤️🔥
➡️ Ссылка для входа
3 201
#Hard
Задача: 132. Palindrome Partitioning II
Дана строка s. Разделите строку так, чтобы каждая подстрока разделения была палиндромом.
Верните минимальное количество разрезов, необходимых для разделения строки s на палиндромы.
Пример:
Input: s = "aab" Output: 1 Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.👨💻 Алгоритм: 1️⃣Определение задачи и начальные условия: Алгоритм обратного отслеживания реализуется путём рекурсивного изучения кандидатов-подстрок. Мы определяем рекурсивный метод findMinimumCut, который находит минимальное количество разрезов для подстроки, начинающейся с индекса start и заканчивающейся на индексе end. Чтобы найти минимальное количество разрезов, мы также должны знать минимальное количество разрезов, которые были найдены ранее для других разделений на палиндромы. Эта информация отслеживается в переменной minimumCut. Начальное значение minimumCut будет равно максимально возможному количеству разрезов в строке, что равно длине строки минус один (т.е. разрез между каждым символом). 2️⃣Генерация подстрок и рекурсивный поиск: Теперь, когда мы знаем начальные и конечные индексы, мы должны сгенерировать все возможные подстроки, начиная с индекса start. Для этого мы будем держать начальный индекс постоянным. currentEndIndex обозначает конец текущей подстроки. 3️⃣Условие палиндрома и рекурсивное разделение: Если текущая подстрока является палиндромом, мы сделаем разрез после currentEndIndex и рекурсивно найдем минимальный разрез для оставшейся строки 😎 Решение:
public class Solution {
public int MinCut(string s) {
return findMinimumCut(s, 0, s.Length - 1, s.Length - 1);
}
private int findMinimumCut(string s, int start, int end, int minimumCut) {
if (start == end || isPalindrome(s, start, end)) {
return 0;
}
for (int currentEndIndex = start; currentEndIndex <= end; currentEndIndex++) {
if (isPalindrome(s, start, currentEndIndex)) {
minimumCut = Math.Min(
minimumCut, 1 + findMinimumCut(s, currentEndIndex + 1, end, minimumCut));
}
}
return minimumCut;
}
private bool isPalindrome(string s, int start, int end) {
while (start < end) {
if (s[start++] != s[end--]) {
return false;
}
}
return true;
}
}3 201
#Medium
Задача: 131. Palindrome Partitioning
Дана строка s. Разделите строку таким образом, чтобы каждая подстрока разделения была палиндромом. Верните все возможные варианты разделения строки s на палиндромы.
Пример:
Input: s = "aab" Output: [["a","a","b"],["aa","b"]]👨💻 Алгоритм: 1️⃣Инициация рекурсивного обхода: В алгоритме обратного отслеживания (backtracking) мы рекурсивно пробегаем по строке, используя метод поиска в глубину (depth-first search). Для каждого рекурсивного вызова задаётся начальный индекс строки start. Итеративно генерируем все возможные подстроки, начиная с индекса start. Индекс end увеличивается от start до конца строки. 2️⃣Проверка на палиндром и продолжение поиска: Для каждой сгенерированной подстроки проверяем, является ли она палиндромом. Если подстрока оказывается палиндромом, она становится потенциальным кандидатом. Добавляем подстроку в currentList и выполняем поиск в глубину для оставшейся части строки. Если текущая подстрока заканчивается на индексе end, то end+1 становится начальным индексом для следующего рекурсивного вызова. 3️⃣Возврат (Backtracking) и сохранение результатов: Возвращаемся, если начальный индекс start больше или равен длине строки, и добавляем currentList в результат. 😎 Решение:
public class Solution {
public IList<IList<string>> Partition(string s) {
var ans = new List<IList<string>>();
Dfs(0, new List<string>(), s, ans);
return ans;
}
private void Dfs(int start, List<string> currentList, string s,
List<IList<string>> result) {
if (start >= s.Length)
result.Add(new List<string>(currentList));
else {
for (int end = start; end < s.Length; end++) {
if (IsPalindrome(s, start, end)) {
currentList.Add(s.Substring(start, end - start + 1));
Dfs(end + 1, currentList, s, result);
currentList.RemoveAt(currentList.Count - 1);
}
}
}
}
bool IsPalindrome(string s, int low, int high) {
while (low < high)
if (s[low++] != s[high--])
return false;
return true;
}
}3 201
#Medium
Задача: 130. Surrounded Regions
Вам дана матрица размером m на n, которая содержит буквы 'X' и 'O'. Захватите регионы, которые окружены:
Соединение: Ячейка соединена с соседними ячейками по горизонтали или вертикали.
Регион: Для формирования региона соедините каждую ячейку 'O'.
Окружение: Регион окружён ячейками 'X', если можно соединить регион с ячейками 'X', и ни одна из ячеек региона не находится на краю доски.
Окруженный регион захватывается путём замены всех 'O' на 'X' в исходной матрице.
Пример:
Input: board = [["X"]] Output: [["X"]]👨💻 Алгоритм: 1️⃣Выбор начальных ячеек и инициация DFS: Начинаем с выбора всех ячеек, расположенных на границах доски. Затем, начиная с каждой выбранной ячейки на границе, выполняем обход в глубину (DFS). 2️⃣Логика и выполнение DFS: Если ячейка на границе оказывается 'O', это означает, что эта ячейка "жива", вместе с другими ячейками 'O', соединёнными с этой граничной ячейкой. Две ячейки считаются соединёнными, если между ними существует путь, состоящий только из букв 'O'. Цель нашего обхода DFS будет заключаться в том, чтобы отметить все такие связанные ячейки 'O', которые исходят из границы, каким-либо отличительным символом, например, 'E'. 3️⃣Классификация и финальная обработка ячеек: После обхода всех граничных ячеек мы получаем три типа ячеек: Ячейки с буквой 'X': эти ячейки можно считать стеной. Ячейки с буквой 'O': эти ячейки не затрагиваются в нашем обходе DFS, то есть они не имеют соединения с границей, следовательно, они захвачены. Эти ячейки следует заменить на букву 'X'. Ячейки с буквой 'E': это ячейки, отмеченные в ходе нашего обхода DFS, то есть ячейки, имеющие хотя бы одно соединение с границами, следовательно, они не захвачены. В результате мы должны вернуть этим ячейкам их исходную букву 'O'. 😎 Решение:
public class Solution {
public void Solve(char[][] board) {
if (board == null || board.Length == 0) {
return;
}
this.ROWS = board.Length;
this.COLS = board[0].Length;
List<int[]> borders = new List<int[]>();
for (int r = 0; r < this.ROWS; ++r) {
borders.Add(new int[] { r, 0 });
borders.Add(new int[] { r, this.COLS - 1 });
}
for (int c = 0; c < this.COLS; ++c) {
borders.Add(new int[] { 0, c });
borders.Add(new int[] { this.ROWS - 1, c });
}
foreach (var pair in borders) {
this.DFS(board, pair[0], pair[1]);
}
for (int r = 0; r < this.ROWS; ++r) {
for (int c = 0; c < this.COLS; ++c) {
if (board[r][c] == 'O')
board[r][c] = 'X';
if (board[r][c] == 'E')
board[r][c] = 'O';
}
}
}
int ROWS, COLS;
protected void DFS(char[][] board, int row, int col) {
if (board[row][col] != 'O')
return;
board[row][col] = 'E';
if (col < this.COLS - 1)
DFS(board, row, col + 1);
if (row < this.ROWS - 1)
DFS(board, row + 1, col);
if (col > 0)
DFS(board, row, col - 1);
if (row > 0)
DFS(board, row - 1, col);
}
}3 201
#Medium
Задача: 129. Sum Root to Leaf Numbers
Вам дан корень бинарного дерева, содержащего только цифры от 0 до 9.
Каждый путь от корня до листа в дереве представляет собой число.
Например, путь от корня до листа 1 -> 2 -> 3 представляет число 123.
Верните общую сумму всех чисел от корня до листа. Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число.
Листовой узел — это узел без детей.
Пример:
Input: root = [1,2,3] Output: 25 Explanation: The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13. Therefore, sum = 12 + 13 = 25.👨💻 Алгоритм: 1️⃣Инициализация: Создайте переменные для хранения суммы чисел (rootToLeaf) и текущего числа (currNumber), а также стек для обхода дерева, начиная с корневого узла. 2️⃣Обход дерева: Используйте стек для глубинного обхода дерева (DFS), обновляя currNumber путём умножения на 10 и добавления значения узла. Для каждого листа добавляйте currNumber к rootToLeaf. 3️⃣Возвращение результата: По завершении обхода всех узлов возвращайте rootToLeaf, содержащую сумму всех чисел от корня до листьев дерева. 😎 Решение:
public class Solution {
public int SumNumbers(TreeNode root) {
int rootToLeaf = 0, currNumber = 0;
int steps;
TreeNode predecessor;
while (root != null) {
if (root.left != null) {
predecessor = root.left;
steps = 1;
while (predecessor.right != null && predecessor.right != root) {
predecessor = predecessor.right;
++steps;
}
if (predecessor.right == null) {
currNumber = currNumber * 10 + root.val;
predecessor.right = root;
root = root.left;
} else {
if (predecessor.left == null) {
rootToLeaf += currNumber;
}
for (int i = 0; i < steps; ++i) {
currNumber /= 10;
}
predecessor.right = null;
root = root.right;
}
} else {
currNumber = currNumber * 10 + root.val;
if (root.right == null) {
rootToLeaf += currNumber;
}
root = root.right;
}
}
return rootToLeaf;
}
}