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
}
}

別卷了