面试题53：正则表达式匹配
请实现一个函数用来匹配包含'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串中所有字符匹配整个模式。
leetcode 链接 https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/ 按这个解题思路不算hard难度吧，不要先有恐惧class Solution { public: bool isMatch(string s, string p) { if (s == "" && p == "") { return true; } if (s != "" && p == "") { return false; } if(p[1] == '*') { if (p[0] == s[0] || (p[0] == '.' && s[0] != '\0')) { return isMatch(s.substr(1), p) || isMatch(s, p.substr(2)); } else { return isMatch(s, p.substr(2)); } } if(s[0] == p[0] || (p[0] == '.' && s[0] != '\0')) { return isMatch(s.substr(1), p.substr(1)); } return false; } };
解题思路：每次从字符串中拿出一个字符，和模式匹配字符串中字符进行比较。如果模式中的字符是'.'或与字符串中字符相同，则当前字符串中字符与模式中字符相匹配，接着匹配后面的字符。
相对而言，当第二个字符不是’*‘时问题简单很多。如果字符串第一个字符和模式中第一个字符相匹配，那么字符串和模式中字符都向后移一位，然后匹配剩下字符。如果存在字符不匹配情况，直接返回false。
模式ba*ab的非确定有限状态机，。当匹配状态进入状态2并且字符串字符是a时，有两个选择，可以进入状态3也可以返回状态2
面试题54：表示数值的字符串
请实现一个函数用来判断字符串是否可以表示数值（包括整数和小数）。例如，字符串"+100","+5e2","-123","-1E16"都是表示数字，但是"12e","1a3.14","12e+5.4"都不是。
leetcode链接 https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/class Solution(object): def isNumber(self, s): """ :type s: str :rtype: bool """ try: float(s) return True except: return False
解题思路：分析好有效的数字表达方式即可。表达数值的字符串遵循如下模式
[sign]itergral-digits[.[fractonal-digitals]][e|E[sign]exponentail-digits] ([]之间为可有可无部分） leetcode上特殊样例太多，过不去，懒得修了
class Solution {
public:
void scanDigits(string &s)
{
while(s != "" && s[0] >= '0' && s[0] <= '9')
{
s = s.substr(1);
}
}
bool isExp(string &s)
{
if (s[0] != 'e' && s[0] != 'E')
{
return false;
}
s = s.substr(1);
if (s[0] == '+' || s[0] == '-')
{
s = s.substr(1);
}
if (s == "")
{
return false;
}
scanDigits(s);
return s == "";
}
bool isNumber(string s) {
if (s == "" || s == " " || ((s[0] < '0' || s[0] > '9') && s[0] != '.' && s[0] != ' '))
{
return false;
}
if (s[0] == '+' || s[0] == '-' || s[0] == ' ' || s[0] == '.')
{
s = s.substr(1);
if (s == "")
{
return false;
}
}
// 扫描string中的数字
scanDigits(s);
cout << s << endl;
if (s == "")
{
return true;
}
bool result = true;
if (s[0] == '.')
{
s = s.substr(1);
scanDigits(s);
if (s == "")
{
return true;
}
if (s[0] == 'e' || s[0] == 'E')
{
result = isExp(s);
}
}
else if (s[0] == 'e' || s[0] == 'E')
{
result = isExp(s);
}
else
{
if (s == " ")
{
return true;
}
return false;
}
return result && s == "";
}
};
面试题55：字符流中第一个不重复的字符
请实现一个函数，用来找到字符流中第一个只出现一次的字符
leetcode链接 https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/class Solution { public: char firstUniqChar(string s) { int arr[256]; for(int i = 0; i < 256; i++) { arr[i] = -1; } for(int i = 0; i < s.length(); i++) { if (arr[s[i]] == -1) { arr[s[i]] = i; } else { arr[s[i]] = -2; } } char result = ' '; int minIndex = s.length(); for(int i = 0; i < 256; i++) { if (arr[i] >= 0 && arr[i] < minIndex) { minIndex = arr[i]; // 注意这里需要记录最小值，以保证是第一个出现的 result = s[minIndex]; } } return result; } };
解题思路：
剑指offer题解：用hash表来实现，字符占8个字节，最多可以表示256个，因此用256长度数组模拟hash表即可。数组中个元素初始化为-1，当第一次遇到字符，将字符对应value值初始化为字符位置，下次再遇到，改为-2。遍历hash表，找到第一个正数，就是不重复字符。
我的想法：也是两次循环，记录每个字符的出现次数，下次再遍历字符串，找到出现次数为1的字符后退出循环。分析主要区别在第二次循环，我的想法如果只出现一次的字符在字符串末尾，需要遍历整个字符串。而剑指offer的题解是遍历的是长度可能更短的hash表。还有就是题目中是一个字符流，不断有新的字符进来，无法实现再次遍历字符串。
网友评论