Задача: 1102. Path With Maximum Minimum Value
Сложность: medium

Дана целочисленная матрица grid размером m x n. Верните максимальное значение пути, начинающегося в (0, 0) и заканчивающегося в (m - 1, n - 1), двигаясь в 4 кардинальных направлениях.

Значение пути определяется минимальным числом на этом пути.

Пример:

Input: grid = [[5,4,5],[1,2,6],[7,4,6]]
Output: 4
Explanation: The path with the maximum score is highlighted in yellow. 

👨‍💻 Алгоритм:

1⃣Начните с оценки curScore = min(grid[0][0], grid[m-1][n-1]), где m и n - общее количество строк и столбцов входной матрицы.

2⃣Выполните BFS на матрице и проверьте, существует ли путь, где все значения больше или равны curScore:
Используйте очередь (deque) для хранения всех непосещенных ячеек со значением, большим или равным curScore.
Извлекайте ячейку из начала очереди, проверяйте, есть ли у нее непосещенные соседние ячейки, и добавляйте их в конец очереди.
Если успешно достигли правой нижней ячейки, значит путь существует.
Если очередь опустела до достижения правой нижней ячейки, пути не существует.

3⃣Если пути не существует, что означает, что curScore слишком велик, уменьшите его на 1 и повторите шаг 2.
В противном случае, верните curScore как ответ.

😎 Решение:

from collections import deque

class Solution:
    def maximumMinimumPath(self, grid: List[List[int]]) -> int:
        def pathExists(curScore):
            R, C = len(grid), len(grid[0])
            visited = [[False] * C for _ in range(R)]
            dq = deque([(0, 0)])
            visited[0][0] = True

            def push(row, col):
                if 0 <= row < R and 0 <= col < C and not visited[row][col] and grid[row][col] >= curScore:
                    dq.append((row, col))
                    visited[row][col] = True

            while dq:
                curRow, curCol = dq.popleft()
                if curRow == R - 1 and curCol == C - 1:
                    return True

                for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    push(curRow + dr, curCol + dc)

            return False

        curScore = min(grid[0][0], grid[-1][-1])
        while curScore >= 0:
            if pathExists(curScore):
                return curScore
            curScore -= 1
        return -1

Ставь 👍 и забирай 📚 Базу знаний

Задача: 996. Number of Squareful Arrays
Сложность: hard

Массив является квадратным, если сумма каждой пары соседних элементов является совершенным квадратом. Если задан целочисленный массив nums, верните количество перестановок nums, которые являются квадратными. Две перестановки perm1 и perm2 различны, если существует некоторый индекс i такой, что perm1[i] != perm2[i].

Пример:

Input: nums = [1,17,8]
Output: 2

👨‍💻 Алгоритм:

1⃣Генерация перестановок:
Сгенерируйте все возможные перестановки массива nums.
Для каждой перестановки проверьте, является ли она квадратной.

2⃣Проверка квадратности:
Для каждой перестановки проверьте, является ли сумма каждой пары соседних элементов совершенным квадратом.
Для этого используйте функцию для проверки, является ли число совершенным квадратом.

3⃣Подсчет квадратных перестановок:
Подсчитайте количество перестановок, которые являются квадратными, и верните это значение.

😎 Решение:

from itertools import permutations
import math

class Solution:
    def numSquarefulPerms(self, nums: List[int]) -> int:
        def isPerfectSquare(x):
            return int(math.isqrt(x)) ** 2 == x
        
        def isSquareful(perm):
            for i in range(len(perm) - 1):
                if not isPerfectSquare(perm[i] + perm[i + 1]):
                    return False
            return True
        
        perms = set(permutations(nums))
        count = sum(1 for perm in perms if isSquareful(perm))
        return count

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1213. Intersection of Three Sorted Arrays
Сложность: easy

Даны три целочисленных массива arr1, arr2 и arr3, отсортированных в строго возрастающем порядке. Верните отсортированный массив, содержащий только те целые числа, которые присутствуют во всех трех массивах.

