Написать пост

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

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

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

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

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

Игра в камни IX

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

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

Задачи, роли и специализации Developer Relations специалистов 2022
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
Следите за новыми постами
Следите за новыми постами по любимым темам
1К открытий3К показов
Также рекомендуем
Обложка поста Как работает антивирус
Как работает антивирус
Рассказываем об истории антивирусов и о том, как софт ищет малвери.
Обложка поста Почему компании массово увольняют айтишников и правда ли IT при смерти
Почему компании массово увольняют айтишников и правда ли IT при смерти
IT-блогер Роман Сакутин рассказал, почему в IT происходят массовые увольнения, правда ли IT-сфера на грани смерти и какие профессионалы находится под ударом.
Обложка поста Аналитик данных: обзор профессии и курса от MDS
Аналитик данных: обзор профессии и курса от MDS
Разобрали профессию аналитика данных: в каких задачах он нужен, какие инструментами пользуется для работы, и рассказали, где можно их изучить.
Обложка поста Сотрудники Apple тестируют своего чат-бота
Сотрудники Apple тестируют своего чат-бота
Apple разработала собственного чат-бота на основе языковой модели по типу ChatGPT. Тесты чат-бота уже ведутся сотрудниками компании.