1.罗马数字转整数
2.最长公共前缀
3.有效的括号
4.实现str()
5.报数
1.罗马数字转整数
2.最长公共前缀
3.有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
使用栈，栈为空或当前字符为左括号，就入栈；当前字符为右括号，判断栈顶是否是对应的左括号。
class Solution {
public:
bool isValid(string s) {
int len = s.size();
if(len & 1==1)
return false;
stack<char> sta;
for(int i=0;i<len;i++){
if(sta.empty() || s[i]=='(' || s[i]=='{' || s[i]=='['){ //栈为空，或当前字符为左括号，入栈
sta.push(s[i]);
}else if(s[i]==')' && sta.top()=='('){
sta.pop();
}else if(s[i]=='}' && sta.top()=='{'){
sta.pop();
}else if(s[i]==']' && sta.top()=='['){
sta.pop();
}else{
return false;
}
}
if(sta.empty())
return true;
else
return false;
}
};
使用哈希表保存括号对应的映射
class Solution {
public:
bool isValid(string s) {
int len = s.size();
if(len & 1==1)
return false;
stack<char> sta;
map<char,char> wordbook;//建立哈希表
wordbook.insert(make_pair<char,char>(')','('));
wordbook.insert(make_pair<char,char>('}','{'));
wordbook.insert(make_pair<char,char>(']','['));
//wordbook
for(int i=0;i<len;i++){
if(sta.empty() || s[i]=='(' || s[i]=='{' || s[i]=='['){ //栈为空，或当前字符为左括号，入栈
sta.push(s[i]);
}else if(wordbook[s[i]] == sta.top()){
sta.pop();
}else{
return false;
}
}
if(sta.empty())
return true;
else
return false;
}
};
4.实现 strStr()
方法一、使用库函数find(在面试时不建议使用)
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle==" ")
return 0;
int pos = haystack.find(needle);
return pos;
}
};
方法二、BF算法 暴力破解 时间复杂度O(M∗N)
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.empty())
return 0;
int i=0,j=0;
while(haystack[i]!=' '&&needle[j]!=' ')
{
if(haystack[i]==needle[j])
{
i++;
j++;
}
else
{
i=i-j+1;
j=0;
}
}
if(needle[j]==' ')
return i-j;
return -1;
}
};