Проблема среднего уровня LeetCode
Это интересная проблема от LeetCode. Это одна из проблем среднего уровня. Его задавали 9 раз в Google и дважды в ходе собеседований по программированию на Amazon.
Так в чем проблема?
У нас есть две целочисленные последовательности A и B одинаковой ненулевой длины.
Нам разрешено менять местами элементы A [i] и B [i]. Обратите внимание, что оба элемента находятся в одной позиции индекса в своих соответствующих последовательностях.
В конце некоторого количества свопов A и B оба строго увеличиваются.
Последовательность строго возрастает тогда и только тогда, когда
A [0] ‹A [1]‹ A [2] ‹…‹ A [A.length - 1]
Для заданных A и B мы должны вернуть минимальное количество свопов, чтобы обе последовательности строго увеличивались. Гарантируется, что данный ввод всегда делает это возможным.
Example: Input: A = [1,3,5,4], B = [1,2,3,7] Output: 1 Explanation: Swap A[3] and B[3]. Then the sequences are: A = [1, 3, 5, 7] and B = [1, 2, 3, 4] which are both strictly increasing.
Примечание.
A, B - это массивы одинаковой длины, и эта длина будет в диапазоне
[1, 1000].
A [i], B [i] - целые значения в диапазоне [0, 2000].
Приходим к решению:
Используемый подход: динамическое программирование
Давайте рассмотрим следующее:
ni → естественно возрастающая последовательность, поэтому обмен не выполняется в позиции i.
si → представляет количество обменов до позиции Я считаю, что своп выполняется в позиции i.
- Пусть переменная n1 представляет собой стоимость отсутствия замены до позиции (i-1), и в этом случае элементы естественным образом увеличиваются по порядку. Это означает, что n1 будет количеством элементов, которое будет естественным образом увеличиваться до позиции (i-1).
- Пусть переменная n2 представляет собой стоимость естественного увеличения до (i) -й позиции, поэтому нет необходимости выполнять замену в i-й позиции.
- Пусть переменная s1 представляет собой стоимость, когда своп выполняется на (i-1) -й позиции.
- Пусть переменная s2 представляет собой стоимость, когда своп выполняется в (i) -й позиции.
Начальные значения
n1 = 0 → n1, естественно, будет 0, поскольку перед первым элементом не будет большего элемента, поэтому количество требуемых свопов будет равно 0
s1 = 1 → учитывая, что первый элемент поменялся местами, поэтому 1 переходит на 1-ю позицию
Теперь есть два основных подхода, которые нам нужно учитывать для каждой итерации цикла:
Дело 1:
Когда соседние элементы обоих массивов a [] и b [] строго увеличиваются
if(a[i-1]<a[i] && b[i-1]<b[i])
n2 = Math.min (n1, n2);
s2 = Math.min (s2, s1 + 1); → Считается, что своп выполняется в позиции i. Замена в (i) -й позиции может потребоваться для (i + 1) -го элемента позиции, чтобы поддерживать строго возрастающее свойство.
Случай 2:
Когда диагональные элементы тоже строго увеличиваются
if(a[i-1]<b[i] && b[i-1]<a[i])
Примечание. Если диагональные элементы строго увеличиваются, соседние элементы обоих массивов могут или не могут быть строго возрастающими.
Если верны и случай 1, и случай 2 ... т. е. если соседние элементы строго увеличиваются, а диагональные элементы также строго увеличиваются, тогда значения n2 и s2 нужно перекрыть.
n2 = Math.min (n2, s1); → Учитывая, что мы не меняем местами, n2 будет минимумом между естественным n2 до (i) -й позиции и количеством обменов s2, сделанных до (i- 1) -я позиция. Это вступает в силу для случаев, когда соседние элементы не строго увеличиваются, а диагональные элементы строго увеличиваются, поэтому необходимо выполнить замену.
s2 = Math.min (s2, n1 + 1) → Минимум (свопов, выполненных до i-й позиции) и (количество натуральных до (i-1) -й позиции + 1 своп, выполненный для позиция i). (n1 + 1) берется в качестве второго параметра, поскольку элементы строго увеличиваются даже для диагональных элементов, поэтому даже если мы поменяем местами (i) -й элемент, стоимость в конечном итоге составит (n1 + 1).
Прежде чем цикл перейдет к итерации с учетом следующей пары элементов,
n1 = n2;
s1 = s2;
Наконец-то,
return Math.min(n1,s1);
Возвращается минимум натурального и количество свопов.
Ниже для справки приведена кодированная на Java функция:
Ресурсы:
1. Проблема LeetCode № 801
2. Репозиторий GitHub для решения других подобных проблем LeetCode.
Это все! Спасибо, что прочитали весь путь! Оставьте свой отзыв. Если вам понравился блог, оставьте и 👏 аплодисменты.
Вы можете связаться со мной на -
Github: https://github.com/Spreeha
LinkedIn: https://www.linkedin.com/in/spreehadutta/
Twitter: https://twitter.com/DuttaSpreeha