# leetcode_OJ WC75 解題心得

• Contest time: Mar 11, 2018

## 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深度優先搜索

#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;
}

};


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了

class Solution
{
public:
double champagneTower(int poured, int query_row, int query_glass)
{
vector<vector <double > > cups;
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)

* 思路，可以看出有兩種情形，一種是本來就會得分的(value <= index)，一種是還沒有得分的 else

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


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