Эта статья взята из личного паблика: TechFlow, оригинальность непроста, прошу внимания
СегодняТемы LeetCodeВ 55-й статье давайте взглянем на 89-й код Грея в LeetCode.
Официальная сложность этого вопросаMedium, проходной балл составляет 48,9%, 639 лайков и 1545 отклонений. Это еще одна тема, в которой больше возражений, чем лайков.Я лично обнаружил, что эти темы с большим количеством возражений имеют особенность, то есть смысл вопроса относительно неясен, а намерение спрашивающего нелегко получить. Я не знаю, потому ли это, что иностранцы не очень хорошо понимают, поэтому они выдвинули так много возражений.
Давайте взглянем на истинное лицо этого вопроса.
смысл названия
В заголовке написано код Грея, код Грея представляет собой серию n-битных двоичных чисел. Эта строка чисел имеет такую характеристику, что первое число равно 0, а каждое число после 0 и предыдущее число начинаются с 0.только один двоичный битразные.
Задача даст нам неотрицательное целое число n и попросит сгенерировать n-битные коды Грея, то есть сгенерировать эти числа. И эти числа хранятся в базе 10.
Я не знаю, понимаете ли вы это, давайте посмотрим на пример.
Образец
Input: 2
Output: [0,1,3,2]
В приведенном выше примере ввод равен 2, что указывает на то, что числа состоят из двух двоичных цифр, а вывод — [0, 1, 3, 2]. Мы переводим 0, 1, 3, 2 в двоичные числа, 0 — это 00, 1 — это 01, 3 — это 11, а 2 — это 10. Аранжированные вместе 00, 01, 11, 10. Мы можем найти, что каждое число отличается от предыдущего числа на один двоичный бит.
В заголовке так много связанных описаний, но на самом деле очень много скрытой информации, которая не дана, и нам приходится догадываться самим. Например, каждое число может появиться только один раз, иначе последовательность бесконечна. Еще одна скрытая информация заключается в том, что такая последовательность не должна быть уникальной, но в заголовке не сказано, все ли допустимые последовательности могут пройти проверку или она должна возвращать результат с наименьшим лексикографическим порядком.
Даже если тема относительно неясна, скрытая информация не объясняется ясно, поэтому неудивительно, что все озадачены.
отвечать
Конечно, вышеперечисленные проблемы на самом деле не проблема. Мы не уверены, что узнаем об этом, попробовав один раз. Суть в том, как найти решение.
Пытаться думать бесполезно, все равно нужно сначала проанализировать и собрать какую-то информацию. Во-первых, n, указанное в заголовке, ограничивает количество двоичных битов, которые можно использовать для каждого числа. Существует $2^n$ типов чисел, которые могут быть представлены n двоичными битами, и мы не можем знать, можно ли соединить так много чисел последовательно. Если предположить, что это возможно, то проблема на самом деле заключается в том, как разместить число $2^n$.
Так что суть дела в том, чтобынайти такую последовательность, согласно нашим предыдущим методам решения всех перестановок и различных перестановок, мы можем с большой вероятностью связать это с задачей поиска.
Продолжайте поиск по идее, остальное просто, наша начальная точка поиска — 0. Вопрос требует, чтобы двоичные биты каждых двух соседних чисел отличались только на единицу, тогда мы можемПройдите эти биты, ища узел преемника 0. Также для каждого узла-преемника мы можем использовать один и тот же метод для поиска его преемников. Кроме того, код Грея не может содержать повторяющихся элементов, мы можем добавить обрезку при поиске.
Этот набор на самом деле представляет собой классический процесс поиска.
Если мы изменим способ мышления, хотя мы можем получить то же самое решение, процесс мышления будет другим. Как изменить образ мышления, это на самом деле просто, скажем мыДумайте об этом как о проблеме теории графов. То есть каждое число является узлом в графе. Если разница между двумя числами составляет только одну двоичную цифру, то они соединены ребром. Вся проблема заключается в том, что мы начинаем с 0 и находим все связанные узлы.
Для задачи обхода по графу метод очень фиксированный, то есть перебор. То есть, если вы думаете под этим углом, вам будет проще думать о поиске выше, и вся ссылка на мышление будет короче. Это также причина, по которой многие великие боги любят учитывать граф при моделировании.
После того, как все это будет понято, написание кода станет само собой разумеющимся.Весь основной код на самом деле не длинный:
class Solution:
def grayCode(self, n: int) -> List[int]:
ret = [0]
elements = {0}
def dfs(cur):
# 遍历与cur唯一不同的二进制位
for i in range(n):
# 针对这一维做亦或，将0变1，1变0
nxt = cur ^ (1 << i)
if nxt in elements:
continue
# 记录答案，继续往下遍历
elements.add(nxt)
ret.append(nxt)
dfs(nxt)
dfs(0)
return ret
Суммировать
С точки зрения идеи и окончательного кода АС, сложность этого вопроса должна быть очень низкой, что на самом деле так и есть, проходимость этого вопроса близка к 50%, что уже является следующим уровнем средней сложности. . Но думать важнее, чем делать правильно. Абстрактное моделирование с помощью теории графов — очень распространенный метод в задачах алгоритмов, который более ценен, чем сама проблема.
Если вы читали вчерашнюю статью, то обнаружите, что вчерашние 87 вопросов по сути являются методом графового моделирования. Но с точки зрения производительности, эти два вопроса действительно совершенно разные. Рекомендуется хорошо ответить на эти два вопроса и испытать на себе яркие мысли и решения.
Сегодняшняя статья здесь, если вам понравилась эта статья, пожалуйста, приходите на волнукачество три, поддержите меня (Подписывайтесь, делайте репосты, лайкайте).
В этой статье используетсяmdniceнабор текста