美文网首页
算功@LeetCode:Longest Substring Wi

算功@LeetCode:Longest Substring Wi

作者: 苏尚君 | 来源:发表于2017-04-15 01:26 被阅读51次

    Log

    • 【170414】完成 01 版书写(C++)
    • 【170415】完成 02 版(Python)、03 版(C++)书写
    • 【170416】看完参考答案,写下思路

    题目

    Longest Substring Without Repeating Characters

    【题目类型备注】

    哈希表, 字符串, 双指针

    提交

    01

    【语言】

    C++

    【时间】

    170414

    【思路】

    1. 指针从头开始,一个一个查找字符,如果遇到的新的字符不在已有的记录表(使用哈希表记录,用字符 ch 映射整数 i,表示在最近的子串中 ch 的坐标)中,就建立新的映射,并且继续下一轮查找
    2. 如果 1. 中遇到了已经在记录表中记录的字符 dupl,那么
    3. 比较目前的最大子串长度与记录表长度(遇到 dupl 前的找到的这个子串的长度),将大者赋予最大子串长度
    4. 将指针移动到记录表中记录的 dulp 所对应的下标处·的后继坐标处·重新开始寻找最大子串
    5. 直到指针走到给定字符串的尾部,算法结束

    【代码】

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
          int lmax = 0, lnow = 0;
          std::unordered_map<char, int> tempchars;
          for (int i=0; i<s.size(); ++i)
          {
            if (tempchars.find(s.at(i)) == tempchars.end())
            {
              tempchars[s.at(i)] = i;
              lnow++;
            }
            else
            {
              if (lmax < lnow)
              {
                lmax = lnow;
              }
              i = tempchars[s.at(i)] + 1;
              tempchars.clear();
              tempchars[s.at(i)] = i;
              lnow = 1;
            }
          }
    
          if (lmax < lnow)
          {
            lmax = lnow;
          }
    
          return lmax;
        }
    
    };
    

    【结果】

    运行时:406 ms

    报告链接:https://leetcode.com/submissions/detail/100093534/

    不知道其他拥有 LeetCode 帐号的人能不能看到该报告,所以顺便附图如下:

    Your runtime beats 6.06% of cpp submissions.

    总之好歹不算太勉强地过了……同样的逻辑用 Python 书写就超时了(在最后的 testcase 爆掉了……有一次侥幸的通过,但大多数情况下无法通过,所以最终求助于 C++)

    02

    【语言】

    Python

    【时间】

    170415

    【思路】

    这次的思路其实是沿用第一次设计的算法的思路。那时候的思路是:

    1. 从头开始找子串,每找到一个新的字符就加入列表 tempchars
    2. 一旦找到旧字符,就把当前的 len(tempchars) 加入到备选的「最大子串长度」中(answers,备选最大子串长度列表),然后从新找到的旧字符开始往后查找
    3. 直到查找完所有字符,算法结束

    当然,那次的算法明显是有问题的:例如面对 "dvdf" 时,上述算法将算出 "dv"(2) 和 "df"(2),而答案显然应该是 "vdf"(3)。于是才有了上述成功提交的版本 01。

    版本 01 利用了哈希表来保存最近一次找到的无重复字符的子串,但缺陷(之一?)就在于:重复扫描了旧字符在旧子串之后(含)的所有字符。而实际上我们没有必要重复扫描那些字符——例如对于字符串 "fabedbca" 而言,(假定字符串从下标 0 开始,)当我们找到第 2 个 "b"(下标为 5)时,我们没必要再从下标 2 开始搜索;我们只要记录子串的首、尾位置(用双指针),在遇到旧字符时更改字符串的首位置,并更改哈希表中的记录,然后继续从尾位置往后搜索即可,直到尾位置扫描到总串的尾部,算法结束。

    该算法的时间复杂度应该是 O(n),不过应该还不是最优:由于在找到重复字符时要修改哈希表,而目前采取的修改哈希表的操作是:在改变首指针位置前,从首指针逐一扫描随后的字符,并移除哈希表中以这些字符为主键的键值对,直到首指针跑到重复字符前一位为止。在最坏情况下,该操作估计会导致头尾指针各扫描了一遍字符串,所以严格说应该是 O(2n)。不知道是否还有其他方法可以保证严格的 O(n)。

    【代码】

    class Solution(object):
        def lengthOfLongestSubstring(self, s):
            """
            :type s: str
            :rtype: int
            """
            if len(s) <= 1:
              return len(s)
            #
            lmax = 0
            lnow = 0
            tempchars = {}
            first = 0
            last = 0
            while (last < len(s)):
              # this loop
              if s[last] not in tempchars:
                tempchars[s[last]] = last
                lnow += 1
              else:
                if lmax < lnow:
                  lmax = lnow
                newfirst = tempchars[s[last]]+1
                for ind in range(first, newfirst):
                  rubbish = tempchars.pop(s[ind])
                first = newfirst
                tempchars[s[last]] = last
                lnow = last - first + 1
              # next loop  
              last += 1
            #
            if lmax < lnow:
              lmax = lnow
            return lmax
    

    【结果】

    运行时:152 ms

    报告链接:https://leetcode.com/submissions/detail/100140073/

    不知道其他拥有 LeetCode 帐号的人能不能看到该报告,所以顺便附图如下:

    Your runtime beats 27.29% of python submissions.

    我还以为这次应该是最优解了,没想到还有更快的解法啊。后面再研究看看。

    03

    【语言】

    C++

    【时间】

    170415

    【思路】

    同提交 02

    【代码】

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
          int lmax = 0, lnow = 0, first = 0, last = 0, newfirst;
          std::unordered_map<char, int> tempchars;
          for (last=0; last<s.size(); ++last)
          {
            if (tempchars.find(s.at(last)) == tempchars.end())
            {
              tempchars[s.at(last)] = last;
              lnow++;
            }
            else
            {
              if (lmax < lnow)
              {
                lmax = lnow;
              }
              newfirst = tempchars[s.at(last)] + 1;
              for (int i=first; i<newfirst; ++i)
              {
                tempchars.erase(s.at(i));
              }
              first = newfirst;
              tempchars[s.at(last)] = last;
              lnow = last - first + 1;
            }
          }
    
          if (lmax < lnow)
          {
            lmax = lnow;
          }
    
          return lmax;
        }
    
    };
    

    【结果】

    运行时:49 ms

    报告链接:https://leetcode.com/submissions/detail/100146824/

    不知道其他拥有 LeetCode 帐号的人能不能看到该报告,所以顺便附图如下:

    Your runtime beats 25.37% of cpp submissions.

    00

    参考解法:

    最优解太美了!问题的关键在于抓住「无重复字符的最长子串」的关键意思(看注释),就可以用极少的存储解决本题!

    唯一的疑惑是:参考解法中容 int 器长度为 256,然后在下面使用时直接用字符当索引,所以应该是将这些索引数值当 ASCII 用。但为什么是 256 而非 128?

    自己实现一遍最优解:

    • [date-language] 。。。

    相关文章

      网友评论

          本文标题:算功@LeetCode:Longest Substring Wi

          本文链接:https://www.haomeiwen.com/subject/pdzgattx.html