ну не, ты ж рассуждаешь и приходишь к оптимальному решению. вот если ты начинаешь писать брутфорс и говоришь «лучше решить не можно!»

Согласен

Категоричным вообще лучше не быть)

Да, совсем чуть чуть

мне кажется если линию оттуда убрать, которая растёт как конь, и сделать интервал побольше, то разница будет виднее на другом масштабе

ну не, ты ж рассуждаешь и приходишь к оптимальному решению. вот если ты начинаешь писать брутфорс и говоришь «лучше решить не можно!»

"Так, увожаемый интервьюер, ну мы то все прекрасно понимаем, что при первой проблеме мы все пойдем на стак оверфлоу, так что давайте я вам продемострирую как эфективно найти решение данной задачи в глобальной сети Интернет"

"Так, увожаемый интервьюер, ну мы то все прекрасно понимаем, что при первой проблеме мы все пойдем на стак оверфлоу, так что давайте я вам продемострирую как эфективно найти решение данной задачи в глобальной сети Интернет"

ага, именно поэтому стековерфлоу полон заминусованных вопросов где чувак вываливает кусок лапши, не говорит в чем проблема, какую задачу решает, а просто пишет «народ, хз чё делаю, хз чего хочу добиться, решите за меня мою проблему, плз»

😂

мне кажется если линию оттуда убрать, которая растёт как конь, и сделать интервал побольше, то разница будет виднее на другом масштабе

что такое x^(1/10), мы ж про квадратный корень вроде говорили, не? т.е. x^(1/2)

что такое x^(1/10), мы ж про квадратный корень вроде говорили, не? т.е. x^(1/2)

Ну да, уже при 10 000 (что вполне реально) разница в 5 раз

Ну да, уже при 10 000 (что вполне реально) разница в 5 раз

Не много так то, но и не мало, чтобы сказать что они индентичны

кстати, https://github.com/jdneo/vscode-leetcode

Не много так то, но и не мало, чтобы сказать что они индентичны

Возрастают примерно одинаково, очень близки графики

кстати, https://github.com/jdneo/vscode-leetcode

Ого, интересно

кстати, https://github.com/jdneo/vscode-leetcode

🔥

Happy Monday! 👋 На этой неделе ищем поддеревья — https://bit.ly/3bJPDKy Рассказываю про сериализацию, подробнее про сложение строк (спойлер: это не O(1)) и рекурсивный вариант решения. PS. У канала есть чат, если хочется обсудить прочитанное и не только (работает кнопка "discuss").

Сегодняшняя задача классная. 1:45 решал дпшечку эту, потом посмотрел в решения — брутфорс по всем возможным квадратам проходит 😂

Я не догадался глянуть в ограничения.

Ну ладно, всё равно дпшечку надо разобрать, а то неинтересно.

Сперва по неверному пути пошёл и потерял час пока отлаживал разные тесткейсы, потом забил и стал подбирать другую формулу перехода.

Сегодняшняя задача классная. 1:45 решал дпшечку эту, потом посмотрел в решения — брутфорс по всем возможным квадратам проходит 😂

А на каком языке? Вчера у меня не прошёл перебор

А на каком языке? Вчера у меня не прошёл перебор

Я не пробовал, в этом и прикол. Ещё смотря какой перебор же. Автор решения предлагает брать единичку и перебирать все возможные квадраты с левым верхним углом в этой единичке.

Я просто сразу подумал, что под конец челенджа не может быть медумной задачи с перебором.

И стал думать в сторону дп.

Интересно, что вчера вечером сам начинал разбирать сегодняшнюю задачу. И сегодня она выпала

Хотя там есть серьёзная загвоздка. Это не совсем брутфорс.

Ладно. Тогда я зря повёлся на «брутфорс» в заголовке.

Какая ж в нём степень будет... n^4?

ну вот есть прикол, который позволяет зная два угла квадрата за O(1) сказать квадрат это или нет

Для каждой клетки квадрат

в смысле все ли там единицы или нет

в смысле все ли там единицы или нет

По диагонали смотреть? На меньший квадрат?

От правого нижнего угла

хм. да чё-то нет — я хотел предложить смотреть на дифы префиксных сумм, если там нолик встречался, то сумма прерывается и поэтому дифы будут отличаться, но я сейчас читаю его решение и там реально n^4

