codility出了lesson 5了。
(1) 合法括号序列，包括( [ { ) ] }这6种字符的字符串，长度N在[0..200000]范围内，为其是否合法。
要求时间复杂度O(N)，空间复杂度O(N)。
用堆栈简单判断就可以了。
// you can also use includes, for example:// #include#include int solution(const string &S) { // write your code in C++ 98 int n = S.size(); stack s; for (int i = 0; i < n; ++i) { if (S[i] == ')') { if ((s.empty()) || (S[s.top()] != '(')) { return false; } s.pop(); } else if (S[i] == ']') { if ((s.empty()) || (S[s.top()] != '[')) { return false; } s.pop(); } else if (S[i] == '}') { if ((s.empty()) || (S[s.top()] != '{')) { return false; } s.pop(); } else { s.push(i); } } return s.empty(); }
(2) x轴上有一群鱼，每条鱼的位置不同。每条鱼游动的方向可能沿着x正方向，也可能沿着x轴负方向。从左到右（沿着x轴正方向）知道每条鱼的大小和游动的方向，每条鱼的大小不同，游动速度一样，两条鱼相遇，大鱼会吃掉小鱼，问时间足够长之后能剩下多少条鱼。
数据范围 鱼数 N [1..10^5]，每条鱼游动的方向只能是+1和-1，鱼大小的范围[0..10^9]。要求复杂度 时间O(N)，空间O(N)。
这个题也不难因为每条鱼速度相同，所以只有反方向的鱼才可能相遇。 我们从左到右把往正方向游动的鱼压入堆栈，当出现第一条负方向游动的鱼时，不断从堆栈弹出那些鱼，这些鱼按顺序和这条鱼相遇，决定哪条被吃掉。直到这条负方向的鱼被吃掉或者堆栈为空。
// you can also use includes, for example:// #include（3） sigma 2012#include int solution(vector &A, vector &B) { // write your code in C++ 98 int n = A.size(),m = n; stack s; for (int i = 0; i < n; ++i) { if (B[i]) { s.push(A[i]); } else { while ((!s.empty()) && (s.top() < A[i])) { s.pop(); --m; } if (!s.empty()) { --m; } } } return m; }