LeetCode 75

def mergeAlternately(word1: str, word2: str) -> str:
    merged = []
    len1, len2 = len(word1), len(word2)
    for i in range(min(len1, len2)):
        merged.append(word1[i])
        merged.append(word2[i])
    if len1 > len2:
        merged.append(word1[len2:])
    elif len2 > len1:
        merged.append(word2[len1:])
    return "".join(merged)

if __name__ == "__main__":
    w1 = "abc"
    w2 = "pqr"
    print(mergeAlternately(w1, w2))

import math

def gcd_of_strings(str1, str2):
    if str1 + str2 != str2 + str1:
        return ""
    return str1[:math.gcd(len(str1), len(str2))]

if __name__ == "__main__":
    s1 = "ABCABC"
    s2 = "ABC"
    result = gcd_of_strings(s1, s2)
    print(result)

def kidsWithCandies(candies, extraCandies):
    max_candies = max(candies)
    return [candy + extraCandies >= max_candies for candy in candies]

if __name__ == "__main__":
    candies = [2, 3, 5, 1, 3]
    extraCandies = 3
    print(kidsWithCandies(candies, extraCandies))

def can_place_flowers(flowerbed, n):
    count = 0
    for i in range(len(flowerbed)):
        if flowerbed[i] == 0 and (i == 0 or flowerbed[i-1] == 0) and (i == len(flowerbed)-1 or flowerbed[i+1] == 0):
            flowerbed[i] = 1
            count += 1
            if count >= n:
                return True
    return count >= n

if __name__ == "__main__":
    # Примеры тестов
    print(can_place_flowers([1, 0, 0, 0, 1], 1))  # True
    print(can_place_flowers([1, 0, 0, 0, 1], 2))  # False

def reverseVowels(s: str) -> str:
    vowels = set(["a", "e", "i", "o", "u", "A", "E", "I", "O", "U"])
    s = list(s)
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and s[left] not in vowels:
            left += 1
        while left < right and s[right] not in vowels:
            right -= 1
        if left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1
    return ''.join(s)

if __name__ == ''__main__'':
    test_str = "Hello, World!"
    print(reverseVowels(test_str))

def reverse_words(s: str) -> str:
    # Trim spaces and split by whitespace
    words = s.split()
    return " ".join(reversed(words))

if __name__ == "__main__":
    s = "  Hello   world!  "
    print(reverse_words(s))

def product_except_self(nums):
    n = len(nums)
    result = [1] * n
    left = 1
    for i in range(n):
        result[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):
        result[i] *= right
        right *= nums[i]
    return result

if __name__ == "__main__":
    nums = [1, 2, 3, 4]
    print(product_except_self(nums))  # [24, 12, 8, 6]

import sys

def increasingTriplet(nums: list[<int>]) -> bool:
    first = second = float("inf")
    for n in nums:
        if n <= first:
            first = n
        elif n <= second:
            second = n
        else:
            return True
    return False

if __name__ == '__main__':
    nums = [1, 2, 3, 4, 5]
    print(increasingTriplet(nums))

def compress(chars):
    read = 0
    write = 0
    n = len(chars)
    while read < n:
        curr = chars[read]
        count = 0
        while read < n and chars[read] == curr:
            read += 1
            count += 1
        chars[write] = curr
        write += 1
        if count > 1:
            for ch in str(count):
                chars[write] = ch
                write += 1
    return write

# Пример использования
if __name__ == "__main__":
    arr = ['a', 'a', 'b', 'b', 'c', 'c', 'c']
    new_length = compress(arr)
    print(arr[:new_length])  # Вывод: ['a', '2', 'b', '2', 'c', '3']

def move_zeroes(nums):
    last_nonzero = 0
    for i in range(len(nums)):
        if nums[i] != 0:
            nums[last_nonzero], nums[i] = nums[i], nums[last_nonzero]
            last_nonzero += 1

# Пример использования
if __name__ == "'__main__'":
    arr = [0, 1, 0, 3, 12]
    move_zeroes(arr)
    print(arr)  # Вывод: [1, 3, 12, 0, 0]

def is_subsequence(s: str, t: str) -> bool:
    i, j = 0, 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == len(s)

if __name__ == '__main__':
    s = input().strip()
    t = input().strip()
    print(is_subsequence(s, t))

def max_area(heights):
    left = 0
    right = len(heights) - 1
    best = 0
    while left < right:
        width = right - left
        if heights[left] < heights[right]:
            best = max(best, heights[left] * width)
            left += 1
        else:
            best = max(best, heights[right] * width)
            right -= 1
    return best

# Пример использования:
if __name__ == '__main__':
    sample_heights = [1,8,6,2,5,4,8,3,7]
    print(max_area(sample_heights))

import collections

