力扣刷题（4）
正则表达式匹配
正则表达式匹配-力扣
思路来源：ithewei
- 若 *p 为空，*s 为空则匹配，*s 为非空则不匹配；
- 当 *s为非空时，*p == *s || *p == ‘.’ 时第一个字符匹配；
- 若 *(p+1) != ’ * '时，则递归判断剩下的是否匹配 first_match && isMatch(++s, ++p)
- 若 *(p+1) == ’ * '，则有两种情况匹配：
- 匹配0个字符，s匹配剩下的，即isMatch(s, p+2)
- 匹配1个字符，继续用p匹配剩下的s，即first_match && isMatch(++s, p)
bool isMatch(char* s, char* p) {if(!*p)return !*s;bool first_match = *s && (*s == *p || *p == '.');if(*(p+1) =='*') {return isMatch(s,p+2) || (first_match && isMatch(++s,p));}else{return first_match && isMatch(++s,++p); }
}
盛最多水的容器
盛最多水的容器-力扣
解法一：最容易想出的方法就是将每个位置都进行比较
int maxArea(int* height, int heightSize) {int* head=height;int* tail=height;int max=0;for(int i=0;i<heightSize-1;i++){for(int j=i+1;j<heightSize;j++){int min=*(head+i) > *(tail+j) ? *(tail+j):*(head+i);int tmp=min*(j-i);if(max < tmp)max=tmp;}}return max;
}
时间复杂度为O（n^2），无法通过，因此需要其他的方法
解法二：
int maxArea(int* height, int heightSize) {int* head=height;int* tail=height+heightSize-1;int max=0;while(head < tail){int min=*(head) < *(tail) ? *(head) : *(tail);int tmp=min*(tail-head);if(max < tmp)max=tmp;*(head) < *(tail) ? head++:tail--;}return max;
}
该解法的时间复杂度为O（n），因此可以轻松的通过
