Elements of Programming Interviews 白班编程记录，求挑刺求反馈

大木虫 · 2018-12-10 05:43:23

399. Evaluate Division

第三遍写这道题，用时21分钟，有3个syntax error和1个sematic error
花了8分钟修改错误，然后AC

syntax error:
1. 在应该assign的地方写了return
2. unordered_map passed by const reference的时候不能用[ ]访问，要用iterator访问（map[key]->second）
3. double 写错成了 string

semantic error:
1. 在查querie的时候遇到from == dst的case时没有检查from是否存在于图中，如果不存在的话，应该返回-1，但是我的程序忘记检查这一项，返回了1，是错的。

延伸：
还有union find的解，但是我对union find不是很熟练，所以不想写了。我知道这样不对，但是我就是做不到现在花时间研究union find解法，因为目前意志力不够强。
不过我要在看一遍union find的视频，掌握其思路。

class Solution {
public:
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
/* 0.MISC */
/* 1. prep */
vector<double> answer;
auto graph = BuildGraph(equations, values);
/* 2. key algo */
for(auto query: queries){
string from = query.first, dst = query.second;
double ansElement = 1.0;
if(from == dst && graph.find(from) != graph.end())ansElement = 1.0;
else if(graph.find(from) == graph.end() || graph.find(dst) == graph.end())ansElement = -1.0;
else{
double ratio = RatioBFS(graph, from, dst);
ansElement = ratio;
}
answer.emplace_back(ansElement);
}
/* 3. answer */
return answer;
}
double
RatioBFS(const unordered_map<string, vector< pair<string, double> > > & graph,
const string& from, const string& dst){
/* 0. MISC */
/* 1. prep */
queue<pair<string, double> > bfsQueue;
unordered_set<string> visited;
bfsQueue.emplace(from, 1.0);
visited.emplace(from);
/* 2. key algo */
while(!bfsQueue.empty()){
auto node = bfsQueue.front(); bfsQueue.pop();
auto nodeName = node.first;
auto nodeRatio = node.second;
for(auto child: graph.find(nodeName)->second){
string childName = child.first;
double relativeRatio = child.second;
if(visited.find(childName) != visited.end())continue;
visited.emplace(childName);
double childRatio = nodeRatio * relativeRatio;
if(childName == dst)return childRatio;
bfsQueue.emplace(childName, childRatio);
}
}
/* 3. answer */
return -1;
}
unordered_map<string, vector< pair<string, double> > >
BuildGraph( const vector<pair<string, string>> equations,
const vector<double>& values){
/* 0. MISC */
/* 1. prep */
unordered_map<string, vector< pair<string, double> > > graph;
/* 2. key algo */
for(int i = 0; i < equations.size(); ++i){
string from = equations[i].first, dst = equations[i].second;
double ratio = values[i];
graph[from].emplace_back(dst, ratio);
graph[dst].emplace_back(from, 1/ratio);
}
/* 3. answer */
return graph;
}
};

复制代码

补充内容 (2018-12-10 05:45):
如果是上白板写这道题，85行代码还是太长，需要舍弃一些。我是这样安排的，先写最核心的BFS部分，再写query的部分，最后写BuildGraph.

wocaole · 2018-12-10 06:57:22

这个不错。向您学习。

大木虫 · 2018-12-10 12:49:55

684. Redundant Connection
第二遍写，没有写出来。明天早上写。

大木虫 · 2018-12-11 06:28:36

684. Redundant Connection

15分钟AC

昨天犯了几个错误，第一，找环如果想要拎出一个方向一致的环，那就要用DFS而不是BFS。第二，mark visited要在pop之后，而不是在child discovery的时候，因为后者会造成trace back 分叉，使环的方向不一致，拎的时候很麻烦。

