На этой неделе хотел разобрать сложную задачу, но думаю, что как подготовка, надо ещё решить среднюю, она как и предыдущая на two pointers и на последовательность значений на графике, но сложнее, хотя если вы решали предыдущие задачи, то она может показаться лёгкой)
13. Container With Most Water (средняя)
Условие - https://telegra.ph/13-Container-With-Most-Water-srednyaya-08-06
Литкод - leetcode.com/problems/container-with-most-water

Ваша задача решить эту задачу на литкоде и успешно засабмитить

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

Список всех задач
#ps_leetcode

Воскресная задача:
Многие компании в качестве средней задачи, но как правило она идет уже как тяжелая, любят давать задачу на интервалы. Тут могут быть вариации, например даны интервалы, найти пересечения или промежутки.
Также эта задача была в контесте для поступления в школу от озона route256. Причем там эта задача была не самой сложной, где-то выше середины в списке, но если ты решал её и все задачи, которые полегче, то этого было достаточно, чтобы набрать проходной балл. Я встречал эту задачу в ВК и Озоне. Но знаю, что и другие компании любят давать подобные задачи.
14. Merge Intervals (средняя)
leetcode.com/problems/merge-intervals/description
Дан массив интервалов , где intervals[i] = [starti, endi], объедините все пересекающиеся интервалы и верните их.

Пример 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Пример 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]

class Solution:
def merge(self, resp_intervals: List[List[int]]) -> List[List[int]]:
«Ваше решение»


Ваша задача решить эту задачу на литкоде и успешно засабмитить

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

Список всех задач
#ps_leetcode

Воскресная задача:
15. Contains Duplicate II (легкая)
leetcode.com/problems/contains-duplicate-ii
Для массива целых чисел nums и целое число k, необходимо вернуть true, если в массиве есть два различных индекса i и j, таких что nums[i] == nums[j] и abs(i - j) <= k.

Пример 1:
Input: nums = [1,2,3,1], k = 3
Output: true

Пример 2:
Input: nums = [1,0,1,1], k = 1
Output: true

Пример 3:
Input: nums = [1,2,3,1,2,3], k = 2
Output: false

class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
«Ваше решение»


Ваша задача решить эту задачу на литкоде и успешно засабмитить

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

Список всех задач
#ps_leetcode

Приступаем к деревьям
16. Invert Binary Tree (легкая)

https://telegra.ph/Invert-Binary-Tree-legkaya-09-03

leetcode.com/problems/invert-binary-tree

Ваша задача решить эту задачу на литкоде и успешно засабмитить

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

Список всех задач
#ps_leetcode

Всем привет, сегодня воскресенье, и мы продолжаем разбирать задачи с литкода.
В предыдущей задаче мы немного разобрались, как ходить по узлам дерева, в этой надо будет пройтись сразу по 2-м бинарным деревьям и сравнить их.
17. Same Tree (легкая)
https://telegra.ph/Same-Tree-09-10

leetcode.com/problems/same-tree

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
«Ваше решение»

Ваша задача решить эту задачу на литкоде и успешно засабмитить

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

Список всех задач
#ps_leetcode

Возвращаемся к задачкам по воскресеньям, и продолжаем решать задачи на деревья
18. Subtree of Another Tree (легкая)
leetcode.com/problems/subtree-of-another-tree

Получаем корни двух двоичных деревьев root и subRoot, верните true, если существует поддерево с той же структурой и значениями узлов subRoot, и false в противном случае. Поддерево двоичного дерева — это дерево, состоящее из узла дерева и всех его потомков. Дерево также можно рассматривать как поддерево самого себя.

Примеры смотрите по ссылке leetcode.com/problems/subtree-of-another-tree

Ваша задача решить эту задачу на литкоде и успешно засабмитить

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

Список всех задач
#ps_leetcode

Псс, всем привет, воскресная задачка:
Сегодня будет задача, которую я недавно получил на собеседовании и она мне показалась интересной, решил поделиться.
Задача:
Имеется сортированный массив, в котором сделали сдвиг, на сколько сделали сдвиг, нам не известно. Также на вход подается число, надо определить, есть ли это число в этом массиве и вернуть его индекс, если этого числа нет в массиве, то вернуть -1.
Примеры:
get_idx([10, 44, 1, 3, 5, 7, 8], 5) -> 4
get_idx([10, 1, 3, 5, 7, 8], 6) -> -1
Upd:
19. Search in Rotated Sorted Array (средняя)
Задача оказалась на литкоде leetcode.com/problems/search-in-rotated-sorted-array/description

Список всех задач
#ps_leetcode

Воскресная задача по недавним собесам.
20. Squares of a Sorted Array (легкая)
leetcode.com/problems/squares-of-a-sorted-array

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

Пример 1:
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Пример 2:
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Ваша задача решить эту задачу на литкоде и успешно засабмитить

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

Список всех задач
#ps_leetcode

Воскресная задача, вернемся к деревьям.
22. Maximum Depth of Binary Tree (легкая)
leetcode.com/problems/maximum-depth-of-binary-tree

Получаем корень двоичного дерева. Надо найти максимальную глубину.

Примеры посмотрите на странице задачи leetcode.com/problems/maximum-depth-of-binary-tree

