У меня есть хобби — решать задачи 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 не обновил свой набор тестов. Если это произошло, сообщите мне об этом).
Ниже я расскажу, как это сделал.
