leetcode总结无止境系列之字符串

字符串的使用穿插于c和c++中,对应的是char*和string。在c语言中又有一系列处理字符串数组的c函数十分重要,c++的string封装了很多库函数,使用起来很方便而且不容易出错。 面试笔试中字符串常用考法主要有以下几个方面:

一、大数问题。整型long long仍然无法表示的大数,一般采用字符串来表示,因此会考到字符串模拟加法、乘法,字符串和整型直接的转换之类的问题(需要考虑各种边界条件,见下面leetcode例题中)

二、字符串的翻转(全部翻转、部分翻转),拼接等问题。 在string中有封装好的reverse函数和"+",所以一般翻转和拼接问题是争对char*数组而言,处理的时候注意数组尾部的'\0'。

三、c中的一系列字符串处理函数都十分的经典,所以有时候面试时会考到自己重新实现这些函数。包括strcpy、strcat、strcmp、atoi、itoa、内存拷贝函数memcpy等。

四、字符串的模式匹配,找重复子串、公共前缀、回文问题和经典的KMP算法等。 回文子串的问题经常会用到动态规划的思想,例题会放到动态规划系列中。 模式匹配时一般按照规则写if..else..语句,像括号有效匹配检测可以借助栈来实现,或者求最长有效匹配长度(先把有效的部分置为另外一个不出现的字符,再统计长度)。

leetcode 上相关题目汇总</span></p>

1.Longest Substring Without Repeating Characters

2.ZigZag Conversion

3.String to Integer (atoi)

4.Longest Common Prefix

5.Substring with Concatenation of All Words

6.Multiply Strings

7.Valid Parentheses

8.Longest Valid Parentheses

9.Minimum Window Substring

crystal /
Published under (CC) BY-NC-SA in categories 面试  tagged with leetcode  数据结构