[Ежедневный алгоритм перфокарты] Самая длинная подстрока без повторяющихся символов

искусственный интеллект алгоритм
[Ежедневный алгоритм перфокарты] Самая длинная подстрока без повторяющихся символов

«Это третий день моего участия в ноябрьском испытании обновлений. Подробную информацию об этом событии см.:Вызов последнего обновления 2021 г.".

【Ежедневные пробные серии】LeetCode200 простых вопросов

Описание темы

дана строкаs, пожалуйста, найдите тот, который не содержит повторяющихся символовсамая длинная подстрокадлина.

Пример 1:

Ввод: s = "abcabcbb"
выход: 3
Объяснение: Поскольку самая длинная подстрока без повторяющихся символов — «abc», ее длина равна 3.

Пример 2:

Ввод: с = "бббб"
выход: 1
Объяснение: Поскольку самая длинная подстрока без повторяющихся символов — «b», ее длина равна 1.

Пример 3:

Ввод: s = "pwwkew"
выход: 3
Объяснение: Поскольку самая длинная подстрока без повторяющихся символов — «wke», ее длина равна 3. Обратите внимание, что ваш ответ должен быть длиной подстроки, «pwke» — это подпоследовательность, а не подстрока.

Пример 4:

Ввод: с = ""
вывод: 0

намекать

  • 0 <= s.length <= 5 * 104
  • sСостоит из английских букв, цифр, символов и пробелов

Идеи решения проблем

Идеи решения проблемы: 滑动窗口 + 双指针установить двойной указатель,leftуказывая на окнолевый конец,rightуказывая на окноследующий элемент справа, размер окнаright - left. Сначала установитеleft=0,right=1,фиксированныйleft, постоянно в движенииright,до того какrightуказанный элемент уже существует в текущем окне, затем найдите позицию элемента в окне и наведите указатель на следующую позицию из этой позиции; илиrightПеремещено за пределы границы, на этот раз сравнениеmax_strиright - leftsize, возвращает самую большую подстроку.在这里插入图片描述 реализация питона

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        length = len(s)
        # 即长度为0或1，len(s)即为最长子串
        if length < 2:
            return length
        # 初始化left，right两个指针
        left, right = 0, 1
        # 最长长度设置为1
        max_str = 1
        # 退出条件，right到达边界
        while right < length:
            # 当right未到达边界，且right指向的元素没有出现在子串中
            while right < length and s[right] not in s[left: right]:
                # right指针右移
                right += 1
            max_str = max(max_str, right - left)
            # 当right未到达边界
            if right != length:
                # 将left指针移动到重复元素的下一个位置
                left += s[left: right].index(s[right]) + 1
        return max_str

Сегодняшняя регистрация завершена, текущий прогресс — 7/200.

Категории