[閒聊] 每日leetcode 75 - Day26

[yam276 (史萊哲林的優等生)]

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


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.48.170 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1752483799.A.F92.html
推 DJYOMIYAHINA: 別卷了