2014年9月18日星期四
3sum
这道题目和3sum closest差不多，都是用夹逼法可以做到，时间复杂度是max(O(n^log n), O(n^2))
但是需要注意的是这道题目要求得到的结果不重复，不重复的结果需要用unique去掉重复的那些元素
unique是C++中用来除去容器中相同元素的函数，它的做法是将重复的元素用后面的元素进行覆盖，所以原来容器的大小是不变化的，在unique后面接一个erase就能够去掉重复元素了
其实用记录上一个结果的方式也能够去掉重复，代码如下
class Solution {
public:
vector > threeSum(vector &num) {
vector> result;
sort(num.begin(), num.end());
if (num.size() <= 2) return result;
const int target = 0;
int prev_a, prev_b, prev_c;
for (auto a = num.begin(); a != prev(num.end(), 2); prev_a = *a, a++){
if (a != num.begin() && prev_a == *a)
continue ;
auto b = next(a);
auto c = prev(num.end());
prev_b = *b + 1;
prev_c = *c + 1;
while (b < c){
int cur_sum = *a + *b + *c;
if (cur_sum == target){
if (!(prev_b == *b && prev_c == *c)){
result.push_back({*a, *b, *c});
prev_b = *b, prev_c = *c;
}
b++, c--;
continue ;
}
if (cur_sum > target)
c--;
else
b++;
}
}
//sort(result.begin(), result.end());
//result.erase(unique(result.begin(), result.end()), result.end());
return result;
}
};
2014年8月28日星期四
[Leetcode]Longest Valid Parenthese
Longest Valid Parentheses
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
这道题只需要从左到右扫描一遍就可以，分为下面的情况
如果碰到的是(，则压栈，压入当前扫描的位置
如果碰到的是)，则
1. 如果栈为空，则说明到该位置并不符合条件，即左括号个数<右括号个数，且不存在某个中间位置i，使得从i到b是符合条件的，也就是能够从中间开始，因为如果存在这样的i，则a到i是符合条件的，i到b是符合条件的，也就是说a到b是符合条件的，所以这段结束了就可以记录一下b的位置，记为last
2. 如果栈不为空，则弹栈，还分下面两种情况
2.1 若此时栈为空，则max_len更新为max(i - last, max_len)
2.2 若此时栈不为空，则更新max_len为max(max_len, i - s.top())，s.top()到i的距离，也就是说在s.top()和i之间的是符合条件的没有问题
订阅：
评论 (Atom)