leetcode_OJ WC76 解題心得
- Contest time: Mar 18, 2018
PA. 800. Similar RGB Color 麻煩的水題
如題目所述，會需要用到一些位元運算，因此稍嫌麻煩，居然寫了一個多小時才寫出來。 中途還被變更的題說明耍了一道，而且題目說明根本說錯了gg。
cti itc 可以在十六進位和char互相轉換，頗為方便。而stringstream可以把字串在視為輸入處理一次轉成十六盡位在輸入給整數。
#define FORI(n) for(int i = 0; i < n; ++ i) #include <cstdlib> class Solution { public: int cti(char c) { if ( '0'<=c && c<='9' ) return c-'0'; else return 10+c-'a'; } char itc(int i) { if (0<=i && i<=9) return '0'+i; else return 'a'+i-10; } string similarRGB(string color) { int dist = 0, best = 99999999; int original = 0; color = color.substr(1,6); stringstream ss; ss<<hex<<color; ss>>original; int R,G,B,nr,ng,nb,nr1,ng1,nb1; string sr,sg,sb; R=original & 0xff0000; G=original & 0xff00; B=original & 0xff; R>>=16; G>>=8; //find smallest R for(int i = 0;i < 16;i++) { nr = i<<4 | i; if(abs(nr-R)<best) { sr=""; best = abs(nr-R); nr = i; sr += itc(i); } } //fins smallest G best = 99999999; for(int i = 0;i < 16;i++) { ng = i<<4 | i; if(abs(ng-G)<best) { sg=""; best = abs(ng-G); ng = i; sg += itc(i); } } //find smallest B best = 99999999; for(int i = 0;i < 16;i++) { nb = i<<4 | i; if(abs(nb-B)<best) { sb=""; best = abs(nb-B); nb = i; sb += itc(i); } } return "#"+sr+sr+sg+sg+sb+sb; } };
PB.801. Minimum Swaps To Make Sequences Increasing 動態規劃
從題目的性質可以看出，每一個階段均要不斷求解這個階段是否要交換（重疊子問題），以符合嚴格遞增的序列。
但是在每一個遞增中，如果每一個元素和它前一個元素都符合嚴格增（最優子結構），那麼整個數列也會是一個嚴格增。
此外，如果本來就符合嚴格增，就不用擔心，或是因為之前的交換(至i-1)而導致第i個需要替換，便需要檢查此次是否要換，也就是向前檢查到前一個。
因此既有符合重疊子問題，又有最優子結構，那就是動態規劃試用的範圍囉
參考連結:什麼時候用動態規劃演算法
出題者解析
解析的翻譯翔見程式碼中的註解
#define FORI(n) for(int i = 0; i < n; ++ i) class Solution { public: int minSwap(vector<int>& A, vector<int>& B) { int sz = A.size(); vector<int> swap(sz, INT_MAX),unswap(sz, INT_MAX); //calculating the step of swapped or not till this place. unswap[0] = 0; swap[0] = 1; for(int i = 1;i < sz;i++) { //如果兩方都依然符合遞增，則可以一次換兩個column或是都不要換，因為之前的已經符合嚴格遞增 if(A[i - 1] < A[i] && B[i - 1] < B[i]) //推理過來必定也會繼續嚴格遞增，否則就會被替換了 { unswap[i] = min(unswap[i - 1], unswap[i]); //如果不要替換，就是依然維持跟上一次一樣的未替換數字（這一次是intmax 所以一定會取到較小的） swap[i] = min(swap[i - 1] + 1, swap[i]); //如果要替換，那麼先前累積的替換次數到這裡就會再多一次，因為現在多的i又要再換一次了。 } //若是這種交叉符合形，則i或是i-1位置可以有一個必要被替換，也就是i, i-1會有遞增形成。（這種意思就是說，因為A B的『雙重符合』遞增在此被打斷了』 //因為被打斷，勢必得利用交換其中一個，例如將i or i-1 其中之一各自替換即可。 if(A[i - 1] < B[i] && B[i - 1] < A[i]) { unswap[i] = min(unswap[i], swap[i - 1]); //如果不要替換這一個，依然能讓整個數列嚴格增，那麼先前的勢必都要符合嚴格遞增的形式，因此得替換上一個 //也就是討論串裡面所說的：the cost n2 of having a legal sequence up to column i that ends with column i not flipped, is going //to be the cost s1 of having a legal sequence up to column i-1 that ends in column i-1 flipped swap[i] = min(unswap[i - 1] + 1, swap[i]); //如果要替換這一個，才能讓整個數列嚴格增，那就代表先前到i-1都要是持續嚴格增，因此從這裡開始替換就是算先前沒替換但這個有替換，所以是從unswap + 1 } } return min(swap[sz - 1], unswap[sz - 1]); } };
PC. 802. Find Eventual Safe States 圖論經典題，查找環以及可能觸及環之所有點
利用一個資料結構來儲存所有點的類型 -1代表尚未處理 0代表不在環上，或是不可能觸及到他人的環 1代表是環的一部分
優化只尋找還沒處理過得點，其他再把標記為0的點，放到結果裡面。
但依然優化不夠TLE:( 先放置吧
Wrong Answer 37/111 複雜的暴力作法，還會錯
TLE 81/111 提早跳出，但依然TLE
以下代碼優化到 101/111 但依然TLE了 先『精神』ac一下。
代碼邏輯見註解
#define FORI(n) for(int i = 0; i < n; ++ i) class Solution { public: vector<int> res, visited, in_cycle; vector<int> eventualSafeNodes(vector<vector<int>>& graph) { in_cycle.resize(graph.size()); fill(in_cycle.begin(), in_cycle.end(), -1); //-1 for unprocessed, 1 for in cycle and 0 for not in cycle FORI(graph.size()) { if(in_cycle[i] == -1) //if this node is not the terminal node { if(graph[i].size()) //the node which unsure in a node should be processed, otherwiswe, just dont do { visited.resize(graph.size()); fill(visited.begin(), visited.end(), 0); // cout<<"Start from "<<i<<endl; if(!dfs(i, i, graph, 0)) { in_cycle[i] = 0; } } else { in_cycle[i] = 0; } } } // cout<<" is in_cycle "; FORI(in_cycle.size()) { if(in_cycle[i] == 0) { res.push_back(i); } // cout<<in_cycle[i]<<" "; } return res; } bool dfs(int cur_node, int start, vector<vector<int>> graph,int step) { // cout<<" DFS to "<<cur_node<<endl; // cout<<" is in_cycle "; FORI(in_cycle.size()) { cout<<in_cycle[i]<<" "; } // cout<<endl; if(in_cycle[cur_node] == 1) { // cout<<"Hit a node that causes cycle "<<endl; return true; } else if(in_cycle[cur_node] == 0) //reach the node that will not form a cycle, which is safe { return false; } if(visited[cur_node] == 1) //visit the visited node again, that is a cycle { // cout<<"Hit a node that visited before, CYCLE CONFIRMED!! now cur_node is "<<cur_node<<endl; in_cycle[cur_node] = 1; return true; } //traversed_path.push_back(cur_node); visited[cur_node] = 1; FORI(graph[cur_node].size()) //search the next node that can be traversed from the current node { //if this node will connect to its neighbor that forms a circle, than cur_node will be treated as circle-hazard as well //cout<<i<<endl; if(dfs(graph[cur_node][i], start, graph, step + 1)) { in_cycle[cur_node] = 1; // cout<<"Node "<<cur_node<<" connect to "<<i<<" that forms a cycle "<<endl; return true; } } visited[cur_node] = 0; //if next traverse meet the terminal, it does not count as meet before that form a cycle since terminal is OK to meet again in_cycle[cur_node] = 0;//this node is terminal since the aforementioned FORI wont get in, so this is the node with output degree zero return false; } };