Ваша задача решить эту задачу на литкоде и успешно засабмитить

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

Список всех задач
#ps_leetcode

Воскресная задача, ну что, давайте проверим дерево на симметричность, повышаем сложность).
23. Symmetric Tree (легкая)
leetcode.com/problems/symmetric-tree

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

Примеры посмотрите на странице задачи leetcode.com/problems/maximum-depth-of-binary-tree

Ваша задача решить эту задачу на литкоде и успешно засабмитить

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

Список всех задач
#ps_leetcode

Всем привет. Возвращаемся к задачам по воскресеньям)
В чате https://t.me/+ChK7imUAJDlhN2Y6 за это время было предложено 3 задачи, предлагаю их разобрать всем)
24. Range Sum of BST (легкая)
На вход подается корень дерева, и минимальное и максимальное значения диапазона. Необходимо пройтись по дереву и сложить все значения из этого диапазона. Картинку можно посмотреть по ссылке
https://leetcode.com/problems/range-sum-of-bst/description/

Ваша задача решить эту задачу на литкоде и успешно засабмитить

В комментариях можно обсуждать и задавать вопросы)

Список всех задач
#ps_leetcode

Всем привет! (К обсуждению прошлой задачи можно тоже подключиться)
Ещё одна задача, которая встречалась в чате.
25. Assign Cookies (легкая)
Вы потрясающий родитель и хотите раздать своим детям по печенью, каждому можно дать не более одного печенья.
У каждого ребенка есть пожелание в размере печенья и все размеры разного размера.
Вам дается 2 списка, в первом - так называемый коэффициент жадности, то есть какой вес должен быть у печанья для i-го ребенка. Во втором списке содержится вес каждого печенья.
Вам надо вывести, сколько детей смогут получить печенье необходимого размера (печенье может весить больше, чем желает ребенок, но не меньше)
Условие на литкоде - https://leetcode.com/problems/assign-cookies/description/

Ваша задача решить эту задачу на литкоде и успешно засабмитить

В комментариях можно обсуждать и задавать вопросы)

Список всех задач
#ps_leetcode

Всем привет!
Возвращаемся к тренировкам с алгоритмами и структурами данных на leetcode
25. 797. All Paths From Source to Target
Нам на вход подается направленный ациклический граф ( в виде списка смежности) из n узлов, наша задача найти все возможные пути от узла 0 до узла n-1 и вывести их в любом порядке.

Граф задан с помощью списка смежности, это значит что graph[i] - это список всех узлов, которые можно посетить из узла i (т.е. существует направленное ребро из узла i в узел graph[i][j]

Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]

Ваша задача решить эту задачу на литкоде и успешно засабмитить

В комментариях можно обсуждать и задавать вопросы)

P.S. Ссылка на задачу в названии, если на знакомы с графами в Грокаем Алгоритмы очень хороший разбор

Список всех задач
#ps_leetcode

Всем привет!
На эту неделю у нас будет задача попроще
2315. Count Asterisks (easy)
Вам дана строка s, в которой каждые две последовательные вертикальные полоски '|' объединены в пару. Другими словами, 1-я и 2-я '|' составляют пару, 3-я и 4-я '|' составляют пару, и так далее.

Верните количество '*' в s, исключая '*' между каждой парой '|'.

Обратите внимание, что каждый '|' будет принадлежать ровно одной паре

Input: s = "l|*e*et|c**o|*de|"
Output: 2
В данном примере поситаются только звездочки между c**o

Условия задачи
https://leetcode.com/problems/count-asterisks/description/

Ваша задача решить эту задачу на литкоде и успешно засабмитить

В комментариях можно обсуждать и задавать вопросы)


Список всех задач
#ps_leetcode

Всех поздравляю с началом новой недели!
Сегодня у нас будет хрестоматийная задачака на DP (динамическое программирование)
118. Pascal's Triangle
Нам на вход поступает число, которое характеризует количество строк Треугольника Паскаля, которые нам надо вывести
В треугольнике Паскаля каждое число равно сумме двух чисел, расположенных непосредственно над ним (чтобы лучше понять посмотрите гифку на самой странице с задачей, она и натолкнет Вас на рекуретную формулу)

https://leetcode.com/problems/pascals-triangle/description/

Ваша задача решить эту задачу на литкоде и успешно засабмитить

В комментариях можно обсуждать и задавать вопросы)


Список всех задач
#ps_leetcode

Доброго дня!
Задача на эту неделю 463. Island Perimeter (easy)
Вам дана матрица row x col, представляющая карту, где grid[i][j] = 1 обозначает сушу, а grid[i][j] = 0 - воду.
Ячейки матрицы соединены по горизонтали/вертикали (не по диагонали). Сетка полностью окружена водой, и в ней есть ровно один остров (то есть одна или несколько соединенных клеток суши).
На острове нет "озер", то есть вода внутри острова не связана с водой вокруг него. Одна клетка - квадрат со стороной длиной 1. Сетка прямоугольная, ширина и высота не превышают 100. Определите периметр острова


Условия задачи
https://leetcode.com/problems/island-perimeter/description/

Ваша задача решить эту задачу на литкоде и успешно засабмитить

В комментариях можно обсуждать и задавать вопросы)


Список всех задач
#ps_leetcode