Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняСтатья 34 Темы LeetCodeВ статье относительно простые темы, многие из которых аналогичны предыдущим. Итак, сегодня мы сделали подборку и закончили следующие три вопроса 57, 59 и 60 за один раз.
Опять же, чтобы сэкономить место и обеспечить качество статьи, я пропустил все простые и небольшое количество средних и сложных вопросов в LeetCode. Легкие вопросы не сложные, даже новичкам вообще не нужно читать решение, хорошо подумать и надо уметь его получить. Поэтому я не буду занимать место.Если у вас есть какие-либо вопросы о Easy, которые вас интересуют, вы можете оставить мне сообщение в апплете ниже.
LeetCode 57 Вставить интервал
Первый вопрос 57 вопросов Вставить интервал, вставить интервал. Вопрос предназначен для того, чтобы дать набор интервалов и один интервал, требующийвставьте этот единственный интервал в коллекцию интервалов, если есть пересечение между двумя интервалами, их нужно объединить, и требуется конечный результат после объединения. С точки зрения названия, это в основном то же самое, что и проблема слияния интервалов, о которой мы говорили в предыдущей статье. Единственное отличие состоит в том, что набор интервалов, указанный в этом вопросе,естественный порядок, нам не нужно его сортировать.
Интервал уже заказан, остальное очень просто, надо только вставить. Условие оценки для вставки интервала все еще такое же, как и раньше.Если левая конечная точка интервала А находится слева от левой конечной точки интервала В, то, пока правая конечная точка интервала А находится справа от левая конечная точка интервала В. Так что в этом вопросе в основном нет сложности, это просто вопрос без содержания, и я не понимаю, почему официальная сложность — «Сложно».
Мы напрямую выпускаем код:
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
ret = []
# l, r记录待插入区间
l, r = newInterval
# 记录待插入区间是否完成插入
flag = False
for x, y in intervals:
# x, y记录当前区间
# 如果当前区间在待插入区间左侧，那么将当前区间插入答案
if y < l:
ret.append([x, y])
# 如果当前区间在待插入区间右侧，那么将两个区间都插入答案
elif r < x:
if not flag:
flag = True
ret.append([l, r])
ret.append([x, y])
# 否则，说明当前区间与待插入区间可以合并
# 更新待插入区间的范围
else:
l, r = min(l, x), max(r, y)
# 如果最后还没有完成插入，说明待插入区间大于所有区间
# 手动插入，防止遗漏
if not flag:
ret.append([l, r])
return ret
Пока вы понимаете условия слияния интервалов, этот вопрос действительно не сложен.
LeetCode 59 Спиральная матрица II
Не так давно мы нашли решение спиральной матрицы I. В спиральной матрице I мы задали матрицу и позволили нам пройти ее по спирали. Эта задача обратная, учитывая длину и ширину нашей матрицы, давайтеСоздайте спиральную матрицу, подобную этой.
Давайте посмотрим на следующий пример:
В этом вопросе мы также можем решить его полностью, используя идею вопроса 54, но этот вопрос проще. Поскольку давайте построим матрицу, нам на самом деле не нужно поддерживать границы каждого направления. пока он появляетсяВыход за пределы или обнаружен уже заполненный номерЗначит, его надо перевернуть. В каком-то смысле этот вопрос должен быть I, а предыдущие 54 вопроса должны быть II, потому что этот вопрос проще.
Если вы не знакомы с решением 54 вопросов, вы можете щелкнуть портал ниже, чтобы узнать, как использовать массив направлений.
LeetCode54 Спиральная матрица, название не важно, главное это умение
Поскольку нам не нужно поддерживать границы в каждом направлении, а количество шагов для перемещения фиксировано, что более важно,Управление происходит не более одного раза за раз, так что этот процесс очень прост, мы можем просто посмотреть код напрямую.
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
# 初始化答案
ret = [[0 for _ in range(n)] for _ in range(n)]
# 初始化方向数组
fx = [[0, 1], [1, 0], [0, -1], [-1, 0]]
# 初始化方向以及起始点
dt = 0
x, y = 0, 0
# n*n的方阵，一共需要填入n*n个数字
for i in range(n*n):
ret[x][y] = i+1
# 移动的下一个位置
x_, y_ = x+fx[dt][0], y+fx[dt][1]
# 如果发生超界或者是遇到的数字大于0，说明需要转向
if x_ < 0 or x_ >= n or y_ < 0 or y_ >= n or ret[x_][y_] > 0:
dt = (dt + 1) % 4
# 转向之后的位置
x, y = x+fx[dt][0], y+fx[dt][1]
return ret
LeetCode 60 К-я перестановка
Эта задача представляет собой задачу перестановки и комбинации.Данное целое число n представляет собой последовательность из n элементов [1,2,3,...,n]. Затем существует целое число K, которое требует, чтобы n элементов были расположены в K-м порядке от наименьшего к наибольшему.
Вопрос на самом деле довольно интересный, думаю может быть на харде, но к сожалению у него хитрый путь, может в этом дело, поэтому его понизили до Medium. Это умное решение должно быть довольно легко придумать Очевидно, поскольку n чисел определены, наименьшая перестановка должна быть [1,2,3,...,n]. И мы уже решали задачу LeetCode31, которая запрашивает данную перестановку, а затем генерирует следующую перестановку, лексикографический порядок которой всего на один бит больше, чем у нее.
В таком случае мы можемПовторите этот алгоритм K-1 раз, получил ответ. Для учащихся, ответивших на 31 вопрос, этот вопрос не представляет сложности. Если вы не знакомы с ответом на 31 вопрос, вы можете щелкнуть портал ниже, вернуться и просмотреть его.
LeetCode 31: рекурсия, возврат, восемь ферзей, полная перестановка
Но на самом деле не нужно так заморачиваться, потому что у Python есть своя библиотека инструментов для перестановки и комбинирования, мы можем вызвать ее напрямую, и сделать это можно всего 5 строками кода.
class Solution:
# 引入包
from itertools import permutations
def getPermutation(self, n: int, k: int) -> str:
# 由于最后返回的结果要是string
# 生成['1','2','3',...,'n']的序列用来计算下一个排列
base = [str(i) for i in range(1, n+1)]
# 调用permutations会得到一个按顺序计算排列的生成器
perms = permutations(base, n)
for i in range(k):
# 我们调用k-1次next就能获得答案了
ret = next(perms)
return ''.join(ret)
Хотя этот метод короток и прост в написании, он также имеет большую проблему, а именно:занимает много времени. Это на самом деле легко вычислить.Сложность генерации следующей перестановки на основе текущей перестановки составляет
. Всего нам нужно вычислить k-1 раз, поэтому общая сложность равна
, k=n!, в крайнем случае, поэтому наихудшая сложность
. Необходимо знать, что всего существует n! видов перестановок n объектов, Если k очень велико, сложность становится взрывоопасной. Впрочем, этот вопрос не слишком смущает, и такая сложность тоже может быть АС. Я лично думаю, что это жаль, потому что простые алгоритмы могут также AC, что приведет к тому, что у многих людей не будет боевого духа для изучения сложных алгоритмов.
Наконец, давайте посмотрим на правильное решение.
На самом деле правильное решениеНе требует никаких новых алгоритмов и структур данных, даже прямо скажем никчемный, но многим просто тяжело соображать. Все еще старая тема, она требует от нас глубокого осмысления проблемы.
Так как очень медленно находить следующую перестановку одну за другой, можем ли мы найти более быстрый способ? Вероятно, есть два способа ускорить скорость, первыйувеличить шаг, например, предыдущий метод заключается в получении перестановки лексикографического порядка + 1 каждый раз, можем ли мы сгенерировать перестановку лексикографического порядка + k? Вторая мысль: можем ли мыпрямой ответ, непосредственно генерировать эту перестановку?
Простой анализ обнаружит, что первое утверждение невозможно или ложно. Потому что, если мы можем придумать алгоритм для решения лексикографического порядка + k, то если мы сделаем это k равным k, требуемому в вопросе, разве это не прямое решение ответа? Поэтому если и может быть лучший путь, то только второй, т. е. метод непосредственного построения ответа. Итак, остается вопрос, как нам напрямую построить этот ответ? Это требует нашего понимания перестановки и комбинации.
Если вы написали от руки полную перестановку набора, вы найдете некоторые закономерности. Например, 123 все устроено. Мы все знаем, что его полные перестановки составляют 123, 132, 213, 231, 31 и 321. Это очень просто.Если мы понаблюдаем за этим, мы обнаружим, что 123 имеет в общей сложности три числа и 6 расположений. Каждое число начинается с 2 видов, а если его заменить на 1234? Если вы перечислите его, вы узнаете, что существует 6 типов. Если вы посмотрите на шаблон, вы обнаружите, что количество видов в начале каждого числа равно (n-1)!.
Его также легко вывести, потому чтокаждое число справедливо, поэтому количество видов в начале каждого числа одинаково. Всего существует n! видов всех перестановок, поэтому каждому номеру соответствует голова, и всего (n-1)! видов. Итак, если мы уже знаем, что первое число равно 1, сколько видов чисел есть во втором числе 2? Тем же методом можно вычислить (n-2)! видов. Кажется, здесь промелькнула искра?
Давайте возьмем пример. Предположим, что мы теперь n = 5. Мы будем знать, что всего есть 120 перестановок. Предположим, мы запрашиваем 100-ю перестановку, поскольку она начинается с 0, она также является 99-й по величине перестановкой. Итак, из того, что мы только что сказали, мы уже знаем, что каждое число начинается с 4! Это 24 вида, затем мы используем 99/24, чтобы получить 4, поэтому число в начале — это 4-е по величине число (0-е по величине число — 1), то есть 5. Ответ сразу сильно сузился, так что дальше? Затем мы вычитаем все случаи до 5 из 99, что равно 96, и получаем 3. То есть ответ - третья перестановка в начале 5, тогда я снова спрашиваю, какое второе число?
Таким же образом, после удаления 5 остается 4 числа, а у каждого числа на втором месте 3. То есть видов 6. Используем 3/6=0, что должно быть 0-м по величине числом, которое 1. Идем дальше, после удаления 5 и 1 осталось 3 числа. Есть 2 случая, когда каждое число занимает третье место, мы используем 3/2=1, мы должны выбрать первое наибольшее число, остальные числа здесь 2, 3, 4, поэтому третья цифра должна быть 3. И так далее, мы можем получить каждую цифру. Общая сложность составляет O(n), что является качественным прорывом по сравнению с описанным выше методом.
Я сделал схему всего процесса расчета, и те, кто не понимает, могут понять это в сочетании со следующей схемой:
Наконец, мы можем реализовать этот метод:
class Solution:
def getPermutation(self, n: int, k: int) -> str:
frac = [1 for _ in range(n+1)]
# 生成一个序列存放所有的元素
nums = [i for i in range(1, n+1)]
# 计算每一位的种类数
for i in range(1, n):
frac[i] = i * frac[i-1]
ret = ''
k -= 1
for i in range(n-1, -1, -1):
# 计算第i位的数字是当前第几大的数
cur = k // frac[i]
# 放完之后取模，表示去除掉之前的所有情况数
k %= frac[i]
# 求出当前元素之后，需要从序列当中移除
ret += str(nums[cur])
nums.remove(nums[cur])
return ret
конец
Даже если с тремя вопросами здесь покончено, сегодняшние три вопроса более или менее связаны с предыдущими вопросами, поэтому я поместил эти три вопроса в одну статью.
Из трех вопросов лично мне больше всего нравится третий вопрос, особенно идеальное решение. Вся его идея и код не сложны, и нет никаких специальных навыков или методов, но придумать этот алгоритм без достаточно глубокого понимания предмета сложно. Собственно, в этом и суть алгоритмических задач.В конкурсе есть много задач, которые невозможно решить, даже если решение известно. Так что нам нужно улучшить уровень алгоритма, оптического алгоритма недостаточно,Также требуется глубокое понимание предметаПросто сделай это.
Сегодняшняя статья здесь, оригинальность непростая, вам нужен вашбеспокойство, ваше небольшое усилие очень важно для меня.