資訊專欄INFORMATION COLUMN
摘要：建好圖之后就是查找了，圖里面查找用或者都可以，寫起來(lái)簡(jiǎn)單點(diǎn)。復(fù)雜度沒(méi)什么差別都是，這道題里面最多是，所以每次查找的復(fù)雜度是，有次查找。注意防止重復(fù)路徑，要用。
399. Evaluate Division
題目鏈接：https://leetcode.com/problems...
無(wú)向圖里找路徑的問(wèn)題，用鄰接鏈或者鄰接矩陣來(lái)建圖，用鄰接鏈的話注意兩個(gè)方向，a/b的時(shí)候，既要把b加到a的鄰接list里，也要把a(bǔ)加到b的鄰接list里面。建好圖之后就是查找了，圖里面查找用bfs或者dfs都可以，dfs寫起來(lái)簡(jiǎn)單點(diǎn)。復(fù)雜度沒(méi)什么差別都是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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66640.html
摘要：題目要求已知一些字母之間的關(guān)系式，問(wèn)是否能夠計(jì)算出其它字母之間的倍數(shù)關(guān)系如已知問(wèn)是否能夠計(jì)算出的值。這里的值因?yàn)樵跅l件中無(wú)法獲知是否等于零，因此也無(wú)法計(jì)算其真實(shí)結(jié)果，也需要返回。即代表點(diǎn)指向點(diǎn)的邊的權(quán)重為，而點(diǎn)指向點(diǎ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ù)逆波蘭表示法，求表達(dá)式的值。給定逆波蘭表達(dá)式總是有效的。逆波蘭表達(dá)式又叫做后綴表達(dá)式。解題思路可以看出逆波蘭表達(dá)式中的每一個(gè)運(yùn)算符屬于該運(yùn)算符前的兩個(gè)數(shù)字間的運(yùn)算。如如波蘭表達(dá)式則加號(hào)前兩個(gè)數(shù)字為。 題目： 根據(jù)逆波蘭表示法，求表達(dá)式的值。 有效的運(yùn)算符包括 +, -, *, / 。每個(gè)運(yùn)算對(duì)象可以是整數(shù)，也可以是另一個(gè)逆波蘭表達(dá)式。 Evaluate the value of...
摘要：小鹿題目根據(jù)逆波蘭表示法，求表達(dá)式的值。給定逆波蘭表達(dá)式總是有效的。算法思路仔細(xì)觀察上述的逆波蘭表達(dá)式，可以發(fā)現(xiàn)一個(gè)規(guī)律就是每遇到一個(gè)操作符，就將操作符前的兩個(gè)操作數(shù)進(jìn)行運(yùn)算，將結(jié)果保存到原位置。 Time：2019/4/14Title: Evaluate Reverse Polish NotationDifficulty: MediumAuthor:小鹿 題目：Evaluate ...
閱讀 3402·2021-09-22 15:17
閱讀 2754·2021-09-02 15:15
閱讀 1785·2019-08-30 15:54
閱讀 2013·2019-08-30 14:02
閱讀 2541·2019-08-29 16:58
閱讀 3000·2019-08-29 16:08
閱讀 1343·2019-08-26 12:24
閱讀 1668·2019-08-26 10:41