def max_k_sum_pairs(nums, k):
    count = collections.Counter(nums)
    pairs = 0
    for num in list(count.keys()):
        comp = k - num
        if comp in count:
            if comp == num:
                pairs += count[num] // 2
            else:
                pairs += min(count[num], count[comp])
            count.pop(num, None)
            count.pop(comp, None)
    return pairs

if __name__ == "__main__":
    nums = [1, 2, 3, 4, 3, 2, 1, 5]
    k = 4
    print(max_k_sum_pairs(nums, k))

def findMaxAverageSubarray(nums, k):
    curr_sum = sum(nums[:k])
    max_sum = curr_sum
    for i in range(k, len(nums)):
        curr_sum += nums[i] - nums[i - k]
        if curr_sum > max_sum:
            max_sum = curr_sum
    return max_sum / k

# Пример использования:
if __name__ == '__main__':
    nums = [1, 12, -5, -6, 50, 3]
    k = 4
    print(findMaxAverageSubarray(nums, k))

def max_vowels(s: str, k: int) -> int:
    vowels = set("aeiouAEIOU")
    count = 0
    max_count = 0
    for i in range(len(s)):
        if s[i] in vowels:
            count += 1
        if i >= k and s[i-k] in vowels:
            count -= 1
        if i >= k-1:
            max_count = max(max_count, count)
    return max_count

if __name__ == "__main__":
    s = "abciiidef"
    k = 3
    result = max_vowels(s, k)
    print(result)

def max_consecutive_ones(nums: list[int], k: int) -> int:
    left = 0
    zero_count = 0
    max_length = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            zero_count += 1
        while zero_count > k:
            if nums[left] == 0:
                zero_count -= 1
            left += 1
        max_length = max(max_length, right - left + 1)
    return max_length

# Пример использования:
nums = [1, 0, 1, 1, 0, 1]
k = 1
print(max_consecutive_ones(nums, k))

def longest_subarray(nums):
    n = len(nums)
    left = 0
    zeros = 0
    max_len = 0
    for right in range(n):
        if nums[right] == 0:
            zeros += 1
        while zeros > 1:
            if nums[left] == 0:
                zeros -= 1
            left += 1
        # Если нулей нет, то удаляем единицу, поэтому длина окна уменьшается на 1
        curr_len = (right - left) if zeros == 0 else (right - left)
        max_len = max(max_len, curr_len)
    return max_len

# Пример использования:
if __name__ == '__main__':
    nums = [1, 1, 0, 1]
    print(longest_subarray(nums))  # Выведет 3

def highest_altitude(gain):
    altitude = 0
    max_altitude = 0
    for g in gain:
        altitude += g
        if altitude > max_altitude:
            max_altitude = altitude
    return max_altitude

if __name__ == "__main__":
    gain = [ -5, 1, 5, 0, -7 ]
    print(highest_altitude(gain))

def pivot_index(nums):
    total_sum = sum(nums)
    left_sum = 0
    for i, num in enumerate(nums):
        if left_sum == total_sum - left_sum - num:
            return i
        left_sum += num
    return -1

# Пример использования
if __name__ == '__main__':
    nums = [1, 7, 3, 6, 5, 6]
    print(pivot_index(nums))  # Ожидаемый вывод: 3

def array_difference(arr1, arr2):
    # Возвращает два массива: 
    # - элементы, присутствующие в arr1, но отсутствующие в arr2
    # - элементы, присутствующие в arr2, но отсутствующие в arr1
    set2 = set(arr2)
    diff1 = [x for x in arr1 if x not in set2]
    set1 = set(arr1)
    diff2 = [x for x in arr2 if x not in set1]
    return [diff1, diff2]

# Пример использования:
if __name__ == ''__main__'':
    arr1 = [1, 2, 3, 4, 5]
    arr2 = [4, 5, 6, 7]
    result = array_difference(arr1, arr2)
    print(result)  # Вывод: [[1, 2, 3], [6, 7]]

from collections import Counter

def unique_occurrences(arr):
    # Подсчитываем количество вхождений каждого числа
    counts = Counter(arr)
    # Проверяем, что количества вхождений уникальны
    return len(counts.values()) == len(set(counts.values()))

if __name__ == '__main__':
    arr = [1, 2, 2, 1, 1, 3]
    print(unique_occurrences(arr))

def are_close(word1, word2):
    if len(word1) != len(word2):
        return False
    from collections import Counter
    count1 = Counter(word1)
    count2 = Counter(word2)
    if set(word1) != set(word2):
        return False
    return sorted(count1.values()) == sorted(count2.values())

if __name__ == __'main'__:
    print(are_close("abc", "bca"))   # True
    print(are_close("a", "aa"))       # False

def equal_pairs(matrix):
    from collections import Counter
    n = len(matrix)
    row_count = Counter(tuple(row) for row in matrix)
    col_count = Counter(tuple(matrix[i][j] for i in range(n)) for j in range(n))
    result = 0
    for key in row_count:
        result += row_count[key] * col_count.get(key, 0)
    return result

