Проблема среднего уровня 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.

  1. Пусть переменная n1 представляет собой стоимость отсутствия замены до позиции (i-1), и в этом случае элементы естественным образом увеличиваются по порядку. Это означает, что n1 будет количеством элементов, которое будет естественным образом увеличиваться до позиции (i-1).
  2. Пусть переменная n2 представляет собой стоимость естественного увеличения до (i) -й позиции, поэтому нет необходимости выполнять замену в i-й позиции.
  3. Пусть переменная s1 представляет собой стоимость, когда своп выполняется на (i-1) -й позиции.
  4. Пусть переменная 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