Задача: для заданной строки верните:

• “IPv4”, если строка является валидным Ipv4 адресом.
• “IPv6”, если строка является валидным Ipv6 адресом.
• “Error”, если не является валидным IP-адресом любого типа.

Входные данные: str — исходная строка содержит только символы английского алфавита, цифры, а также символы ‘.’, ‘:’

Справка:

• IPv4-адрес — это IP-адрес в формате «x1.x2.x3.x4», где 0 <= xi <= 255 и xi не может содержать начальные нули.
• IPv6-адрес — это IP-адрес в форме «x1:x2:x3:x4:x5:x6:x7:x8», где 1 <= xi.length <= 4, xi — это шестнадцатеричная строка, которая может содержать цифры, строчные английские буквы (от «a» до «f») и заглавные английские буквы (от «A» до «F»). В xi разрешены ведущие нули.

Примеры:

1. «192.168.1.1»
   Output: “IPv4”
2. «192.168.01.1»
   Output: “Error”
3. «2001:0db8:85a3:0000:0000:8a2e:0370:7334»
   Output: “IPv6”
4. «2001:0db8:85a3::8A2E:037j:7334"
   Output: “Error”

Разбор

Применяем принцип разделяй и властвуй:

1. Разбиваем строку на блоки, разделенные символами ‘.’ или ‘:’.
2. Если кол-во блоков равно 4 -> используем функцию для валидации IPv4.
3. Если кол-во блоков равно 8 -> используем функцию для валидации IPv6.
4. В противном случае, сразу возвращаем сообщение об ошибке.

Функция для валидациия IPv4:

• Каждый из 4х блоков проверяем на валидность.
• Каждый блок должен быть не меньше 1 и не больше 3х символов.
• Каждый блок должен быть числом от 0 до 255, а также не должно быть начальных нулей.

Функция для валидации IPv6:

• Каждый из 8 блоков проверяем на валидность.
• Размер каждого блока должен быть не меньше 1 и не больше 4х символов.
• Каждый блок может содержать цифры [0–9] или буквы [a-f, A-F].

Реализация

Весь код тут:
https://gist.github.com/unilecs/90d9b8a6dd3e4d3041caa60b0b19dad9

Play-test

https://dotnetfiddle.net/ONaJxK

Validate IP address was originally published in UniLecs on Medium, where people are continuing the conversation by highlighting and responding to this story.

Задача: Находим блок поврежденных пикселей. Вам дана матрица пикселей, где ‘0’ представляет рабочий пиксель, а ‘1’ представляет поврежденный пиксель.

• Поврежденные пиксели связаны (т.е. есть только одна поврежденная область на матрице). Пиксели соединены по горизонтали и вертикали.
• Также вам даны два целых числа x и y, которые представляют расположение одного из поврежденных пикселей.

Необходимо найти площадь наименьшего (выровненного по оси) прямоугольника, охватывающего все поврежденные пиксели.

Входные данные: Стороны матрицы имеют размер от 1 до 100 пикселей включительно. Элементы матрицы символы ‘0’, ‘1’.

Вывод: площадь наименьшего прямоугольника, охватывающего все поврежденные пиксели.

Пример:

