leetcode_OJ WC92 解題心得
- Contest time: Jul 8,2018
- 紀念一下難得打進前10%
- 思路: 直接解即可 注意先以原矩陣比較大的row or col(看誰大) 開一個暫時存放用的，以免segfault，最後丟到res，其中大小剛好跟原本的矩陣是對稱的
- 分析: Time complexity = O(ROW * COL), Space complexity = O(ROW * COL)
#define FORI(n) for(int i = 0; i < n; ++ i)
class Solution
{
public:
vector<vector<int>> transpose(vector<vector<int>>& arr)
{
vector<vector<int>>trans, res;
int big = max(arr[0].size(), arr.size());
trans.resize(big);
FORI(trans.size())
{
trans[i].resize(big);
}
cout << 1 <<endl;
for(int i = 0; i < arr.size(); i++)
{
for(int j = 0; j < arr[0].size(); j++)
{
trans[j][i] = arr[i][j];
}
}
cout << 1 <<endl;
res.resize(arr[0].size());
FORI(res.size())
{
res[i].resize(arr.size());
}
cout << 1 <<endl;
for(int i = 0; i < arr[0].size(); i++)
{
for(int j = 0; j < arr.size(); j++)
{
res[i][j] = trans[i][j];
}
}
return res;
}
};
- 思路:
- 用一個struct表示每一個node的父節點以及他的深度(annotated node)，接的用一個map儲存該節點與其對應資訊的關係(因為在二元樹，節點數值都是單一的，不必擔心重複蓋過的問題)
- 使用 dfs_information這個函數來走訪樹，同時儲存節點的父親、深度資訊。
- 將該map貼到第二個map，查找最深的node，找完後移除他(要貼到第二個map的原因在於，如果用原本的map，移除後找第二深的，最後要LCA會喪失最深節點的資訊，會錯)
- 如果有一個一樣深的節點(一樣最深)則samllest subtree會是他們的LCA(應該很好想像，因為一樣深的關係，勢必得找他們的LCA)，如果最深的節點沒有人跟他一樣深，那就是他自己作為最小subtree
- 兩個最深的節點就LCA，一個就返回最深的
- 分析: Time complexity = O(N), Space complexity = O(N) (auxiliary map structure to store the information, where N is # of nodes of the binary tree)
/**
* 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:
struct node_info
{
TreeNode* parent;
int depth;
};
map<TreeNode*, node_info> node_info_map;
map<TreeNode*, node_info> node_info_map_2;
TreeNode* deepest_node;
TreeNode* deepest_2nd_node;
TreeNode* res;
TreeNode* subtreeWithAllDeepest(TreeNode* root)
{
if(root->left == NULL && root->right == NULL) //if tree size is 1 just return the root
{
return root;
}
dfs_information(root, 0);
//find the 1st deepest leaf
int deepest = 0;
deepest_node = deepest_2nd_node = NULL;
node_info_map_2 = node_info_map;
for(map<TreeNode* , node_info>::iterator it = node_info_map_2.begin(); it != node_info_map_2.end(); it++)
{
if(it->first->left == NULL && it->first->right == NULL)
{
//
if(it->second.depth > deepest)
{
deepest = it->second.depth;
deepest_node = it->first;
}
}
}
node_info_map_2.erase(deepest_node);
//find the 2nd deepest leaf if same depth, then update the sceond one for the LCA
for(map<TreeNode* , node_info>::iterator it = node_info_map_2.begin(); it != node_info_map_2.end(); it++)
{
if(it->first->left == NULL && it->first->right == NULL)
{
//
if(it->second.depth == deepest)
{
deepest = it->second.depth;
deepest_2nd_node = it->first;
}
}
}
//if no other deepest with same depth, do not do LCA, since the deepest_node "ITSELF" is the smallest subtree containing the deepest_node
if(deepest_2nd_node == NULL)
{
return deepest_node;
}
climbup_LCA(deepest_node, deepest_2nd_node);
return res;
}
void dfs_information(TreeNode* root, int depth)
{
if(root == NULL)
{
return;
}
node_info_map[root].depth = depth;
if(root->left)
{
node_info_map[root->left].parent = root;
dfs_information(root->left, depth + 1);
}
if(root->right)
{
node_info_map[root->right].parent = root;
dfs_information(root->right, depth + 1);
}
}
void climbup_LCA(TreeNode* node_p, TreeNode* node_q)
{
if(node_info_map[node_p].parent == node_info_map[node_q].parent)
{
res = node_info_map[node_p].parent;
return;
}
else if(node_info_map[node_p].parent == node_q)
{
res = node_q;
return;
}
else if(node_info_map[node_q].parent == node_p)
{
res = node_p;
return;
}
else if(node_info_map[node_p].depth > node_info_map[node_q].depth) //the one who is lower has to climb up one depth
{
climbup_LCA(node_info_map[node_p].parent, node_q);
}
else
{
climbup_LCA(node_p, node_info_map[node_q].parent);
}
}
};
- 在此也額外分享LCA的解法 經典tree題目，一定要會！！！！！
236. Lowest Common Ancestor of a Binary Tree
- 思路: 儲存每個節點的parent節點資訊，之後看哪個節點比較深，就往parent節點回溯，最後看兩個節點的parent是否一樣，就是答案，蠻直觀的，畫個圖就能想像。
- 分析: Time complexity = O(N), Space complexity = O(N) (auxiliary map structure to store the information, where N is # of nodes of the binary tree)
- 心得: 用map來儲存節點的資訊真的好用(因為unique value的關係，形成很好的node_value, node_information pair)，以後可以多練tree了
/**
* 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:
struct node_info
{
TreeNode* parent;
int depth;
};
map<TreeNode* , node_info> node_info_map;
TreeNode* res;
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* node_p, TreeNode* node_q)
{
dfs_information(root, 0);
node_info_map[root].parent = root; //for the root itself without runtime error
res = root; //initialize
climbup_LCA(node_p, node_q);
return res;
}
//traverse the tree first to find the child-parent pair
void dfs_information(TreeNode* root, int depth)
{
if(root == NULL)
{
return;
}
node_info_map[root].depth = depth;
if(root->left)
{
node_info_map[root->left].parent = root;
dfs_information(root->left, depth + 1);
}
if(root->right)
{
node_info_map[root->right].parent = root;
dfs_information(root->right, depth + 1);
}
}
//climb up to find the LCA, using depth comparison algorithm
void climbup_LCA(TreeNode* node_p, TreeNode* node_q)
{
//
if(node_info_map[node_p].parent == node_info_map[node_q].parent)
{
res = node_info_map[node_p].parent;
return;
}
else if(node_info_map[node_p].parent == node_q)
{
res = node_q;
return;
}
else if(node_info_map[node_q].parent == node_p)
{
res = node_p;
return;
}
else if(node_info_map[node_p].depth > node_info_map[node_q].depth) //the one who is lower has to climb up one depth
{
climbup_LCA(node_info_map[node_p].parent, node_q);
}
else
{
climbup_LCA(node_p, node_info_map[node_q].parent);
}
}
};
- 思路: 簡單來說就只是找有『回文』性質的植樹，由於偶數的回文ABBCCBBA、ABBA除了11以外都是11的倍數，因此可以忽略掉加快時間。
對於大於九百萬的，因為測資上界是一千萬，可以用OEIS檢測
- 補充: 對於900萬以上的測資怎麼樣就是TLE，後來自己生了一次測資，發現900萬以上直到1000萬，測資上界的只剩下100030001這個，因此超過那個TLE的數字，我選擇直接回傳100030001，結果莫名其妙就AC了@@，因此也有直接列出OEIS版本的解法(算是有點偷吃步)，詳見LeetCode討論串我寫的這篇文章
- 分析: Time complexity O(N * sqrt (N)), Space complexity O(1), where N is the magnitude of input.
class Solution
{
public:
int primePalindrome(int num)
{
if(num == 1)
{
return 2;
}
else if(num >= 9989900)
{
return 100030001;
}
int flag = 0, cnt = 2;
while(1)
{
if(cnt >= num)
{
if(is_prime(cnt))
{
if(is_palindrome(cnt) )
{
break;
}
}
}
cnt++;
}
return cnt;
}
bool is_prime(int num)
{
for(int i = 2;i <= sqrt(num) ; i++)
{
if(num % i == 0)
{
return 0;
}
}
return 1;
}
bool is_palindrome(int num)
{
string str = to_string(num);
string rev = str;
if(num > 11 && str.size() % 2 == 0)
{
return 0;
}
reverse(rev.begin(), rev.end());
return str == rev;
}
};
- 還沒做，好像是dijkstra的變化題，程度尚不夠，之後再來試試看囉:D