力扣刷题（4）

本文主要是介绍力扣刷题（4），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

正则表达式匹配

正则表达式匹配-力扣

思路来源：ithewei

1. 若 *p 为空，*s 为空则匹配，*s 为非空则不匹配；
2. 当 *s为非空时，*p == *s || *p == ‘.’ 时第一个字符匹配；
3. 若 *(p+1) != ’ * '时，则递归判断剩下的是否匹配 first_match && isMatch(++s, ++p)
4. 若 *(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），因此可以轻松的通过

这篇关于力扣刷题（4）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---