Пример:

Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
Output: [1,5]
Explanation: Only 1 and 5 appeared in the three arrays.

👨‍💻 Алгоритм:

1⃣Инициализируйте counter как TreeMap для записи чисел, которые появляются в трех массивах, и количество их появлений.

2⃣Пройдитесь по массивам arr1, arr2 и arr3, чтобы посчитать частоты появления элементов.

3⃣Итерация через counter, чтобы найти числа, которые появляются три раза, и вернуть их в виде отсортированного массива.

😎 Решение:

class Solution:
    def arraysIntersection(self, arr1, arr2, arr3):
        from collections import Counter

        counter = Counter(arr1) + Counter(arr2) + Counter(arr3)
        return [num for num, freq in counter.items() if freq == 3]

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1242. Web Crawler Multithreaded
Сложность: medium

Учитывая URL startUrl и интерфейс HtmlParser, реализуйте многопоточный веб-краулер, который будет просматривать все ссылки, находящиеся под тем же именем хоста, что и startUrl. Верните все URL, полученные вашим веб-краулером, в любом порядке.

Ваш краулер должен: Начинать со страницы: startUrl Вызывать HtmlParser.getUrls(url), чтобы получить все URL с веб-страницы данного URL. Не просматривать одну и ту же ссылку дважды. Исследовать только те ссылки, которые находятся под тем же именем хоста, что и startUrl.

Пример:

Input:
urls = [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.google.com",
  "http://news.yahoo.com/us"
]
edges = [[2,0],[2,1],[3,2],[3,1],[0,4]]
startUrl = "http://news.yahoo.com/news/topics/"
Output: [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.yahoo.com/us"
]

👨‍💻 Алгоритм:

1⃣Извлечь имя хоста из startUrl.
Использовать многопоточность для обработки URL-адресов.

2⃣Хранить посещенные URL-адреса, чтобы избежать повторного посещения.

3⃣Использовать HtmlParser для получения URL-адресов с веб-страниц.

😎 Решение:

from concurrent.futures import ThreadPoolExecutor
from urllib.parse import urlparse
import threading

class HtmlParser:
    def getUrls(self, url: str) -> [str]:
        pass

def extract_hostname(url):
    parsed_url = urlparse(url)
    return parsed_url.netloc

def crawl(startUrl, htmlParser):
    hostname = extract_hostname(startUrl)
    visited = set()
    lock = threading.Lock()

    def visit(url):
        if extract_hostname(url) == hostname:
            with lock:
                if url not in visited:
                    visited.add(url)
                    for next_url in htmlParser.getUrls(url):
                        executor.submit(visit, next_url)

    with ThreadPoolExecutor(max_workers=10) as executor:
        executor.submit(visit, startUrl)

    return list(visited)

Ставь 👍 и забирай 📚 Базу знаний

Привет ребята, мне на easyoffer.ru нужен:

🐍 Middle/Senior Python Developer

Стек:
DRF, PostgreSQL, Redis, Celery, Docker, Sentry

Задачи:
🟠Разработка и поддержка REST API для новых фичей
🟠Интеграция с веб-сервисами и внешними API
🟠Подключение и поддержка платежных систем
🟠Написание юнит- и интеграционных тестов
🟠Оптимизация производительности и масштабирование
🟠Взаимодействие с ML-моделями — будет плюсом

Ожидания:
🟠2+ лет опыта DRF
🟠Опыт интеграций платежных систем
🟠Опыт работы с PostgreSQL, Celery, Redis, Docker
🟠Умение проектировать архитектуру REST-API
🟠Ответственный подход к качеству кода и тестированию

Опыт в стартапах и небольших командах будет плюсом

Условия:
– Частичная занятость (2-3 часа в день)
– Удаленная работа
– Свободный график
– Почасовая оплата

✈ Если вас заинтересовала вакансия, напишите мне @kivaiko
1. Резюме
2. Ссылку на github
3. Комфортную ставку за час

