LeetCode10
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
这里s是要匹配的字符串，p是带有“ . ”和“ * ”的匹配串。
这道题可以用递归和DP解决，主要难点是需要考虑的情况比较多，直接上代码（递归写法）
bool isMatch(string s, string p) {
if (p.empty())
return s.empty(); //如果p和s都完全匹配 则返回
if ('*' == p[1])
{
/*考虑出现aaa a*ab这种情况 对a*后面的进行递归验证（aa a*也一样，只不过他们substr（2）等于空）
相当于返回递归出口
*/
if(isMatch(s, p.substr(2)))
return true;
if(!s.empty())
{
if((s[0] == p[0] || '.' == p[0])) //考虑：aab a*
return isMatch(s.substr(1), p);
else
return false;
}
else
return false;
}
else
{
if(!s.empty()) //考虑：aaa aab
{
if((s[0] == p[0] || '.' == p[0]))
{
return isMatch(s.substr(1), p.substr(1));
}
else
return false;
}
else
return false;
}
}
如注释：
总体按照p[1]是否为“ * ”进行分类：
- p[1]==‘ * ’：* >=1进行递归，同时考虑跳过 * 匹配成功的情况，返回true
- p[1]!=‘ * ’ ：比较简单，直接依次判断每个字符是否相等
LeetCode11
题意：在二维坐标系中，(i, ai) 表示 从 (i, 0) 到 (i, ai) 的一条线段，任意两条这样的线段和 x 轴组成一个木桶，找出能够盛水最多的木桶，返回其容积。
解析：暴力肯定不可以，会超时。这里主要判断那些可以省略计算的地方。
举个例子：5 9 8 4 2，如果5和2进行计算，以2为标准，且5和2的距离最远，所以计算后2不用再和9 8 4计算，因为结果肯定比前一次结果小（要么比2小，要么距离更近），所以只需O（n）时间便可以解出，代码如下：
int maxArea(vector<int>& height) {
int l=0;
int size=height.size();
int r=size-1;
int max=0;
while(l<r)
{
int v=min(height[l],height[r])*(r-l);
if(v>max)
max=v;
//cout<<max<<" ";
if(height[l]<height[r])
l++;
else
r--;
}
return max;
}
