Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняТемы LeetCode45-я статья, давайте взглянем на 76 вопросов LeetCode, минимальную подстроку окна. Минимальная подстрока окна.
Официальная сложность этого вопросаHard, приняли 34,2%, понравилось 4202 человека, против выступили 299 человек. Судя по проходимости и количеству лайков, этот вопрос качественный и немного сложный, поэтому, пожалуйста, подготовьтесь, это довольно сложный вопрос.
Тема и примеры
Давайте посмотрим на смысл вопроса.Смысл этого вопроса очень короткий, учитывая две строки S и T. Требуется проектирование сложности
Алгоритм находит в строке S подстроку, которая может содержать все символы строки T. Запрос на возврат содержимого окна допустимой и минимальной длины.
Уведомление:
- Возвращает "", если такого окна не существует.
- Если окно существует, заголовок гарантированно имеет ровно один.
Пример:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
анализировать
Давайте проанализируем эту проблему, каждый должен почувствовать ее сложность по смыслу вопроса. Поскольку описанная выше проблема ограничивает сложность используемого нами алгоритма, она должна быть
, однако сложность нашего обхода строки уже
То есть мы не можем вводить дополнительные вычислительные затраты, иначе это не должно соответствовать требованиям заголовка.
Некоторые студенты могут подумать о легендарном
Время определить, соответствует ли строкаАлгоритм КМП, не имеет значения, если вы не знаете алгоритма, потому что он не работает. Потому что то, что мы ищем, — это не положение полностью равных подстрок, а подстроки с одинаковыми символами, поэтому это не может быть решено путем введения алгоритма сопоставления строк. Студенты, не изучившие алгоритм КМП, могут вздохнуть с облегчением, и никакого нового алгоритма в этом вопросе введено не будет.
рутина решения проблем
Вообще говоря, когда мы сталкиваемся с алгоритмической проблемой, у нас часто возникают два основных мыслительных процесса. одинприспособление, грубо говоря, заключается в применении алгоритма, который может быть использован для решения задачи. По смыслу вопроса сначала прочувствуйте, какой алгоритм будет использоваться, а потом выводите подробно процесс адаптации, чтобы увидеть, действительно ли он применим или есть ли какие-то ямки, или какие новые проблемы появятся. Если все в порядке и рассуждения имеют смысл, то этот алгоритм является решением. Второй методмоделирование, то есть начать со смысла вопроса, провести глубокий анализ смысла вопроса, смоделировать и абстрагировать проблему, найти суть проблемы и сделать вывод, какой алгоритм можно использовать для ее решения. реши.
Чтобы привести очень простой пример, в целом наши алгоритмы динамического программирования являются адаптациями. Это все, что мы чувствуем или предполагаем, что мы можем использовать динамическое программирование, затем найти состояние и переход и, наконец, установить уравнение перехода состояния. Некоторые поисковые задачи обычно моделируются.Мы сначала анализируем проблему, затем находим пространство существования решения, которое необходимо найти, а затем разрабатываем алгоритм для поиска и сокращения и, наконец, находим ответ.
Говорят, что некоторыеЛучшие мастера Эти два метода используются вместе, поэтому решение может быть найдено так быстро. Я, конечно, не эксперт, так что это только мое предположение. Этот мыслительный процесс очень полезен, особенно когда мы берем интервью и сталкиваемся с вопросом, который никогда раньше не задавался.Если у вас нет рутины, очень часто у вас пустые мысли или вы пытаетесь понять это. Когда у вас есть рутина, вы можете попытаться найти ответ медленно.
Возвращаясь к самому вопросу, мы уже попробовали это только сейчас, и использовать алгоритм сопоставления строк онлайн невозможно. Кажется, нет другого алгоритма, который можно было бы применить в поле зрения, поэтому давайте попробуем мыслить иначе и попробуем моделировать.
Прежде всего, мы можем быть уверены, что нам нужно найти ответ при обходе, чтобы гарантировать, что сложность алгоритма
. Наша цель — найти подстроки, т. е. мыПроцесс обхода должен соответствовать подстроке, и у нас есть способ быстро определить, допустима ли эта подстрока. Таким образом, мы можем пройти и оценить возможность ответа одновременно. Тогда мы можем подумать, что это проблема обслуживания интервалов.Метод, который мы часто используем для обслуживания интервалов, - это два указателя. Итак, мы можем увидеть, работают ли два указателя.
На самом деле правильное решение этой проблемы — два указателя.
отвечать
Мы поддерживаем интервал, и нам нужно судить о составе символов в интервале.Легко думать, что мы можем использовать dict для сохранения количества вхождений каждого символа. В этой теме мыНужно только рассмотреть случай покрытия, то есть большее количество символов не считается незаконным. Таким образом, мы можем поддерживать словарь и обновлять его каждый раз, когда читается символ.Когда символы в словаре соответствуют требованиям, чтобы сделать длину интервала как можно короче, мы можем попытаться переместить левую часть словаря. интервал, чтобы максимально сократить длину интервала.
С точки зрения поддержания интервала, мы каждый раз перемещаем одну единицу в правую сторону интервала и перемещаем левую сторону только тогда, когда смысл вопроса был удовлетворен в интервале. Получите лучший интервал, соответствующий смыслу вопроса, переместив всплывающий элемент слева.
Давайте посмотрим на основной код процесса:
# 存储区间内的字符
segement = {}
for i in range(n):
segement[s[i]] += 1
# 当满足条件的时候移动区间左侧
while l <= i and satisified(segment):
# 更新最佳答案
if i - l + 1 < ans_len:
ans_len = i - l + 1
beg, end = l, i + 1
# 弹出元素
segement[s[l]] -= 1
l += 1
Тут еще есть небольшая проблема, а именно, как судить о легальности этого сегмента? мы можемИспользуйте совпадающее число для записи количества совпавших символов.. Когда количество вхождений символа в сегмент равно количеству раз в T, совпадение увеличивается на единицу. Когда количество совпадений равно количеству типов символов в T, это можно считать допустимым.
Соединяем всю логику и можем пройти этот вопрос.
class Solution:
def minWindow(self, s: str, t: str) -> str:
from collections import Counter, defaultdict
# 通过Counter直接获取T当中的字符构成
counter = Counter(t)
n, m = len(s), len(counter)
l, beg, end = 0, 0, 0
cur = defaultdict(int)
matched = 0
flag = False
# 记录合法的字符串的长度
ans_len = 0x3f3f3f3f
for i in range(n):
if s[i] not in counter:
continue
cur[s[i]] += 1
# 当数量匹配上的时候，matched+1
if cur[s[i]] == counter[s[i]]:
matched += 1
# 如果已经找到了合法的区间，尝试缩短区间的长度
while l <= i and matched == m:
if i - l + 1 < ans_len:
flag = True
beg, end = l, i+1
ans_len = i - l + 1
# 弹出左侧元素
c = s[l]
if c in counter:
cur[c] -= 1
if cur[c] < counter[c]:
matched -= 1
l += 1
return "" if not flag else s[beg: end]
Суммировать
На данный момент проблема решена. Многие учащиеся могут задаться вопросом, почему мы используем двойные петли, но все же
алгоритм?
Это распространенная проблема с двумя алгоритмами указателя, и это обычная тема. Когда мы проанализируем сложность,Вы не можете просто посмотреть, сколько слоев петель используется, но чтобы захватить сердце вычислений. Например, в этой задаче переменной, на которую нацелен наш внутренний цикл while, является l, и переменная l увеличивается для i в целом. Другими словами, независимо от того, сколько раз выполняется внешний цикл, внутренний цикл может выполняться не более n раз. Ну, конечно, это
алгоритм.
Этот вопрос вообще немного сложен, особенно в начале, вы можете чувствовать, что не имеете ни малейшего понятия и не можете начать. В это время очень важно иметь ясный ум и надежную цепочку мышления.Надеюсь каждый сможетизучить процесс мышления, чтобы в будущем можно было решать больше алгоритмических задач.
Если вам понравилась эта статья, пожалуйстаобращать внимание, подбодрите меня и облегчите доступ к другим статьям.
В этой статье используетсяmdniceнабор текста