Виммельбух, 3, перетяжка
Виммельбух, 3, перетяжка
Виммельбух, 3, перетяжка
Написать пост

7 математических задач на LeetCode для продвинутых

Аватарка пользователя Мария Кривоченко
Мария Кривоченко

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

2К открытий17К показов

LeetCode — одна из самых популярных платформ для решения задач по программированию и подготовки к техническим собеседованиям. Мы выбрали 7 математических задач уровня Medium и Hard и предлагаем вам проверить свои навыки.

У каждой задачи может быть несколько решений — на разных языках программирования. Мы предложили варианты на Python от участника сообщества.

Игра в камни IX

Алиса и Боб играют в камни. Они выстроили ряд из n камней, каждому из которых присвоили значение. То есть у них есть массив целых чисел stones, где stones[i] — значение i-го камня.

Алиса и Боб играют по очереди, Алиса ходит первой. На каждом ходу можно убрать любой камень из stones. Если сумма значений всех убранных камней делится на 3, участник проигрывает. Алиса также проигрывает, если камни заканчиваются.

Система для Хекслета, релиз ChatGPT Omni и Джейло на репите: Ретроперспектива недели с Кириллом Мокевниным
tproger.ru

Предполагая, что игроки выбрали оптимальные стратегии, верните true, если победит Алиса, и false, если победит Боб.

Решение
			# Time:  O(n)
# Space: O(1)

import collections


class Solution(object):
    def stoneGameIX(self, stones):
        """
        :type stones: List[int]
        :rtype: bool
        """
        count = collections.Counter(x%3 for x in stones)
        if count[0]%2 == 0:
            # iff both counts are not zero, then alice takes the least one at first, the remains are deterministic for bob to lose:
            # - assumed count[1] is the least one:
            #   1(,1,2)*,2,(,2)* => bob loses
            #            ^
            # - assumed count[2] is the least one:
            #   2(,2,1)*,1,(,1)* => bob loses
            #            ^
            return count[1] and count[2]
        # iff abs(count[1] - count[2]) >= 3, then alice takes the most one at first, the remains are deterministic for bob to lose:
        # - assumed count[1] is the most one
        #   1(,1,2)*,0,1(,2,1)*,1,(,1)* => bob loses
        #                       ^
        #   1(,1,2)*,1,0,1,(,1)* => bob loses
        #                ^
        # - assumed count[2] is the most one
        #   2(,2,1)*,0,2(,1,2)*,2,(,2)* => bob loses
        #                       ^
        #   2(,2,1)*,2,0,2,(,2)* => bob loses
        #                ^
        return abs(count[1]-count[2]) >= 3

Сколько существует способов достичь пункта назначения через k шагов

Вы находитесь на бесконечной числовой оси на точке startPos, положение точки равно положительному целому числу. Цель — прийти к точке endPos, положение которой также равно положительному целому числу. За один шаг вы можете переместиться на одну позицию влево или вправо.

Вычислите, сколько способов достичь endPos существует, если нужно совершить k шагов (k также равно положительному целому числу)? Количество способов может быть большим, поэтому выведите значение в формате 10^9 + 7.

Решение
			# Time:  O(k)
# Space: O(k)

