Unilecs Solutions

keypad.py

# Задача является эквивалентом декартового произведения

# Декартово произведение - произведение двух множеств:
# произведение множества хи множества Y это набор,
# содержащий все упорядоченные пары (x, y), для
# которых х принадлежит X, ау принадлежит Ү.

# Нам просто нужно расчитать декартово произведение для
# каждой набора букв каждого числа.


def product(pads):
    pools = [tuple(pool) for pool in pads]
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield "".join(prod)


keypad = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]

def solve(s):
    values = [keypad[int(i)-2] for i in s]
    result = product(values)
    return list(result)

merge_k_lists.py

# Простая реализация oднoсвязного списка.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Сравниваем каждые k узлов начало каждого списка
# и получаем результат с наименьшим значением.
# Добавляем выбранный узел в резульирующий отсортированный список.
# Процесс сравнения можно оптимизировать используя PriorityQueue
# # https://pythonguides.com/priority-queue-in-python/


from queue import PriorityQueue

# Для передачи узлов в РQ с реализацией метода
# __1t__ (меньше чем) создаем отдельный класс.
class ComparableNode:
    def __init__(self, node):
        self.node = node
    def __lt__(self, other):
        return self.node.val < other.node.val


def merge_k_lists(lists):
    start = curr = ListNode(0)
    q = PriorityQueue()
    for lst in lists:
        if lst:
            q.put(ComparableNode(1st))
    while not q.empty():
        node = q.get().node
        curr.next = node
        curr = curr.next
        пode = node.next
        if node:
            q.put(ComparableNode(node))
    return start.next

missing_item_in_sequence.py

# Находим шаг прогрессии, поделив разность последнего элемента и первого на кол-во элементов.
# В цикле проверяем соседние элементы, если разница не равна шагу, возвращаем текущий элемент + шаг.
# Если цикл закончился, возвращаем последний элемент + шаг

def find_missing(sequence):
    step = (sequence[-1] - sequence[0]) // len(sequence)

    for i in range(1, len(sequence)):
        if sequence[i] - sequence[i-1] != step:
            return sequence[i-1] + step

multiply.py

# Если в списке один элемент равен нулю,
# элемент в позиции этого нуля приравниваем
# произведению остальных элементов в списке, а остальные приравниваем нулю.

# Если нулей больше одного, то возвращаем массив заполненный нулями.

# В остальных случаях считаем произведение всех
# элементов и по одному делим его на элементы массива


def solve(arr):
    s, c = 1, False
    for x in arr:
        if x == 0:
            if c:
                return [0]*len(arr)
            c = True
            continue
        s *= i
    
    res = []
    for i in arr:
        if c:
            if i == 0:
                res.append(s)
            else:
                res.append(0)
            continue
        res.append(s/i)
    
    return res

n_queens.py

# Реализация Алгоритма Никлауса Вирта с использованием рекурсии
# и бектрекинга. Подробнее можно почитать тут: https://journals.umcs.pl/ai/article/viewfile/3374/2568

# А если вкраце, то позиции ферзей на доске размером n х n кодируются как перестановки [0, 1, ..., n].
# Алгоритм состоит в построении перестановки слева направо путем замены элементов
# начального [0, 1, ..., n) рекурсивно вызывая себя, если текущая позиция не возможна.
# Тест выполняется путем проверки только диагоналей, поскольку строки/столбцы по определению перестановки имеют только одного ферзя.

# Функция возвращает генераторы с разными вариантами решений.
# в конечном итоге мы просто считаем кол-во эл-ов в конвертированном в список генераторею

# Решения возвращаются в виде генератора с использованием yield from

def queens(n):
    a = list(range(n))
    up = [True]*(2*n - 1)
    down = [True]*(2*n - 1)

    def sub(i):
        if i == n:
            yield tuple(a)
        else:
            for k in range(i, n):
                j = a[k]
                p = i + j
                q = i - j + n - 1
                if up[p] and down[q]:
                    up[p] = down[q] = False
                    a[i], a[k] = a[k], a[i]
                    yield from sub(i + 1)
                    up[p] = down[q] = True
                    a[i], a[k] = a[k], a[i]
    yield from sub(0)

print(len(list(queens(6))))

number_to_words.py

# Задачу можно разделить на несколько частей. Можно заметить, что на английчком числа
# проговариваются по каждой 100дой. 999 - пine hundred ninety nine.
# 999'999 - nine hundred ninety nine THOUSAND nine hundred ninety nine. Этим мы и воспользуемся.