Задача: 1087. Brace Expansion
Сложность: medium

Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.

Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.

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

Пример:

Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

👨‍💻 Алгоритм:

1⃣Вызовите функцию findAllWords(String, Integer) с данной строкой s и значением startPos равным 0. startPos представляет текущую позицию в строке s. Если строка, которую нужно рассмотреть, пуста (startPos == s.length()), верните список, содержащий пустую строку.

2⃣Вызовите функцию storeFirstOptions с строкой s, целым числом startPos и пустым списком firstOptions. Найдите набор символов, начиная с позиции startPos, и сохраните их в списке firstOptions. Это может быть один символ или все символы между скобками. Отсортируйте список firstOptions. Верните обновленное значение startPos, которое теперь указывает на первый индекс следующей группы символов в строке s, которую мы будем рассматривать. Сохраните это значение в переменной remStringStartPos. Сделайте рекурсивный вызов функции findAllWords(String, Integer) с строкой s и remStringStartPos. Сохраните возвращенный список слов в переменной wordsWithRemString.

3⃣Переберите слова в wordsWithRemString и добавьте вышеуказанный символ в начало каждого слова, сохраняя новую строку в списке expandedWords. Верните список expandedWords.

😎 Решение:

class Solution:
    def storeFirstOptions(self, s: str, startPos: int, firstOptions: List[str]) -> int:
        if s[startPos] != '{':
            firstOptions.append(s[startPos])
        else:
            startPos += 1
            while s[startPos] != '}':
                if s[startPos].islower():
                    firstOptions.append(s[startPos])
                startPos += 1
            firstOptions.sort()
        return startPos + 1

    def findAllWords(self, s: str, startPos: int) -> List[str]:
        if startPos == len(s):
            return [""]
        
        firstOptions = []
        remStringStartPos = self.storeFirstOptions(s, startPos, firstOptions)
        wordsWithRemString = self.findAllWords(s, remStringStartPos)
        
        expandedWords = []
        for c in firstOptions:
            for word in wordsWithRemString:
                expandedWords.append(c + word)
        return expandedWords

    def expand(self, s: str) -> List[str]:
        return self.findAllWords(s, 0)

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1058. Minimize Rounding Error to Meet Target
Сложность: medium

Учитывая массив цен [p1,p2...,pn] и цель, округлите каждую цену pi до Roundi(pi) так, чтобы округленный массив [Round1(p1),Round2(p2)...,Roundn(pn)] в сумме достиг заданной цели. Каждая операция Roundi(pi) может быть либо Floor(pi), либо Ceil(pi). Верните строку "-1", если округленный массив невозможно привести к целевому значению. В противном случае возвращается наименьшая ошибка округления, которая определяется как Σ |Roundi(pi) - (pi)| для i от 1 до n, в виде строки с тремя местами после десятичной дроби.

Пример:

Input: prices = ["0.700","2.800","4.900"], target = 8
Output: "1.000"

👨‍💻 Алгоритм:

1⃣Округли каждую цену вниз и вычисли текущую сумму округленных цен.
Найди разницу между целевой суммой и текущей суммой.

2⃣Определи количество округлений вверх, необходимых для достижения целевой суммы.
Если разница отрицательная или больше количества элементов в массиве, верни "-1".

3⃣Вычисли ошибки округления для всех элементов и отсортируй их по возрастанию.
Выбери необходимые округления вверх и вычисли общую ошибку округления.

😎 Решение:

import math

def minimizeRoundingError(prices, target):
    floors = [math.floor(float(p)) for p in prices]
    ceils = [math.ceil(float(p)) for p in prices]
    total_floor = sum(floors)
    
    difference = target - total_floor
    if difference < 0 or difference > len(prices):
        return "-1"
    
    rounding_errors = [(ceil - floor, float(p) - floor) for p, floor, ceil in zip(prices, floors, ceils)]
    rounding_errors.sort(key=lambda x: x[1])
    
    rounding_error_sum = sum(floor - float(p) for floor, p in zip(floors, prices))
    
    for i in range(difference):
        rounding_error_sum += 1
    
    for i in range(difference):
        rounding_error_sum += rounding_errors[i][1]
    
    return "{:.3f}".format(rounding_error_sum)

