Ура! 10- ая юбилейная воскресная задачка, закрепляем two pointers на средней задаче, она очень похожа на предыдущую https://t.me/python_simple/112:
10. Remove Duplicates from Sorted Array II (средняя)
leetcode.com/problems/remove-duplicates-from-sorted-array-ii

На вход подается целочисленный массив nums, отсортированный в неубывающем порядке, удалите дубликаты, так, чтобы каждое число повторялось не более 2-х раз. Порядок элементов должен быть сохранен.
Возвратите k после размещения окончательного результата в первых k слотах nums.
Нельзя использовать доп массив для размещения в нем результата.

Пример 1:
Input: nums = [1,1,1,2,2,3]
Output: 5
При этом nums = [1,1,2,2,3,_], но последние элементы не должны быть именно «_», они могут быть чем угодно, их можно не трогать

Пример 2:
Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7
При этом nums = [0,0,1,1,2,3,3,_,_]

def removeDuplicates(nums):
«Ваше решение»

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

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

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

Воскресная задачка. Сегодня не будем ещё начинать новый паттерн литкод задач. Закрепим то, что уже знаем ещё одной задачкой из топ 300 задач)
11. Replace Elements with Greatest Element on Right Side (легкая)
leetcode.com/problems/replace-elements-with-greatest-element-on-right-side

Получаем массив arr, замените каждый элемент в этом массиве самым большим элементом среди элементов справа от него, а последний элемент замените на -1.
После этого верните массив.

Пример 1:
Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]

Пример 2:
Input: arr = [400]
Output: [-1]

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

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

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

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

Воскресная задачка.
12. Best Time to Buy and Sell Stock (легкая)
leetcode.com/problems/best-time-to-buy-and-sell-stock

На вход приходит prices, где prices[i] — цена данной акции на i-й день.
Необходимо максимизировать свою прибыль, выбрав один день для покупки одной акции и другой день в будущем для продажи этой акции.
Верните максимальную прибыль, которую вы можете получить от этой сделки. Если вы не можете получить никакой прибыли, верните 0.

Пример 1:
Input: prices = [7,1,5,3,6,4]
Output: 5

Пример 2:
Input: prices = [7,6,4,3,1]
Output: 0

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

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

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

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

На этой неделе хотел разобрать сложную задачу, но думаю, что как подготовка, надо ещё решить среднюю, она как и предыдущая на 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