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

#task_226 #решаем_задачки_дома

🎓 Существует множество задач, где необходимо быстро вычислить некоторую сумму на заданном промежутке или отрезке. Есть даже соответствующая структура данных - Range Sum Query!
💡 И сегодня мы разберем одну из таких задач: быстрый подсчет суммы чисел в заданном промежутке в матрице.

#announcement #task_227 #решаем_задачки_дома

Довольно часто необходимо оптимизировать подсчет каких то константных значений. В данной задаче мы рассматривали так называемые префиксные суммы в матрице. То есть для заданной матрицы мы подсчитываем префиксные суммы и уже их используем для быстрого (О(1) по времени) подсчета суммы произвольной подматрицы.
Полный разбор, как обычно, по ссылке ниже!

#task_227 #решаем_задачки_дома

🎓 Продолжаем задачи на поиск суммы в произвольных матрицах. Сегодня задача посложнее, необходимо определить кол-во подматриц, сумма элементов которых равна X.

P.S. Спасибо @Dream_Cat4er за присланную задачу!

#announcement #task_228 #решаем_задачки_дома

Довольно интересная задача с техникой, которую стоит знать. Задача связана с предыдущей #task_227 с префиксными суммами!

#task_228 #решаем_задачки_дома

🎓 Давненько у нас не было задач на динамическое программирование! Надеюсь, вы не забыли этот класс задач 😜

#announcement #task_229 #решаем_задачки_дома

Task #229: Кубики

Задачу можно решить с помощью двумерного динамического программирования. Пусть f(n,k) — количество пирамидок высоты k с основанием n.

Смотрим полный разбор (2 мин)

#task_229 #решаем_задачки_дома

Анонс #230. Быстрый маршрут

Одна из классических задач на поиск оптимального маршрута из точки А в точку B!

Анонс задачи (1 мин)

#announcement #task_230 #решаем_задачки_дома

Task #230. Быстрый маршрут

Задачу можно решить алгоритмом Дейкстры, но его необходимо модифицировать. Вместо расстояния до вершины i будем хранить ...

Смотрим полный разбор (2 мин)

#task_230 #решаем_задачки_дома

Анонс #231. Обрезка строки

Задача из раздела динамического программирования, дерзайте! Разбор с решением опубликуем в понедельник!

Анонс задачи (1 мин)

#announcement #task_231 #решаем_задачки_дома

Task #231. Обрезка строки

Итак воспользуемся методом динамического программирования. Пусть dl, r - наименьшее кол-во символов, которое следует удалить из подстроки s(l)...s(r)...

Смотрим полный разбор (2 мин)

#task_231 #решаем_задачки_дома

Анонс #232. Счастливый телефонный номер

Если вы не запрогаете эту задачу за 15 минут, у меня для вас плохие новости!

Анонс задачи (1 мин)

#announcement #task_232 #решаем_задачки_дома

Task #232. Счастливый телефонный номер

Даже если вы сделали задачу перебором, не все так плохо! Но задачу можно решить и за O(1)!

Смотрим полный разбор (2 мин)

#task_232 #решаем_задачки_дома

Анонс #233. Заглавные буквы

Задача с текущего контеста Leetcode!

Анонс задачи (1 мин)

#announcement #task_233 #решаем_задачки_дома

Task #233. Заглавные буквы

Обработка строк с небольшой оптимизацией!

Смотрим разбор (1 мин)

#task_233 #решаем_задачки_дома

Анонс #234. Острова

Задача по программированию с собеседования в Microsoft! Сможете решить?!

Анонс задачи (1 мин)

#announcement #task_234 #решаем_задачки_дома

Разбор #234. Острова

Один из самых простых и понятных способов решения таких задач - это алгоритм поиска в глубину. Детали смотрите в нашей статье!

Смотрите разбор (2 мин)

#task_234 #решаем_задачки_дома

Анонс #235. Индекс цитирования

Как вычислить индекс цитирования?! Попробуйте вычислить индекс Хирша!

Анонс задачи (1 мин)

#announcement #task_235 #решаем_задачки_дома

Разбор #235. Индекс цитирования

Индекс Хирша (h-index) – показатель, предложенный в 2005 г. физиком Хорхе Хиршем в качестве альтернативы классическому "индексу цитируемости", представляющему собой суммарное число ссылок на работы учёного. Критерий основан на учёте числа публикаций исследователя и числа цитирований этих публикаций.

Смотрите разбор (2 мин)

#task_235 #решаем_задачки_дома

Анонс #236. Ближайшее значение в двоичном дереве поиска

Последняя задачка уходящего лета! Уже совсем скоро мы откроем новый сезон задач!

Анонс задачи (1 мин)

#announcement #task_236 #решаем_задачки_дома