最近我做了Flipkart Online评估,我被一个问题卡住了很长一段时间。问题是这样的。一家广告公司有一系列广告对,每个广告都应该一个接一个地播放。如果给予“ABC”广告,对公司来说是有利的。我们必须找到所有广告至少播放一次的顺序。如果可能有多种这样的方式,请按字典顺序给出较小的一种。
例如:
4
"XYZ", "IOP"
"QWE", "XYZ"
"ABC", "TUV"
"TUV", "QWE"
可能的顺序是从“ABC”->“TUV”->“QWE”->“XYZ”->“IOP”开始
在规定的时间内我无法想出办法。经过我的思考,这与查找从源开始连通图是否可能是相似的,然后查看最小的顺序。
如果其他方法也可行,有人可以帮助我吗?或者这是推论的正确方法吗?
算法:
您需要创建一个邻接列表,以便子节点按字典顺序排序。
在 C++ 中,你可以使用向量的向量来做到这一点,在这里:
vector<pair<string,vector<string>> adjList
例如:
// not your example but a case when two ads can be shown after ABC
// preference should be for EFG over TUV
ABC -> EFG, TUV
您需要一张地图来标记已访问过的位置,数据结构为:
您必须在此图上执行图遍历,以便访问所有节点。 在遍历过程中,如果您已到达末尾且未标记所有已访问的节点,则需要在向后遍历时将它们标记为未访问。
如果您仍有疑问或答案中缺少某些内容,请告诉我。