Ставь 👍 и забирай 📚 Базу знаний

Задача: 815. Bus Routes
Сложность: hard

Дан массив routes, представляющий автобусные маршруты, где routes[i] - это автобусный маршрут, который i-й автобус повторяет бесконечно.

Например, если routes[0] = [1, 5, 7], это означает, что 0-й автобус путешествует в последовательности 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... бесконечно.
Вы начинаете на автобусной остановке source (вы изначально не находитесь в автобусе) и хотите добраться до автобусной остановки target. Перемещаться между автобусными остановками можно только на автобусах.

Верните наименьшее количество автобусов, которые вам нужно взять, чтобы доехать от source до target. Верните -1, если это невозможно.

Пример:

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

👨‍💻 Алгоритм:

1⃣Верните 0, если source и target совпадают. Инициализируйте пустую карту adjList, чтобы хранить ребра, где ключ - это автобусная остановка, а значение - список целых чисел, обозначающих индексы маршрутов, которые имеют эту остановку. Инициализируйте пустую очередь q и неупорядоченное множество vis, чтобы отслеживать посещенные маршруты. Вставьте начальные маршруты в очередь q и отметьте их посещенными в vis.

2⃣Итерация по очереди, пока она не пуста: извлеките маршрут из очереди, итерируйтесь по остановкам в маршруте. Если остановка равна target, верните busCount. В противном случае, итерируйтесь по маршрутам для этой остановки в карте adjList, добавьте непосещенные маршруты в очередь и отметьте их посещенными.

3⃣Верните -1 после завершения обхода в ширину (BFS).

😎 Решение:

class Solution:
    def numBusesToDestination(self, routes, source, target):
        if source == target:
            return 0
        
        from collections import defaultdict, deque
        
        adjList = defaultdict(list)
        for route, stops in enumerate(routes):
            for stop in stops:
                adjList[stop].append(route)
        
        q = deque()
        vis = set()
        for route in adjList[source]:
            q.append(route)
            vis.add(route)
        
        busCount = 1
        while q:
            for _ in range(len(q)):
                route = q.popleft()
                for stop in routes[route]:
                    if stop == target:
                        return busCount
                    for nextRoute in adjList[stop]:
                        if nextRoute not in vis:
                            vis.add(nextRoute)
                            q.append(nextRoute)
            busCount += 1
        return -1

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1062. Longest Repeating Substring
Сложность: medium

Дана строка s. Вернуть длину самой длинной повторяющейся подстроки. Если повторяющаяся подстрока отсутствует, вернуть 0.

Пример:

Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.

👨‍💻 Алгоритм:

1⃣Перемещайте скользящее окно длиной L по строке длиной N.

2⃣Проверьте, находится ли строка в скользящем окне в хэш-наборе уже виденных строк. Если да, то повторяющаяся подстрока находится здесь. Если нет, сохраните строку из скользящего окна в хэш-наборе.

3⃣Очевидный недостаток этого подхода — большое потребление памяти в случае длинных строк.

😎 Решение:

class Solution:
    def search(self, L, n, S):
        seen = set()
        for start in range(n - L + 1):
            tmp = S[start:start + L]
            if tmp in seen:
                return start
            seen.add(tmp)
        return -1

    def longestRepeatingSubstring(self, S):
        n = len(S)
        left, right = 1, n
        while left <= right:
            L = left + (right - left) // 2
            if self.search(L, n, S) != -1:
                left = L + 1
            else:
                right = L - 1
        return left - 1

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1250. Check If It Is a Good Array
Сложность: hard

