Leet Code Weekly Contest 270
1. Finding 3-Digit Even Numbers
Brute-force.
class Solution {
public:
vector<int> findEvenNumbers(vector<int>& digits)
{
unordered_set<int> ret;
for (int i = 0; i < digits.size(); i++)
{
if (digits[i] == 0)
{
continue;
}
for (int j = 0; j < digits.size(); j++)
{
if (i == j)
{
continue;
}
for (int k = 0; k < digits.size(); k++)
{
if (i == k || j == k || digits[k] % 2 == 1)
{
continue;
}
ret.insert(digits[i] * 100 + digits[j] * 10 + digits[k]);
}
}
}
vector<int> ans = vector<int>(ret.begin(), ret.end());
sort(ans.begin(), ans.end());
return ans;
}
};2. Delete the Middle Node of a Linked List
We can actually convert the list to a vector and convert it back :)
class Solution
{
public:
ListNode* deleteMiddle(ListNode* head)
{
vector<int> ret;
while (head != NULL)
{
ret.push_back(head->val);
head = head->next;
}
int pos = ret.size() / 2;
ListNode *ans = NULL;
for (int i = ret.size() - 1; i >= 0; i--)
{
if (i == pos)
{
continue;
}
ans = new ListNode(ret[i], ans);
}
return ans;
}
};3. Step-By-Step Directions From a Binary Tree Node to Another
Go up until we reach the LCA (Lowest Common Ancestor) node and then go down..
class Solution
{
public:
unordered_map<TreeNode*, TreeNode*> parent;
unordered_map<int, TreeNode*> node_of;
void dfs(TreeNode *x)
{
if (x == NULL)
{
return;
}
node_of[x->val] = x;
if (x->left != NULL)
{
parent[x->left] = x;
dfs(x->left);
}
if (x->right != NULL)
{
parent[x->right] = x;
dfs(x->right);
}
}
string getDirections(TreeNode* root, int startValue, int destValue)
{
dfs(root);
unordered_set<int> tree_values;
for (TreeNode *x = node_of[destValue]; true; x = parent[x])
{
tree_values.insert(x->val);
if (x == root)
{
break;
}
}
string ans = "";
TreeNode *x = node_of[startValue];
while (tree_values.find(x->val) == tree_values.end())
{
ans.push_back('U');
x = parent[x];
}
while (x->val != destValue)
{
if (x->left != NULL && tree_values.find(x->left->val) != tree_values.end())
{
ans.push_back('L');
x = x->left;
}
else
{
ans.push_back('R');
x = x->right;
}
}
return ans;
}
};4. Valid Arrangement of Pairs
It's literally solving the euler-path on a directed graph. So first, obviously we should start from a node of which the in-degree is less than out-degree (if such node doesn't exist, then randomly choose one). Then if you know an algorithm called Hierholzer’s Algorithm, it's all solved.
class Solution {
public:
int total_pairs;
unordered_set<int> vals;
unordered_map<int, vector<int>> targets;
unordered_map<int, int> in_degree;
unordered_map<int, int> out_degree;
void init(vector<vector<int>>& pairs)
{
total_pairs = pairs.size();
for (auto &pair : pairs)
{
int x = pair[0], y = pair[1];
vals.insert(x);
vals.insert(y);
if (targets.find(x) == targets.end())
{
targets[x] = vector<int>();
}
targets[x].push_back(y);
out_degree[x]++;
in_degree[y]++;
}
}
int find_start()
{
for (auto &x : vals)
{
if (out_degree[x] > in_degree[x])
{
return x;
}
}
return *vals.begin();
}
vector<int> trace;
void dfs(int x)
{
while (targets[x].size() > 0)
{
int y = targets[x].back();
targets[x].pop_back();
dfs(y);
}
trace.push_back(x);
}
vector<vector<int>> validArrangement(vector<vector<int>>& pairs)
{
init(pairs);
dfs(find_start());
for (auto &x : trace)
{
cout << x << endl;
}
vector<vector<int>> ans;
for (int i = trace.size() - 1; i > 0; i--)
{
ans.push_back(vector<int>({ trace[i], trace[i - 1] }));
}
return ans;
}
};