Задача. Пропущенная двоичная строка
Дан массив строк 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