Дан массив nums из целых положительных чисел. Ваша задача - выбрать некоторое подмножество nums, умножить каждый элемент на целое число и сложить все эти числа.Массив считается хорошим, если из него можно получить сумму, равную 1, при любом возможном подмножестве и множителе. Верните True, если массив хороший, иначе верните False.

Пример:

Input: nums = [12,5,7,23]
Output: true

👨‍💻 Алгоритм:

1⃣Если наибольший общий делитель (НОД) всех чисел в массиве равен 1, то массив считается хорошим.

2⃣Если НОД всех чисел больше 1, то массив не считается хорошим

3⃣Получить сумму, равную 1, умножая и складывая элементы.

😎 Решение:

import math
from functools import reduce

def isGoodArray(nums):
    return reduce(math.gcd, nums) == 1

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1431. Kids With the Greatest Number of Candies
Сложность: easy

Дано n детей с конфетами. Вам дан целочисленный массив candies, где каждый candies[i] представляет количество конфет у i-го ребенка, и целое число extraCandies, обозначающее количество дополнительных конфет, которые у вас есть.

Вернуть булев массив result длиной n, где result[i] равно true, если, дав i-му ребенку все дополнительные конфеты, он будет иметь наибольшее количество конфет среди всех детей, или false в противном случае.

Обратите внимание, что несколько детей могут иметь наибольшее количество конфет.

Пример:

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.

👨‍💻 Алгоритм:

1⃣Найдите максимальное количество конфет в массиве candies, сохраняя его в переменной maxCandies.

2⃣Создайте булев список answer и пройдитесь по массиву candies, добавляя в answer значение true, если текущий ребенок с добавленными extraCandies имеет количество конфет больше или равное maxCandies, иначе добавляйте false.

3⃣Верните список answer.

😎 Решение:

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        maxCandies = max(candies)
        return [candy + extraCandies >= maxCandies for candy in candies]

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1063. Number of Valid Subarrays
Сложность: hard

Дан целочисленный массив nums. Вернуть количество непустых подмассивов, в которых левый элемент не больше других элементов подмассива.

Подмассив — это непрерывная часть массива.

Пример:

Input: nums = [1,4,2,5,3]
Output: 11
Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

👨‍💻 Алгоритм:

1⃣нициализируйте переменную ans значением 0. Инициализируйте пустой стек st, который будет хранить индексы элементов в стеке.

2⃣Итерируйте по элементам массива nums для каждого индекса i: продолжайте извлекать элементы из стека st, пока стек не станет пустым или элемент nums[i] не станет больше элемента на вершине стека. Для каждого извлеченного элемента добавляйте количество подмассивов как i - st.top(). Поместите текущий индекс i в стек.

3⃣Извлеките все оставшиеся элементы из стека и для каждого рассмотрите размер nums как индекс следующего меньшего элемента. Соответственно, добавьте nums.size() - st.top() к переменной ans. Верните ans.

😎 Решение:

class Solution:
    def validSubarrays(self, nums: List[int]) -> int:
        ans = 0
        st = []
        
        for i in range(len(nums)):
            while st and nums[i] < nums[st[-1]]:
                ans += (i - st.pop())
            st.append(i)
        
        while st:
            ans += (len(nums) - st.pop())
        
        return ans

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1162. As Far from Land as Possible
Сложность: medium

Дана сетка размером n x n, содержащая только значения 0 и 1, где 0 представляет воду, а 1 представляет землю. Найдите ячейку с водой, такое что её расстояние до ближайшей ячейки с землёй максимально, и верните это расстояние. Если в сетке нет ни земли, ни воды, верните -1.

Расстояние, используемое в этой задаче, - это манхэттенское расстояние: расстояние между двумя ячейками (x0, y0) и (x1, y1) равно |x0 - x1| + |y0 - y1|.

Пример:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.

👨‍💻 Алгоритм:

1⃣Итерируйте по матрице и вставьте координаты ячеек с землёй в очередь. Инициализируйте переменную distance значением -1 для хранения текущего шага обхода в ширину (BFS). Также создайте копию матрицы visited для пометки ячеек с водой как посещённые, чтобы не вставлять их снова в очередь.