class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
/* 0. MISC */
/* 1. prep */
auto graph = BuildGraph(edges);
stack<int> dfsStack;
vector<bool> visited(edges.size() + 1, false);
vector<int> traceBack(edges.size() + 1, -1);
unordered_set<string> cycleEdges;
dfsStack.emplace(1);
/* 2. key algo */
while(!dfsStack.empty()){
int node = dfsStack.top(); dfsStack.pop();
visited[node] = true;
for(int child: graph[node]){
if(visited[child] == false){
traceBack[child] = node;
dfsStack.emplace(child);
}else if(child != traceBack[node]){
int dest = child;
string startEdge = Encode({node, dest});
cycleEdges.emplace(startEdge);
int current = node;
while(current != dest){
int next = traceBack[current];
cycleEdges.emplace(Encode({current, next}));
current = next;
}
for(int i = edges.size() - 1; i >= 0; --i){
string edgeStr = Encode(edges[i]);
if(cycleEdges.find(edgeStr) != cycleEdges.end()){
return edges[i];
}
}
}
}
}
/* 3. answer */
return {-1, -1}; /* handle err case */
}
string Encode(const vector<int>& edge){
return to_string(min(edge[0], edge[1])) + " " + to_string(max(edge[0], edge[1]));
}
vector<vector<int>> BuildGraph(const vector<vector<int>>& edges){
/* 0. MISC */
/* 1. prep */
vector<vector<int>> graph(edges.size() + 1, vector<int>());
/* 2. key algo */
for(auto edge: edges){
graph[edge[0]].emplace_back(edge[1]);
graph[edge[1]].emplace_back(edge[0]);
}
/* 3. answer */
return graph;
}
};

复制代码

大木虫 · 2018-12-13 00:40:58

LC 312. Burst Balloons

经典DP题目，backtracking + DP + memo，28分钟AC
核心要点是找到正确的拓扑图，正确的拓扑图的branching factor比较低。
找到正确拓扑图的要点是按照题目逻辑从多个方向想解，这里的运用是从正向想解和反向想解。

正向拓扑图这里的branch factor很大（n）因为每扎一个气球都会影响之后的sub problem，所以每次都要重新构建，sub problem无法得到有效重复利用
反向拓扑图则成功地把branch factor减小到2，因为后扎的气球无法影响到前扎的气球，所以sub problem不会受main problem的影响（无后效性），因此只要逻辑上保证sub problem可以构建最优解，sub problem就可以被重复利用达到提速的目的。

class Solution {
public:
int maxCoins(vector<int>& nums) {
/* 0. MISC */
if(nums.empty())return 0;
/* 1. prep */
vector<vector<int>> dpMatrix(nums.size(), vector<int>(nums.size(), -1));
/* 2. key algo */
MaxCoinsRec(nums, 0, nums.size() - 1, 1, 1, dpMatrix);
/* 3. answer */
return dpMatrix[0][nums.size() - 1];
}
int MaxCoinsRec(const vector<int>& nums, int start, int last, int leftSide, int rightSide, vector<vector<int>>& dpMatrix){
/* 0. MISC */
if(start > last)return 0; /* empty case */
if(dpMatrix[start][last] != -1)return dpMatrix[start][last];
/* 1. prep */
int maxAns = 0;
/* 2. key algo */
for(int i = start; i <= last; ++i){
int curAns =
nums[i] * leftSide * rightSide +
MaxCoinsRec(nums, start, i - 1, leftSide, nums[i], dpMatrix) +
MaxCoinsRec(nums, i + 1, last, nums[i], rightSide, dpMatrix);
maxAns = max(maxAns, curAns);
}
/* 3. answer */
dpMatrix[start][last] = maxAns;
return maxAns;
}
};

复制代码

totolin · 2018-12-18 00:57:05

楼主加油啊～～

Tonyclint

请问楼主这是什么语言啊

R.F

楼主很厉害，谢谢分享。楼主在白板写完以后还会敲代码到计算机里面去运行么？

yolanda杨杨

喜欢lz这种高质量的刷题方式，感觉我自己也要反省一下，自己一直很介意刷题量上不去其实没有必要，重要的是把刷过的题目搞明白。

TsaiChaioAn

刚拿到offer 9月开学的表示：我是商科转码，修过必修课但课程太水没啥子用，适用EPI吗？如果不适合，建议做什么较佳呢？谢谢各位!!

Elements of Programming Interviews 白班编程记录，求挑刺求反馈

浏览过的版块