Игра Яндекс Практикума
Игра Яндекс Практикума
Игра Яндекс Практикума
Написать пост

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

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

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

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

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

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

Игра в камни IX

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

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

Python-интервью: что спрашивают и как успешно ответить
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К открытий15К показов
Также рекомендуем
🔥 Теперь 3D-модели можно крутить-вертеть прямо в Терминале благодаря Terminal3d
🔥 Теперь 3D-модели можно крутить-вертеть прямо в Терминале благодаря Terminal3d
Разработчик Лиам Илан представил Terminal3d — утилиту с открытым исходным кодом для просмотра 3D-моделей прямо в Терминале с помощью ASCII-графики
Редкие языки программирования: зачем они нужны и что на них пишут
Редкие языки программирования: зачем они нужны и что на них пишут
Современные разработчики все чаще обращаются к редким языкам программирования, чтобы решить специфические задачи проекта. Разбираемся, как и когда их нужно использовать.
Языки программирования, которые стоит начать учить в 2024 году
Языки программирования, которые стоит начать учить в 2024 году
Изучили популярность и сложность языков программирования, а также размер зарплат разработчиков, чтобы вам было проще сделать выбор.
PyTorch или TensorFlow — что выбрать
PyTorch или TensorFlow — что выбрать
IT-блогер Daniel Dan выпустил новое видео, в котором сравнил PyTorch или TensorFlow, их плюсы и минусы, а также ключевые различия.