2⃣Выполните BFS: Обходите текущие элементы в очереди и для каждого элемента проверяйте координаты в четырёх направлениях, являются ли они ячейками с водой (0). Если да, вставьте их в очередь и измените их на ячейки с землёй (1) в матрице visited. После каждого пройденного уровня (внутренний цикл while завершён), увеличьте переменную distance.

3⃣Повторяйте, пока очередь не станет пустой. Верните значение distance. Если оно равно 0, это означает, что не было ячеек с водой и обход завершился после первого шага, поэтому верните -1. Если в матрице не было ячеек с землёй, цикл while вообще не начнётся, и переменная distance останется с начальным значением (-1).

😎 Решение:

from collections import deque

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        visited = [row[:] for row in grid]
        q = deque()
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    q.append((i, j))
        
        distance = -1
        while q:
            qSize = len(q)
            for _ in range(qSize):
                landCell = q.popleft()
                for dir in directions:
                    x, y = landCell[0] + dir[0], landCell[1] + dir[1]
                    if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and visited[x][y] == 0:
                        visited[x][y] = 1
                        q.append((x, y))
            distance += 1
        
        return -1 if distance == 0 else distance

Ставь 👍 и забирай 📚 Базу знаний

Задача: 972. Equal Rational Numbers
Сложность: hard

Даны две строки s и t, каждая из которых представляет собой неотрицательное рациональное число. Вернуть true тогда и только тогда, когда они представляют одно и то же число. Строки могут использовать скобки для обозначения повторяющейся части рационального числа.

Рациональное число может быть представлено с использованием до трех частей: <ЦелаяЧасть>, <НеповторяющаясяЧасть> и <ПовторяющаясяЧасть>. Число будет представлено одним из следующих трех способов:

<ЦелаяЧасть>
Например, 12, 0 и 123.
<ЦелаяЧасть><.><НеповторяющаясяЧасть>
Например, 0.5, 1., 2.12 и 123.0001.
<ЦелаяЧасть><.><НеповторяющаясяЧасть><(><ПовторяющаясяЧасть><)>
Например, 0.1(6), 1.(9), 123.00(1212).
Повторяющаяся часть десятичного разложения обозначается в круглых скобках. Например:

1/6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66).

Пример:

Input: s = "0.(52)", t = "0.5(25)"
Output: true
Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

👨‍💻 Алгоритм:

1⃣Преобразование дроби. Определите и изолируйте повторяющуюся часть дроби. Преобразуйте строку, представляющую число, в выражение вида S=x/(10^k-1), где x — повторяющаяся часть, а k — её длина.

2⃣Вычисление геометрической суммы. Преобразуйте повторяющуюся часть в сумму вида S=x*(r/(1-r)), где r = 10^(-k). Найдите значение дроби для повторяющейся части, используя формулу геометрической прогрессии.

3⃣Обработка неповторяющейся части. Определите значение неповторяющейся части дроби как обычное число. Объедините результаты для повторяющейся и неповторяющейся частей для получения итогового значения.

😎 Решение:

from math import gcd

class Fraction:
    def __init__(self, n, d):
        g = gcd(n, d)
        self.n = n // g
        self.d = d // g

    def iadd(self, other):
        numerator = self.n * other.d + self.d * other.n
        denominator = self.d * other.d
        g = gcd(numerator, denominator)
        self.n = numerator // g
        self.d = denominator // g

class Solution:
    def isRationalEqual(self, S: str, T: str) -> bool:
        f1 = self.convert(S)
        f2 = self.convert(T)
        return f1.n == f2.n and f1.d == f2.d

    def convert(self, S: str) -> Fraction:
        state = 0
        ans = Fraction(0, 1)
        decimal_size = 0

        for part in S.split('.'):
            state += 1
            if not part:
                continue
            x = int(part)
            sz = len(part)

            if state == 1:
                ans.iadd(Fraction(x, 1))
            elif state == 2:
                ans.iadd(Fraction(x, 10 ** sz))
                decimal_size = sz
            else:
                denom = 10 ** decimal_size
                denom *= 10 ** sz - 1
                ans.iadd(Fraction(x, denom))
        return ans

