s*******y
发帖数: 45 | 1 在这里看到了第二个题，试着写了一下，http://www.mitbbs.com/article_t/JobHunting/32695723.html
发现，建立图结构，从字符串数组中建图，再写DFS版本的拓扑排序，共三大块，C++代
码量不下60行。
题目描述：
想请教高手们在回答的第二题时候，代码可以多少行搞定？
请问如何在有限时间内写出精简代码的？
多谢
[ |
d******k
发帖数: 32 | 2 如果正确的解法是这样，60行就60行，没什么问题。
【在 s*******y 的大作中提到】
: 在这里看到了第二个题，试着写了一下，http://www.mitbbs.com/article_t/JobHunting/32695723.html
: 发现，建立图结构，从字符串数组中建图，再写DFS版本的拓扑排序，共三大块，C++代
: 码量不下60行。
: 题目描述：
: 想请教高手们在回答的第二题时候，代码可以多少行搞定？
: 请问如何在有限时间内写出精简代码的？
: 多谢
: [
|
q********c
发帖数: 1774 | 3 60行对于电面来讲是nightmare,也说明出题人很糟糕。
【在 d******k 的大作中提到】
: 如果正确的解法是这样，60行就60行，没什么问题。
|
s*******y
发帖数: 45 | 4 如果真碰到了，也没有办法啊～～
有没有什么好的写法呢
【在 q********c 的大作中提到】
: 60行对于电面来讲是nightmare,也说明出题人很糟糕。
|
s**x
发帖数: 7506 | 5 我的理解是超过20 行code的方法 一般都有问题。
要是真的很复杂，只能讲思路了。 |
w********s
发帖数: 1570 | 6 你可以写一个函数，然后不实现，把主要逻辑实现以下。
【在 s*******y 的大作中提到】
: 在这里看到了第二个题，试着写了一下，http://www.mitbbs.com/article_t/JobHunting/32695723.html
: 发现，建立图结构，从字符串数组中建图，再写DFS版本的拓扑排序，共三大块，C++代
: 码量不下60行。
: 题目描述：
: 想请教高手们在回答的第二题时候，代码可以多少行搞定？
: 请问如何在有限时间内写出精简代码的？
: 多谢
: [
|
t*****y
发帖数: 25 | 7 我想的是用一个hash，存放每一对字母的相对顺序。
假设输入涵盖了所有的26*25／2的排列可能，最后的hash是会是这样，
z => []
y => [yz]
x => [xy, xz]
w => [wx, wy, wz]
....
再按每个字母对应的集合所含元素排序就好。
Map> inequalities = new HashMap
HashSet>();
for (int i = 0; i < words.get(0).length(); i++) {
int index = 0;
String thisword = words.get(index);
while (index < words.size() - 1){
String nextword = words.get(index + 1);
char c1 = thisword.charAt(i);
char c2 = nextword.charAt(i);
if (c1 != c2) {
if (i == 0 || thisword.substring(0, i).equals(nextword.
substring(0,i))) {
HashSet inequality;
if (inequalities.get(c1) == null){
inequality = new HashSet();
inequalities.put(c1, inequality);
}else{
inequality = inequalities.get(c1);
}
inequality.add(new String(new char[]{c1,c2}));
}
}
thisword = nextword;
index++;
}
} |
s*****r
发帖数: 108 | 8 我在某个 onsite 的一题是这道 之前没做过
手写完整程序带无解处理之类的 记得写满了白板
不属于易错或难写的算法 不过量确实大 |
l***i
发帖数: 1309 | 9 this is a problem used in google codejam before. Not many people solved it. |
C******w
发帖数: 23 | |
s*****r
发帖数: 108 | 11 哪个题？那必然是不同的要求
【在 l***i 的大作中提到】
: this is a problem used in google codejam before. Not many people solved it.
|
j****z
发帖数: 13 | 12 是不是可以这么写
void sort(int ind, vector>& graph, vector& result, vector
& visited){
if(visited[ind])return;
visited[ind]=true;
for(auto i:graph[ind])
sort(i,graph,result,visited);
result.push_back(ind+'a');
}
void topocharacter(vector& in,vector& result){
vector> graph(26,vector());
for(int i=0;i
for(int j=0;in[i][j]&&in[i+1][j];j++)
if(in[i][j]!=in[i+1][j])
graph[in[i+1][j]-'a'].push_back(in[i][j]-'a');
vector visited(26,false);
for(int i=0;i<26;i++)
if(!graph[i].empty())
sort(i,graph,result,visited);
} |
l******o
发帖数: 144 | 13 不用60行。43行我这个（没编译没跑没测，如果错误请见谅）
vector f(const vector& vs) {
map> edges;
unordered_set out_vertices;
for (size_t i = 0; i + 1 < vs.size(); i++) {
const auto& s1 = vs[i];
const auto& s2 = vs[i + 1];
size_t j;
for (j = 0; j < s1.size() && j < s2.size(); j++) {
if (s1[j] != s2[j]) {
edges[s1[j]].insert(s2[j]);
break;
}
}
if (j == s2.size() && j < s1.size()) throw runtime_error();
for (char c : s1) out_vertices.insert(c);
for (char c : s2) out_vertices.insert(c);
}
unordered_map in_degrees;
for (const auto& p : edges) {
for (char c : p.right) {
if (in_degrees[c]++ == 0) out_vertices.erase(c);
}
}
vector result;
while (!out_vertices.empty()) {
unordered_set new_out_vertices;
for (char c : out_vertices) {
result.emplace_back(c);
auto it = edges.find(c);
if (it != edges.end()) {
for (char c : it->right) {
if (--in_degrees[c] == 0) {
new_out_vertices.insert(c);
in_degrees.erase(c);
}
}
}
}
out_vertices.swap(new_out_vertices);
}
if (!in_degrees.empty()) throw runtime_error();
return result;
}
【在 s*******y 的大作中提到】
: 在这里看到了第二个题，试着写了一下，http://www.mitbbs.com/article_t/JobHunting/32695723.html
: 发现，建立图结构，从字符串数组中建图，再写DFS版本的拓扑排序，共三大块，C++代
: 码量不下60行。
: 题目描述：
: 想请教高手们在回答的第二题时候，代码可以多少行搞定？
: 请问如何在有限时间内写出精简代码的？
: 多谢
: [
|
