2017.5.15学习总结

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]是否为“ * ”进行分类：

1. p[1]==‘ * ’：* >=1进行递归，同时考虑跳过 * 匹配成功的情况，返回true
2. 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;
        
    }

Android开发艺术探索

Android中的IPC方式