# combinatorics
class Solution(object):
    def numberOfWays(self, startPos, endPos, k):
        """
        :type startPos: int
        :type endPos: int
        :type k: int
        :rtype: int
        """
        MOD = 10**9+7
        fact, inv, inv_fact = [[1]*2 for _ in xrange(3)]
        def nCr(n, k):
            while len(inv) <= n:  # lazy initialization
                fact.append(fact[-1]*len(inv) % MOD)
                inv.append(inv[MOD%len(inv)]*(MOD-MOD//len(inv)) % MOD)  # https://cp-algorithms.com/algebra/module-inverse.html
                inv_fact.append(inv_fact[-1]*inv[-1] % MOD)
            return (fact[n]*inv_fact[n-k] % MOD) * inv_fact[k] % MOD

        r = k-abs(endPos-startPos)
        return nCr(k, r//2) if r >= 0 and r%2 == 0 else 0

Найдите палиндром определенной длины

Палиндром — это число, которое читается одинаково справа налево и слева направо.

queries — массив целых чисел; intLength — положительное целое число. Определите массив answer, где answer[i] — либо меньший палиндром queries[i], длина которого равна intLength либо -1, если такого палиндрома не существует.

Решение
			# Time:  O(n * l)
# Space: O(1)

# math
class Solution(object):
    def kthPalindrome(self, queries, intLength):
        """
        :type queries: List[int]
        :type intLength: int
        :rtype: List[int]
        """
        def reverse(x):
            result = 0
            while x:
                result = result*10+x%10
                x //= 10
            return result

        def f(l, x):
            x = 10**((l-1)//2)+(x-1)
            if x > 10**((l+1)//2)-1:
                return -1
            return x*10**(l//2)+reverse(x//10 if l%2 else x)

        return [f(intLength, x) for x in queries]


# Time:  O(n * l)
# Space: O(l)
# math
class Solution2(object):
    def kthPalindrome(self, queries, intLength):
        """
        :type queries: List[int]
        :type intLength: int
        :rtype: List[int]
        """
        def f(l, x):
            if 10**((l-1)//2)+(x-1) > 10**((l+1)//2)-1:
                return -1
            s = str(10**((l-1)//2)+(x-1))
            return int(s+s[::-1][l%2:])

        return [f(intLength, x) for x in queries]

Сколько прямых линий нужно, чтобы построить диаграмму

У вас есть двумерный массив целых чисел stockPrices. stockPrices[i] = [day_i, price_i] — цена акции в день i. Линейный график, отражающий динамику цен, создается из точек stockPrices[i], лежащих на плоскости XY, где ось X — день, а ось Y — цена. Один из таких графиков показан ниже:

7 математических задач на LeetCode для продвинутых 1

Найдите минимальное число линий, которое нужно, чтобы объединить все точки на плоскости и построить график.

Решение
			# Time:  O(nlogn)
# Space: O(1)

# sort, math, gcd
class Solution(object):
    def minimumLines(self, stockPrices):
        """
        :type stockPrices: List[List[int]]
        :rtype: int
        """
        def gcd(a, b):
            while b:
                a, b = b, a%b
            return a
    
        stockPrices.sort()
        result = 0
        prev = None
        for i in xrange(1, len(stockPrices)):
            dy, dx = stockPrices[i][1]-stockPrices[i-1][1], stockPrices[i][0]-stockPrices[i-1][0]
            g = gcd(dy, dx)
            if not prev or prev != (dy//g, dx//g):
                prev = (dy//g, dx//g)
                result += 1
        return result

Сократить произведение диапазона целых чисел

У вас есть два целых числа left и right, где left <= right. Вычислите произведение всех целых чисел, входящих в диапазон [left, right]. Затем сократите произведение, выполнив следующие действия:

  • уберите все нули в конце получившегося числа. 
  • если в получившемся числе больше десяти цифр, представьте его в формате <pre>...<suf>, где <pre> — первые пять цифр, а <suf> — последние.
  • представьте получившееся число в виде строки <pre>...<suf>eC.
Решение
			# Time:  O(r - l)
# Space: O(1)

import math


class Solution(object):
    def abbreviateProduct(self, left, right):
        """
        :type left: int
        :type right: int
        :rtype: str
        """
        PREFIX_LEN = SUFFIX_LEN = 5
        MOD = 10**(PREFIX_LEN+SUFFIX_LEN)
        curr, zeros = 1, 0
        abbr = False
        for i in xrange(left, right+1):
            curr *= i
            while not curr%10:
                curr //= 10
                zeros += 1
            q, curr = divmod(curr, MOD)
            if q:
                abbr = True
        if not abbr:
            return "%se%s" % (curr, zeros)
        decimal = reduce(lambda x, y: (x+y)%1, (math.log10(i) for i in xrange(left, right+1)))
        prefix = str(int(10**(decimal+(PREFIX_LEN-1))))
        suffix = str(curr % 10**SUFFIX_LEN).zfill(SUFFIX_LEN)
        return "%s...%se%s" % (prefix, suffix, zeros)

Почитайте число анаграмм

У вас есть строка s, в которой находятся одно или несколько слов. Каждая пара слов разделена пробелом.

Строка t — анаграмма строки s, i-е слово строки t — может быть анаграммой только i-го слова строки s. Например, acb dfe — анаграмма abc def, а def cab и adc bef — нет.

Вычислите число анаграмм s. Их количество может быть большим, поэтому выведите значение в формате 10^9 + 7.

Решение
			# Time:  O(n)
# Space: O(n)

import collections


# combinatorics
class Solution(object):
    def countAnagrams(self, s):
        """
        :type s: str
        :rtype: int
        """
        MOD = 10**9+7
        fact, inv, inv_fact = [[1]*2 for _ in xrange(3)]
        def lazy_init(n):
            while len(inv) <= n:  # lazy initialization
                fact.append(fact[-1]*len(inv) % MOD)
                inv.append(inv[MOD%len(inv)]*(MOD-MOD//len(inv)) % MOD)  # https://cp-algorithms.com/algebra/module-inverse.html
                inv_fact.append(inv_fact[-1]*inv[-1] % MOD)

        def factorial(n):
            lazy_init(n)
            return fact[n]

        def inv_factorial(n):
            lazy_init(n)
            return inv_fact[n]

        def count(j, i):
            result = 1
            cnt = collections.Counter()
            for k in  xrange(j, i+1):
                cnt[s[k]] += 1
            result = factorial(sum(cnt.itervalues()))
            for c in cnt.itervalues():
                result = (result*inv_factorial(c))%MOD
            return result

        result = 1
        j = 0
        for i in xrange(len(s)):
            if i+1 != len(s) and s[i+1] != ' ':
                continue
            result = (result*count(j, i))%MOD
            j = i+2
        return result

Проверьте, реально ли добраться до точки

Есть бесконечно большая сетка. Вы находитесь в точке (1, 1) и должны добраться до (targetX, targetY), используя определенное число шагов. targetX и targetY — целые числа.

За один шаг вы можете переместиться из точки (x, y) в любую из следующих:

  • (x, y – x);
  • (x – y, y);
  • (2 * x, y);
  • (x, 2 * y).

Определите, можете ли вы добраться до (targetX, targetY) из (1, 1), верните true, если да, иначе верните false.

Решение
			# Time:  O(log(min(a, b)))
# Space: O(1)

# number theory
class Solution(object):
    def isReachable(self, targetX, targetY):
        """
        :type targetX: int
        :type targetY: int
        :rtype: bool
        """
        def gcd(a, b):
            while b:
                a, b = b, a%b
            return a
    
        g = gcd(targetX, targetY)
        return g == (g&~(g-1))  # co-prime other than factor 2
Следите за новыми постами
Следите за новыми постами по любимым темам
2К открытий17К показов
Также рекомендуем
🔥 У Яндекса появился аналог GitHub Copilot для помощи с написанием кода
🔥 У Яндекса появился аналог GitHub Copilot для помощи с написанием кода
Яндекс запускает Yandex Code Assistant — аналог GitHub Copilot для российских разработчиков. Этот ИИ-ассистент помогает генерировать продолжение кода на популярных языках, таких как C++, Go, Java и Python
Работа с JSON и XML в Python: парсинг, генерация и валидация
Работа с JSON и XML в Python: парсинг, генерация и валидация
Работа с JSON и XML в Python. Показываем варианты использования. Рассматриваем пошаговую инструкцию и основные способы работы с JSON и XML в Python ✔ Tproger
Как сделать свою нейросеть за 10 минут на Python
Как сделать свою нейросеть за 10 минут на Python
IT-блогер Хауди Хо рассказал в новом видео, как сделать собственную нейросеть на языке Python всего за 10 минут.
🔥 Python, Go, Ruby — сайты создателей популярнейших языков собрали в одном месте
🔥 Python, Go, Ruby — сайты создателей популярнейших языков собрали в одном месте
Свежий проект собрал личные сайты создателей популярных языков программирования Python, Go и Ruby в одном месте, но столкнулся с техническими трудностями, такими как высокая загрузка процессора