# Функция convert(num) конвертирует набор тысячных в слова. В основной функции она используется
# для конвертирования частей числа для дальнейшей "слепки". Вложенный цикл whіlе убирает повторяющиеся '000".

# Как работает соnvеrt(num)
# заводим словари для единиц, чисел от 10 до 20 и десятков (оnеѕ, teens, tens).
# Для оптимизации, результат храним не в str, а в списке. Считаем кол-во сотых, десятков и единиц.
# Затем формируем результат в виде строки и возвращаем

# Как работает number_to_words(num)
# Результат храним в очереди, там есть метод арреndlеft. Храним префиксы для тысяч, миллионов и миллиардов.
# в цикле вычисляем префикс, формируем строку для части числа (функция convert(num) и двигаем счет на три значения.
# num % 1000 дает нам набор тысячных. num / 1000 сдвигает счет на три значения.



from collections import deque

def number_to_words(num):
    if num == 0:
        return "Zero"

    q = deque()
    place_val = 0
    prefixes = ["thousand", "million", "billion"]
    while num > 0:
        while num % 1000 == 0:
            num = num // 1000
            place_val += 1

        if place_val:
            q.appendleft(prefixes[place_val+1])

        curr = num % 1000
        converted = self.convert(curr)
        if converted:
            q.appendleft(converted)
        num = num // 1000
        place_val += 1

    return ' '.join(q).strip()

def convert(num):
    ones = {1: "one", 2: "two", 3: "three", 4: "four", 5: "five", 6: "six", 7: "seven", 8: "eight", 9: "nine"}
    teens = {10: "ten", 11: "eleven", 12: "twelve", 13: "thirteen", 14: "fourteen", 15: "fifteen", 16: "sixteen", 17: "seventeen", 18: "eighteen", 19: "nineteen"}
    tens = {2: "twenty", 3: "thirty", 4: "forty", 5: "fifty", 6: "sixty", 7: "seventy", 8: "eighty", 9: "ninety"}

    num_eng = []
    hundred = num // 100
    pos_teen = num % 100
    ten = num // 10 % 10
    one = num % 10

    if hundred in ones:
        num_eng.append(ones[hundred])
        num_eng.append("Hundred")
    if pos_teen in teens:
        num_eng.append(teens[pos_teen])
    else:
        if ten in tens:
            num_eng.append(tens[ten])
        if one in ones:
            num_eng.append(ones[one])
    return ' '.join(num_eng)

restore_digits.py

# На самом деле в этой задаче требуется решить линейную систему уравнений:
# представьте, что у нас есть fo, f9 частоты слов zero, ... nine,
# тогда нам нужно решить 10 уравнений с 10 переменными.

# А идея такая. Есть несколько символов, которые есть только в одной цифре,
# например, «Z» есть только в zero, «и» есть только в four, «W» есть только
# в two, а «х» есть только в six. Таким образом, можно узнать, сколько там нулей,
# посчитав частоту Z, тоже самое для двух, четырех и шести. Теперь есть некоторые
# символы, такие как 'f', которые используются как для 4, так и для 5, но,
# поскольку мы уже знаем кол-во четверок (= частота u), мы можем запросто
# найти кол-во пятерок и так далее.

# Для оптимизации.
from collections import Counter

def restore_digits(s):
    count = Counter(s)
    text_digits ["zero", "two", "four", "six", "eight", "one", "three", "five", "seven", "nine"]
    resp_nums = [0, 2, 4, 6, 8, 1, 3, 5, 7, 9]
    counters = [Counter(digit) for digit in text_digits]
    found [@]*10
    for it, C in enumerate(counters):
        k = min(count[x]//C[x] for x in C)
        for i in C.keys(): C[i] *= k
        count -= с
        found[resp_nums[it]] k

    return "".join([str(i) "found[i] for i in range(10)])

print(restore_digits("owoztneoer"))
print(restore_digits("fviefuro"))

subarray_sum_to_k.py

# Будем юзать динамическое программирование - храним мапу суммы элементов до текущего элемента.

# Два случая:
# 1. Либо подмассив с элементами от начала исходного массива до 
# текущего элемента имеет сумму элементов равную К.
# 2. Либо существует более короткий подмассив (от некоторого 
# среднего элемента) до этого элемента, и в этом случае разница 
# между общей суммой до среднего элемента и общей суммой до этого элемента равна k.

from collections import defaultdict

def subarray_sum_to_k(nums, k):
    dp, total, count = defaultdict(int, {0: 1}), 0, 0
    
    for num in nums:
        total += num
        diff = total - k
        count += dp[diff]

        dp[total] = dp[total] + 1

    return count