Ставь 👍 и забирай 📚 Базу знаний

Привет ребята, мне на easyoffer.ru нужен:

🐍 Middle/Senior Python Developer

Стек:
DRF, PostgreSQL, Redis, Celery, Docker, Sentry

Задачи:
🟠Разработка и поддержка REST API для новых фичей
🟠Интеграция с веб-сервисами и внешними API
🟠Подключение и поддержка платежных систем
🟠Написание юнит- и интеграционных тестов
🟠Оптимизация производительности и масштабирование
🟠Взаимодействие с ML-моделями — будет плюсом

Ожидания:
🟠2+ лет опыта DRF
🟠Опыт интеграций платежных систем
🟠Опыт работы с PostgreSQL, Celery, Redis, Docker
🟠Умение проектировать архитектуру REST-API
🟠Ответственный подход к качеству кода и тестированию

Опыт в стартапах и небольших командах будет плюсом

Условия:
– Частичная занятость (2-3 часа в день)
– Удаленная работа
– Свободный график
– Почасовая оплата

✈ Если вас заинтересовала вакансия, напишите мне @kivaiko
1. Резюме
2. Ссылку на github
3. Комфортную ставку за час

Задача: 1426. Counting Elements
Сложность: easy

Дан целочисленный массив arr, посчитайте, сколько элементов x в нем есть таких, что x + 1 также находится в arr. Если в arr есть дубликаты, считайте их отдельно.

Пример:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

👨‍💻 Алгоритм:

1⃣Создайте вспомогательную функцию для проверки, содержится ли элемент в массиве.

2⃣Итерируйте по каждому элементу массива и используйте вспомогательную функцию для проверки, содержится ли элемент x + 1 в массиве.

3⃣Увеличьте счетчик, если x + 1 найден, и верните значение счетчика.

😎 Решение:

class Solution:
    def countElements(self, arr: List[int]) -> int:
        def integerInArray(arr, target):
            for x in arr:
                if x == target:
                    return True
            return False
        
        count = 0
        for x in arr:
            if integerInArray(arr, x + 1):
                count += 1
        return count

Ставь 👍 и забирай 📚 Базу знаний

Задача: 662. Maximum Width of Binary Tree
Сложность: medium

Дан корень бинарного дерева, верните максимальную ширину данного дерева.

Максимальная ширина дерева - это максимальная ширина среди всех уровней.

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

Гарантируется, что ответ будет в диапазоне 32-битного знакового целого числа.

Пример:

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).

👨‍💻 Алгоритм:

1⃣Инициализация:
Создайте очередь для хранения узлов и их позиций на уровне.
Начните с корневого узла и его позиции 0.

2⃣Обработка каждого уровня:
Для каждого уровня дерева получите его узлы и их позиции.
Вычислите ширину уровня как разницу между максимальной и минимальной позициями плюс один.

3⃣Обновление максимальной ширины:
Обновите максимальную ширину, если текущая ширина уровня больше.

