В этой серии постов “Leetcode” я опубликую решения проблем с leetcode. Это правда, что вы можете найти большинство/множество решений leetcode в Интернете, но я постараюсь опубликовать свои решения для проблем, которые интересны, или для проблем, для которых решения не очень хорошо объяснены и заслуживают лучшего объяснения.
Цель состоит в том, чтобы делиться знаниями и чтобы люди, которые учатся, готовятся к собеседованиям или просто практикуются, могли лучше решать проблемы. Пожалуйста, не стесняйтесь комментировать, если у вас есть предложение или другой подход!
Учитывая массив nums с n целыми числами, ваша задача – проверить, может ли он стать неубывающим, изменив не более 1 элемента.
Мы определяем, что массив неубывающий, если nums[i][i + 1] выполняется для каждого i (на основе 0), такого что (0 – 2).
Резюме: У вас есть метод, который возвращает значение true. Массив, переданный в качестве входных данных, может увеличиваться (не уменьшаться), что означает, что значения в массиве равны или больше, чем у предыдущего элемента в массиве. Вы можете изменить не более одного элемента в массиве, чтобы это произошло.
Решения, предоставляемые leetcode, довольно запутанны (и код только на python). И оптимальное решение кажется более сложным, чем оно есть на самом деле.
Первое Решение
Основная идея
Пройдите по массиву, если есть элемент, который нарушает ограничение (увеличивается), затем измените/отметьте его. Продолжайте просматривать массив, если произойдет еще одно нарушение, затем верните false, так как мы не можем изменять более одного раза. Если не было никакого нарушения или мы изменили не более одного раза, тогда верните true.
Объяснение и код
Увеличивающийся массив должен быть примерно таким:
[1,2,2,3,4,5,5]
Каждый элемент в массиве: array[i] меньше или равен следующему элементу: array[i+1].
массив[i][i+1]
Таким образом, входной массив потенциально может нарушить это ограничение в какой-то момент:
[…2,8,5,…]
В приведенном выше примере, который представляет собой массив, в какой-то момент один из элементов не больше или не равен следующему. В этом случае:
8 не больше или равно 2
Так что просто делайте, как сказано в проблеме, измените ее, чтобы исправить!
Нам нужно изменить какой-то элемент, чтобы ограничения не были нарушены. Теперь вопрос в том, что изменить, какое значение?
Главное здесь – помнить, что нам всегда нужно изменять массив до состояния, соответствующего ограничениям, в этом случае мы должны увеличивать элементы массива.
Итак, у нас есть следующие ограничения относительно состояния массива при любом индексе:
Любой элемент, предшествующий индексу “i”: array[i-1], должен быть меньше или равен элементу с индексом “i”: array[i]
Любой элемент после индекса “i”: array[i+1] должен быть больше или равен элементу с индексом “i”: array[i]
Нам нужны эти 2 ограничения, чтобы гарантировать, что значения массива увеличиваются, и нам нужно их поддерживать.
Какое бы изменение мы ни решили внести, эти 2 ограничения должны быть сохранены после изменения.
На данный момент решение простое, если мы рассмотрим “комбинации”, которые мы могли бы иметь как с предыдущими, так и со следующими элементами в массиве, со ссылкой на индекс, где ограничения не поддерживаются.
- Если предыдущий элемент в массиве больше следующего элемента, то нам нужно изменить следующий элемент на значение текущего элемента:
массив[i+1][i]
Пример:
[…8,10,5,…]//Не в порядке возрастания, 10 > 5
массив[i] массив[i-1] > массив[i+1] 8 > 5
Итак, чтобы исправить это, мы меняем массив[i + 1] на массив[i]:
[…8,10,10,…]
Это единственный способ гарантировать, что мы сохраняем растущий порядок и соблюдаем ограничения.
- Если предыдущий элемент в массиве меньше следующего элемента, нам нужно изменить текущий элемент на значение следующего элемента:
массив[i][i+1]
[…4,9,7…]//Не в порядке возрастания, 9 > 7
массив[i] массив[i-1] < массив[i+1] 4 > 7
Итак, чтобы исправить это, мы меняем массив[i] на массив [i + 1]:
[…4,7,7,…]
Это единственный способ гарантировать, что мы сохраняем растущий порядок и соблюдаем ограничения.
Обратите внимание, что мы также могли бы изменить массив [i + 1] на 9, но это может испортить следующие элементы после массива [i + 1].
Код выглядит следующим образом:
public boolean checkPossibility(int[] nums) {
boolean changed = false;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
if (changed) return false;
if (i != 0 && nums[i - 1] > nums[i + 1]) {
nums[i + 1] = nums[i];
}
changed = true;
}
}
return true;
}
В реальном коде нам действительно не нужно ничего менять для второго случая, где array[i-1] < array [i + 1], потому что мы будем продолжать проверять массив с помощью array [i + i], и поскольку это значение вообще не изменяется, мы можем игнорировать “фактическое” изменение, которое происходит в массиве[i].
Что нам всегда нужно, так это иметь логическую переменную, которая указывает, вносили ли мы ранее изменения в массив. Итак, в случае, если мы это сделали, и переменная “изменена” имеет значение true, тогда мы больше не можем вносить какие-либо другие изменения, и мы должны вернуть false, если требуется другое изменение.
Код прост и понятен. Одним из недостатков этого подхода является то, что мы изменяем входные данные, что не очень хорошо, если мы пытаемся мыслить в терминах чистых функций.
Сложность
- Время: O(n), мы только один раз перебираем весь массив
- Space: O(1), мы только создаем новую переменную: “изменено”, однако это не зависит от размера входных данных, следовательно, у нас постоянная сложность пространства.
Второе решение
Если вы действительно не хотите изменять входные данные, есть способы избежать этого. Одним из которых является следующее:
public boolean checkPossibility2(int[] nums) {
boolean changed = false;
int currentValue = nums[0];
for (int i = 0; i < nums.length - 1; i++) {
if (currentValue > nums[i + 1]) {
if (changed) return false;
if (i != 0 && nums[i - 1] > nums[i + 1]) {
currentValue = nums[i];
} else {
currentValue = nums[i + 1];
}
changed = true;
} else {
currentValue = nums[i + 1];
}
}
return true;
}
Идея та же, но нам нужно иметь другую переменную: “currentValue”, чтобы удерживать текущее значение на случай, если оно изменится.
Другое решение:
Вы также можете сделать то же самое, что и в подходе 1, и изменить исходный массив, но сохранить измененное значение и индекс, поэтому в конце цикла for вы заменяете исходное значение обратно. Хотя это решение, похоже, не изменяет исходный ввод, это может привести к проблемам, если у вас есть одновременный доступ к методу, поскольку в какой-то момент времени входные данные могут отличаться. Очевидно, что это не проблема для данной проблемы, но это то, что следует учитывать при работе в параллельных приложениях, и всегда полезно помнить.
Оригинал: “https://dev.to/marcelos/leetcode-665-non-decreasing-array-55kf”