399. Evaluate Division
题目：
写得很复杂
但其实就是要你把数字关系性画成图
路径长度就是节点相除的数字 反向就是倒数
思路：
画成图是最难的部分
再来因为题目保证每条路都合法
不会有走不同路到节点会不同结果
所以直接从起点开始走 途中纪录 visited
一旦遇到 cur == target就可以走了
反之找完图都找不到终点就给 None
另外因为传入的参考可能会被编译器判断生命周期不够
你要加上 'a 的投名状保证他们不会用到一半不见
Code:
impl Solution {
pub fn calc_equation(
equations: Vec<Vec<String>>,
values: Vec<f64>,
queries: Vec<Vec<String>>,
) -> Vec<f64> {
// 建图
let mut graph: HashMap<&str, Vec<(&str, f64)>> = HashMap::new();
for (eq, &val) in equations.iter().zip(values.iter()) {
let a = eq[0].as_str();
let b = eq[1].as_str();
graph.entry(a).or_default().push((b, val));
graph.entry(b).or_default().push((a, 1.0 / val));
}
// DFS 实作
fn dfs<'a>(
graph: &HashMap<&'a str, Vec<(&'a str, f64)>>,
cur: &'a str,
target: &'a str,
acc: f64,
visited: &mut HashSet<&'a str>,
) -> Option<f64> {
if !graph.contains_key(cur) {
return None;
}
if cur == target {
return Some(acc);
}
visited.insert(cur);
for &(next, val) in &graph[cur] {
if !visited.contains(next) {
if let Some(ans) = dfs(graph, next, target,
acc * val, visited) {
return Some(ans);
}
}
}
None
}
// 查询
let mut res = Vec::with_capacity(queries.len());
for q in &queries {
let start = q[0].as_str();
let end = q[1].as_str();
let mut visited = HashSet::new();
if let Some(ans) = dfs(&graph, start, end, 1.0, &mut visited) {
res.push(ans);
} else {
res.push(-1.0);
}
}
res
}
}

别卷了