matrix = [

[‘0’,’0',’1',’0'],

[‘0’,’1',’1',’0'],

[‘0’,’1',’0',’0']

].

x = 0, y = 2

Output: 6

Разбор

Классический подход в подобных задачах — использование поиска в глубину (Depth-first search, DFS).

То есть из каждой текущего пикселя матрицы мы запускаем поиск вглубь матрицы до тех пор, пока встречаются поврежденные пиксели. И для каждой из сторон мы сохраним крайние координаты поврежденных пикселей. Таким образом, мы сможем определить длину поврежденной области по оси X и оси Y, и найдем площадь поврежденной области.

Детали реализации:

• Eсли исходная задача позволяет изменять исходные данные, в нашем случае, это матрица, то для того, чтобы алгоритм не считал уже пройденные элементы, мы можем изменить значение поврежденного пикселя.
• Если вы не хотите изменять исходные данные, то обычно используется вспомогательный массив посещенных координат visited. Таким образом на каждом шаге поиска в глубину, вы пропускаете уже пройденные элементы.

В нашем случае, мы можем изменить исходные данные, поэтому для простоты воспользуемся 1м вариантом.

Реализация

Play-test

https://dotnetfiddle.net/sRMdAC

Damaged pixels was originally published in UniLecs on Medium, where people are continuing the conversation by highlighting and responding to this story.

Задача: вам дана специальная клавиатура, все клавиши которой размещены в один ряд. Ряд длиной в 26 символов.
Изначально ваш курсор находится в индексе 0. Чтобы ввести символ, вы должны переместить курсор в указатель нужного символа. Время, необходимое для перемещения курсора с указателя i на указатель j, равно |i — j|.

Вы хотите ввести слово. Необходимо рассчитать, сколько времени нужно, чтобы набрать ее.

Входные данные: keyboard — строка в 26 символов, все символы — строчные английские буквы; word — слово, которые вам нужно набрать.

Вывод: время, которое необходимо, чтобы набрать входное слово курсором.

Примеры:

1. keyboard = “abcdefghijklmnopqrstuvwxyz”, word = “cba”
   Output: 4
   Пояснение:
   ‘c’: |0–2| = 2;
   ‘b’: |2–1| = 1;
   ‘a’: |1–0| = 1.
   В сумме получаем 2 + 1 + 1 = 4.
2. keyboard = “abcdefghijklmnopqrstuvwxyz”, word = “tag”
   Output: 44
   Пояснение:
   ‘t’: |0–19| = 19;
   ‘a’: |19–0| = 19;
   ‘g’: |0–6| = 6.
   В сумме получаем: 19 + 19 + 6 = 44.

Разбор

Давайте приведем интуитивный алгоритм:

1. Сохраним позиции символов нашей клавиатуры. Можно использовать хэш-таблицу или массив длиной 26, т.к. мы используем только строчные буквы английского алфавита — indices[].
2. Заводим счетчик текущего курсора pos — он будет указывать на позицию текущего символа для ввода. По умолчанию курсор (счетчик) находится в позици 0.
3. Также инициализируем результирующую переменную time = 0.
4. Проходим по входному слову, которое необходимо набрать на клавиатуре. На каждой итерации добавляем к time разность по модулю курсора и позицию текущего символа для ввода, т.е. Abs(pos — indices[i]).
5. Обновим курсор: теперь он равен indices[i].
6. Выводим результат time.

Детали смотрите ниже!

Реализация

https://gist.github.com/unilecs/a8a6d42724421836345576dcc0a56162

Play-test

https://dotnetfiddle.net/TU3PVj

One-row keyboard was originally published in UniLecs on Medium, where people are continuing the conversation by highlighting and responding to this story.

Задача: дан лиценизионный ключ, представленный в виде строки S. Строка разделена на N + 1 подгруппу, разделенных N дефисами. Также дано число K.

Необходимо преобразовать лицензионный ключ таким образом, чтобы каждая подгруппа содержала ровно K символов, за исключением 1й подгруппы, которая может быть короче K символов, но должна содержать хотя бы 1 символ. Также между 2мя любыми группами должно быть вставлен дефис. Все строчные буквы преобразовать в прописные.

Входные данные: строка S, состоящая только из букв английского алфавита, цифр и дефисов. K — целое число.

Вывод: преобразованная строка.

Примеры:

1. S = “5F3Z-2e-9-w”, K = 4
   Output: “5F3Z-2E9W”
2. S = “2–5g-3-J”, K = 2
   Output: “2–5G-3J”

Разбор

Алгоритм довольно простой: главная особенность решения в том, что мы парсим строку с конца, т.к. по условиям задачи нам необходимо оставить 1й блок с K символов или меньше, смотрите 2й пример.

Все детали реализации смотрите в коде!

Реализация

https://gist.github.com/unilecs/587aedf4cb17a00fb0c12d1227c371ee

Play-test

https://dotnetfiddle.net/4aM7re

Update License Key Format was originally published in UniLecs on Medium, where people are continuing the conversation by highlighting and responding to this story.

Задача: дан вложенный список целых чисел NestedList:

• каждый элемент представляет собой целое число или список, элементы которого также могут быть целыми числами или другими списками.

Необходимо реализовать итератор CustomIterator:

класс CustomIterator:

• CustomIterator(List<NestedInteger> nestedList) — конструктор, ктр инициализирует итератор вложенным списком nestedList.
• int Next() — метод класса, ктр возвращает следующее целое число во вложенном списке.
• boolean hasNext() — метод, ктр возвращает true, если во вложенном списке все еще есть целые числа, и false в противном случае.

Примеры:

1. NestedList = [[1, 1], 2, [1, 1]]
   Output: [1, 1, 2, 1, 1]
2. NestedList = [1, [4, [6]]]
   Output: [1, 4, 6]

Разбор

Самый простой способ решить эту задачу — это превратить вложенный список в обычный одномерный список. Как это сделать?!

Можно воспользоваться рекурсией: будем проходит по вложенному списку и добавлять в результирущий массив элемент, если это простое число, если же мы встретили вложенный список, то вызываем рекурсию с этим списком.

Таким образом по окончанию основного цикла в результирующем массиве мы получим все элементы, порядок элементов также сохраниться, т.к. мы проходим слева направо.

Далее все просто: мы просто заведем глобальную переменную, которая будет следить за позицией текущего элемента в итераторе. Эту переменную используем в методах HasNext и Next.

Детали реализации смотрите в коде!

Реализация

https://gist.github.com/unilecs/669e9ee2fcdd8c1d8d719d8d1bd8bbce

Play-test

https://dotnetfiddle.net/GKEGUo

Custom Iterator was originally published in UniLecs on Medium, where people are continuing the conversation by highlighting and responding to this story.

Задача: вы набираете имя на клавиатуре, которая иногда залипает и выводит символ несколько раз.

Необходимо проверить набранное имя с оригинальным и вернуть true, если возможно, что это было оригинальное имя, но с залипанием некоторых символов (возможно, было 0 залипаний), false — в противном случае.

Входные данные: origin — оригинальное имя, typed — набранное имя на клавиатуре. Обе строки содержат только прописные буквы английского алфавита: [‘a’,…,’z’].

Вывод: true/false

Примеры:

1. Origin: “albert”,
   Typed: “albert”
   Output: true
2. Origin: “albert”,
   Typed: “aaalberrt”
   Output: true (“залипли” символы ‘a’ и ‘r’)
3. Origin: “lee”,
   Typed: “lle”
   Output: false (оригинальное имя содержит 2 символа ‘e’)

Разбор

Эта задачу довольно легко можно решить за 3 прохода:

• сначала мы собираем информацию формата символ -> количество послед.вхождений для обоих строк (origin, typed);
• затем проходим и сравниваем элементы такой коллекции. Если мы встретили отличный символ или символ в набранной строке, у ктр кол-во послед.вхождений меньше, чем в оригинальной строке, то сразу выводим false.

Однако мы можем оптимизировать алгоритм как по времени, так и по памяти. Воспользуемся методом двух указателей: 1й указатель будет идти по оригинальной строке, 2й по набранной.

А идея довольно простая: на каждой итерации, мы будем проверять, равны ли текущие символы в строках.

• eсли да, то мы увеличиваем оба указателя;
• в противном случае мы предполагаем, что мы встретили символ, ктр ‘залип’, т.е. текущий набранный символ должен быть равен предыдущему. Если же и эта проверка не пройдена, то мы смело выводим false.

Смотрите детали реализации методом 2х указателей ниже!

Реализация

Код с комментариями!
https://gist.github.com/unilecs/e13c78b00563a4ddef89cf1faa140c0f

Play-test

https://dotnetfiddle.net/Fpe4R4

Long pressed string was originally published in UniLecs on Medium, where people are continuing the conversation by highlighting and responding to this story.

Задача: дано бинарное дерево, необходимо написать алгоритм, который вернет максимальное среднее значение поддерева.

Справка:

• Поддерево — это любой узел этого дерева плюс всего его потомки.
• Среднее значение дерева — это сумма его значений, деленная на количество узлов.

Входные данные: root — корень бинарного дерева

Вывод: максимальное среднее значение поддерева.

Примеры:

Output: 6

Пояснение: Max[

• (5 + 6 + 1) / 3 = 4
• 6 / 1 = 6
• 1 / 1 = 1

] = 6

Разбор

Воспользуемся методом поиска в глубину (DFS). Для каждого узла мы рекурсивно запустим поиск в глубину и найдем кол-во дочерних узлов слева и справа, а также сумму этих значений. Далее определим среднее значение для текущего узла и сравним с результирующим максимальным значением.

Рекурсивная подфункция будет возвращать массив, где 1й элемент — это кол-во дочерних узлов, а 2й элемент — сумма значений дочерних узлов.

Детали реализации смотрите ниже.

Реализация

https://gist.github.com/unilecs/b7c21026a06afbb556188b59f494866e

Play-test

https://dotnetfiddle.net/lf7r7B

Максимальное среднее значение бинарного поддерева was originally published in UniLecs on Medium, where people are continuing the conversation by highlighting and responding to this story.

Задача: дано игровое поле, которое задано матрицей m x n, где каждая ячейка представляет собой клетку корабля «X» или пустую клетку «.».

Необходимо найти количество всех кораблей на игровом поле.

Примечание: корабли можно размещать на игровом поле только горизонтально или вертикально. Также по крайней мере, 1 горизонтальная или вертикальная клетка разделяет два корабля.

Входные данные: board — символьная матрица, содержащая символы ‘.’, ‘X’. Размер сторон матрицы от 1 до 100.

Вывод: количество всех кораблей

Пример:

Board = [

[‘X’, ‘.’, ‘.’, ‘X’],

[‘.’, ‘.’, ‘.’, ‘X’],

[‘.’, ‘.’, ‘.’, ‘X’]]

Output: 2

Разбор

Первый способ решения — это запустить поиск в глубину (DFS), пометить посещенные клетки корабля и посчитать общее количество кораблей. Поиск в глубину довольно дорогой метод по времени, также он использует рекурсию.

Чтобы избежать этого, мы можем оптимизировать наш алгоритм, используя тот, факт, что корабли могут распологаться только по горизонтали или только по вертикали. Т.е. нам нужно посчитать только первые клетки кораблей.

Если на очередном шаге мы встретили клетку корабля, мы проверяем предыдущую клетку по вертикали и по горизонатли, если там также находится клетка корабля, то мы пропускаем эту итерацию. Так как мы уже посчитали этот корабль раньше.

Если же на очередном шаге мы встретили клетку корабля и предыдушие клетки по горизонтали и вертикали не являются клетками корабля, то значит мы нашли 1ю клетку нового корабля. В этом случае увеличиваем наш результирующий счетчик.

Детали смотрите в коде.

Реализация

https://gist.github.com/unilecs/1d63a9881b198e059eee7d7b72539399

Play-test

https://dotnetfiddle.net/s8z4UR

Морской бой was originally published in UniLecs on Medium, where people are continuing the conversation by highlighting and responding to this story.

Дадим определение “одинокого узла” в двоичном дереве. Это узел, который является единственным потомком своего родительского узла. Корень дерева не является одиноким узлом, так как у него нет родительского узла.

Задача: вам дано двоичное дерево. Необходимо вернуть массив, содержащий значения всех одиноких узлов в дереве.

Входные данные: root — корень двоичного дерева.

Вывод: массив значений одиноких узлов.

Пример:

Output: [9, 4]

Разбор

Рекурсивно пройдем по двоичному дереву: для каждого узла проверим условие для одинокого узла, т.е. только один из потомков (правый или левый) должен отсутствовать. Если это условие выполняется, записываем значение единственного потомка в результирующий список.
Продолжаем рекурсивный поиск для следующих узлов.

Реализация

https://gist.github.com/unilecs/0a8aac8308c1dce726bf65afc0c6f449

Play-test

https://dotnetfiddle.net/dcFTsv

Get Lonely Binary Nodes was originally published in UniLecs on Medium, where people are continuing the conversation by highlighting and responding to this story.

Задача: Необходимо вернуть заголовок столбца в Excel по порядковому номеру N.

A -> 1

B -> 2

C -> 3

…

Z -> 26

AA -> 27

AB -> 28

…

Входные данные: N — целое число от 1 до 2³¹ — 1.

Вывод: заголовок столбца в Excel

Примеры:

1. N = 1
   Output: “A”
2. N = 28
   Output: “AB”
3. N = 701
   Output: “ZY”

Разбор

Для простоты разберем на простом примере. Мы знаем, что номер столбца для столбца “ABZ” закодирован по следующей формуле:

N = A * 26² + B * 26¹ + Z * 26⁰
N = A * 26² + B * 26¹ + Z

Чтобы получить символ Z нам нужно взять остаток от деления на 26:
N % 26 = Z
Далее мы делим N на 26, тем самым мы двигаемся к следующему символу (B) и повторяем процесс. Таким образом мы получим все символы столбца под номером N.

В реализации стоит учесть, что в Excel нумерация столбцов идет от 1, в коде же нумерация смиволов A-Z будет начинаться с 0. Поэтому перед началом каждой итерации, мы уменьшаем текущий номер на 1.

Детали реализации смотрите ниже.

Реализация

https://gist.github.com/unilecs/9816810892bda78415466dcb8b154a97

Play-test

https://dotnetfiddle.net/jYKn7A

Convert column number to Excel title was originally published in UniLecs on Medium, where people are continuing the conversation by highlighting and responding to this story.