if __name__ == "__main__":
    arr = [[1, 2, 1],
           [2, 2, 2],
           [1, 2, 1]]
    print(equal_pairs(arr))  # Expected output: 3

def removeStars(s: str) -> str:
    stack = []
    for char in s:
        if char == '*':
            if stack:
                stack.pop()
        else:
            stack.append(char)
    return "".join(stack)

if __name__ == "__main__":
    test_str = "leet**cod*e"
    result = removeStars(test_str)
    print(result)  # Expected output: "lecoe"

def asteroidCollision(asteroids: list[int]) -> list[int]:
    stack = []
    for a in asteroids:
        collision = False
        # Пока есть возможность столкновения: справа движущийся астероид в стеке и левый текущий астероид
        while stack and a < 0 and stack[-1] > 0:
            if abs(stack[-1]) < abs(a):
                # Верхний астероид меньше - уничтожается
                stack.pop()
                continue
            elif abs(stack[-1]) == abs(a):
                # Оба равны по размеру - уничтожаются
                stack.pop()
            collision = True
            break
        if not collision:
            stack.append(a)
    return stack

if __name__ == "__main__":
    asteroids = [5,10,-5]
    print(asteroidCollision(asteroids))

def decodeString(s: str) -> str:
    stack = []
    current = ""
    num = 0
    for c in s:
        if c.isdigit():
            num = num * 10 + int(c)
        elif c == "[":
            stack.append((current, num))
            current = ""
            num = 0
        elif c == "]":
            prev_str, repeat = stack.pop()
            current = prev_str + current * repeat
        else:
            current += c
    return current

# Пример использования
if __name__ == "__main__":
    input_str = "3[a2[c]]"
    print(decodeString(input_str))  #!-- Oжидаемый вывод: accaccacc 

from collections import deque

class RecentCounter:
    def __init__(self):
        self.q = deque()

    def ping(self, t: int) -> int:
        self.q.append(t)
        while self.q and self.q[0] < t - 3000:
            self.q.popleft()
        return len(self.q)

if __name__ == "__main__":
    counter = RecentCounter()
    print(counter.ping(1))      # -> 1
    print(counter.ping(100))    # -> 2
    print(counter.ping(3001))   # -> 3
    print(counter.ping(3002))   # -> 3

import collections

def predictPartyVictory(senate: str) -> str:
    n = len(senate)
    qR = collections.deque()
    qD = collections.deque()
    for i, s in enumerate(senate):
        if s == 'R':
            qR.append(i)
        else:
            qD.append(i)
    while qR and qD:
        iR = qR.popleft()
        iD = qD.popleft()
        if iR < iD:
            qR.append(iR + n)
        else:
            qD.append(iD + n)
    return 'R' if qR else 'D'

if __name__ == '__main__':
    senate = 'RDD'
    print(predictPartyVictory(senate))

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def deleteMiddle(head: ListNode) -> ListNode:
    if not head or not head.next:
        return None
    slow = head
    fast = head
    prev = None
    while fast and fast.next:
        fast = fast.next.next
        prev = slow
        slow = slow.next
    if prev:
        prev.next = slow.next
    return head

# Пример использования:
def printList(head: ListNode):
    while head:
        print(head.val, end=" ")
        head = head.next
    print()

if __name__ == "__main__":
    # Создаем список: 1->2->3->4->5
    node5 = ListNode(5)
    node4 = ListNode(4, node5)
    node3 = ListNode(3, node4)
    node2 = ListNode(2, node3)
    head = ListNode(1, node2)
    head = deleteMiddle(head)
    printList(head)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def oddEvenList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    odd = head
    even = head.next
    evenHead = even
    while even and even.next:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next
    odd.next = evenHead
    return head

def print_list(head: ListNode):
    while head:
        print(head.val, end=" - ")
        head = head.next
    print()

# Пример использования:
nodes = [ListNode(i) for i in range(1, 8)]
for i in range(len(nodes)-1):
    nodes[i].next = nodes[i+1]
head = nodes[0]
head = oddEvenList(head)
print_list(head)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head):
    prev = None
    current = head
    while current:
        nxt = current.next
        current.next = prev
        prev = current
        current = nxt
    return prev

if __name__ == "__main__":
    # Создаем односвязный список: 1 -> 2 -> 3 -> 4 -> None
    node4 = ListNode(4)
    node3 = ListNode(3, node4)
    node2 = ListNode(2, node3)
    head = ListNode(1, node2)
    
    # Разворачиваем список
    new_head = reverseList(head)
    
    # Выводим развернутый список
    current = new_head
    while current:
        print(current.val, end=" ")
        current = current.next
    print()

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def pair_sum(head: ListNode) -> int:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    prev = None
    current = slow
    while current:
        nxt = current.next
        current.next = prev
        prev = current
        current = nxt
    max_sum = 0
    first, second = head, prev
    while second:
        sum_pair = first.val + second.val
        if sum_pair > max_sum:
            max_sum = sum_pair
        first = first.next
        second = second.next
    return max_sum

