Задача. Пропущенная двоичная строка
Дан массив строк nums, содержащий N уникальных двоичных строк длиной N каждая.
Необходимо вернуть двоичную строку длины N, которая нет в nums (если вариантов несколько, верните любой).
Разбор
Одна из простых идей заключается в том, чтобы пройтись по всевозможным двоичным числам заданной длины и проверить есть ли данное число в исходном массиве.
1. Все элементы исходного массива добавляем в хэш-сэт.
2. Так как все элементы массива имеют одинаковую длину, определим длину двоичного числа по 1му элемента: length = nums[0].Length.
3. В этой задаче мы также учитываем ведущие нули для двоичного числа длины length. Например, 0001 - двоичное число длины 4. Поэтому нам фактически нужно пройтись по всем двоичным числам от 0 до максимального двоичного числа длины length. А как определить сколько это?
- Если нам нужно найти все двоичные числа размера 1, то это будут 0 и 1. - Если нам нужно найти все двоичные числа размера 2, то это будут 00, 01, 10, 11. - Для размера N, количество чисел будет равно 2^N.
4. Теперь мы можем запустить цикл от 0 до 2^length, в цикле каждое число преобразуем в двоичное с ведущими нулями и проверяем есть ли оно в хэш-сете.
5. Возвращаем первый элемент, которого нет в хэш-сете (в исходном массиве).
Реализация
static string FindMissedBinaryString(string[] nums)
{
var set = new HashSet<string>(nums);
var len = nums[0].Length;
int digitNum = (int)Math.Pow(2, len);
for (int i = 0; i < digitNum; i++)
{
string binary = ConvertNumToBinaryString(i, len);
if (!set.Contains(binary))
{
return binary;
}
}
return "";
}https://gist.github.com/unilecs/26abc5bc60104341e2e4e48defeb898f