8、String to Integer (atoi)
题目
这道题目关键是要考虑清楚各种输入用例。针对每一种情况，函数都能处理，也就是函数鲁棒性很高。代码如下：
class Solution {
public:
int myAtoi(string str) {
int index=;
int flag = ;
long long res=;
if(str.length()==)return ;
while (str[index]==' ')//去除空白
index++;
if(str[index] == '-')//负数
{
flag = -;
index++;
}
else if(str[index] == '+')//负数
{
flag = ;
index++;
}
int len = str.length();
while (str[index]>=''&&str[index]<='')
{
res = res * +str[index]-'';
if(res > INT_MAX)
return flag> ? INT_MAX:INT_MIN;
index++;
}
return res*flag;
}
};
----------------------------------------------------------------------------------------------分割线------------------------------------------------------------------------------------
9、Palindrome Number
题目
话不多说，直接看代码:
class Solution {
public:
bool isPalindrome(int x) {
if (x == -)
{
return false;
}
if (x<)
{
//x=0-x;
return false;
}
int length = (int)log10(x*1.0)+;//判断x的位数
//int s[20];
int temp1 = x;
int temp2 = x;
int middle = length/;
int i,j,left,right,power=length-;
for (i=;i<=middle;i++)
{
left=temp1/(int)pow(10.0,power);
temp1=temp1%(int)pow(10.0,power);
power--;
right = temp2%;
temp2 = temp2/;
if (left != right)
{
return false;
}
}
return true;
}
};
--------------------------------------------------------------------------------------------------分割线---------------------------------------------------------------------------
10、Regular Expression Matching
题目
这道题目，一开始我以为要用到编译原理里面学到的自动机构造方法，后来在网上看别人的解题思路，其实可以采用递归的方法直接进行匹配，其思路是这样的;
思路1：递归。根据下一个字符是否是'*'分情况判断。
- 如果p的下一个字符不是'*'，只需判断当前字符是否相等，或者p[cur]='.'，递归处理s[1]和p[1]；
- 如果是p的下一个'*'，则当前s和p相等或者p='.'情况下，依次判断s[0...s.length]和p2]是否match；
实现代码可以参考如下：
class Solution {
public:
bool isMatch(string s, string p) {
return isMatch(s.c_str(),p.c_str());
}
bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (*p == ) return *s == ;
if (*(p+) != '*')
{
if (*s != && (*p == *s || *p == '.')) return isMatch(s+, p+);
else return false;
}
else
{
// *s == *p
while (*s != && (*s == *p || *p == '.'))
{
if (isMatch(s, p+)) return true;
s++;
}
return (isMatch(s, p+));
}
}
};
当然，这道题还可以采用自动机进行解决，不过难度也是很大的，需要对模式串进行分析，构造出自动机，然后通过s串逐个字符的匹配。下面是最开始未完成的代码：
class node
{
public:
node()
{
val = ;
self = -;
isEnd = false; }
node(char c)
{
val = c;
self = -;
isEnd = false;
} public:
char val;
int self;//是否包含*
bool isEnd;//是否是终态 }; class Solution {
public:
bool isMatch(string s, string p)
{
if("" == s)
return true;
if("" == p)
return false;
vector<node*> status;//存储自动机状态节点
node *temp; temp = new node(p[]);
status.push_back(temp); int i=;
int index = ;
while (p[i] != '\0')//注意，如果模式是a*aaa最终转换为节点为{a,3,true},true表示当前节点是终态
{
index = status.size();
if(p[i] == '*')
{
if(status[index-]->self != -)//考虑模式中有a*a*这种情况,当处理第二个*时，前一个节点的self不为-1
status[index-]->self = ;
else
status[index-]->self++;
i++;
continue;
}
if(p[i] == status[index-]->val)
{
status[index-]->self++;
i++;
continue;
}
temp = new node(p[i]);
status.push_back(temp); i++; }
index = status.size();
index--;
//比如a*b*最后做出的两个节点都是终态
status[index]->isEnd = true;//最后一个节点肯定是终态 while (index >= )//判断各个节点是不是终态
{
if(status[index]->self != -)
status[index]->isEnd = true;
else//只要当前不是终态，那它之前的所有节点都不是终态
{
break;
}
index--;
} i=;
index = ;
int nodeCount = status.size(); while(s[i] != '\0')
{
if(index >= nodeCount)
return false;
if(status[index]->val == '.')
{
if(status[index]->self != -)
{
if(status[index]->isEnd)
return true;
else
{ }
}
else
{
i++;
index++;
continue;
}
}
else
{ }
i++;
} }
};
---------------------------------------------------------------------------------------------------分割线--------------------------------------------------------------------------
11、Container With Most Water
题目
题目要求：给定n个非负整数，构成n个点，其点坐标为(i,ai),然后过每个点做x轴的垂线，形成n条线段，任意选择两条垂线段作为“容器”，求最大容器的所能容下的水量。
这类求最值的问题，第一想法都是暴利，也就是一次遍历两两线段，求其容器体积，并找出最大值，其代码如下：
class Solution {
public:
int maxArea(vector<int>& height) {
int count = height.size();
int i,j;
int volumn = ,temp;
for (i = ;i < count;i++)
{
for(j = i+;j < count;j++)
{
temp = height[i] > height [j] ? height[j] : height[i];//取最小值，也就是边矮的
if(volumn < temp * (j-i))
volumn = temp * (j-i);
}
}
return volumn;
}
};
很显然，这中思路的时间复杂度肯定是O(n*n);
仔细一想，这个题目可以采用首尾夹逼的策略进行求解，其代码如下：
class Solution {
public:
int maxArea(vector<int> &height) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int i = ;
int j = height.size() - ;
int ret = ;
while(i < j)
{
int area = (j - i) * min(height[i], height[j]);
ret = max(ret, area);
if (height[i] <= height[j])
i++;
else
j--;
}
return ret;
}
};