😎 Решение:

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def widthOfBinaryTree(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        max_width = 0
        queue = deque([(root, 0)])
        
        while queue:
            level_length = len(queue)
            _, first_pos = queue[0]
            for i in range(level_length):
                node, pos = queue.popleft()
                if node.left:
                    queue.append((node.left, 2 * pos))
                if node.right:
                    queue.append((node.right, 2 * pos + 1))
            max_width = max(max_width, pos - first_pos + 1)
        
        return max_width

Ставь 👍 и забирай 📚 Базу знаний

Задача: 762. Prime Number of Set Bits in Binary Representation
Сложность: hard

Если даны два целых числа left и right, верните количество чисел в диапазоне [left, right], имеющих простое число битов в двоичном представлении. Напомним, что число битов в двоичном представлении - это количество единиц, присутствующих в числе 1. Например, 21 в двоичном представлении - это 10101, которое имеет 3 бита.

Пример:

Input: left = 10, right = 15
Output: 5

👨‍💻 Алгоритм:

1⃣Создайте функцию для подсчета количества единиц в двоичном представлении числа.

2⃣Создайте функцию для проверки, является ли число простым.

3⃣Пройдите через все числа в диапазоне [left, right] и подсчитайте числа, у которых количество битов в двоичном представлении является простым числом.

😎 Решение:

def countPrimeSetBits(left, right):
    def countBits(x):
        return bin(x).count('1')
    
    def isPrime(x):
        if x < 2:
            return False
        for i in range(2, int(x ** 0.5) + 1):
            if x % i == 0:
                return False
        return True
    
    count = 0
    for num in range(left, right + 1):
        if isPrime(countBits(num)):
            count += 1

Ставь 👍 и забирай 📚 Базу знаний

Задача: 667. Beautiful Arrangement II
Сложность: medium

Даны два целых числа n и k, составьте список answer, содержащий n различных положительных чисел в диапазоне от 1 до n, который соответствует следующему требованию:

Предположим, что этот список answer = [a1, a2, a3, ... , an], тогда список [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] имеет ровно k различных чисел. Верните список answer. Если существует несколько допустимых ответов, верните любой из них.

Пример:

Input: n = 3, k = 1
Output: [1,2,3]
Explanation: The [1,2,3] has three different positive integers ranging from 1 to 3, and the [1,1] has exactly 1 distinct integer: 1

👨‍💻 Алгоритм:

1⃣Инициализация списка:
Начните с создания списка от 1 до n: [1, 2, 3, ..., n].

2⃣Конструирование шаблона с k различиями:
Для обеспечения k различных значений разностей используйте следующий подход:
Включайте числа попеременно с конца и начала списка, начиная с n и 1, чтобы создать как можно больше уникальных разностей.
Если требуется меньше k, оставшиеся числа просто добавляйте в порядке возрастания, чтобы не увеличивать количество уникальных разностей.

3⃣Заполнение списка:
Заполните оставшуюся часть списка последовательными числами, чтобы сохранить уникальные числа в диапазоне от 1 до n.

😎 Решение:

def constructArray(n, k):
    answer = []
    left, right = 1, n
    
    for i in range(k + 1):
        if i % 2 == 0:
            answer.append(left)
            left += 1
        else:
            answer.append(right)
            right -= 1
    
    if k % 2 == 0:
        answer.extend(range(left, right + 1))
    else:
        answer.extend(range(right, left - 1, -1))
    
    return answer

Ставь 👍 и забирай 📚 Базу знаний

Задача: 42. Trapping Rain Water
Сложность: hard

Дано n неотрицательных целых чисел, представляющих карту высот, где ширина каждого столбца равна 1. Вычислите, сколько воды он может удержать после дождя.

Пример:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

👨‍💻 Алгоритм:

1️⃣Найдите максимальную высоту столбца с левого конца до индекса i в массиве left_max.

2️⃣Найдите максимальную высоту столбца с правого конца до индекса i в массиве right_max.

3️⃣Итерируйте по массиву высот height и обновляйте ans: добавьте min(left_max[i], right_max[i]) - height[i] к ans.

😎 Решение:

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) == 0:
            return 0
        ans = 0
        size = len(height)
        left_max, right_max = [0] * size, [0] * size
        left_max[0] = height[0]
        for i in range(1, size):
            left_max[i] = max(height[i], left_max[i - 1])
        right_max[size - 1] = height[size - 1]
        for i in range(size - 2, -1, -1):
            right_max[i] = max(height[i], right_max[i + 1])
        for i in range(1, size - 1):
            ans += min(left_max[i], right_max[i]) - height[i]
        return ans

Ставь 👍 и забирай 📚 Базу знаний