Беседа об алгоритмах
!!НАШ БЛОГ ПЕРЕЕХАЛ!!
Мы создали свой сайт! Все материалы, опубликованные в этом блоге, переехали туда.
Наш новый сайт maddevelop.ru
Первая задача
Условие
Дан массив целых неповторяющихся положительных чисел. Числа, соседние по числовой оси (при этом они могут находиться в разных частях массива), следует заключить в диапазон типа string, в котором указываются через тире начальное число диапазона и конечное. Необходимо получить строку, где в порядке возрастания указаны все диапазоны и/или отдельные цифры, в них не входящие.
Пример
Входной массив: { 3, 7, 5, 9, 4, 10 }
Ответ: "3 - 5, 7, 9 - 10"
Решение
// Массив преобразуется в строку "на лету". Сложность - O(n).
private static string ArrayToString(int[] array)
{
Array.Sort(array);
StringBuilder sb = new StringBuilder();
int length = array.Length;
if (length == 0)
sb.Append("");
else if (length == 1)
sb.Append(array[0].ToString());
else
{
bool defis = false;
for (int i = 1; i < length; i++)
{
if (array[i] - array[i - 1] == 1)
{
// Если дефис не поставлен, а числа идут подряд, то пишу число и дефис.
if (!defis)
{
sb.Append(quot;{array[i - 1].ToString()} - ");
defis = true;
}
continue;
}
// Если число идёт не подряд, то пишу предыдущее число и ставлю запятую.
sb.Append(quot;{array[i - 1].ToString()}, ");
defis = false;
}
// Добавляю последнее число.
sb.Append(array[length - 1].ToString());
}
return sb.ToString();
}
Конечно, сначала массив следует упорядочить и только потом пытаться получать выходную строку.
Решение следовало продемонстрировать на бумаге. А для этого необходимо сразу держать в голове все граничные случаи, такие как идущие подряд числа, все числа массива не лежат в диапазонах, последнее значение - отдельное и прочие. Учитывая их, я запутался и не смог решить задачу.
Товарищ предложил мне попробовать её сделать не "на лету", а через списки диапазонов. Такой способ действительно проще для реализации, хоть и увеличатся пространственная и временные сложности.
// Более длинный способ, сложность в худшем случае O(n*n).
private static string ArrayToStringLong(int[] array)
{
Array.Sort(array);
StringBuilder sb = new StringBuilder();
int length = array.Length;
if (length == 0)
return "";
else if (length == 1)
return array[0].ToString();
else
{
IList<List<int>> list = new List<List<int>>(); // Создаю список списков
// Текущий список, описывающий диапазон.
List<int> current = new List<int>() { array[0] };
for (int i = 1; i < length; i++)
{
if (array[i] - array[i - 1] == 1)
{
current.Add(array[i]);
continue;
}
else
{
// Обязательно делать ToList(), так как List - ссылочный тип.
// Метод ToList() позволит передать список по значению.
list.Add(current.ToList());
current.Clear();
current.Add(array[i]);
}
}
list.Add(current.ToList()); // Последний диапазон добавляем в список списков.
// Преобразую список диапазонов в выходную строку.
for (int i = 0; i < list.Count; i++)
{
if (list[i].Count == 1)
sb.Append(quot;{list[i].ElementAt(0).ToString()}, ");
else
sb.Append(quot;{list[i].ElementAt(0).ToString()} -
{list[i].ElementAt(list[i].Count - 1).ToString()}, ");
}
string output = sb.ToString();
return output.Remove(output.Length - 2, 2);
}
}
Вторая задача
Условие
Даны два массива целых неповторяющихся положительных чисел одинаковой длины. Создать третий массив такой, что его i-е значение, равняется количеству пар одинаковых чисел из значений от 0 до i первых двух массивов.
Пример
Первый массив: { 1, 2, 42, 8, 15 }
Второй массив: { 2, 5, 8, 7, 1 }
Выходной массив: { 0, 1, 1, 2, 3 }
Пояснение к получению выходного массива
0-й элемент
Первый массив: { 1 }
Второй массив: { 2 }
Числа различаются, поэтому выходной массив { 0 }.
1-й элемент
Первый массив: { 1, 2 }
Второй массив: { 2, 5 }
И в первом массиве, и во втором есть цифра 2, поэтому выходной массив { 0, 1 }.
2-й элемент
Первый массив: { 1, 2, 42 }
Второй массив: { 2, 5, 8 }
В массивах по-прежнему одинаковая цифра - 2, поэтому выходной массив { 0, 1, 1 }.
3-й элемент
Первый массив: { 1, 2, 42, 8 }
Второй массив: { 2, 5, 8, 7 }
Появляется ещё пара цифр 8, поэтому выходной массив { 0, 1, 1, 2 }.
4-й элемент
Первый массив: { 1, 2, 42, 8, 15 }
Второй массив: { 2, 5, 8, 7, 1 }
Цифра 1 есть также в обоих массивах, поэтому выходной массив { 0, 1, 1, 2, 3 }.
Решение
То, что следует использовать хеш-таблицу я придумал почти сразу. Ещё время ушло на догадку о второй хеш-таблицы.
public static int[] GetPairs(int[] first, int[] second)
{
int length = first.Length;
if (length == 0)
return null;
int[] output = new int[length];
HashSet<int> firstHash = new HashSet<int>();
HashSet<int> secondHash = new HashSet<int>();
if (first[0] == second[0])
output[0] = 1;
firstHash.Add(first[0]);
secondHash.Add(second[0]);
for (int i = 1; i < length; i++)
{
output[i] = output[i - 1];
firstHash.Add(first[i]);
secondHash.Add(second[i]);
if (first[i] == second[i])
{
output[i] = ++output[i];
continue;
}
if (secondHash.Contains(first[i]))
output[i] = ++output[i];
if (firstHash.Contains(second[i]))
output[i] = ++output[i];
}
return output;
}
К сожалению, снова не смог подумать о таких случаях, как пара массивов { 1, 2 } - { 1, 2 } и { 1, 2 } - { 2, 1 }. Поэтому итоговый ответ получил после пары подсказок.
Вывод
Для успешного прохождения собеседований с алгоритмами достаточно набить руку на сайтах типа Leetcode и Codewars. Тогда при взгляде на задачу будет видеть��я верное решение с учётом всех граничных ситуаций. Я, правда, прорешал их небольшое количество из-за того, что посвятил своё время освоению некоторых технологий.