programming

Google code jam Qualification Round 2018 Saving The Universe Again [暴力法]: 對S所有排序可能情況逐一檢查，保留合法者，並回傳最小的交換次數。 假設P 'length = L 且 C有K個。 Complexity = C(L, K) (所有排列情況)* L = L*L!/((K!) * (L-K)!) ，指數成長。 雖然可以先從 C(L, K)過濾掉不可能的情況，但加速有限。 [遞迴公式] 設 m(P, D) 為字串P限制D下的最佳解。 假設沒有S則m(P,D) = 0; 否則設第一個S的位置為T，P = CCC..CSP'。 則遞迴公式為: m(P, D) = min ( T + m(P', D - 1)), T - 1 +  m(P', D/2) , T - 2 + m (P', D/4 - 1) ... (m(P'', D/(2^T) - 1))). 範例: m(CSCSS, 3) = min( 1(用來swap C S CSS) + m(CCSS, 2) , m(SCSS, 1(=3>>1)) ) 其中 m(SCSS, 1)不可能。 遞迴的求 1 + m(CCSS, 2) = 1 + min( (2 + m(CCS, 1)), m(CSS, 1)) 其中 m(CSS, 1)不可能。 故再次遞迴 opt = 1 + 2 + m(CCS, 1) = 1 + 2 + 2 = 5 [bottom up] [Time Complexity]:

[輸入] length(s) = n; [暴力法] 將s按照一位或兩位的方式切割，試過所有組何，看是否是合法並累計之。 在每個決策點 展成一顆 二元樹，故知道葉節點共有O(2^n)個； 所以暴力法複雜度是O(n*2^n) 二元樹例子如下: [遞迴公式]: [bottom up] [Time Complexity] [Space Complexity] [Example] [Solution] class Solution { public: int numDecodings(string s) { if (!s.length()) { return 0; } else if (s.at(0) == '0') { return 0; } vector<int> v(s.length() + 1, 0); v[0] = 1; v[1] = 1; int prev = s.at(0) - '0'; for (int i = 1; i < s.length(); i++) { int now = (s.at(i) - '0'); int n = 10 * prev + now; if (n > 26) { if (now == 0) { return 0; } v[i + 1] = v[i]; } else { if (n == 0) { return 0; } else if (now == 0) { v[i + 1] = v[i - 1]; ...

[暴力法] 等價於把K個相同的物品放置到n個相異的籃子中。 Complexity = C(k + n - 1,  n - 1) or C(k + n - 1,  k); By  n ,  m  and  k  ( 1 ≤  n ,  m  ≤ 500 ,  0 ≤  k  ≤ 500 ). max Complexity ~ C(1000, 500) ~ (4^500) Stirling's approximation  yields the following approximation, when  {\displaystyle n,i}  are sufficiently large: {\displaystyle {n \choose i}\sim {\sqrt {n \over 2\pi i(n-i)}}\cdot {n^{n} \over i^{i}(n-i)^{n-i}}} In particular, when  {\displaystyle n}  is sufficiently large: {\displaystyle {2n \choose n}\sim {\frac {4^{n}}{\sqrt {\pi n}}}} [遞迴公式] 設opt(s, t)為在前s個weeks可缺席t堂課最佳解，h(s, i)是在第s個week缺席i堂課花費的hour數。 則 opt(s, t) = min(opt(s -1, t - i) + h(s, i)), i = 0 to k。 [bottom up] 一開始我們在第0周(s = 0)，該時的opt(0, i) = h(s, i) 最後opt(n,k)就是最佳解。 [Time Complexity]: 共有n列，每列有k個元素，每個元素需要計算k個組合，故複雜度為O(n*(k^2))。 [Space Complexity]: 用兩列每列k+1個元素的表格即可。 [Example] 1.輸入 n = 3, m = 5, k = 4 01011 10011 11100 ...

my answer: class Solution { bool DFS(int v, set<int> &s, vector<vector<int>>& g, vector<int> &a) { int u = -1; for (int i = 0; i < g[v].size(); i++) { u = g[v][i]; if ((a[u] == 1) || (s.find(u) != s.end())) { set<int>::iterator it; a[v] = 1; return true; } else if (a[u] == -1) { s.insert(u); if (DFS(u, s, g, a)) { a[v] = 1; return true; } s.erase(u); } } a[v] = 0; return false; } public: vector<int> eventualSafeNodes(vector<vector<int>>& graph) { queue<int> empty; vector<int> r; vector<int> a(graph.size(), -1); set<int> s; for (int i = 0; i < graph.size(); i++) { if (a[i] != -1) ...

解答思路 以上面表格的例子解釋: 如果min(A[i], B[i]) > max(A[i -1], B[i - 1])， 則A[i], B[i]無論有無swap都是正確的。 反之如果min(A[i], B[i]) <  max(A[i -1], B[i - 1])，那麼一定只有一種pattern 意及，min(A[i], B[i]) 與 min(A[i -1], B[i -1])要在同一列上；max(A[i], B[i]) 與 max(A[i -1], B[i -1])要在同一列上。 以上面的範例來說，一開始觀察min(A[1], B[1]) = 39 > max(A[0], B[0])；所以這裡的順序是無所謂的。我們前進到下一對。 min(A[2], B[2]) = 40 <= max(A[1], B[1])  = 41; 這裡便要求要一定的順序。 也就是min(A[2], B[2]) = 40和min(A[1], B[1]) = 39, 也就是max(A[2], B[2]) = 54和max(A[1], B[1]) = 41 需在同一列上。 同時，我們發現min(A[2], B[2]) = 40和min(A[1], B[1]) = 39並不在同一列上(同理，max(A[2], B[2]) = 54和max(A[1], B[1]) = 41不在同一列上)。 要達成這樣的目標有兩種方式；要嘛swap 41和39；要嘛swap 40和54，我們在這裡無法決定。 至少，我們已經知道在這個區間內有配對需要交換。 所以我們繼續下去， 一直到發現下一個邊界min(A[i], B[i]) > max(A[i -1], B[i - 1])為止。 我們可以從下圖看出這個區間的範圍。 注意到黃色區域的數字都是互相關聯的；也就是說，當我們固定了其中任何一組的順序，其他各組的順序也就定下來了；不然，會違反嚴格遞增的條件。 例如，當我們選定(63, 43)這組63在上面時， 我們就決定了下面的順序: 如橙色標明，需要5次交換。 反之，如果是下面的次序，需要4次交換(用綠色標明)。 因為4次比較少，所以我們選擇4次交換的方式。 執行過程即不斷的尋找區間...

1st version: 36 / 36 test cases passed. Status: Accepted Runtime: 47 ms Submitted: 0 minutes ago class Solution { public: int bestRotation(vector<int>& A) { int gain = 0; int r; priority_queue<int, vector<int>, greater<int>> q; for (int i = 0; i < A.size(); i++) { int diff = i - A[i]; if (diff >= 0) { gain++; q.push(diff); } } int current = gain; r = 0; for (int shift = 1; shift <= A.size() - 1; shift++) { while (!q.empty() && (shift > q.top())) { q.pop(); current--; } if (A[shift - 1] <= (A.size() - 1)) { current++; q.push(shift + (A.size() - 1) - A[shift - 1]); } if (current > gain) { r = shift; gain = current; } } ...

origin class Solution { public: int numMatchingSubseq (string S, vector<string>& words) { int r = 0; vector<vector<int>> posMap(26, vector<int>(0)); for (int i = 0; i < S.length(); i++) { posMap[S.at(i) - 'a'].push_back(i); } int i, j, k; for (i = 0; i < words.size(); i++) { int pos = -1; for (j = 0; j < words[i].length(); j++) { char c = words[i].at(j); int idx = c - 'a'; for (k = 0; k < posMap[idx].size(); k++) { if (posMap[idx][k] > pos) { pos = posMap[idx][k]; break; } } if (k == posMap[idx].size()) { break; } } if (j == words[i].length()) { r++; } } return r; } ...

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

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

class Solution { public: int maxChunksToSorted(vector<int>& arr) { vector<int> sorted(arr); sort(sorted.begin(), sorted.end()); vector<int> max; int max_now = -1; for (int i = 0; i < arr.size(); i++) { if (arr[i] > max_now) { max_now = arr[i]; max.push_back(arr[i]); } else max.push_back(max_now); } int total = 0; for (int i = 0; i < arr.size(); i++) { if (sorted[i] == max[i]) { total++; } } return total; } };

class Solution { public: int reachNumber(int target) { if (target == 0) return 0; if (target < 0) target *= -1; int remain = target; int step = 0; bool odd = (target & 1); while(remain > 0) { step++; remain -= step; } int pattern = step % 4; int pattern2 = pattern % 2; printf("%d %d %d\n", step, pattern, pattern2); if (odd) { if ((pattern == 1) || (pattern == 2)) return step; else { if (pattern == 0) return (step + 1); if (pattern == 3) return (step + 2); } } else { if ((pattern == 0) || (pattern == 3)) return step; else { if (pattern == 1) return (step + 2); if (pattern == 2) re...

class Solution { public: int openLock(vector<string>& deadends, string target) { map<string, int> m; map<string, int>::iterator mit; for (int i = 0; i < deadends.size(); i++) { m.insert(make_pair(deadends[i], -1)); } queue<pair<string, int> > q; string s("0000"); if (m.find(s) != m.end()) { return -1; } q.push(make_pair(s, 0)); m.insert(make_pair(s, 0)); while(!q.empty()) { string now = q.front().first; int length = q.front().second; //printf("%s %d\n", now.c_str(), length); q.pop(); for (int i = 0; i < 4; i++) { string up(now); char c = up.at(i); if (c < '9') { c = c + 1; } else { c = '0'; } ...

#include <iostream> #include <limits.h> #include <vector> #include <string> #include <iterator> #include <map> #include <queue> #include <list> #include <algorithm> #include <stdio.h> #include <set> using namespace std; class Solution { int total; string start; int digit; int numbers; bool DFS(set<string> &used, string &now, string &ans) { if(used.size() == total) { now.erase(0, 1); now.push_back('0'); if (now == start) { return true; } } for (int i = 0; i < numbers; i++) { string tmp(now); tmp.erase(0, 1); tmp.push_back('0' + i); if (used.find(tmp) == used.end()) { ans.push_back('0' + i); used.insert(tmp); bool done = DFS(used, tmp, ans); if (d...

链接：https://www.zhihu.com/question/35967887/answer/125238385 来源：知乎 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 std::vector<std::string> split(const std::string &s, const std::string &d) { std::vector<std::string> v; char *str = new char[s.size()+1]; strcpy(str, s.c_str()); while (char *t = strsep(&str, d.c_str())) v.push_back(t); delete[] str; return v; } std::string &ltrim(std::string &s) { if (s.empty()) return s; std::string::const_iterator iter = s.begin(); while (iter != s.end() && isspace(*iter++)); s.erase(s.begin(), --iter); return s; } std::string &rtrim(std::string &s) { if (s.empty()) return s; std::string::const_iterator iter = s.end(); while (iter != s.begin() && isspace(*--iter)); s.erase(++iter, s.end()); return s; } std::string &trim(std::string &s) { ltrim(s); rtrim(s); return s; } bool startsWith(const std::string &str, co...