五月天精品网站,亚女pv免费,骚逼五月婷婷影院,中文字幕HEYZ0毛片,日本成人性爱视频网站,骚逼av,欧美成人版,亚洲乱伦电影

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?除法求值，我們先來看題面：

https://leetcode-cn.com/problems/evaluate-division/

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

給你一個變量對數(shù)組 equations 和一個實數(shù)值數(shù)組 values 作為已知條件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每個 Ai 或 Bi 是一個表示單個變量的字符串。

另有一些以數(shù)組 queries 表示的問題，其中 queries[j] = [Cj, Dj] 表示第 j 個問題，請你根據(jù)已知條件找出 Cj / Dj = ? 的結(jié)果作為答案。

返回所有問題的答案。如果存在某個無法確定的答案，則用 -1.0 替代這個答案。如果問題中出現(xiàn)了給定的已知條件中沒有出現(xiàn)的字符串，也需要用 -1.0 替代這個答案。

注意：輸入總是有效的。你可以假設(shè)除法運算中不會出現(xiàn)除數(shù)為 0 的情況，且不存在任何矛盾的結(jié)果。

示例

解題

https://blog.csdn.net/qq_41231926/article/details/90904134

思路：圖的深度優(yōu)先遍歷

本題是一題經(jīng)典的圖論算法，這里的除法運算可以看成是連接兩個節(jié)點的一條有向邊，那么計算結(jié)果存在的條件是什么呢？

（1）兩個字符串在equations中都出現(xiàn)過。

（2）這兩個字符串在equations中存在聯(lián)系，即同屬于一個連通分量。

首先，利用一個Map將字符串與數(shù)字編號一一對應(yīng)起來。

對于圖的深度優(yōu)先遍歷，我們選擇用一個鄰接矩陣graph來存儲圖的邊權(quán)值，同時每一次求兩點間的距離都初始化一個visited數(shù)組來標記哪些節(jié)點已經(jīng)被遍歷過。深度優(yōu)先遍歷過程中，求解距離用的不應(yīng)該是加法，而應(yīng)該是乘法。

時間復(fù)雜度是O(n * m)，其中n為queries中的查詢數(shù)，而m指的是由equations生成的節(jié)點數(shù)。空間復(fù)雜度是O(m ^ 2)。

public?class?Solution?{
?
????private?Map stringToInteger = new?HashMap<>();
?
????private?int?index = 0;
?
????private?double[][] graph;
?
????private?boolean[] visited;
?
????public?double[] calcEquation(List> equations, double[] values, List> queries) {
????????for?(List list : equations) {
????????????for?(String string?: list) {
????????????????if?(!stringToInteger.containsKey(string)) {
????????????????????stringToInteger.put(string, index++);
????????????????}
????????????}
????????}
????????graph = new?double[index][index];
????????for?(int?i = 0; i < equations.size(); i++) {
????????????List list = equations.get(i);
????????????String string0 = list.get(0), string1 = list.get(1);
????????????int?index1 = stringToInteger.get(string0), index2 = stringToInteger.get(string1);
????????????graph[index1][index2] = values[i];
????????????graph[index2][index1] = 1.0?/ values[i];
????????}
????????double[] result = new?double[queries.size()];
????????Arrays.fill(result, -1.0);
????????for?(int?i = 0; i < result.length; i++) {
????????????List list = queries.get(i);
????????????String string0 = list.get(0), string1 = list.get(1);
????????????if?(stringToInteger.containsKey(string0) && stringToInteger.containsKey(string1)) {
????????????????if?(string0.equals(string1)) {
????????????????????result[i] = 1.0;
????????????????} else?{
????????????????????int?index1 = stringToInteger.get(string0), index2 = stringToInteger.get(string1);
????????????????????visited = new?boolean[index];
????????????????????double?len = 1.0;
????????????????????dfs(index1, index2, len, result, i);
????????????????}
????????????}
????????}
????????return?result;
????}
?
????private?void?dfs(int?begin, int?end, double?len, double[] result, int?k) {
????????if?(graph[begin][end] == 0) {
????????????visited[begin] = true;
????????????for?(int?i = 0; i < index; i++) {
????????????????if?(!visited[i] && graph[begin][i] != 0) {
????????????????????dfs(i, end, len * graph[begin][i], result, k);
????????????????}
????????????}
????????} else?{
????????????result[k] = len * graph[begin][end];
????????}
????}
?
}