# Пример использования:
if __name__ == '__main__':
    # Создаем связный список: 5 -> 4 -> 2 -> 1
    n4 = ListNode(1)
    n3 = ListNode(2, n4)
    n2 = ListNode(4, n3)
    n1 = ListNode(5, n2)
    print(pair_sum(n1))  # Выведет 6, так как пары (5,1) и (4,2); максимум 5+1 = 6

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

def maxDepth(root):
    if root is None:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

# Пример использования:
if __name__ == '__main__':
    # Создадим дерево:
    #      1
    #     / \
    #    2   3
    #       / \
    #      4   5
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.right.left = TreeNode(4)
    root.right.right = TreeNode(5)
    print(maxDepth(root))

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

def leaf_similar(root1, root2):
    def dfs(root):
        if root:
            if not root.left and not root.right:
                yield root.val
            yield from dfs(root.left)
            yield from dfs(root.right)
    return list(dfs(root1)) == list(dfs(root2))

# 'Пример использования:'
if __name__ == "__main":
    # 'Дерево 1:'
    #        3
    #       / \
    #      5   1
    #     / \   \
    #    6   2   9
    #       / \
    #      7   4
    tree1 = TreeNode(3)
    tree1.left = TreeNode(5, TreeNode(6), TreeNode(2, TreeNode(7), TreeNode(4)))
    tree1.right = TreeNode(1, None, TreeNode(9))
    
    # 'Дерево 2:'
    #        3
    #       / \
    #      5   1
    #       \    \
    #        2    4
    #       / \
    #      7   9
    tree2 = TreeNode(3)
    tree2.left = TreeNode(5, None, TreeNode(2, TreeNode(7), TreeNode(9)))
    tree2.right = TreeNode(1, None, TreeNode(4))
    
    # 'Проверка:'
    print("Leaf-similar trees:", leaf_similar(tree1, tree2))

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

def countGoodNodes(root):
    def dfs(node, max_val):
        if not node:
            return 0
        # Если значение узла не меньше максимального на пути, то узел «хороший»
        count = 1 if node.val >= max_val else 0
        max_val = max(max_val, node.val)
        count += dfs(node.left, max_val)
        count += dfs(node.right, max_val)
        return count
    return dfs(root, root.val) if root else 0

# Пример использования:
if __name__ == "__main__":
    # Создание бинарного дерева:
    #       3
    #      / \
    #     1   4
    #    /   / \
    #   3   1   5
    root = TreeNode(3)
    root.left = TreeNode(1)
    root.right = TreeNode(4)
    root.left.left = TreeNode(3)
    root.right.left = TreeNode(1)
    root.right.right = TreeNode(5)
    
    print(countGoodNodes(root))

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

def pathSum(root: TreeNode, targetSum: int) -> int:
    prefix = {0: 1}
    def dfs(node, curr_sum):
        if not node:
            return 0
        curr_sum += node.val
        count = prefix.get(curr_sum - targetSum, 0)
        prefix[curr_sum] = prefix.get(curr_sum, 0) + 1
        count += dfs(node.left, curr_sum)
        count += dfs(node.right, curr_sum)
        prefix[curr_sum] -= 1
        return count
    return dfs(root, 0)

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

class Solution:
    def longestZigZag(self, root):
        self.ans = 0
        def dfs(node, is_left, length):
            if node is None:
                return
            self.ans = max(self.ans, length)
            if is_left:
                dfs(node.left, False, length + 1)
                dfs(node.right, True, 1)
            else:
                dfs(node.right, True, length + 1)
                dfs(node.left, False, 1)
        dfs(root, True, 0)
        dfs(root, False, 0)
        return self.ans

# Пример использования:
if __name__ == "__main__":
    # Формирование дерева
    n4 = TreeNode(4)
    n5 = TreeNode(5)
    n2 = TreeNode(2, n4, n5)
    n3 = TreeNode(3)
    root = TreeNode(1, n2, n3)

    sol = Solution()
    print(sol.longestZigZag(root))

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

def lowestCommonAncestor(root, p, q):
    if root is None:
        return None
    if root == p or root == q:
        return root
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left is not None and right is not None:
        return root
    return left if left is not None else right

if __name__ == "__main__":
    # Пример построения дерева
    root = TreeNode(3)
    root.left = TreeNode(5)
    root.right = TreeNode(1)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(2)
    root.right.left = TreeNode(0)
    root.right.right = TreeNode(8)
    lca = lowestCommonAncestor(root, root.left, root.right)
    print(lca.val if lca else "None")

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

