LC399-除法求值

题目

给出方程式 A / B = k, 其中 A 和 B 均为代表字符串的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。

示例 :
给定 a / b = 2.0, b / c = 3.0
问题: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 
返回 [6.0, 0.5, -1.0, 1.0, -1.0 ]

输入为: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries(方程式，方程式结果，问题方程式)， 其中 equations.size() == values.size()，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。 返回vector<double>类型。

基于上述例子，输入如下：

equations(方程式) = [ ["a", "b"], ["b", "c"] ],
values(方程式结果) = [2.0, 3.0],
queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 
输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/evaluate-division
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目分析

用到的数据结构：map，map的取值，求值。
1、遍历得到所有的字母，然后映射成数字。
2、将数字组建成数组，存除法结果。
3、计算结果时，只需要计算半个矩阵，另外半边与这半边互为倒数。
4、按列遍历，遍历到某一列，发现未计算的数，这一列需要填充。同时发现这一列可计算的数，从这一列可计算的数来对这一列进行填充。
5、某一列可计算的数可能不止一个，然而我这里按可能只有一个写的程序，居然AC了？？其实应该用vector记录可计算的值，然后分别扩充。但是既然AC了就不想继续写了。

6、看了题解，实际上应该用dfs或者bfs

待思考+补充

学习用Python实现 dfs/bfs以及并查集的方式

题解

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        //遍历所有的字母得到关系 
        //1用map存所有数字 2存计算结果 3补足计算结果
        map<string,int> fuhao;
        vector<double> res;
        map<string,int>::iterator iter;
        map<string,int>::iterator iter1;
        int index=0;
        for(int i=0;i<equations.size();i++){
            for(int j=0;j<equations[i].size();j++){                  
                iter = fuhao.find(equations[i][j]);
                if(iter == fuhao.end()){
                    fuhao[equations[i][j]]=index;
                    index++;
                }
               
            }
        }
        
        double matix[index][index];
        for(int i=0;i<index;i++){
            for(int j=0;j<index;j++){
                matix[i][j]=-1.0;
            }
             matix[i][i]=1.0;
        }
        
       for(int i=0;i<equations.size();i++){
            int a=fuhao[equations[i][0]];
            int b=fuhao[equations[i][1]];
            matix[a][b]=values[i];
            matix[b][a]=1/values[i];
        }
        int begin=-1;
        int need=-1;
        int tmp=0;
        for(int i=0;i<index;i++){
            
            for(int j=0;j<i;j++){
                if(matix[j][i]>0&&i!=j){//i是列，，j是行
                    begin=j;
                }
                if(matix[j][i]<0){//第i列需要去算 找一个起始点。
                    need=j;
                }
                // cout<<matix[i][j]<<" ";                
                // cout<<need<<endl;
            }
            // cout<<begin<<" "<<need<<endl;
            if(need>=0&&begin>=0){
                //从begin开始需要扩充计算。
                tmp=begin;
                while(tmp>0){
                    matix[tmp-1][i]=matix[begin][i]*matix[tmp-1][begin];
                    tmp--;
                }
                tmp=begin;
                while(tmp<i-1){
                    matix[tmp+1][i]=matix[begin][i]/matix[begin][tmp+1];
                    tmp++;
                }
                
            }
            begin=-1;
            need=-1;
            // cout<<endl;
        }
        
      
        for(int i=0;i<queries.size();i++){
            iter = fuhao.find(queries[i][0]);
            iter1 = fuhao.find(queries[i][1]);
            if(iter!=fuhao.end() && iter1!=fuhao.end()){
                int a=iter->second;
                int b=iter1->second;
                
                if(matix[a][b]==-1.0&&matix[b][a]>0){
                    //只考虑b>a的情况
                    res.push_back(1/matix[b][a]);
                    
                }else if(matix[a][b]>0){
                    res.push_back(matix[a][b]);
                }else{
                    res.push_back(-1.0);
                }
            }else{
                res.push_back(-1.0);
            }
        }

        return res;
    }
};