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])
{
/*考慮出現(xiàn)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計算，因為結(jié)果肯定比前一次結(jié)果心鸾铡（要么比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;
}
