Как я могу подсчитать, сколько горизонтальных мазков требуется, чтобы нарисовать массив зданий?
Учитывая массив целых чисел, каждый элемент представляет собой здание. Например: int buildings[] = {1, 4, 3, 2, 3, 1}.
Если бы я нарисовал здания горизонтально кистью, сколько ударов кистью я бы использовал?
Я должен написать функцию, которая возвращает количество этих мазков кистью. Например 5.
Я могу легко сделать это во время выполнения O(n^2), используя 2 цикла.
Внешний контур проходит по уровням каждого здания (по самому высокому зданию).
Внутренний цикл работает с массивом от
0доnи сравнивает разницу высот (0или1) между двумя соседними элементами.
Как я могу сделать это в O(n) времени и O(n) пространстве?
Ответы 4
Мазок кисти начинается всякий раз, когда высота увеличивается слева направо, и заканчивается, когда она уменьшается. Вам нужно только смотреть, когда он увеличивается, потому что, если вы просто посчитаете начальные точки каждого штриха, у вас будет счет хода. Вместо того, чтобы перебирать уровни высоты во внутреннем цикле, просто вычтите один уровень высоты из предыдущего, чтобы получить разницу.
В псевдокоде:
int BrushCount(int[] buildings)
{
int brushCount = 0;
int prevHeight = 0;
for(int i = 0; i < buildings.length; i++)
{
if (buildings[i] > prevHeight)
brushCount = brushCount + (buildings[i] - prevHeight);
prevHeight = buildings[i];
}
return brushCount;
}
Работает за O(n).
Обновление prevHeight должно происходить безоговорочно, иначе алгоритм будет некорректным, когда вам потребуется несколько мазков кисти на одной высоте.
При подсчете с конца массива в качестве начального значения результата используется последний элемент, а предыдущий элемент сравнивается с текущим.
Если они равны, то результат увеличивается на единицу; если предыдущий меньше текущего, ничего не делать; если предыдущий больше текущего, тогда результат = результат + предыдущий-текущий
int i=sizeof buildings;
int t=buildings[i];
while(i>0){
if (buildings[i-1]-buildings[i]>0) t+=(buildings[i-1]-buildings[i]);
else if (buildings[i-1]-buildings[i]==0) ++t;
--i;
}
return t;
Немного кода гольфа :) (На основе отличного объяснение самгака.)
const f = A => A.reduce((a,b,i,A) => a + Math.max(0, b - A[i-1]));
console.info(f([1, 4, 3, 2, 3, 1]))
console.info(f([4, 1, 2, 1, 2, 2]))@ Нил, что делает мою не «настоящей»?
Код-гольф заключается в том, чтобы сделать код максимально коротким. Это забавная игра, но ее никогда не следует использовать в коде, написанном для вашего работодателя.
@ Нил, это только в том случае, если ты планируешь выиграть раунд. Поддерживаю свою строчку является кода гольфа, пусть и не самую короткую.
public static int brushCount(int[] buildings)
{
int count=0;
for(int i=0; i<=buildings.length-1; i++){
if ((i+1)<(buildings.length)){
if (buildings[i]>buildings[i+1]){
count += buildings[i]-buildings[i+1];
}
}else{
count += buildings[i];
}
}
return count;
}
Просто небольшая придирка - ваш псевдокод не подходит для двух примеров OP. Можете ли вы сказать, почему?