Кодирование проблемы с собеседованием
Сложный уровень
Середина
Запрошено
Amazon, VMware
Обсуждены два решения
- Использование вложенных циклов - решение методом грубой силы
- Техника использования скользящего окна - эффективное решение
Основные выводы после прочтения этого блога
Это одна из хороших проблем для понимания идеи техники скользящего окна. Используя этот подход, мы можем эффективно решить несколько задач интервью в пространстве O (n) и O (1). (Подумайте!)
Давайте разберемся в проблеме:
Вам дан массив единиц и нулей, и вам дано целое число m, которое означает количество разрешенных переворотов. Найдите положение нулей, которое при перевороте дает максимальную непрерывную серию единиц.
Пример 1
Input: A[]= [1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1], m = 2 Output: [5, 7] Explanation: We are allowed to flip the maximum of 2 zeroes. If we flip A[5] and A[7], we get 8 consecutive 1’s which is maximum possible under given constraints Input: A[] = [1, 1, 0, 1, 0, 1, 0, 0, 1], m = 1 Output: 2 Explanation: We are allowed to flip maximum 1 zero. If we flip A[2], we get 4 consecutive 1's which is maximum possible under given constraints.
Примечания к проблемам
- Возвращает индексы максимальной непрерывной серии единиц по порядку.
- Если существует несколько возможных решений, верните последовательность с минимальным начальным индексом.
1. Решение методом грубой силы - использование вложенных циклов
Идея алгоритма
Решение методом перебора состоит в том, чтобы рассмотреть каждый подмассив, запустив два вложенных цикла. Для каждого подмассива подсчитайте количество нулей в нем и верните подмассив максимального размера с m или меньшим количеством нулей. (Подумайте!)
Код алгоритма C ++
Анализ алгоритмов
Сложность времени: в худшем случае нам нужно проверить каждый небольшой подмассив. Для этого мы запускаем два вложенных цикла в решении, где для каждого значения i j изменяется от i до n -1. Общее количество циклов = n + n -1 + n-2… + 1 = n (n-1) / 2 = O (n²)
Космическая сложность = O (1)
Возможные вопросы интервьюера
- Почему сложность пространства O (1)?
- Изучить лучший, средний и наихудший сценарий?
- Как мы можем улучшить временную сложность?
2. Эффективное решение: использование техники скользящего окна.
Шаги алгоритма
- Инициализируйте левый и правый указатели окна с нулями в качестве начального индекса, l = 0, r = 0.
- Увеличьте правый указатель, если идет ноль, тогда уменьшите m, иначе нет.
- На каждом шаге увеличения правого указателя сохраняется значение размера окна и значение левого и правого индекса, если предыдущее окно меньше текущего.
- Если m становится нулем, увеличивайте левый указатель до тех пор, пока левый указатель не достигнет правого указателя или не появятся следующие нули.
- Выполняйте шаги b, c, d, пока указатель записи не достигнет размера массива.
ручка для обработки углов
я. Если m == 0 и array = [1,0,1,0]
решение: строка № 42 по 46
Код алгоритма C ++
vector<int> Solution::maxOne(vector<int> &A, int m) { int l = 0,r = 0; vector<int> ans; int ansleft, ansright; int cntsize = 0; while(r < A.size()) { if (A[r] == 1) { if(cntsize < (r-l+1) && r < A.size()) { ansleft = l; ansright = r; cntsize = r-l+1; } r++; } else if(A[r] == 0 && m >0) { m--; if(cntsize < (r-l+1) && r < A.size()) { ansleft = l; ansright = r; cntsize = r-l+1; } r++; } else { while(l < r && m == 0) { if(A[l] == 1) l++; else { m++; l++; break; } } if(l == r && m == 0) { l++; r++; } } } if(cntsize > 0) { for(int i = ansleft;i <= ansright; i++) { ans.push_back(i); } } return ans; }
Анализ алгоритмов
Сложность пространства = O (1) пробел, поскольку используется единственная переменная.
Сложность времени = наихудший: O (2 * n), если каждый элемент повторяется 2 раза, и лучший: O (n), если каждый элемент повторяется 1 раз.
Возможные вопросы интервьюера
- Почему мы перемещаем правый указатель вперед, когда A [r] == 1?
- Почему мы проверяем условие r ‹A.size ()?
- Почему мы уменьшаем m, когда находим A [r] = 0?
- Объясните код, когда значение m становится равным нулю.
- Почему временная сложность O (n)? Объясните это, посчитав общее количество критических операций, выполненных циклом?
- Можно ли решить эти проблемы другим подходом? (Подумайте!)
Проблемы для практики - подход со скользящим окном
- Массив A размера 2n, в нем n + 1 уникальный элемент, и ровно один из этих элементов повторяется n раз. Вернуть элемент, повторенный n раз.
- Для массива, состоящего из n целых чисел, найдите непрерывный подмассив заданной длины, который имеет максимальное среднее значение.
- Учитывая массив положительных чисел, вычислите количество возможных смежных подмассивов, у которых произведение меньше заданного числа K.