programming

Bad int numSubarrayBoundedMax(vector<int>& A, int L, int R) { bool valid = false; int start = -1; int sub_start = -1; int r = 0; for (int i = 0; i < A.size(); i++) { if (A[i] <= R) { if (start == -1) { start = i; } if (A[i] >= L) { valid = true; if (sub_start != -1) { r -= ((i - sub_start) * (i - sub_start + 1) / 2); sub_start = -1; } } else if (sub_start == -1) { sub_start = i; } } else { if (valid) { r += ((i - start) * (i - start + 1)) / 2; if (sub_start != -1) { r -= ((i - sub_start) * (i - sub_start + 1) / 2); } } // reset ...

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...

#include <cstdlib> #include <new> template <class T> struct Mallocator { typedef T value_type; Mallocator() = default; template <class U> constexpr Mallocator(const Mallocator<U>&) noexcept {} [[nodiscard]] T* allocate(std::size_t n) { if(n > std::size_t(-1) / sizeof(T)) throw std::bad_alloc(); if(auto p = static_cast<T*>(std::malloc(n*sizeof(T)))) return p; throw std::bad_alloc(); } void deallocate(T* p, std::size_t) noexcept { std::free(p); } }; template <class T, class U> bool operator==(const Mallocator<T>&, const Mallocator<U>&) { return true; } template <class T, class U> bool operator!=(const Mallocator<T>&, const Mallocator<U>&) { return false; } https://elloop.github.io/c++/2016-09-19/stl-apply-imp-95-simple-allocator http://www.cnblogs.com/suzhou/p/5381738.html http://www.justskins.com/forums/shm_open-vs-open-253314.html http://www.drdobbs.com/creati...

class Solution { public: string reorganizeString(string S) { map<char, int> m; map<char, int>::iterator it; string ans; for (int i = 0; i < S.length(); i++) { it = m.find(S.at(i)); if (it != m.end()) { it->second++; } else { m.insert(make_pair(S.at(i), 1)); } } int max; vector<pair<int, char>> tmp; for (it = m.begin(); it != m.end(); it++) { tmp.push_back(make_pair(it->second, it->first)); } sort(tmp.begin(), tmp.end()); int sum = 0; for (int i = 0; i < tmp.size() - 1; i++) { sum += tmp[i].first; } if (tmp[(tmp.size()-1)].first > sum + 1) { return ans; } for (int i = 0; i < tmp.size(); i++) { int pos = 0; char c = tmp[i].second; int count = tmp[i].first; ...