一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 940|回复: 12
收起左侧

关于oa2的order dependency的问题

[复制链接] |试试Instant~ |关注本帖
Erroration 发表于 2016-11-6 00:53:25 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类 硕士 全职@Amazon - Other - 其他 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
Order dependency这道题地里很多小伙伴都说要取输入进来的order的ordername也就是一个String作为Map里的key来看待。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
1.那么这就是说对于Order o1 = Order(‘A’)和Order o2 = Order(‘A’)这两者实际上是一样的么?

2.在1的基础上,假设我们有OrderDependency d1:o1->o3; o2->o3,其中Order o3 = Order(‘C’)那么在处理过程中,等同于o1->o3, o1->o3。这样在处理完的两个hashmap里就有:outgoingedges:A[], C[A, A]      indegree:A2 C0 此时最后的输出就是 C, A 只有两个order,这样是正确的么?

本帖被以下淘专辑推荐:

 楼主| Erroration 发表于 2016-11-6 00:54:58 | 显示全部楼层
这个问题困扰很久了,求路过的哪位大神不吝赐教
回复 支持 反对

使用道具 举报

whiskey547 发表于 2016-11-6 07:23:18 | 显示全部楼层
1是对的,给的数据不会出现2的情况,这两个dependency完全一摸一样,不会有这样的数据。
回复 支持 反对

使用道具 举报

 楼主| Erroration 发表于 2016-11-6 07:24:55 | 显示全部楼层
whiskey547 发表于 2016-11-6 07:23
1是对的,给的数据不会出现2的情况,这两个dependency完全一摸一样,不会有这样的数据。

感动,谢谢!这样就放心了
回复 支持 反对

使用道具 举报

bogart 发表于 2016-11-6 22:30:29 | 显示全部楼层
whiskey547 发表于 2016-11-6 07:23
1是对的,给的数据不会出现2的情况,这两个dependency完全一摸一样,不会有这样的数据。
. 1point 3acres 璁哄潧
或者可以直接用数组吧?减去‘A’ 是不是就和course schedule II一样了
回复 支持 反对

使用道具 举报

 楼主| Erroration 发表于 2016-11-7 03:17:19 | 显示全部楼层
bogart 发表于 2016-11-6 22:30
或者可以直接用数组吧?减去‘A’ 是不是就和course schedule II一样了

那如果order name是“dshsadfcjs”呢
回复 支持 反对

使用道具 举报

bogart 发表于 2016-11-7 04:31:51 | 显示全部楼层
  1. vector<string> getOrderList(vector<pair<string, string> > &orderDependencies){.鐣欏璁哄潧-涓浜-涓夊垎鍦
  2.         vector<string> res;
  3.         if (orderDependencies.empty()) {
  4.                 return res;
  5.         }. visit 1point3acres.com for more.
  6.         // initialize two maps.
  7.         map<string, vector<string> > graph;
  8.         map<string, int> indegree;. 1point3acres.com/bbs
  9.         for (int i = 0; i < orderDependencies.size(); i++) {
  10.                 graph[orderDependencies[i].second].push_back(orderDependencies[i].first);
  11.                 if (indegree.find(orderDependencies[i].second) == indegree.end()) {
  12.                         indegree[orderDependencies[i].second] = 0;
  13.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  14.                 indegree[orderDependencies[i].first]++;
  15.         }
  16.         int num = indegree.size();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  17.         // push indegree == 0 into queue.. Waral 鍗氬鏈夋洿澶氭枃绔,
  18.         queue<string> events;. 鍥磋鎴戜滑@1point 3 acres
  19.         for (map<string, int>::iterator it = indegree.begin(); it != indegree.end(); it++) {
  20.                 if ((*it).second == 0) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  21.                         events.push((*it).first);
  22.                 }
  23.         }. from: 1point3acres.com/bbs
  24.         // traverse the queue
  25.         while (!events.empty()) {.1point3acres缃
  26.                 string top = events.front();
  27.                 events.pop();
  28.                 res.push_back(top);
  29.                 for (int i = 0; i < graph[top].size(); i++) {
  30.                         indegree[graph[top][i]]--;
  31.                         if (indegree[graph[top][i]] == 0) {
  32.                                         events.push(graph[top][i]);. 鍥磋鎴戜滑@1point 3 acres
  33.                         }.1point3acres缃
  34.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  35.         }
  36.         if (res.size() != num) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  37.                 return vector<string>();
  38.         }
  39.         return res;
  40. }
复制代码
回复 支持 反对

使用道具 举报

冒险小燕 发表于 2016-11-11 09:55:42 | 显示全部楼层

大神~~~~~这个c++代码是在amazon界面上跑的吗?我同学java的,在amazon界面上一个test case都过不了,不知道为啥。。私下里都对。。。
回复 支持 反对

使用道具 举报

NEO_FISH 发表于 2016-11-26 04:06:34 | 显示全部楼层
借楼问一下,如果有重复的order最后输出结果里是不是调用哪个都行?只要order里的string是正确的就没问题?自己新建一个呢?
回复 支持 反对

使用道具 举报

amethlex 发表于 2016-11-27 07:43:22 | 显示全部楼层
对 你的猜想是对的
回复 支持 反对

使用道具 举报

lela900900 发表于 2016-11-27 11:21:23 | 显示全部楼层
有没有java的代码跑过test case的 参考下?多谢多谢
回复 支持 反对

使用道具 举报

skysbjdy 发表于 2016-11-29 05:02:11 | 显示全部楼层

我的代码给你写到一样. 这个代码在OA2里面跑过吗?? 我就是担心有个别的test case过不了.
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 06:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表