programming

[輸入] 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; } ...