Посты по тегу «алгособес»

Для задачки было предложено такое однострочное решение с разными вариациями:

def solve(string):
    s = ''.join([ch for ch in string if ch in '()'])
    return len(max(s.split(')'), key=len))

Рабочее решение? Нет.
Если мы скормим скормим этой функции строку (()(())), то правильный ответ (глубина): 3, а функция вернет 2. Логика "количество открывающих скобок подряд" ломается на любых вложенных структурах, которые идут не первой веткой.

☝🏻 Как решать правильно
Скучное, но рабочее решение со сложностью O(n) подразумевает обычный счетчик. Мы идем по строке, увеличиваем счетчик на (, уменьшаем на ) и на каждом шаге обновляем глобальный максимум.

def max_depth(s: str) -> int:
    current_depth = 0
    max_depth = 0
    
    for char in s:
        if char == '(':
            current_depth += 1
            max_depth = max(max_depth, current_depth)
        elif char == ')':
            current_depth -= 1
            # Валидация корректности (опционально)
            if current_depth < 0:
                return -1 
                
    return max_depth if current_depth == 0 else -1

Вариант для эстетов (функциональный):

Если уж очень хочется в одну строку, можно использовать accumulate. Мы мапим скобки в 1 и -1, считаем префиксные суммы (accumulate) и берем максимум.

from itertools import accumulate

def solve_poly(s: str) -> int:
    # Превращаем '(' в 1, ')' в -1, остальное в 0
    depths = accumulate(1 if c == '(' else -1 if c == ')' else 0 for c in s)
    return max(depths, default=0)

#алгособес

🙁Глубина скобочек 😌

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

Дано: Строка, содержащая корректное математическое выражение (цифры, знаки операций, скобки).
Задача: Вернуть целое число, обозначающее максимальную степень вложенности скобок.

Примеры:

solve('1 + 2') 
# Результат: 0

solve('(1) + ((2))') 
# Результат: 2 (максимум во второй части выражения)

solve('(3 * n + 1) / 2') 
# Результат: 1

Кидайте свои однострочники (и не только) в комментарии 👇🏻

#алгособес