Leetcode中字符串总结

本文是个人对LeetCode中字符串类型题目的总结,纯属个人感悟,若有不妥的地方,欢迎指出。

一、有关数字

1、数转换

Interger to romanRoman to integer这两题是罗马数字和整数之间的相互转换,首先要懂得什么是罗马数字以及相应的组数规则。LeetCode的题中给出的数字最大的是3999,。针对第一题有两种解法:第一是列举出罗马数字在个十百千上的各种情况,形成一个二维矩阵,然后对整数不停的取余、除10来确定相应的罗马数字;第二种是先列出罗马数字组成情况,然后通过从大到小去给定的数字试探。针对第二题,要抓住罗马数的组词规则,然后遍历字符串,若当前值比后一个小,则减去当前值,若不小则加上。

2、计算加、乘

Multiply stringsadd binary,前者是两字符串对应的数字相乘后者是相加,首先这里肯定会涉及到一个进位的问题,这里采用的方法是定义一个进位量,进位量的计算是通过与进制数(十进制或二进制)相除得到。这种方法针对链表和数组求和也是适用的。针对第一题是定义一个中间变量去保存每次对应的乘积,最后计算进位数,这里值得注意的有:下标和中间数组的开始的去0操作,这点和String to integer atoi中前处理一样。第二题要考虑最高位的进位和字符和数字之间的转换。

3、跳过空格

String to integer atoi这题的思路比较简单,就是遍历字符串,保存的结果乘以10加上当前字符对应的数。但有很多需要注意的地方:一是,字符串中的空格问题,若字符串前后有空格,要跳过;二是,字符串中正、负号的问题;三是,字符串的数转换为整数时,可能越界的问题。这里针对越界的问题,有两种解决方法:一是,提升保存结果变量的类型,如变为long long 类;二是,每次乘以10之前先判断是否乘10之后是否会越界。

Length of last word和上面提到的一点要特别注意,从后面开始遍历字符串时,要注意跳过空格。

4、验证数字

valid number判断给定字符是否是有效数字类型的。这里针对三种不是数字是合法的情况,第一是字符".",二是字符"e",三是正反号“+”、“-”。其他非数字的字符是非法的。针对这三种情况,也不是所有的出现方式都是合法的。所以本题的关键是给出这三种对应的合法情况,针对字符'e',若其出现之前没有数字出现或是早就有'e'出现了,这种情况肯定是非法的,否则,就是合法的,同时更新exp和num,这里要说明的是num为什么还是false的?以字符''e'为分隔去看;针对字符".",之前要是没有出现"."和“e”,不然是非法的,更新dot为true;对于正负号,出现在字符中间时,若其前一个不是"e"也是非法的。另外开始时肯定要跳过前后的空格和开始的正负号。

二、最长问题

1、最长回文串

Longest palindromic substring求出给定字符串中的最长回文子串。首先要明白回文串是什么---回文串是正反读起来是一样的。思路有两种,一种是暴力解法,遍历字符串,求出以每个字符为中心的回文串长度,同时维持回文串的最大长度这个变量即可,这里求以每个字符为中心的回文长度时,要注意回文串有两种形式:长度是奇数和长度是偶数,此外还要维持一个变量保存最长回文串的起点位置;方法二是Manacher's Algorithm算法,可以在线性的时间内求出最大回文串的长度,算法的关键在于利用了回文串的特点----关于中心点两边相等。该算法分三步:第一步是,改造给定字符串,通过在字符之间插入特定的字符使字符串的长度是奇数个,同时也使得只要出现回文串在改造后的新字符串中都是奇数个;第二步,明白新回文串和原字符回文串中的关系;第三步,求出新字符串中各个字符所对应的回文串长度。另外维持一个最大长度,这样可以避免再次扫描数组找最大的长度。

2、最长无重复子串

Longest substring without repeating characters要特别注意的一点是,更新最长无重复子串起点的条件有两条:当前字符在之前出现过,还有,要在起点之后出现过,怎么理解第二点了?恩,如:“adbefghba”,当第二个字符b出现时,start移动到第一个字符b处,但移动到第二字符a时,难道因为a出现过一次,就要将起点移动到第一个字符a?显然不是,所以,出现重复时一定要是在起点之后,才能更新起点。这题最好结合相关代码理解。

3、最长连续序列

Longest consecutive sequence,还是利用hash表的思想,将字符串存入unordered_set中,然后遍历字符串,若某字符在hash表中,然后看该字符的左右是否在hash表中,最后右减左,再减1(因为跳出while循环时,两者都不是和当前字符的相邻)。另外,我们遍历到一个字符的左右时,若是删除了,可避免重复访问,因为若是现在这个字符和之前的某个字符相邻,则之前的字符肯定遍历到了当前字符,所以不必在遍历一遍。

三、字符串匹配

1、两字符串是否匹配

Implement strstr,判断一个是不是另一个的子串,暴力解法是,两字符串对应的字符一个个对比,直到找个匹配的,这样的时间复杂度为O(kn)。关键的点是不匹配时目标函数的下标的返回。这里是通过i+j作为目标函数的下标的方式,即可以保证i不动,但目标通过j 的移动,实现对目标串随对比串的移动;至于KMP算法,就是利用之前对比的信息,来实现快速跳转对比,从而加速对比过程。

2、表达式匹配

Regular expression matching关键在于当遇到“*”时的处理情况,这里最好用动态规划的方法,好理解一些。当前字符不是*时,只要判断之前对应的是否匹配和当前对应的字符是否匹配即可。当遇到的是*时,*可以代表0个也可代表多个前一个字符,所以要分这两种情况考虑。

Wildcard matching若当前字符时*,两字符当前对应的位相匹配时,则两者同时向后移动就行,若不匹配则考虑返回上一个*的下一位开始对比,若当前是*,则要记下此时两个字符串中的位置,所以要定义两个指针,用于返回比较。

四、找规律

count and say的单次循环中,当当前字符和前一个不相等时,就将字符的个数和对应的字符存入中间变量中,因为下次的初始值是上一次的结果,所以要用每次的结果去做初始值。

Zigzag conversion关键在于找到竖行和斜行字符对应下标的关系。以每行为单位去进行。

Simplify path关键在于对题意的理解,和采取的思路,这里两个"/"之间的字符来判断操作。

五、哈希

Anagrams以一各个单词取出来,排序以后插入哈希表中,若遇到已存在哈希表中的字符,则将其对应的原字符串存入结果中,但是对于已经存在哈希表中那个字符对应是否存入,要看是否为第一遇到重复的,可以通过设置,已经存入结果的,将其下标设为-1,每次判断已在哈希中的字符串的对应下标和-1的大小来决定。这一题可以为好多这类型的题提供思路,要好好理解。

 六、深搜

Palindrome partitioning深搜的套路要好好理解。

上一篇:Leetcode 394.字符串编码


下一篇:Winform下有关控件焦点问题