摘要:建好圖之后就是查找了,圖里面查找用或者都可以,寫起來簡單點。復(fù)雜度沒什么差別都是,這道題里面最多是,所以每次查找的復(fù)雜度是,有次查找。注意防止重復(fù)路徑,要用。
399. Evaluate Division
題目鏈接:https://leetcode.com/problems...
無向圖里找路徑的問題,用鄰接鏈或者鄰接矩陣來建圖,用鄰接鏈的話注意兩個方向,a/b的時候,既要把b加到a的鄰接list里,也要把a加到b的鄰接list里面。建好圖之后就是查找了,圖里面查找用bfs或者dfs都可以,dfs寫起來簡單點。復(fù)雜度沒什么差別都是O(V+E),這道題里面E = equations.length, V最多是2E,所以每次查找的復(fù)雜度是O(equations.length),有queries.length次查找。注意防止重復(fù)路徑,要用visited。
public class Solution { public double[] calcEquation(String[][] equations, double[] values, String[][] queries) { // build graph, use adjacent list map = new HashMap(); for(int i = 0; i < equations.length; i++) { String[] equation = equations[i]; if(!map.containsKey(equation[0])) map.put(equation[0], new ArrayList()); map.get(equation[0]).add(new Info(equation[1], values[i])); if(!map.containsKey(equation[1])) map.put(equation[1], new ArrayList()); map.get(equation[1]).add(new Info(equation[0], 1 / values[i])); } double[] result = new double[queries.length]; for(int i = 0; i < result.length; i++) { result[i] = find(queries[i][0], queries[i][1], 1, new HashSet()); } return result; } HashMap> map; private double find(String start, String end, double value, Set visited) { if(visited.contains(start)) return -1; if(!map.containsKey(start)) return -1; if(start.equals(end)) return value; visited.add(start); for(Info next : map.get(start)) { double sub = find(next.den, end, value * next.val, visited); if(sub != -1.0) return sub; } visited.remove(start); return -1; } class Info { String den; double val; Info(String den, double val) { this.den = den; this.val = val; } } }
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/66640.html
摘要:題目要求已知一些字母之間的關(guān)系式,問是否能夠計算出其它字母之間的倍數(shù)關(guān)系如已知問是否能夠計算出的值。這里的值因為在條件中無法獲知是否等于零,因此也無法計算其真實結(jié)果,也需要返回。即代表點指向點的邊的權(quán)重為,而點指向點的邊的全中為。 題目要求 Equations are given in the format A / B = k, where A and B are variables ...
Problem Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the ...
Problem Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. Note: Division between two inte...
摘要:題目根據(jù)逆波蘭表示法,求表達式的值。給定逆波蘭表達式總是有效的。逆波蘭表達式又叫做后綴表達式。解題思路可以看出逆波蘭表達式中的每一個運算符屬于該運算符前的兩個數(shù)字間的運算。如如波蘭表達式則加號前兩個數(shù)字為。 題目: 根據(jù)逆波蘭表示法,求表達式的值。 有效的運算符包括 +, -, *, / 。每個運算對象可以是整數(shù),也可以是另一個逆波蘭表達式。 Evaluate the value of...
摘要:小鹿題目根據(jù)逆波蘭表示法,求表達式的值。給定逆波蘭表達式總是有效的。算法思路仔細觀察上述的逆波蘭表達式,可以發(fā)現(xiàn)一個規(guī)律就是每遇到一個操作符,就將操作符前的兩個操作數(shù)進行運算,將結(jié)果保存到原位置。 Time:2019/4/14Title: Evaluate Reverse Polish NotationDifficulty: MediumAuthor:小鹿 題目:Evaluate ...
閱讀 3392·2021-09-22 15:17
閱讀 2740·2021-09-02 15:15
閱讀 1750·2019-08-30 15:54
閱讀 2001·2019-08-30 14:02
閱讀 2529·2019-08-29 16:58
閱讀 2988·2019-08-29 16:08
閱讀 1330·2019-08-26 12:24
閱讀 1653·2019-08-26 10:41