¯\_(ツ)_/¯

т.е. прямо натурально разбегаться двумя указателями по всем квадратам для каждой единички.

(n*m)^2 получится

На Го брутфорс тоже прошёл, подтверждаю :)

ктстаи, недавно я стал читать разборы задач от этого чувака. иногда попадаются интересные идеи https://github.com/azl397985856/leetcode/blob/master/problems/221.maximal-square.md

(читаю через хром-переводчик)

Через переводчик с китайского, хорооош 👍

ктстаи, недавно я стал читать разборы задач от этого чувака. иногда попадаются интересные идеи https://github.com/azl397985856/leetcode/blob/master/problems/221.maximal-square.md

怎么好，我明白这样的内容

иногда мне кажется, что литкод — это китайская платформа

иногда мне кажется, что литкод — это китайская платформа

Но скорее всего алгоритмы гугла КОТОРЫЕ НЕ СЛЕДЯТЬ, ЧЕГО ЭТО ВЫ, ступили и подумали что мне нужен китайский...

Сервера вроде в Штатах

Есть ещё форк вот такой leetcode-cn.com

Это же не форк, это их китайская морда

Это же не форк, это их китайская морда

🔥

Есть ещё форк вот такой leetcode-cn.com

Сайт, одобренный ком партией

Запрещены переменные с названиями “Capitalism”, “ChinaFault”, “WinnieThePoo” и “Mao”

Запрещены переменные с названиями “Capitalism”, “ChinaFault”, “WinnieThePoo” и “Mao”

Кстати, вот вам смешно, но в WeeChat реально нельзя сделать названия чата MaoZeDong

Никто и не смеётся. Это было смешно в 2008 году, а в 2020 уже страшно.

Понравилась задача сегодня. Подумать заставляет. С третьей попытки прошла тесты.

https://leetcode.com/problems/maximal-square/discuss/600018/C-O(m*n)-DP-solution-beats-95-runtime

Понравилась задача сегодня. Подумать заставляет. С третьей попытки прошла тесты.

💪

Товарыщи

Кто нибудь решал задачку (уже вчерашнюю) быстрее чем за N*M

?

Я — нет. Остановился на варианте с ДП, с которым 1,5 часа мучился.

Я — нет. Остановился на варианте с ДП, с которым 1,5 часа мучился.

Ого, значит задачка не такая легкая как мне сначала показалось

Я предыдущую вообще не решил…

Пришлось скопировать и разбирать

Ну хз, для кого как, конечно. Ну я вот сперва по не правильному пути пошёл и час там сидел, пока не сделал шаг назад и вывел нормальную формулу перехода для дпшечки.

Ну хз, для кого как, конечно. Ну я вот сперва по не правильному пути пошёл и час там сидел, пока не сделал шаг назад и вывел нормальную формулу перехода для дпшечки.

В предыдущей или этой?

В этой.

Щас я попробую реализовать одну мою идею в этой

Кажется, задача сегодня это почти LRU 🙂 По крайней мере, я по той же схеме решал.

Кстати, похоже ещё одна новая задачка.

Даже в индекс гугла ещё не прососался.

да, похожая. но на мой взгляд эта была проще

ага. тут ничего не надо перекладывать.

удалил и забыл.

в общем, эта техника с хранением указателей в мапе теперь надолго мне запомнится 😄

а ты хранил указатели? у меня опять получилось пройти с первым же интуитивным решением )

ну да, как и в задаче с LRU. я завожу связный список куда кладу элементы. итераторы кладу в мапу, чтобы потом по ключу (элементу) достать этот итератор и за O(1) удалить его из списка.

Мы уже обсуждали здесь, что иначе придётся искать элемент в списке каждый раз обходя его с головы, и это как бы не то зачем списки нужны.

а ты хранил указатели? у меня опять получилось пройти с первым же интуитивным решением )

интуитивное это как? каждый раз бегать по списку и вычищать из него повторяющиеся элементы? 🤔

не совсем. у меня хранится индекс со значениями и ссылка на первый уникальний элемент. при каждом добавлении я заново ищу следующий уникальный элемент, начиная с текущего