Последние посты
Golang | LeetCode
22 сент., 16:11
Задача: 1064. Fixed Point Сложность: mediumДан массив различных целых чисел arr, отсортированный в порядке возрастания. Верните наименьший индекс i, который удовлетворяет условию arr[i] == i. Если такого индекса нет, верните -1.Пример: Input: arr = [-10,-5,0,3,7] Output: 3 Explanation: For the given array, arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3, thus the output is 3.👨💻 Алгоритм:1⃣Инициализируйте значение left как 0, right как N - 1 и answer как -1.2⃣Пока размер области поиска не равен нулю, то есть left <= right, выполните следующие шаги: найдите mid как mid = (left + right) / 2. Сравните arr[mid] и mid: если arr[mid] = mid, сохраните mid в answer и перейдите в левую часть, изменив right на mid - 1; если arr[mid] < mid, перейдите в правую часть, изменив left на mid + 1; если arr[mid] > mid, перейдите в левую часть, изменив right на mid - 1.3⃣Верните answer.😎 РGolang | LeetCode
22 сент., 09:06
Задача: 1413. Minimum Value to Get Positive Step by Step Sum Сложность: easyДан массив целых чисел nums, вы начинаете с начального положительного значения startValue.На каждой итерации вы вычисляете поэтапную сумму startValue плюс элементы из nums (слева направо).Верните минимальное положительное значение startValue, такое что поэтапная сумма никогда не будет меньше 1.Пример: Input: nums = [-3,2,-3,4,2] Output: 5 Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1. step by step sum startValue = 4 | startValue = 5 | nums (4 -3 ) = 1 | (5 -3 ) = 2 | -3 (1 +2 ) = 3 | (2 +2 ) = 4 | 2 (3 -3 ) = 0 | (4 -3 ) = 1 | -3 (0 +4 ) = 4 | (1 +4 ) = 5 | 4 (4 +2 ) = 6 | (5 +2 ) = 7 | 2Golang | LeetCode
22 сент., 07:00
🔴AI кодинг интервью с разработчиком из международного FinTech в четверг в 19:00ДА! Вайбкодинг реально начали проверять на интервью, поэтому мы нашли собеседующего, который проводит AI-секцию в международном финтехе, чтобы вы увидели что на ней спрашивают и как к ней подготовитьсяКак это будет: 📂 Александр Дмитриев, разработчик из известного международного финтеха, ex-VK, ex-Ozon проведет вайбкодинг секцию разработчику-добровольцу 📂 Александр будет задавать реальные вопросы с секций, которые проводил сам и комментировать ответы 📂 В конце можно будет задать любой вопрос АлександруЭто бесплатно. Эфир проходит в рамках менторской программы от ШОРТКАТ для разработчиков, которые хотят сменить работу, повысить свой грейд, ЗП и прокачать скиллы.Переходи
Golang | LeetCode
21 сент., 16:11
Задача: 231. Power of Two Сложность: easyДано целое число n, верните true, если оно является степенью двойки. В противном случае верните false.Целое число n является степенью двойки, если существует целое число x, такое что n == 2^x.Пример: Input: n = 1 Output: true Explanation: 2^0 = 1👨💻 Алгоритм:1⃣Проверка на ноль: Если n равно нулю, верните false, так как ноль не является степенью двойки.2⃣Преобразование к длинному типу: Преобразуйте n к типу long, чтобы избежать переполнения при выполнении побитовых операций.3⃣Побитовая проверка: Используйте побитовую операцию, чтобы проверить, является ли число степенью двойки. Число является степенью двойки, если результат выражения (x & (-x)) равен x.Golang | LeetCode
21 сент., 09:06
Задача: 441. Arranging Coins Сложность: easyУ вас есть n монет, и вы хотите построить лестницу из этих монет. Лестница состоит из k рядов, где i-й ряд содержит ровно i монет. Последний ряд лестницы может быть неполным.Дано целое число n, верните количество полных рядов лестницы, которые вы сможете построить.Пример: Input: n = 5 Output: 2 Explanation: Because the 3rd row is incomplete, we return 2.👨💻 Алгоритм:1⃣Если мы глубже посмотрим на формулу задачи, мы можем решить её с помощью математики, без использования итераций.2⃣Напомним, что условие задачи можно выразить следующим образом: k(k + 1) ≤ 2N.3⃣Это можно решить методом выделения полного квадрата, (k + 1/2)² - 1/4 ≤ 2N. Что приводит к следующему ответу: k = [sqrt(2N + 1/4) - 1/2].
Golang | LeetCode
20 сент., 16:11
Задача: 647. Palindromic Substrings Сложность: mediumРеализуйте структуру данных MapSum, поддерживающую:- Insert(key string, val int) — вставляет или обновляет значение по ключу. - Sum(prefix string) — возвращает сумму значений всех ключей, начинающихся с указанного префикса.Пример: mapSum := Constructor() mapSum.Insert("apple", 3) mapSum.Sum("ap") // 3 mapSum.Insert("app", 2) mapSum.Sum("ap") // 5 (3 + 2)👨💻 Алгоритм:1⃣Хранение данных Используем map[string]int для хранения всех ключей и их значений.Golang | LeetCode
20 сент., 09:06
Задача: 315. Count of Smaller Numbers After Self Сложность: hardДан целочисленный массив nums, верните целочисленный массив counts, где counts[i] - это количество элементов справа от nums[i], которые меньше nums[i].Пример: Input: nums = [5,2,6,1] Output: [2,1,1,0] Explanation: To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.👨💻 Алгоритм:1⃣Реализуйте дерево отрезков (segment tree). Поскольку дерево инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4.2⃣Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия: Смещайте число на num + offset.Golang | LeetCode
19 сент., 16:11
Задача: 283. Move Zeroes Сложность: easyДан целочисленный массив nums. Переместите все нули в конец массива, сохраняя относительный порядок ненулевых элементов.Обратите внимание, что вы должны сделать это на месте, не создавая копию массива.Пример: Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0]👨💻 Алгоритм:1⃣Инициализация указателей: Инициализируйте два указателя: lastNonZeroFoundAt для отслеживания позиции последнего ненулевого элемента и cur для итерации по массиву.2⃣Итерация и обмен элементами: Итерируйтесь по массиву с помощью указателя cur. Если текущий элемент ненулевой, поменяйте его местами с элементом, на который указывает lastNonZeroFoundAt, и продвиньте указатель lastNonZeroFoundAt.Golang | LeetCode
19 сент., 09:06
Задача: №28. Find the Index of the First Occurrence in a String Сложность: easyУчитывая две строки, needle и haystack, верните индекс первого вхождения needle в haystack, или -1, если needle не является частью haystack.Пример: Input: haystack = "sadbutsad", needle = "sad" Output: 0👨💻 Алгоритм:1⃣Обработка граничного случая: - Если needle — пустая строка, вернуть 0 (по определению).2⃣Итерация по возможным позициям: - Проходим по всем индексам i от 0 до len(haystack) - len(needle), - На каждой итерации сравниваем срез haystack[i:i+len(needle)] с needle.3⃣Проверка совпадений: - Если подстроки совпали — возвращаем текущий индекс i.Golang | LeetCode
18 сент., 16:11
Задача: 943. Find the Shortest Superstring Сложность: hardУчитывая массив строк words, верните наименьшую строку, которая содержит каждую строку в words в качестве подстроки. Если существует несколько допустимых строк наименьшей длины, верните любую из них. Вы можете предположить, что ни одна строка в words не является подстрокой другой строки в words.Пример: Input: words = ["alex","loves","leetcode"] Output: "alexlovesleetcode"👨💻 Алгоритм:1⃣Реализовать функцию overlap для вычисления максимального перекрытия двух строк, где одна строка заканчивается, а другая начинается.2⃣Реализовать функцию merge для объединения двух строк с максимальным перекрытием. Использовать жадный алгоритм для нахождения двух строк с максимальным перекрытием и объединить их, повторяя до тех пор, пока не останется одна строка.3⃣Вернуть результат.😎 Решение: package mainGolang | LeetCode
16 сент., 16:11
Задача: 164. Maximum Gap Сложность: mediumДан массив целых чисел nums. Верните максимальную разницу между двумя последовательными элементами в его отсортированной форме. Если массив содержит менее двух элементов, верните 0.Необходимо написать алгоритм, который работает за линейное время и использует линейное дополнительное пространство.Пример: Input: nums = [3,6,9,1] Output: 3 Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.👨💻 Алгоритм:1⃣Инициализация: Определите минимальное и максимальное значения в массиве для расчета возможного максимального интервала (разрыва) между элементами в идеально распределенном массиве. Вычислите размер ведра (bucket size), необходимый для размещения всех элементов массива так, чтобы если массив был равномерно распределен, каждый ведер должен содержать хотя бы один элемент. Размер ведраGolang | LeetCode
16 сент., 09:06
Задача: 999. Available Captures for Rook Сложность: easyВам дана матрица 8 x 8, изображающая шахматную доску. На ней есть ровно одна белая ладья, представленная символом "R", некоторое количество белых слонов "B" и некоторое количество черных пешек "p". Пустые клетки обозначаются символом '.'. Ладья может перемещаться на любое количество клеток по горизонтали или вертикали (вверх, вниз, влево, вправо), пока не достигнет другой фигуры или края доски. Ладья атакует пешку, если она может переместиться на ее клетку за один ход. Примечание: Ладья не может перемещаться через другие фигуры, такие как слоны или пешки. Это означает, что ладья не может атаковать пешку, если путь ей преграждает другая фигура. Верните количество пешек, которые атакует белая ладья.Пример: Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".","."Golang | LeetCode
15 сент., 16:11
Задача: 1230. Toss Strange Coins Сложность: mediumУ вас есть несколько монет. Вероятность выпадения орла для i-й монеты равна prob[i].Верните вероятность того, что количество монет, на которых выпал орел, равно target, если вы подбросите каждую монету ровно один раз.Пример: Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0 Output: 0.03125👨💻 Алгоритм:1⃣Инициализация: Создайте переменную n и инициализируйте её размером массива prob. Создайте 2D массив dp размером n + 1 строк и target + 1 столбцов, где dp[i][j] хранит вероятность получить j орлов, используя первые i монет. Установите базовый случай dp[0][0] = 1.2⃣Итерация: Используйте два вложенных цикла для заполнения массива dp.Golang | LeetCode
15 сент., 09:06
Задача: 287. Find the Duplicate Number Сложность: mediumДан массив целых чисел nums, содержащий n + 1 целых чисел, где каждое число находится в диапазоне [1, n] включительно. В массиве есть только одно повторяющееся число, верните это повторяющееся число. Вы должны решить задачу, не изменяя массив nums и используя только постоянное дополнительное пространство.Пример: Input: nums = [1,3,4,2,2] Output: 2👨💻 Алгоритм:1⃣Определение дубликата: Итерируйте по массиву, оценивая каждый элемент (назовем его cur). Используйте абсолютное значение текущего элемента, чтобы получить индекс. Если элемент по индексу cur отрицательный, значит, мы уже встречали этот элемент ранее, и cur является дубликатом. Сохраните cur как дубликат и выйдите из цикла. Если элемент по индексу cur положительный, инвертируйте знак этого элемента, чтобы пометить его как встреченный, и перейдите к следующемуGolang | LeetCode
14 сент., 16:11
Задача: 1361. Validate Binary Tree Nodes Сложность: easyУ вас есть n узлов бинарного дерева, пронумерованных от 0 до n-1, где узел i имеет двух детей: leftChild[i] и rightChild[i]. Верните true, если и только если все заданные узлы образуют ровно одно допустимое бинарное дерево.Если у узла i нет левого ребенка, то leftChild[i] будет равен -1, аналогично для правого ребенка.Обратите внимание, что узлы не имеют значений и мы используем только номера узлов в этой задаче.Пример: Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1] Output: true👨💻 Алгоритм:1⃣Проверка количества родителей для каждого узла: Создайте массив для отслеживания количества родителей для каждого узла. Проходите через leftChild и rightChild, увеличивая счетчик для каждого ребенка. Если какой-либо узел имеет более одного родителя, возвращайте false.2⃣Поиск корневого узла и проверка наGolang | LeetCode
11 сент., 16:11
Задача: 528. Random Pick with Weight Сложность: mediumВам дан массив положительных целых чисел w, где w[i] описывает вес индекса i. Вам нужно реализовать функцию pickIndex(), которая случайным образом выбирает индекс в диапазоне [0, w.length - 1] (включительно) и возвращает его. Вероятность выбора индекса i равна w[i] / sum(w).Например, если w = [1, 3], вероятность выбора индекса 0 составляет 1 / (1 + 3) = 0.25 (т.е. 25%), а вероятность выбора индекса 1 составляет 3 / (1 + 3) = 0.75 (т.е. 75%).Пример: Input ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] [[[1,3]],[],[],[],[],[]] Output [null,1,1,1,1,0]Explanation Solution solution = new Solution([1, 3]); solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4. solution.pickIndex(); // return 1 solution.pickIndex(); // return 1Golang | LeetCode
11 сент., 09:06
Задача: 1046. Last Stone Weight Сложность: easyВам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два самых тяжелых камня и разбиваем их вместе. Предположим, что два самых тяжелых камня имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y имеет новый вес y - x. В конце игры остается не более одного камня. Верните вес последнего оставшегося камня. Если камней не осталось, верните 0.Пример: Input: stones = [2,7,4,1,8,1] Output: 1👨💻 Алгоритм:1⃣Создай максимальную кучу из массива камней.2⃣Извлекай два самых тяжелых камня, разбивай их, и, если необходимо, возвращай оставшийся камень обратно в кучу.3⃣Повторяй шаг 2, пока не останется один или ноль камней, и верни вес последнего оставшегося камня или 0,Golang | LeetCode
10 сент., 16:11
Задача: 258. Add Digits Сложность: easyДано целое число num. Повторно складывайте все его цифры, пока результат не станет однозначным, и верните его.Пример: Input: num = 38 Output: 2 Explanation: The process is 38 --> 3 + 8 --> 11 11 --> 1 + 1 --> 2 Since 2 has only one digit, return it.👨💻 Алгоритм:1⃣Инициализируйте переменную digital_root значением 0.2⃣В цикле, пока num больше 0: Добавьте к digital_root последнюю цифру num. Уменьшите num, удалив последнюю цифру.Golang | LeetCode
10 сент., 09:06
Задача: 1302. Deepest Leaves Sum Сложность: mediumДано корень бинарного дерева, вернуть сумму значений его самых глубоких листьев.Пример: Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8] Output: 15👨💻 Алгоритм:1⃣Поместите корень в стек.2⃣Пока стек не пуст. Извлеките узел из стека и обновите текущее число. Если узел является листом, обновите сумму самых глубоких листьев deepest_sum. Поместите правый и левый дочерние узлы в стек.3⃣Верните deepest_sum.😎 Решение: package mainGolang | LeetCode
9 сент., 09:06
Задача: 1402. Reducing Dishes Сложность: hardШеф-повар собрал данные об уровне удовлетворенности от своих n блюд. Шеф может приготовить любое блюдо за 1 единицу времени.Коэффициент удовольствия от блюда определяется как время, затраченное на приготовление этого блюда вместе с предыдущими блюдами, умноженное на уровень удовлетворенности от этого блюда, то есть time[i] satisfaction[i].Верните максимальную сумму коэффициентов удовольствия, которую шеф-повар может получить после приготовления некоторого количества блюд.Блюда можно готовить в любом порядке, и шеф может отказаться от некоторых блюд, чтобы достичь максимального значения.Пример: Input: satisfaction = [-1,-8,0,5,-9] Output: 14 Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-11 + 02 + 53 = 14). Each dish is prepared in one unit of time.👨💻 Алгоритм:1⃣
