leetcode_OJ WC75 解題心得
- Contest time: Mar 11, 2018
眼睛發炎，打扣途中頗不舒服，只有快速解出PA後，PB DFS沒寫好不斷WA，PD用暴力解然並卵TLE，就，寫個網誌來檢討吧
PA. 796. Rotate String 簡單字串題
- 思路：水題不解釋
#define FORI(n) for(int i = 0; i < n; ++ i) class Solution { public: bool rotateString(string aa, string bb) { string tmp=aa; string tmp2; FORI(aa.size()) { tmp2=tmp[0]; tmp = tmp.substr(1,aa.size()-1); tmp+=tmp2; if(tmp == bb) return 1; } return 0; } };
PB. 797. ALl path from src to dst 圖論題，起終點所有可能路徑
從起點到終點的所有路徑，圖論演算法經典題目!!!!!!!!!!!!!!!!!!!!!
- 思路：dfs深度優先搜索
這個是WA的代碼，總會有些case沒有找到，因為在output deg那裡的邏輯些許錯誤
#define FORI(n) for(int i = 0; i < n; ++ i) class Solution { public: vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) { int target = 0; int pos = 0, total_size = 0; vector<int> res_part, output_deg; output_deg.resize(graph.size()); vector<vector<int>> final_res; FORI(graph.size()) { if(graph[i].size()==0) { target = i; } else { total_size+=graph[i].size(); output_deg[i] = graph[i].size(); } } int visited = 0, i=0, tmp, undone = 1; while(visited != total_size) { res_part.push_back(pos); if(output_deg[pos]) { tmp = pos; pos = graph[pos][output_deg[pos]-1]; output_deg[tmp]--; visited++; } else { FORI(output_deg.size()) { if(output_deg[i]) pos = output_deg[i]; } } if(graph[pos].size()==0) { pos = 0; res_part.push_back(target); final_res.push_back(res_part); res_part.clear(); } } return final_res; } };
這個是正確解法的代碼，使用的演算法便是：DFS深度優先搜索，以找出起終點的所有路徑
Geekforgeeks reference
weibo
weibo的作法採用非遞迴做法
1.選取起點
2.移動，移到的點把它標記為走訪過，若該點不是終點，則擴散查找周圍『還沒有走過的點』
3.走到了終點之後，『退回上一步』，也是最重要的一個步驟，因為還有可能有其他路徑，故從終點的上一個步驟
4.下面的代碼中，原本44行的return寫上後會造成答案減少，原因在於做backtrace的時候，退回包刮終點也要標記為沒有走訪過，
如果終點仍然標記為走訪過，那麼之後第二條路徑要走到終點的時候便會看到終點已經走訪過，便不再向前走去終點，而導致結果不齊全
#define FORI(n) for(int i = 0; i < n; ++ i) class Solution { public: vector<vector <int>>final_res; vector<int>res, visited; stack<int> traversed_path; vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) //graph in adjacency list { int dst; FORI(graph.size()) { if(graph[i].size()==0) { dst = i; } visited.push_back(false); } dfs(0,dst,res,graph); return final_res; } void dfs(int cur_node, int dst, vector<int> res, vector<vector<int>> graph) { traversed_path.push(cur_node); visited[cur_node] = true; if(cur_node == dst) { stack<int> copied_stk = traversed_path; while(copied_stk.size()) { res.push_back(copied_stk.top()); copied_stk.pop(); } reverse(res.begin(), res.end()); final_res.push_back(res); res.clear(); //return ; } else { FORI(graph[cur_node].size()) { if(!visited[graph[cur_node][i]]) { dfs(graph[cur_node][i], dst, res, graph); } } } //back trace if there will be still some nodes have to be visited but now path are blocked since adj nodes are marked visited visited[cur_node] = false; cur_node = traversed_path.top(); traversed_path.pop(); } };
PC. 799. Champagne Tower 數學規劃與觀察題
- 思路：雖然題目有點嚇人，但只是個障眼法，剛開始想說一次在第一盃添加一次，再讓每一次的流水依序往下流竄，如果有杯子已經滿水位，就將row++
再度往下流竄，直到底，然不僅時間複雜度太高也在第260個測資WA了
事實上，只要先將最高的那一杯水，任意裝滿他的pour量，先不用在乎是否已經超出滿水位，只要先把多出的水依序流竄，並且左右均分即可，而會多出的水位就是 當前水位 - 一杯水 之後再將這個堆出的水位評分給樓下兩杯即可。 很智障的是 以為樓下兩杯是 row+1 col-1 and row+1 col+1 利馬拿了一個RE，實際上應該是col col+1啦w
class Solution { public: double champagneTower(int poured, int query_row, int query_glass) { vector<vector <double > > cups; cups.resize(101); //padding for(int i=0;i<101;i++) { for(int j=0;j<=i;j++) { cups[i].push_back(0.0); } } cups[0][0] = poured; for(int i=0;i<100;i++) { for(int j=0;j<=i;j++) { if(cups[i][j] >= 1.0) { cups[i+1][j] += (cups[i][j] - 1.0) / 2.0 ; cups[i+1][j+1] += (cups[i][j] - 1.0) / 2.0 ; cups[i][j] = 1.0; } } } return cups[query_row][query_glass]; } };
PD. 800. Smallest rotation with highest score 數學推理+區間查詢線性優化O(N)
此題的時間複雜度一定要在O(N)，必須使用區間查詢算法，大神室友馬上想到線段樹segment tree查找
區間查詢算法概念，從暴力到NlogN 到N
* 思路，可以看出有兩種情形，一種是本來就會得分的(value <= index)，一種是還沒有得分的 else
第一類型
首先第一種本來就可以得分，例如[2,3,1,4,0]中的1 , 0，向右移動自然可以得分，所以他的右邊可以的步數便是[index+1(直接向左移動到最右側（超過後重新從結尾回來），必然符合的開外掛模式),len-1（移動到他下一個）]
以及[0(不動)，index - value（例如上面的1在2 至多移動到1的位置，也就是 2 - 1 一步）]
第二類型
而另外一種當前無法得分的，便要[index+1 (開外掛移到最右邊), total_len - (value - index)(繼續移動，value - index 代表與最大移動次數的相差，也就是它必須向右移動val - index這個差值才有分，向右移動的至少次數，換過來講用 len 來扣除就是向左移動的最大次數)]
求出每一個數字應該有的區間，把他們映射到區間查詢段，使用python的pair表示開始和結束
for index, value in enumerate(arr): if index < value: #one segment for this ones pair.append([index + 1 ,total_len - (value - index)]) #segment start and end else: #two segments for this one pair.append([index + 1, total_len - 1]) pair.append([0, index - value])
最後找到prefix sum (加總到此時的總和)，思緒見註解
segment_query = [0] * (total_len + 1) #aux arrat for the prefix sum, segment query for i in range (len(pair)): #+1 padding segment_query[pair[i][0]] += 1 #go in the interval, overlapping with all the other segment segment_query[pair[i][1] + 1] -= 1 #leave the interval, cancelling the infulence of segment overlapping
整體AC代碼如下
class Solution: def bestRotation(self, arr): best = 0 shift = 0 total_len = len(arr) #start_pos_arr = [] pair = [] #initial the start_pos_arr to record the starting position of the given array #initial score for index, value in enumerate(arr): if index < value: #one segment for this ones pair.append([index + 1 ,total_len - (value - index)]) #segment start and end else: #two segments for this one pair.append([index + 1, total_len - 1]) pair.append([0, index - value]) segment_query = [0] * (total_len + 1) #aux arrat for the prefix sum, segment query for i in range (len(pair)): #+1 padding segment_query[pair[i][0]] += 1 #go in the interval, overlapping with all the other segment segment_query[pair[i][1] + 1] -= 1 #leave the interval, cancelling the infulence of segment overlapping cur_pts = 0 for i in range (len(segment_query)): cur_pts += segment_query[i] if( cur_pts > best): best = cur_pts shift = i return shift