def rightSideView(root):
    if not root:
        return []
    result = []
    from collections import deque
    queue = deque([root])
    while queue:
        level_length = len(queue)
        for i in range(level_length):
            node = queue.popleft()
            if i == level_length - 1:
                result.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return result

# Пример использования:
if __name__ == "__main__":
    # Построим примерное бинарное дерево:
    #       1
    #      / \
    #     2   3
    #      \   \
    #       5   4
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.right = TreeNode(5)
    root.right.right = TreeNode(4)
    print(rightSideView(root))  # Ожидаемый вывод: [1, 3, 4]

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

def maxLevelSum(root):
    from collections import deque
    if not root:
        return 0
    max_sum = -float('inf')
    level = 1
    queue = deque([root])
    best_sum = -float('inf')
    while queue:
        cur_sum = 0
        size = len(queue)
        for _ in range(size):
            node = queue.popleft()
            cur_sum += node.val
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        if cur_sum > best_sum:
            best_sum = cur_sum
        level += 1
    return best_sum

# Пример использования:
# Построение бинарного дерева:
#         1
#        / \
#       7   0
#      / \
#     7  -8
if __name__ == "__main__":
    root = TreeNode(1)
    root.left = TreeNode(7)
    root.right = TreeNode(0)
    root.left.left = TreeNode(7)
    root.left.right = TreeNode(-8)
    print(maxLevelSum(root))  # Вывод: 7

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

def searchBST(root: TreeNode, val: int) -> TreeNode:
    while root:
        if root.val == val:
            return root
        elif root.val < val:
            root = root.right
        else:
            root = root.left
    return None

# Пример использования
if __name__ == "__main__":
    # Создание BST:
    #       4
    #      / \
    #     2   7
    #    / \
    #   1   3
    root = TreeNode(4)
    root.left = TreeNode(2)
    root.right = TreeNode(7)
    root.left.left = TreeNode(1)
    root.left.right = TreeNode(3)

    result = searchBST(root, 2)
    if result:
        print(result.val)  # Вывод: 2
    else:
        print("Не найдено")

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

def deleteNode(root, key):
    if not root:
        return None
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        curr = root.right
        while curr.left:
            curr = curr.left
        root.val = curr.val
        root.right = deleteNode(root.right, curr.val)
    return root

def canVisitAllRooms(rooms):
    visited = set()
    stack = [0]
    while stack:
        room = stack.pop()
        if room not in visited:
            visited.add(room)
            for key in rooms[room]:
                if key not in visited:
                    stack.append(key)
    return len(visited) == len(rooms)

if __name__ == "__main__":
    # Пример использования:
    rooms = [[1], [2], [3], []]
    print(canVisitAllRooms(rooms))  # Expected output: True

def findCircleNum(isConnected):
    n = len(isConnected)
    visited = [False] * n
    def dfs(i):
        for j in range(n):
            if isConnected[i][j] == 1 and not visited[j]:
                visited[j] = True
                dfs(j)
    count = 0
    for i in range(n):
        if not visited[i]:
            visited[i] = True
            dfs(i)
            count += 1
    return count

# Пример использования:
if __name__ == '__main__':
    isConnected = [
        [1, 1, 0],
        [1, 1, 0],
        [0, 0, 1]
    ]
    print(findCircleNum(isConnected))

from collections import defaultdict

def minReorder(n, roads):
    # Построение графа, где для каждого ребра (u, v) добавляем:
    # - из u в v с меткой 1 (ребро направлено от u к v, требуется переориентация)
    # - из v в u с меткой 0 (ребро уже идёт в сторону 0, если использовать эту связь)
    graph = defaultdict(list)
    for u, v in roads:
        graph[u].append((v, 1))
        graph[v].append((u, 0))
        
    res = 0
    visited = set()
    
    def dfs(node):
        nonlocal res
        visited.add(node)
        for neighbor, cost in graph[node]:
            if neighbor not in visited:
                res += cost
                dfs(neighbor)
    
    dfs(0)
    return res

# Пример использования:
n = 6
roads = [[0, 1], [1, 3], [2, 3], [4, 0], [4, 5]]
print(minReorder(n, roads)) # Ожидаемый результат: 3

def calcEquation(equations, values, queries):
    graph = {}
    for (a, b), k in zip(equations, values):
        if a not in graph:
            graph[a] = []
        if b not in graph:
            graph[b] = []
        graph[a].append((b, k))
        graph[b].append((a, 1/k))
        
    def dfs(src, target, visited):
        if src == target:
            return 1.0
        visited.add(src)
        for neighbour, value in graph[src]:
            if neighbour in visited:
                continue
            product = dfs(neighbour, target, visited)
            if product != -1:
                return value * product
        return -1
    
    res = []
    for x, y in queries:
        if x not in graph or y not in graph:
            res.append(-1.0)
        elif x == y:
            res.append(1.0)
        else:
            res.append(dfs(x, y, set()))
    return res

