文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

leetcode 3. Longest

2023-01-31 07:53

关注

题目:

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

大意是找出最长无重复子串


算法思路:

  这道题应该可以用动态规划做,我用的是double point的方法

  一个指针start指向子串头部,另一个指针end指向子串尾部

  每次递增end,判断end所指字符是否在当前子串中出现过

    • 如果出现过,则将start指针向后移动一位

    • 否则,将end指针向后移动,并更新最长子串长度                           

  最后返回子串最大长度即可


  该算法可以在start指针移动时进行优化,但是我优化后发现结果也没啥变化,就贴原来的代码吧


代码:

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        sLen = len(s)
        if sLen == 0 or sLen == 1:
            return sLen

        letters = list(s)

        hashSet = {}
        hashSet[letters[0]] = 1

        start = 0
        end = 1

        maxLen = 1

        while end != sLen:
            letter = letters[end]

            if hashSet.has_key(letter) and hashSet[letter] > 0:
                hashSet[letters[start]] -= 1
                start += 1
                continue

            hashSet[letter] = 1
            end += 1
            if end - start > maxLen:
                maxLen = end - start

        return maxLen


阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     807人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     351人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     314人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     433人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     221人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