leetcode_OJ WC97 解題心得
- Contest time: Aug 12, 2018
- 題意：找只在自己的句子中出現過一次而對方未出現的詞彙
- 思路：水題，map計數跑兩次即可。
- 分析：Time complexity O(N), Space complexity O(N)
class Solution
{
public:
vector<string> uncommonFromSentences(string A, string B)
{
map<string, int>mymap;
map<string, int>mymap2;
stringstream ss(A);
stringstream ss2(B);
vector<string> stra;
vector<string> strb;
vector<string> res;
string tmp;
while(ss >> tmp)
{
stra.push_back(tmp);
}
while(ss2 >> tmp)
{
strb.push_back(tmp);
}
for(int i = 0; i < stra.size(); i++)
{
mymap[stra[i]]++;
}
for(int i = 0; i < strb.size(); i++)
{
mymap2[strb[i]]++;
}
for(map<string, int>::iterator it = mymap.begin(); it != mymap.end(); it++)
{
if(it->second == 1)
{
if(mymap2[it->first] == 0)
{
res.push_back(it->first);
}
}
}
for(map<string, int>::iterator it = mymap2.begin(); it != mymap2.end(); it++)
{
if(it->second == 1)
{
if(mymap[it->first] == 0)
{
res.push_back(it->first);
}
}
}
return res;
}
};
- 題意：矩陣中逆時針旋轉，問界內的座標有哪些
- 思路：模擬，先從題目給的圖片可看出行走的距離是一個1 1 2 2 3 3 4 4 5 5 6 6每兩組遞增一次一，一樣用
for loop + dx dy (或說drow dcolumn)代表要走的方向，每次走一點看看是否在界內即可。
不用想太難，想說還要自己建一個grid在看是否界內，這樣太麻煩，只要想像成有 無限大的地圖持續走訪，看看是否在邊界即可
- 分析：Time complexity O(max(ROW, COL) ^ 2), Space complexity O(ROW * COL)
class Solution
{
public:
vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0)
{
//1 1 2 2 3 3 4 4 5 5 6 6
//0 1 2 3 4 5 6 8 7 8 9 10* increase if it is in the odd number
int rpos = r0, cpos = c0, dir = 0, go = 1;
int cnt = 0, ans_cnt = 0;
int dr[4] = {0, 1, 0, -1};
int dc[4] = {1, 0, -1, 0};
vector<vector<int>> res;
//push back the start position
res.push_back({rpos, cpos});
ans_cnt++;
while(ans_cnt < R * C)
{
for(int i = 1; i <= go; i++)
{
rpos += dr[dir];
cpos += dc[dir];
if(rpos >= 0 && rpos < R && cpos >=0 && cpos < C) //push back th eanswer if it is in the grid
{
res.push_back({rpos, cpos});
ans_cnt++;
}
}
if(cnt & 1) //to make 1 1 2 2 3 3 4 4 5 5 sequence
{
go++;
}
cnt++;
dir++;
dir %= 4; //change direction
}
return res;
}
};
- 題意：每一個人都討厭自己以外的某人(edge)，問如何分成兩組(bipartie graph)使每一組裡面的所有人不會互相討厭
- 思路：題意如同二分圖檢測問題，解題流程如下
- 首先初始化一些必要的資料結構，例如
visited[N + 1]這個array用以紀錄走訪過的點避免重複走訪，其中dislikes就是adjecent list中的edges。
- DFS，沒走過的點標記為-1，
走過的點分兩種，一種放0色、另一種1色，查找adjacent list看接下來要走訪點，並且依據當前顏色選擇另一個顏色為相鄰頂點上色(異色)。
- 查找的途中發現相鄰點已經上過色並且是相同色，代表無法切割成二分圖，將結果標示為false
- 分析：Time complexity O(V + E)(vector of dislikes acts as an adjacent list method for graph), Space complexity O(V + E) (adjacent list plus the visited array to mark the traversed vertices) 想知道使用相鄰list 時間複雜度分析後是O(V + E)而非O(V*E)可以看這篇
- 心得，本以為很難，想到是二分圖檢測居然一次過了，完全出乎意料呢:D，以前圖論問題頗卡，算是罩門，光是一個深度優先搜索寫了半天還是無窮遞迴解不下去，算是為自己的圖論算法打下信心囉 :D
class Solution
{
public:
bool is_bipartie;
bool possibleBipartition(int N, vector<vector<int>>& dislikes) //dislike act as adjacent matrix
{
int visited[N + 1] , visit_cnt; //visited matrix. -1 as unvisited, 0 as color1, 1 as color2
memset(visited, -1, sizeof(visited));
is_bipartie = true;
dfs(1, 0, visited, dislikes);
return is_bipartie;
}
void dfs(int cur_vertex,int cur_color, int* visited, vector<vector<int>>& dislikes)
{
visited[cur_vertex] = cur_color;
for(int i = 0; i < dislikes.size(); i++)
{
if(dislikes[i][0] == cur_vertex) //check if unvisited and is the path of current vertex
{
if(visited[dislikes[i][1]] == -1) //unvisited
{
dfs(dislikes[i][1], cur_color == 1 ? 0 : 1 /*change the color for adjacent vertices*/, visited, dislikes);
}
else if(visited[dislikes[i][1]] == cur_color) //visited, same color, not bipartie graph
{
is_bipartie = false;
}
}
}
}
};