Comments 51
Почему в "правильном ответе" на кдпв первый столбец пустой?
Что получится для массива стенок: 2,4,1,7,3,5?
Решить эту задачу за один проход списка не получится, но получится за два — все дело в вычислений самых верхних левой и правой стенок.Может я неправильно понял задачу, но кажется за один вполне можно. В профиль же тут получается в любом случае кривая пирамида. Т.е. можно просто идти с 2х сторон списка выбирая в каждый заход каждого направления следующую стенку, больше текущей и суммируя весь объём между ней и текущей. Если два поиска встретились — тут отбрасываем последний заход более высокой стороны (т.к. у нас с дугой стороны вытекает) и дорабатываем более низкий. В худшем случае обрабатываем список дважды (когда самые высокие это крайние стенки. В лучшем — за один проход.
Можно и за один прямой проход, но там надо хитро учитывать новые ступени. слишком муторно. Ткните, где я не прав?
Upd: Если каждый заход идти со стороны более низкого, то второй проход, вроде бы, вообще исключается.
Собственно ниже, вроде, уже привели
на сях как-то так в один проход делается.
int v[] = {1, 2, 3, 4, 6, 3, 2, 4, 7, 3, 4, 6, 1, 2, 1};
int count = 0;
for (int l=0,r=sizeof(v)/sizeof(v[0]),lM = v[0], rM = v[sizeof(v)/sizeof(v[0])];
l < r;
lM = max(lM,v[l]), rM = max(rM,v[r]))
if(lM >= rM)
count += rM - v[r--];
else
count += lM - v[l++];
3|
2| X ~ X ~ X
1| X X X X X
3| X
2| X ~ X ~ X
1| X X X X X
int trap(vector<int>& v)
{
if (empty(v)) return 0;
int c(0);
for (int l(0), r(size(v)-1), lM(v.front()), rM(v.back()); l < r; lM = max(lM, v[l]), rM = max(rM, v[r]))
c += lM < rM ? lM - v[l++] : rM - v[r--];
return c;
}
Так побыстрей будет
int trap(vector<int>& v)
{
if (empty(v)) return 0;
int c(0);
for (int l(0), r(size(v)-1), lM(v.front()), rM(v.back()); l < r;)
if (lM < rM)
{
c += lM - v[l++];
lM = max(lM, v[l]);
}
else
{
c += rM - v[r--];
rM = max(rM, v[r]);
}
return c;
}
Решить эту задачу за один проход списка не получится
Можно решить за один проход, если использовать дополнительный стэк. Но это не самое простое решение, конечно.
Также рекомендую к просмотру: https://www.youtube.com/watch?v=ftcIcn8AmSY
Что-то вроде такого
trap :: [Int] -> Int
trap = fst . foldl drain (0, []) . zip [0..]
where drain (!s, []) x = (s, [x])
drain (!s, [t@(_, ht)]) x@(_, hx) =
if ht <= hx then (s, [x]) else (s, [x, t])
drain acc@(!s, stack@((_, hb):r@((pt, ht):_))) x@(px, hx) =
case compare hx hb of
EQ -> acc
GT -> drain (s + (px - pt - 1) * min (ht - hb) (hx - hb), r) x
LT -> (s, x:stack)
func trap(height []int) int {
result, left, right := 0, 0, len(height) - 1
maxL, maxR := 0, 0
for left < right {
if height[left] < height[right] {
if height[left] > maxL {
maxL = height[left]
} else {
result += maxL - height[left]
}
left++
} else {
if height[right] > maxR {
maxR = height[right]
} else {
result += maxR - height[right]
}
right--
}
}
return result
}
Эта задача на ресурсе с задачками, где можно потестить свои реализации: leetcode.com/problems/trapping-rain-water
Можно за один проход
Нет, нельзя. Как можно говорить об одном проходе, если вы используете мутабельные массивы, которые позволяют вам обращаться к произвольному элементу по индексу в любом месте?
А где вы увидели операцию изменения массива в коде выше?
Вообще говоря, случайный доступ тут не нужен, достаточно положить вход в Data.Sequence и обращаться только к голове и хвосту.
Произвольный доступ к количеству проходов не имеет отношения. Думаю, не совру, если скажу, что под одним проходом подразумевается случай, когда каждый элемент списка читается не более одного раза.
Иначе у вас реализация не эквивалентные, вы сделали на списке (по сути — итераторе, если использовать императивную терминологию), а люди — на массиве.
Я бы тоже попробовал поиграть с реализацией задачки, но к сожалению как всегда за аналогиями потреяли лес, и я не понимаю, что требуется. Как во всех этих задачах про "Вася заходит в комнату и подмечает, что в зеркале отражается люстра, а значит..."
Было-бы очень неплохо если-бы вы указали на ограничение входных типов вначале статьи, до слов за которые я зацепился.
The name list is also used for several concrete data structures that can be used to implement abstract lists, especially linked lists and arrays.
Видимо, есть большая путаница. Вот тут, к примеру, определение односвязного списка приравнено к спискам: freecontent.manning.com/wp-content/uploads/2015/05/arrays-vs-lists.pdf
В нескольких статьях на Хабре встречал описание рядом односвязного списка и стека и недоумевал, почему существуют два названия для одного и того же.
Список в хаскелле это классический фпшный список:
data List a = Nil | Cons a (List a)Который, как видно, односвязный и совсем не основан на массиве. И контекст вроде как раз и был, что мы используем хаскел терминологию.
Можно за один проход и без стека, просто обходить массив не с одной стороны, а идти с обоих концов
Про это решение я тоже знаю, но у меня в голове "один проход" как-то плохо сочетается с random-access к входу. Ведь сначала нам нужно прочитать весь вход в массив ("первый" проход), а потом искать в нём, используя random-access ("второй" проход).
Решение, которое я предложил, считывает по одному элементу из списка и обновляет состояние алгоритма. Суммарные требования к памяти у обоих алгоритмов примерно одинаковые (может потребоваться хранить весь вход в памяти).
Но по идее это тоже 2 прохода, ведь в среднем каждый элемент мы смотрим 2 раза например
if height[left] < height[right] — true
left++
if height[left] < height[right] — false
right++
При таком порядке исполнения мы 2 раза читаем элемент height[right]. Значит потенциально это более сложно записанная версия:
for elm in height
...
for elm in reverse(height)
...Где тоже каждый элемент будет обработан два раза.
Это решение работает за экспоненту по времени и памяти. Посчитайте, сколько нужно времени для входа [4000000, 0, 4000000].
Откуда взялся log_2? Если я правильно понял идею, то оно работает за O(MAX_VALUE * n). Если брать на вход целые произвольной точности, то вполне себе https://en.wikipedia.org/wiki/Pseudo-polynomial_time.
highestLeft :: [Height] -> [Height]
highestLeft [] = []
highestLeft l = scanl1 max l
highestRight :: [Height] -> [Height]
highestRight [] = []
highestRight l = scanr1 max l
У меня получилось такое решение, вроде выдает правильный ответ и считает в один проход:
water :: [Int] -> Int
water xs = snd $ foldl' go ([], 0) xs where
go ([], result) elm = ([elm], result)
go (x:xs, result) elm = if x > elm then (x:elm:xs, result) else ([elm], result + getResult (min x elm) xs) where
getResult roof elms = sum $ (\x -> roof - x) <$> elmsМожно обойтись без промежуточного списка, если хитро аккумулировать результаты. Но немного лень извращаться. Фолд гарантирует, что мы видим все элементы ровно один раз.
Исправил ошибку, когда неправильно считался последний чанк, если правая стенка оказывалась ниже левой:
water :: [Int] -> Int
water xs = transformResult $ foldl' go ([], 0) xs where
transformResult ([], result) = result
transformResult ([_], result) = result
transformResult (x:elm:xs, result) = result + getIntermediateResult (min x elm) xs
go ([], result) elm = ([elm], result)
go (x:xs, result) elm = if x > elm then (x:elm:xs, result) else ([elm], result + getIntermediateResult (min x elm) xs)
getIntermediateResult roof elms = sum $ (\x -> roof - x) <$> elmsКак всегда хабр в последнюю секунду не даёт редактировать. Вызов функции min лишний, у нас по построению и так понятно где что:
water :: [Int] -> Int
water xs = transformResult $ foldl' go ([], 0) xs where
transformResult ([], result) = result
transformResult ([_], result) = result
transformResult (_:elm:xs, result) = result + getIntermediateResult elm xs
go ([], result) elm = ([elm], result)
go (x:xs, result) elm = if x > elm then (x:elm:xs, result) else ([elm], result + getIntermediateResult (min x elm) xs)
getIntermediateResult roof elms = sum $ (\x -> roof - x) <$> elmsСоответственно вариант без промежуточного списка с одним только состоянием:
data WaterState = Empty | NonEmpty Int Int Int deriving Show
water :: [Int] -> Int
water xs = snd $ foldl' go (Empty, 0) xs where
go :: (WaterState, Int) -> Int -> (WaterState, Int)
go (Empty, result) elm = traceShowId (NonEmpty elm elm 1, result)
go (NonEmpty x s count, result) elm = traceShowId $ if x > elm then (NonEmpty x (s + x - elm) (count + 1), result) else (NonEmpty elm elm 1, result + getResult x elm count s) where
getResult x elm count s = (if x <= elm then s else s - (x - elm) * count) - xОн не работает для стакана у которого последняя левая стенка выше правой, но в целом как мне кажется иллюстрирует идею. Тут уже гарантированно все элементы обходятся 1 раз, и промежуточных списков просто нет. Хотя по-хорошему такой код я бы писать, конечно, не рекомендовал)
Посмотрел по ссылке выше функция со списками тоже не работает для сложного случая вроде [0,1,0,2,1,0,1,3,2,1,2,1]. Думал несколько минут — как сделать в один фолд с одного конца, а не проходом с двух концов — не представляю.
Соответственно вариант без промежуточного списка с одним только состоянием
Я почти уверен, что корректного решения с такими свойствами (обработка потока с O(1) дополнительной памяти) не существует (Контр-пример может выглядеть как длинная лестница вроде [n, n-1..0] ++ [x]. Как-то нужно впихнуть в O(1) все возможные исходы для всех возможных лестниц как функцию от x).
Он не работает для стакана у которого последняя левая стенка выше правой
Какой смысл приводить решение, которое не работает в общем случае?
я сначала написал решение, а потом (уже когда вышло время на редактирование) увидел стакан на котором функция неверно считает. Так что могу только посыпать голову пеплом, но не удалить комментарий. Плюс как подход в целом, всё еще полезно. наверное.
А про решение без доп. памяти — я тоже пришел к такому же выводу.
Сколько воды утекло? Решаем задачу лунной походкой на Haskell