if __name__ == "'__main__'":
    equations = [["a", "b"], ["b", "c"]]
    values = [2.0, 3.0]
    queries = [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]]
    print(calcEquation(equations, values, queries))

import collections

def nearest_exit(maze, entrance):
    rows = len(maze)
    cols = len(maze[0])
    ex, ey = entrance
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    visited = {(ex, ey)}
    queue = collections.deque([(ex, ey, 0)])
    while queue:
        x, y, steps = queue.popleft()
        if (x, y) != (ex, ey) and (x == 0 or x == rows - 1 or y == 0 or y == cols - 1):
            return steps
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == '.' and (nx, ny) not in visited:
                visited.add((nx, ny))
                queue.append((nx, ny, steps + 1))
    return -1

# Пример использования:
maze = [
    ['+', '+', '.', '+'],
    ['.', '.', '.', '+'],
    ['+', '+', '+', '.']
]
entrance = (1, 0)
print(nearest_exit(maze, entrance))

def orangesRotting(grid):
    from collections import deque
    if not grid:
        return -1
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 2:
                queue.append((i, j, 0))  # i, j, minute
            elif grid[i][j] == 1:
                fresh += 1
    minutes = 0
    directions = [(1,0),(-1,0),(0,1),(0,-1)]
    while queue:
        i, j, minutes = queue.popleft()
        for di, dj in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == 1:
                grid[ni][nj] = 2
                fresh -= 1
                queue.append((ni, nj, minutes + 1))
    return minutes if fresh == 0 else -1

# Пример использования:
if __name__ == ""__main__"":
    grid = [
        [2,1,1],
        [1,1,0],
        [0,1,1]
    ]
    result = orangesRotting(grid)
    print(result)

import random

def kth_largest(nums, k):
    # k-е по величине число соответствует элементу с индексом len(nums) - k
    return quickselect(nums, 0, len(nums) - 1, len(nums) - k)

def quickselect(nums, left, right, index):
    if left == right:
        return nums[left]
    pivot_index = random.randint(left, right)
    pivot_index = partition(nums, left, right, pivot_index)
    if index == pivot_index:
        return nums[pivot_index]
    elif index < pivot_index:
        return quickselect(nums, left, pivot_index - 1, index)
    else:
        return quickselect(nums, pivot_index + 1, right, index)

def partition(nums, left, right, pivot_index):
    pivot_value = nums[pivot_index]
    nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
    store_index = left
    for i in range(left, right):
        if nums[i] < pivot_value:
            nums[store_index], nums[i] = nums[i], nums[store_index]
            store_index += 1
    nums[right], nums[store_index] = nums[store_index], nums[right]
    return store_index

if __name__ == '__main__':
    arr = [3, 2, 1, 5, 6, 4]
    k = 2
    print(kth_largest(arr, k))  # Expected output: 5

import heapq

class SmallestInfiniteSet:
    def __init__(self):
        self.min_heap = []
        self.added = set()
        self.curr = 1

    def popSmallest(self):
        if self.min_heap:
            smallest = heapq.heappop(self.min_heap)
            self.added.remove(smallest)
            return smallest
        else:
            smallest = self.curr
            self.curr += 1
            return smallest

    def addBack(self, num):
        if num < self.curr and num not in self.added:
            heapq.heappush(self.min_heap, num)
            self.added.add(num)

# Пример использования:
if __name__ == '__main__':
    s = SmallestInfiniteSet()
    print(s.popSmallest()) # вывод: 1 
    print(s.popSmallest()) # вывод: 2 
    s.addBack(1)
    print(s.popSmallest())  # вывод: 1 
    print(s.popSmallest())  # вывод: 3 

import heapq

def max_subsequence_score(nums1, nums2, k):
    # Создаем список пар и сортируем по значениям второго массива по убыванию
    pairs = list(zip(nums1, nums2))
    pairs.sort(key=lambda pair: pair[1], reverse=True)
    
    current_sum = 0
    min_heap = []
    best_score = 0
    
    # Проходим по парам, используя значение из второго массива как потенциальный минимум  
    for a, b in pairs:
        heapq.heappush(min_heap, a)
        current_sum += a
        # Если размер кучи превышает k, удаляем наименьшее значение, чтобы сохранить сумму максимальной
        if len(min_heap) > k:
            current_sum -= heapq.heappop(min_heap)
        # Когда размер кучи равен k, обновляем лучший результат
        if len(min_heap) == k:
            best_score = max(best_score, current_sum * b)
    
    return best_score

# Пример использования:
if __name__ == "__main__":
    nums1 = [1, 3, 3, 2]
    nums2 = [2, 1, 3, 4]
    k = 3
    print(max_subsequence_score(nums1, nums2, k))

