[LeetCode]HashTable主题系列{第3题}

1. 内容介绍

开一篇文章记录在leetcode中HashTable主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解结果,反思}的格式来记录,供日后复习和反思[注:有些题目的解法比较单一,就没有优化过程]。题目的顺序按照leetcode给出的题目顺序,有些题目在并不是按照题目本身序号顺序排列的,也不是严格按照难易程度来排列的。

因此,这篇文章并不具有很强的归类总结性,归类总结性知识将会在其他文章记录,本篇重点在记录解题过程中的思路,希望能对自己有所启发。

2. 题目和解题过程

2.1 Longest Substring Without Repeating Characters

  • 题目:Given a string, find the length of the longest substring without repeating characters.Examples:Given "abcabcbb", the answer is "abc", which the length is 3.Given "bbbbb", the answer is "b", with the length of 1.Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
  • 分析:题目点明了三个要素:子串,无重复字符,最长。其中子串意味着选取的字符串在源字符串中是连续存在的,无重复和最长是自明的。题目的难点之一是对于一个字符,如何在现有子串中快速判重,显然,遍历搜索时间复杂度是O(n),红黑树set查询的时间复杂度是O(logn),而哈希表unordered_set拥有最快速的速度,其时间复杂度是O(1)。以下先给出一个暴力解法,便于理清基本思路和观察可以优化的地方,同时也方便拿时间和优化解法的时间进行对比,凸显算法设计的重要性。
  • 初解:先从源字符串S头部第一个字符开始,向后连续生成子串,对于每一个后续的字符进行判重,如果重复则记录下当前子串长度和内容,然后移动到第二个字符重复之前的过程,依次类推,直到源字符串的最后一个字符。其中如果遇到比当前最长无重复子串长度更长的子串,则更新此记录。该解法的时间复杂度约为O(n2)。
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        string longest_substr="";
        for(int index=0; index < s.size(); ++index)
        {
            set<char> char_set;
            string tmp_substr = "";
            find_longest_substr(s, index, char_set, tmp_substr);
            if(tmp_substr.size() > longest_substr.size())
                longest_substr = tmp_substr;
        }
        return longest_substr.size();
    }
    void find_longest_substr(string& s, int index, set<char>& char_set, string& tmp_substr)
    {
        for(int start = index; start < s.size(); ++start)
        {
            if(char_set.find(s[start])==char_set.end())
            {
                char_set.insert(s[start]);
                tmp_substr+=s[start];
            }
            else break;
        }
    }
};
  • 初解结果:
  • 优化解法1:初解中每次遇到重复字符时,重新从当前起始字符的下一个字符开始搜索,这样会做额外的无用功,因为例如字符串abcdad,从a开始搜索时a字符重复但是中间字符串bcd并未重复,因此可以不必重新从b开始搜索,而是将首部的a去掉直接从bcda后的d开始继续搜索。根据上面的例子可以总结出一个规律:当出现重复字符时,只需要将该字符在子串中重复的位置以前的字符去除掉,然后判断当前剩余的字符长度加上现有子串长度之和小于当前计算出来的最长子串长度时,可以终止搜索了,否则继续沿着当前搜索的位置向后搜索,直到源字符串结尾。此处的优化思想是从现有结果中提取无需重复计算的结果,节省计算时间,减少总体重复计算的总量。至于查重方法,暂时使用红黑树实现的set。
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() <= 1) 
            return s.size();
        int length = 0, last_pos = 0;
        set<char> substring;
        for(int i = 0; i < s.size(); ++i)
            find_longest_substr(s, i, substring, last_pos, length);
        if(length < substring.size())
            length = substring.size();
        return length;
    }
    void find_longest_substr(string& s, int& index, set<char>& substring, int& last_pos, int& length)
    {
        if(substring.find(s[index]) == substring.end())
            substring.insert(s[index]);
        else
            erase_duplicate_subsubstring(s, index, substring, last_pos, length);
    }
    void erase_duplicate_subsubstring(string& s, int& index, set<char>& substring, int& last_pos, int& length)
    {
        if(length < substring.size())
            length = substring.size();
        for(int j = last_pos; j < index; ++j)
        {
            substring.erase(s[j]);
            if(s[j]==s[index])
            {
                last_pos = j+1;
                break;
            }
        }
        substring.insert(s[index]);
    }
};
  • 优化结果1:
  • 优化解法2:将查重方式改为哈希表unordered_set。
  • 优化结果2:结果差别不大,不予展示。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM小冰成长之路

51Nod-1645-中位数变换

ACM模版 描述 ? 题解 这个题很明显是找规律的问题,直接暴力肯定会超时……虽然我也是暴力也两发才反应过来……平时做题总是抱着侥幸心理,比赛时却总是胆小如鼠…...

2117
来自专栏落影的专栏

程序员进阶之算法练习(二十五)

前言 算法题是锻炼思维的好工具,在解决问题的层面考察思考能力。 正文 1. Compote 题目链接 题目大意: 给出a、b、c三种材料,可以1:2:4组成...

3829
来自专栏Danny的专栏

面向对象三大特征

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

1852
来自专栏大数据文摘

正则表达式太慢?这里有一个提速100倍的方案(附代码)

2324
来自专栏chenjx85的技术专栏

leetcode-169-Majority Element

2114
来自专栏移动端开发

快速排序OC、Swift版源码

前言: 你要问我学学算法在工作当中有什么用,说实话,当达不到那个地步的时候,可能我们不能直接的感觉到它的用处!你就抱着这样一个心态,当一些APP中涉及到算法...

2208
来自专栏小红豆的数据分析

小蛇学python(6)python实现经典排序算法并可视化分析复杂度

排序算法在算法界是一个怎么样的存在?就好像在学术界中数学的地位,说直接用好像用不上,可是不会做起事情来总会捉襟见肘,左支右绌。找工作的时候,有的面试官甚至会让我...

2082
来自专栏进击的程序猿

进击算法:字符串匹配的 BM 算法

各种文本编辑器的 "查找" 功能(Ctrl+F),大多采用 Boyer-Moore 算法。

2733
来自专栏Dawnzhang的开发者手册

数据结构与算法学习笔记之高效、简洁的编码技巧“递归”

盗梦空间想象大多数人都看过:电影讲述的是主人公诺兰进入希里安·墨菲梦境植入想法的行动。为了向希里安·墨菲梦植入理念,影片进入四层梦境,即所谓:“梦中的梦中 梦中...

1153
来自专栏编舟记

函数式编程简介

1900年,Hilbert 提出了数学界悬而未决的10大问题,后续陆续添加成了23个问题,被称为著名的 Hilbert 23 Problem。针对其中第2个决定...

1964

扫码关注云+社区

领取腾讯云代金券