Сегодня я нашел очень интересный вопрос алгоритма. Ниже приведено описание его алгоритма, которое происходит из вопроса интервью в Твиттере.
Описание алгоритма луж Twitter
Сначала посмотрите на картинку
Числа на рисунке выше описаны в соответствии с содержанием массива. Наконец, высота стены будет смоделироваться в соответствии с размером каждого числа, и будет создана стена. Спросите вас, когда идет дождь, сколько воды может быть заполнена этой стеной, в 1 как подсчет.
Вот стена после заполнения воды
Прочитав приведенную выше картинку, вы чувствуете, что это весело? Действительно, давайте кратко проанализируем его внедрение алгоритма ниже.
На самом деле, этот принцип относительно прост, есть несколько ключевых моментов:
1. Определенно нет воды с левой и правой стороны
2. Высота нагрузки воды зависит от минимального значения двух максимальных значений на левой и правой сторонах себя
Давайте использовать JS для его реализации:
Кода -копия выглядит следующим образом:
/**
* Рассчитайте, сколько воды может быть установлено на стене с условиями массива в качестве высоты
* Пример массива [2,5,1,2,3,4,7,7,6,9]
**/
функция getWaterCounts (arg) {
var i = 0,
j = 0,
count = 0;
// как первые, так и последние предметы должны быть исключены
for (i = 1; i <arg.length - 1; i ++) {
var left = math.max.apply (null, arg.slice (0, i + 1));
var right = math.max.apply (null, arg.slice (i, arg.length));
var min = слева> = справа? Право: слева;
// должно преобладать максимальное значение левой и правой стороны
// Если текущее значение больше или равно этому значению, ничего не делайте
if (arg [i] <min) {
count += min - arg [i];
}
}
console.log (count);
}
getwatercounts ([2,5,1,2,3,4,7,7,6,9]); // 11
Суммировать
Хе -хе, разве реализация не очень проста? На самом деле, пока вы готовы думать, вы можете использовать JS для реализации многих забавных вещей.