def total_cost(costs, k):
    n = len(costs)
    # Если k больше количества кандидатов, используем минимальное значение
    k = min(k, n)
    
    # Вычисление префиксных сумм для первых k элементов
    prefix = [0] * (k + 1)
    for i in range(1, k + 1):
        prefix[i] = prefix[i - 1] + costs[i - 1]
    
    # Вычисление суффиксных сумм для последних k элементов
    suffix = [0] * (k + 1)
    for j in range(1, k + 1):
        suffix[j] = suffix[j - 1] + costs[n - j]
    
    res = float("inf")
    # Перебор вариантов: i работников слева и k-i с конца
    for i in range(0, k + 1):
        cost_sum = prefix[i] + suffix[k - i]
        if cost_sum < res:
            res = cost_sum
    return res

if __name__ == "__main__":
    # Пример использования:
    costs = [10, 3, 3, 6, 2]
    k = 3
    print(total_cost(costs, k))

def guess(num):
    # Placeholder implementation; normally provided by the system.
    # For example, suppose the target number is 42.
    target = 42
    if num == target:
        return 0
    elif num > target:
        return -1
    else:
        return 1

def guessNumber(n):
    left = 1
    right = n
    while left <= right:
        mid = (left + right) // 2
        res = guess(mid)
        if res == 0:
            return mid
        elif res < 0:
            right = mid - 1
        else:
            left = mid + 1
    return -1  # Number not found

if __name__ == "__main__":
    n = 100
    number = guessNumber(n)
    print("Guessed number is:", number)

def successfulPairs(spells, potions, success):
    potions.sort()
    n = len(potions)
    res = []
    import bisect
    for spell in spells:
        target = (success + spell - 1) // spell
        index = bisect.bisect_left(potions, target)
        res.append(n - index)
    return res

if __name__ == "__main__":
    spells = [5, 1, 3]
    potions = [1, 2, 3, 4, 5]
    success = 7
    print(successfulPairs(spells, potions, success))

def findPeakElement(nums):
    left = 0
    right = len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[mid + 1]:
            right = mid
        else:
            left = mid + 1
    return left

if __name__ == "__main__":
    nums = [1, 2, 3, 1]
    print(findPeakElement(nums))  # Вывод: 2

def minEatingSpeed(piles, h):
    left, right = 1, max(piles)
    while left < right:
        mid = (left + right) // 2
        hours = sum((pile + mid - 1) // mid for pile in piles)
        if hours <= h:
            right = mid
        else:
            left = mid + 1
    return left

if __name__ == '__main__':
    # Пример использования
    piles = [30, 11, 23, 4, 20]
    h = 6
    print(minEatingSpeed(piles, h))

def letter_combinations(digits):
    if not digits:
        return []
    mapping = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz'
    }
    result = []

    def backtrack(index, path):
        if index == len(digits):
            result.append(path)
            return
        for letter in mapping[digits[index]]:
            backtrack(index + 1, path + letter)

    backtrack(0, '')
    return result

# Пример использования:
if __name__ == '__main__':
    digits = '23'
    combinations = letter_combinations(digits)
    print(combinations)

def combinationSum3(k, n):
    result = []
    def backtrack(start, path, total):
        if len(path) == k and total == n:
            result.append(path[:])
            return
        if len(path) > k or total > n:
            return
        for i in range(start, 10):
            path.append(i)
            backtrack(i + 1, path, total + i)
            path.pop()
    backtrack(1, [], 0)
    return result

if __name__ == "__main__":
    k = 3
    n = 7
    print(combinationSum3(k, n))

def tribonacci(n):
    if n == 0:
        return 0
    if n <= 2:
        return 1
    a, b, c = 0, 1, 1
    for _ in range(3, n+1):
        a, b, c = b, c, a + b + c
    return c

if __name__ == "'__main__":
    n = int(input().strip())
    print(tribonacci(n))

def minCostClimbingStairs(cost):
    a, b = 0, 0
    for x in cost:
        a, b = b, x + min(a, b)
    return min(a, b)

if __name__ == "'__main__'":
    cost = [10, 15, 20]    # Пример ввода
    print(minCostClimbingStairs(cost))

def rob(nums):
    prev, curr = 0, 0
    for num in nums:
        prev, curr = curr, max(curr, prev + num)
    return curr

if __name__ == "__main__":
    test_nums = [1, 2, 3, 1]
    print(rob(test_nums))

def domino_tromino_tiling(n: int) -> int:
    if n == 0:
        return 1
    if n == 1:
        return 1
    if n == 2:
        return 2
    # Используем оптимизированную версию: dp[n] = 2*dp[n-1] + dp[n-3]
    dp0, dp1, dp2 = 1, 1, 2
    for i in range(3, n + 1):
        dp = 2 * dp2 + dp0
        dp0, dp1, dp2 = dp1, dp2, dp
    return dp2

