最近我做了Flipkart Online评估,我被一个问题卡住了很长一段时间。问题是这样的。一家广告公司有一系列广告对,每个广告都应该一个接一个地播放。如果给予“ABC”广告,对公司来说是有利的。我们必须找到所有广告播放一次的顺序。如果可能有多种这样的方式,请按字典顺序给出较小的一种。
例如:
4
"XYZ", "IOP"
"QWE", "XYZ"
"ABC", "TUV"
"TUV", "QWE"
可能的顺序是从“ABC”->“TUV”->“QWE”->“XYZ”->“IOP”开始
在规定的时间内我无法想出办法。经过我的思考,这与查找从源开始连通图是否可能是相似的,然后查看最小的顺序。
如果其他方法也可行,有人可以帮助我吗?或者这是推论的正确方法吗?
您收到的输入对是有向图的边。字符串是该图的顶点。 “ABC”就是这样的顶点之一。问题是在该图中找到一条从顶点“ABC”开始的路径,该路径恰好访问每个顶点一次。这就是寻找 汉密尔顿路径 选择字典序较小的路径的问题。
这是一个 NP 问题,因此没有已知的具有多项式时间复杂度的解决方案。
这是一个简单的深度优先搜索算法(在 JavaScript 可运行片段中)来查找这样的汉密尔顿路径。它首先为图创建一个邻接列表,对该邻接列表中的每个列表进行排序(以保证我们首先获得字典顺序),然后启动 DFS:
function hamilton(pairs, start) {
// Build an adjacency list
const adj = {};
for (const [src, dst] of pairs) {
adj[src] ??= []; // Create vertex if not yet exists
adj[dst] ??= []; // Create vertex if not yet exists
adj[src].push(dst); // dst is a neighbor of src
}
// For each vertex, sort the list of neighbors lexically
for (const neighbors of Object.values(adj)) {
neighbors.sort();
}
const n = Object.keys(adj).length;
// Apply a naive DFS algorithm
const visited = new Set; // Ordered Set (insertion order)
function dfs(node) {
if (visited.has(node)) {
return false; // Made a cycle
}
visited.add(node);
if (visited.size === n) { // Solution!
return true;
}
for (const neighbor of adj[node]) {
if (dfs(neighbor)) {
return true; // Success
}
}
visited.delete(node); // Backtrack
}
// Start DFS search
if (dfs(start)) { // Success
// Convert ordered Set to array
return Array.from(visited);
}
}
// Example run
const pairs = [
["XYZ", "IOP"],
["QWE", "XYZ"],
["ABC", "TUV"],
["TUV", "QWE"],
];
const path = hamilton(pairs, "ABC");
console.log(...path); // ABC TUV QWE XYZ IOP