programming

Start to test at 2018 Feb 28 8:00 20 .  Valid Parentheses class Solution { /*if c = '(' or '{' or '[', return true; otherwise, return false*/ bool isLeftOperator(char c) { return ((c == '{') || (c == '[') || (c == '(')); } bool isMatch(char c1, char c2) { if (c1 == '}') return (c2 == '{'); if (c1 == ']') return (c2 == '['); if (c1 == ')') return (c2 =='('); return false; } public: // '(', ')', '{', '}', '[' and ']', bool isValid(string s) { /*use a stack to store the operators*/ stack<char> stack; char now, c; for (int i = 0; i < s.length(); i++) { now = s.at(i); if (isLeftOperator(now)) { stack.push(now); } else { /*boundary ...

slow: class Solution { public: int rotatedDigits(int N) { int total = 0; for (int i = 1; i <= N; i++) { int digit; int r = 0; int base = 1; int now = i; while (now) { digit = now % 10; now /= 10; if (digit == 0 || digit == 1 || digit == 8) r += (digit * base); else if (digit == 2) r += 5 * base; else if (digit == 5) r += 2 * base; else if (digit == 6) r += 9 * base; else if (digit == 9) r += 6 * base; else { r = i; break; } base *= 10; } if (r != i) { //printf("* %d %d\n", r, i); total++; } } ...

class Solution { public: int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) { vector<int> distance(n, INT_MAX); vector<list<pair<int, int>>> edges(n); distance[src] = 0; queue<int> q; list<pair<int, int>>::iterator it; for (int i = 0; i < flights.size(); i++) { int s = flights[i][0]; int t = flights[i][1]; int cost = flights[i][2]; edges[s].push_back(make_pair(t, cost)); } q.push(src); int remain = K; while (remain-- >= 0) { int count = q.size(); for (int i = 0; i < count; i++) { int now = q.front(); q.pop(); for (it = edges[now].begin(); it != edges[now].end(); it++) { if ((distance[now] + it->second) < distance[it->first]) { ...

class Solution { public: int swimInWater(vector<vector<int>>& grid) { //DFS int w, h; h = grid.size(); w = grid[0].size(); vector<vector<bool>> visit; for (int i = 0; i < h; i++) { vector<bool> tmp(w, false); visit.push_back(tmp); } typedef pair<int, pair<int,int>> item; std::priority_queue<item, vector<item>, std::greater<item>> q; item t = (make_pair(grid[0][0], make_pair(0, 0))); visit[0][0] = true; q.push(t); while(1) { int x, y; int max = 0; item now = q.top(); q.pop(); y = now.second.first; x = now.second.second; if (y > 0 && !visit[y - 1][x]) { int max = grid[y - 1][x] > now.first ? grid[y - 1][x] : now.first ; q.push(make_pair(max, make_pair(y - 1, x))); visit...