if __name__ == "'__main__'":
    n = 10
    print(domino_tromino_tiling(n))

import math

def unique_paths(m, n):
    return math.comb(m+n-2, m-1)

if __name__ == "__main__":
    m = 3
    n = 7
    print(unique_paths(m, n))

def longest_common_subsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

# Пример использования:
if __name__ == "__main__":
    text1 = "abcde"
    text2 = "ace"
    print(longest_common_subsequence(text1, text2))  # Выведет 3

def max_profit(prices: list<int>, fee: int) -> int:
    cash = 0
    hold = -prices[0]
    for price in prices[1:]:
        cash = max(cash, hold + price - fee)
        hold = max(hold, cash - price)
    return cash

# 'Пример использования'
if __name__ == '__main__':
    prices = [1, 3, 2, 8, 4, 9]
    fee = 2
    print(max_profit(prices, fee))  # Вывод: 8

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    return dp[m][n]

if __name__ == "__main__":
    word1 = input().strip()
    word2 = input().strip()
    print(minDistance(word1, word2))

def count_bits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

# 'Пример использования'
if __name__ == '__main__':
    n = 10
    print(count_bits(n))

def single_number(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

# Пример использования:
if __name__ == "__main__":
    nums = [4, 1, 2, 1, 2]
    print(single_number(nums))

def min_flips(a: int, b: int, c: int) -> int:
    flips = 0
    # Пока хотя бы одно число не обнулится
    while a or b or c:
        a_bit = a & 1
        b_bit = b & 1
        c_bit = c & 1
        # Если бит c равен 0, оба бита a и b должны быть 0
        if c_bit == 0:
            if a_bit == 1:
                flips += 1
            if b_bit == 1:
                flips += 1
        # Если бит c равен 1, хотя бы один из битов a и b должен быть 1
        else:
            if (a_bit | b_bit) == 0:
                flips += 1
        a //= 2
        b //= 2
        c //= 2
    return flips

if __name__ == "__main__":
    # Пример использования:
    a_val = 2
    b_val = 6
    c_val = 5
    print(f"Minimum flips: {min_flips(a_val, b_val, c_val)}")

class TrieNode:
    def __init__(self):
        self.children = { }
        self.end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.end_of_word = True
        
    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.end_of_word

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

if __name__ == '__main__':
    trie = Trie()
    trie.insert("apple")
    print(trie.search("apple"))  -#> True
    print(trie.search("app"))    -#> False
    print(trie.startsWith("app")) -#> True

import bisect

def suggestedProducts(products, searchWord):
    products.sort()
    ans = []
    prefix = ""
    for ch in searchWord:
        prefix += ch
        idx = bisect.bisect_left(products, prefix)
        suggestion = []
        for i in range(idx, min(idx+3, len(products))):
            if products[i].startswith(prefix):
                suggestion.append(products[i])
            else:
                break
        ans.append(suggestion)
    return ans

# Пример использования функции
if __name__ == "'__main__'":
    products = ['mobile', 'mouse', 'moneypot', 'monitor', 'mousepad']
    searchWord = 'mouse'
    print(suggestedProducts(products, searchWord))

def eraseOverlapIntervals(intervals):
    # Сортируем интервалы по значению конца
    intervals.sort(key=lambda x: x[1])
    count = 0
    end = float('-inf')
    for interval in intervals:
        if interval[0] >= end:
            end = interval[1]
        else:
            count += 1
    return count

if __name__ == "__main__":
    # Пример использования:
    intervals = [[1,2], [2,3], [3,4], [1,3]]
    result = eraseOverlapIntervals(intervals)
    print(result)  # Ожидаемый вывод: 1

def findMinArrowShots(points):
    if not points:
        return 0
    # Сортировка по конечной точке интервала
    points.sort(key=lambda x: x[1])
    arrows = 1
    arrow_pos = points[0][1]
    # Проход по оставшимся интервалам
    for start, end in points[1:]:
        if start > arrow_pos:
            arrows += 1
            arrow_pos = end
    return arrows

# Пример использования:
if __name__ == "__main__":
    intervals = [[10, 16], [2, 8], [1, 6], [7, 12]]
    print(findMinArrowShots(intervals))

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack = []  # 'stack' хранит индексы
    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            idx = stack.pop()
            answer[idx] = i - idx
        stack.append(i)
    return answer

if __name__ == "__main__":
    temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
    print(dailyTemperatures(temperatures))

class StockSpanner:
    def __init__(self):
        self.stack = []

    def next(self, price: int) -> int:
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span

# Пример использования:
if __name__ == "__main__":
    stockSpanner = StockSpanner()
    # Пример входных данных
    prices = [100, 80, 60, 70, 60, 75, 85]
    # Ожидаемые span: [1, 1, 1, 2, 1, 4, 6]
    results = [stockSpanner.next(price) for price in prices]
    print(results)