leetcode_OJ WC98 99 解題心得
- 暑假最後因實習進度交接，有點累，打了weekly contest結果懶得更新，這次一次更新吧
- Contest time WC98: Aug 19, 2018 (題解完成)
- Contest time WC99: Aug 26, 2018 (題解完成)
WC98
PA. 888. Fair Candy Swap 水題
- 題意:兩人各持有數堆糖果，每一堆有n個糖果，問各自交換哪一堆可以讓他們兩個的糖果數量一樣
- 思路:直接做，兩個人一樣取平均，暴力找即可。
- 分析:Time complexity: O(N^2), Space complexity O(N)
class Solution { public: vector<int> fairCandySwap(vector<int>& A, vector<int>& B) { int suma, sumb, flg; suma = sumb = 0; flg = 0; vector<int> res; for(int i = 0; i < A.size(); i++) { suma += A[i]; } for(int i = 0; i < B.size(); i++) { sumb += B[i]; } int fair = (suma + sumb) / 2; for(int i = 0; i < A.size(); i++) { for(int j = 0; j < B.size(); j++) { if(suma - A[i] + B[j] == sumb - B[j] + A[i]) { res.push_back(A[i]); res.push_back(B[j]); flg = 1; break; } } if(flg) { break; } } return res; } bool check(vector<int>& A, vector<int>& B) { int suma, sumb; suma = sumb = 0; for(int i = 0; i < A.size(); i++) { suma += A[i]; } for(int i = 0; i < B.size(); i++) { sumb += B[i]; } return (suma == sumb) && (suma) && (sumb);//should be more than zero } };
PB. 890. Find and Replace Pattern string + map
- 題意:找出趨勢一樣的單字，在此趨勢一樣是指英文字出先的『頻率、方式』一致，例如 aabb = ccbb = jjkk , apple = knnrx 等
-
WA思路:趨勢一樣代表說，我下一個是不一樣的字母，則你也是;我如果是一樣的則你也要一樣，這樣直接做即可（但是接下來會遇到一個問題，稍後下方『缺失分析』會提及）
class Solution { public: vector<string> findAndReplacePattern(vector<string>& words, string pattern) { vector<string> res; for(auto it: words) { if(check(it, pattern)) { res.push_back(it); } } return res; } bool check(string to_chk, string pat) { if(to_chk.size() != pat.size()) { return false; } for(int i = 0; i < to_chk.size() - 1; i++) { if(to_chk[i] == to_chk[i + 1]) //趨勢要一致 { if(pat[i] != pat[i + 1]) { return false; } } else { if(pat[i] == pat[i + 1]) //趨勢要一致 { return false; } } } return true; } };
-
缺失分析:WA的原因在於，這樣會把aba = xyx = abc 但實際上這題要求連每一個字母出現頻率也要一樣，因此最後a b c各自只有一個並不屬於同一類
- 改進思路:多一個map來統計，並且對照組的map內容要和pattern一樣，在英文字母一樣的時候不用管，不一樣時要看各自map內容物是否相等，否則返回false
class Solution { public: vector<string> findAndReplacePattern(vector<string>& words, string pattern) { vector<string> res; for(auto it: words) { if(check(it, pattern)) { res.push_back(it); } } return res; } bool check(string to_chk, string pat) { if(to_chk.size() != pat.size()) { return false; } /*check the mapping correspondence*/ map<char, int> chkmap; map<char, int> patmap; for(auto it : to_chk) { chkmap[it]++; } for(auto it : pat) { patmap[it]++; } /*check the changing trend*/ for(int i = 0; i < to_chk.size() - 1; i++) { if(to_chk[i] == to_chk[i + 1]) { if(pat[i] != pat[i + 1]) { return false; } } else { if(pat[i] == pat[i + 1]) { return false; } else if(patmap[pat[i]] != chkmap[to_chk[i]] || patmap[pat[i + 1]] != chkmap[to_chk[i + 1]]) /*such as abc and aba should not be the same, if no this part, will get wrong answer*/ { return false; } } } return true; } };
- 分析(正解整體):Time complexity: O(N * K), where N is # of words, and K is the length of word, Space complexity O(N * K), each time for each pattern and word, we use a map to assist.
PC. 889. Construct Binary Tree from Preorder and Postorder Traversal 重建樹
- 題意:由先序和後序建立一顆二元樹
- 思路: https://imgur.com/a/s9kTWbG (Picture source credit to: https://www.youtube.com/watch?v=53aOi0Drp9I )
- 首先preorder = {root left right}, post order = {left right root}，利用上方的圖片可以看到，舉例來說 pre = [1,2,4,5,3,6,7]. post = [4,5,2,6,7,3,1]，pre = 1 245 367, post = 452 673 1，pre[1]必為左子樹根，正好對應到post[2] (但不盡然每次都是post[2])，因此可以用code中找出ileft subtree的root位置，最後便能用以下四個(左右子數各自對應之pre post traversal)
while(pre[1] != post[left_subtree_root_pos]) //find the equal for the right subtree { left_subtree_root_pos++; }
- post traversal of left subtree = post[0:left_subtree_root_pos] (雙端皆為封閉區間 []而非())
- post traversal of right subtree = post[left_subtree_root_pos + 1:-2] (雙端皆為封閉區間)
- pre traversal of left subtree = pre[1:left_subtree_root_pos + 1] (雙端皆為封閉區間)
- pre traversal of right subtree = pre[left_subtree_root_pos + 2:-1] (雙端皆為封閉區間)
- 接著利用root->left = recursively_construct(left_subtree_pre_traverse, left_subtree_post_traverse)
- 再利用root->right = recursively_construct(right_subtree_pre_traverse, right_subtree_post_traverse)
- 首先preorder = {root left right}, post order = {left right root}，利用上方的圖片可以看到，舉例來說 pre = [1,2,4,5,3,6,7]. post = [4,5,2,6,7,3,1]，pre = 1 245 367, post = 452 673 1，pre[1]必為左子樹根，正好對應到post[2] (但不盡然每次都是post[2])，因此可以用code中找出ileft subtree的root位置，最後便能用以下四個(左右子數各自對應之pre post traversal)
- 分析:Time complexity O(N^2), Space complexity O(N^2) where N is the # of nodes, since each time for every node(N), we have to go through the array of traversed node again(N), which in total is O(N^2)
- 備註:可以用程式碼附的print_subtree_dbg 來看看子樹到底包了哪些東西喔，比較好瞭解，以及一些stdio
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* constructFromPrePost(vector<int>& pre, vector<int>& post) { return construct(pre, post); } TreeNode* construct(vector<int>& pre, vector<int>& post) { if(pre.size() == 1 && post.size() == 1) // the base case with leaf { //printf("base case presize %d postsize %d\n", pre.size(), post.size()); TreeNode* newnode = new TreeNode(pre[0]); return newnode; } else if(pre.size() == 0 && post.size() == 0) //the null { return NULL; } vector<int> left_subtree_pre; vector<int> left_subtree_pos; vector<int> right_subtree_pre; vector<int> right_subtree_pos; int left_subtree_root_pos = 0; while(pre[1] != post[left_subtree_root_pos]) //find the equal for the right subtree { left_subtree_root_pos++; } // printf("\nleft pos %d with root %d\n", left_subtree_root_pos, pre[0]); for(int i = 0; i <= left_subtree_root_pos; i++)//construct the post traverse of left subtree { left_subtree_pos.push_back(post[i]); } for(int i = left_subtree_root_pos + 1; i < post.size() - 1; i++)//construct the post traverse of right subtree { right_subtree_pos.push_back(post[i]); } for(int i = 1; i <= left_subtree_root_pos + 1; i++)//construct the pre traverse of left subtree { left_subtree_pre.push_back(pre[i]); } for(int i = left_subtree_root_pos + 2; i <= post.size() - 1; i++)//construct the pre traverse of right subtree { right_subtree_pre.push_back(pre[i]); } // print_subtree_dbg("left pos",left_subtree_pos); // print_subtree_dbg("right pos",right_subtree_pos); // print_subtree_dbg("left pre",left_subtree_pre); // print_subtree_dbg("right pre",right_subtree_pre); newnode->left = construct(left_subtree_pre, left_subtree_pos); TreeNode* newnode = new TreeNode(pre[0]); //or post[-1] newnode->right = construct(right_subtree_pre, right_subtree_pos); return newnode;//after construct, return it } void print_subtree_dbg(string cond, vector<int>& vec) { cout << cond << " : " ; for(int i = 0; i < vec.size(); i++) { printf("%d ", vec[i]); } printf("\n"); } };
PD. 891. Sum of Subsequence Widths 數學題，較難
- 題意: 找出所有子序列的寬度，寬度定義為，子序列最大元素扣除子序列最小元素。
- 思路: 暴力解顯然行不通，但可以看出每一個元素都會被當作該集合的最大與最小值，因此可以得到如圖中的概念
，舉例來說(因為linux上中英文同時打有點麻煩，故以下舉例以英文表示)- From the given example as [1, 2, 4] (Note that the correct answer should be 9), we have the following subseq with non zero width(i.e. element more than 1):[1, 2] [1, 4] [2, 4] [1, 2, 4]
- 1 as min: [1, 2], [1, 4], [1, 2, 4] / as max: none / total = (a[1] - a[0]) + (a[2] - a[0]) + (a[2] - a[0])
- 2 as min: [2, 4] / as max: [1, 2] (a[1] - a[0]) / total = (a[2] - a[1])
- 4 as min: none / as max: [1, 4], [2, 4]. [1, 2, 4] (all duplicated)
- after clanup we can found that this is equal to (a[2] + a[2] + a[2]) (max 4 for 3 times) + (a[1] - a[1]) (2 max for 1 times and so do min) + (-a[0] - a[0] - a[0]) (1 min for 3 times)
-
分析: Time complexity: O(N log N) due to sorting, Space complexity O(1))
-
以下程式碼TLE，原因在於每一次的相加都要呼叫pow_mod，計算量高，相當費時
#define ll long long const ll MOD = 1e9 + 7; class Solution { public: int sumSubseqWidths(vector<int>& A) { ll res = 0, sz = A.size(); sort(A.begin(), A.end()); for(int i = 0; i < sz; i++) { ll delta = A[i] * pow_mod(2, i) - A[i] * pow_mod(2, sz - i - 1); res += delta; res %= MOD; } return res; } ll pow_mod(ll base, int pow) { ll res = 1; for(int i = 0; i < pow; i++) { res <<= 1; res %= MOD; } return res - 1;//exclude the null set
- 由於陣列元素最多到20000，故利用
先將結果cache起來再計算
for(int i = 1; i < sz; i++) { dp[i] = (dp[i - 1] % MOD * 2) % MOD; }
#define ll long long const ll MOD = 1e9 + 7; class Solution { public: int sumSubseqWidths(vector<int>& A) { ll res = 0, sz = A.size(); sort(A.begin(), A.end()); ll dp[20001] = {0}; dp[0] = 1; for(int i = 1; i < sz; i++) { dp[i] = (dp[i - 1] % MOD * 2) % MOD; } for(int i = 0; i < sz; i++) { res += A[i] * (dp[i] - dp[sz - i - 1]); res %= MOD; } return res; } };
WC99
PA. 892. Surface Area of 3D Shapes 求表面積，水題
- 題意: 有 2d grid(2dvector 構成), size is grid.size() * grid.size()，在grid[i][j]有高度為v的立方體堆積（可以想像一下以前的小白方塊），求最後整體的表面積，注意，[[1,1]] [[1,2]] 的答案都是6，因為在grid以外的方塊不採計，被這個提議沒說清楚擺了一道...
- 思路: 直接算，扣掉重合部份即可(也就是每次看i - 1, j - 1之於自己的重合部份)
- 分析: Time complexity: O(N^2), Space complexity O(1)
class Solution { public: int surfaceArea(vector<vector<int>> grid) { int res = 0, border = grid.size(); for(int i = 0; i < grid.size(); i++) { for(int j = 0; j < grid[i].size(); j++) { if(j > border - 1 || i > border - 1) { continue; } else { if(grid[i][j]) { res += grid[i][j] * 4 + 2; } if(j > 0) //adjacent sticked area { res -= 2 * min(grid[i][j], grid[i][j - 1]); } if(i > 0) //adjacent sticked area { res -= 2 * min(grid[i][j], grid[i - 1][j]); } } } } return res; } };
PB. 893. Groups of Special-Equivalent Strings 簡單字串題
- 題意: 問 str1, str2 各自中，奇數或偶數位置字元對調，可否成為另一個 ex: abc = cba, abcd = cdab = adcb = cbad
- 思路: 用map先將一方的odd even以char->count代表基數或偶數中char各自對應多少個，在跑第二個word，跑得過程若出現0代表先前沒出現過(例如 abc, dbc 跑第二個d映射過去會是0(當初abc沒有d因此不屬於同一類型))，直接返回false，全部跑畢才返回true())
- 分析: Time complexity = O(N^2), Space complexity = O(N * K) where N is the size of input vector and K is the length of word since for each word we construct the map
- 反思: 覺得有點太冗長，歡迎提供更好作法
class Solution { public: int len, sz, cnt; int numSpecialEquivGroups(vector<string>& A) { vector<bool>visit(A.size(), 0); vector<vector<string>> res; vector<string>tmp; len = A[0].size(); sz = A.size(); cnt = 0; for(int i = 0; i < sz - 1; i++) { if(visit[i]) { continue; } else { tmp.clear(); tmp.push_back(A[i]);//push itself visit[i] = true; for(int j = i + 1; j < sz; j ++) { if(eqv(A[i], A[j])) { tmp.push_back(A[j]); visit[j] = true; } } cnt++; res.push_back(tmp); } } if(!visit[sz - 1]) { cnt++; } return cnt; } bool eqv(string s1, string s2) { map<char, int> odd; map<char, int> even; for(int i = 0; i < len; i++) { if(i & 1) { odd[s1[i]]++; } else { even[s1[i]]++; } } for(int i = 0; i < len; i++) { if(i & 1) { if(odd[s2[i]] == 0) { return false; } } else { if(even[s2[i]] == 0) { return false; } } } //reverse odd.clear(); even.clear(); for(int i = 0; i < len; i++) { if(i & 1) { odd[s2[i]]++; } else { even[s2[i]]++; } } for(int i = 0; i < len; i++) { if(i & 1) { if(odd[s1[i]] == 0) { return false; } } else { if(even[s1[i]] == 0) { return false; } } } return true; } };
PC. 894. All Possible Full Binary Trees 所有可能的二元樹
- 題意: 就是所有的二元樹可能，建出後把root放到vector返回
- 思路: 遞迴求解，因為完整二元樹必定有奇數個節點，因此若進入的N不是奇數直接返回空vector，接著逐步建立，切割為i個節點的left subtree和n - i - 1(包含根部)的right subtree遞迴下去解，再接起來如下程式碼
左右都會是FBT，因此 += 2的迴圈能避開偶數情形，最後奇數+奇數+1正好也是奇數，沒有問題
for(int left = 1; left < N; left += 2 /*(since no even number)*/) //left subtree node count { vector<TreeNode*> left_subtree = allPossibleFBT(left); vector<TreeNode*> right_subtree = allPossibleFBT(N - left - 1);
- 分析: Time Conplexity O(2^N), Space complexity O(2^N) (卡塔蘭數)
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<TreeNode*> allPossibleFBT(int N) { printf("N = %d \n", N); TreeNode* root = new TreeNode(0); root->left = root->right = NULL; vector<TreeNode*> res; if(!(N & 1)) { return {}; } else if(N == 1) { res.push_back(root); return res; } for(int left = 1; left < N; left += 2 /*(since no even number)*/) //left subtree node count { vector<TreeNode*> left_subtree = allPossibleFBT(left); vector<TreeNode*> right_subtree = allPossibleFBT(N - left - 1); //minus left subtree and the root for(auto it : left_subtree) { for(auto it2 : right_subtree) //all conbinations of left X right subtree (cartesian product) { TreeNode* new_node = new TreeNode(0); //connect two subtree with the root new_node->left = it; new_node->right = it2; res.push_back(new_node); } } } return res; } };
PD. 895. Maximum Frequency Stack 最大頻率棧，雙map應用
- 題意: 設計一個棧，使得彈出時能返回最大頻率的元素，若有複數個元素頻率相等，則返回最接近棧頂的
- 思路: 用一個map
- 分析: Time complexity O(1), since using unordered_map for inserting data, which is actually the hash, takes O(N) time, and we use stack.top(), pop() to implement "frequency pop" which is also O(1). Space complexity O(N) if N > 10001.
- 另見: 精簡前的code，多使用了一個 map stack來存放元素對應的位置（實際上直接存元素即可，另外開一個stack紀錄最大值變化略顯多此一舉)
#define MAXN 10001 class FreqStack { public: unordered_map<int, int>num_freq; //hash of num to its occurances // stack<int> freq_stk[MAXN]; --> this cause MLE since static memory size is too big(use the upper limit from problem) unordered_map<int, stack<int>> freq_stk; //data structure of freq stack, record the occurance of number to certain freq, ex push 2 push 3 push 2 push 4, we have freq[1] = [3, 4](top), freq[2] = [2] int maxfreq; FreqStack() { maxfreq = 0; } void push(int x) { if (++num_freq[x] > maxfreq) { maxfreq = num_freq[x]; } freq_stk[num_freq[x]].push(x); // printf("push %d, maxfreq now %d \n", x, maxfreq); } int pop() { if(freq_stk[maxfreq].size() == 0) { maxfreq--;//means all the numbers corresponding to that freq has been used out } int res = freq_stk[maxfreq].top(); freq_stk[maxfreq].pop(); // printf("pop val %d maxfreq %d\n", res, maxfreq); num_freq[res]--; return res; } }; /** * Your FreqStack object will be instantiated and called as such: * FreqStack obj = new FreqStack(); * obj.push(x); * int param_2 = obj.pop(); */`