Архив за 31 июля 2024

У меня есть хобби — решать задачи LeetCode непредназначенным для этого образом, часто при помощи запутанных однострочников. Такие самостоятельно накладываемые ограничения делают задачки интереснее и заставляют искать нестандартные решения.

Одним из ежедневных челленджей LeetCode была такая задача (я немного упростил её для понятности):

Есть список из уникальных строк битов, каждая из которых имеет длину . Сгенерировать новую строку длиной , отсутствующую в этом списке.

Например, если у нас есть список "010", "110", "111", то возможным решением будет "001". Задача с LeetCode имеет большой набор тестов — 183 тестовых сценариев с , а точную формулировку задачи можно найти здесь.

Я решил её, подобрав такое случайное порождающее значение (seed), что случайно генерируемые строки битов проходили бы все тестовые сценарии. Вот код решения:

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        random.seed((69299878 + sum(ord(c)*(i*j+111) for (i, n) in enumerate(nums) for (j, c) in enumerate(n))) % 999999999)
        return ''.join(random.choice('01') for _ in nums)

Можете попробовать это решение самостоятельно (оно должно работать, если LeetCode не обновил свой набор тестов. Если это произошло, сообщите мне об этом).

Ниже я расскажу, как это сделал.Читать полностью »