399. Evaluate Division ---------------H ~~~~~~~~！！！！

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.

Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.

 

Example 1:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
note: x is undefined => -1.0

Example 2:

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

 

Constraints:

• 1 <= equations.length <= 20
• equations[i].length == 2
• 1 <= Ai.length, Bi.length <= 5
• values.length == equations.length
• 0.0 < values[i] <= 20.0
• 1 <= queries.length <= 20
• queries[i].length == 2
• 1 <= Cj.length, Dj.length <= 5
• Ai, Bi, Cj, Dj consist of lower case English letters and digits.

A:

build a graph， then do dfs to find the path from C to D.

class Solution {

public:

vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {

// build a graph, so that we can reach C to D at query

// find nodes

unordered_set<string> S;

for(auto eq : equations){

S.insert(eq[0]);

S.insert(eq[1]);

}

vector<double> results;

for(auto & query : queries){

string C = query[0], D = query[1];

if(S.find(C) == S.end() || S.find(D) == S.end()){

results.emplace_back(-1);

continue;

}

unordered_set<string> visited;

double res;

if(dfs(equations, values, visited, C,D, res))

results.emplace_back(res);

else

results.emplace_back(-1);

}

return results;

}

private:

bool dfs(vector<vector<string>>& equations, vector<double>& values, unordered_set<string> &visited, string C, string D, double &res){

if(visited.find(C) != visited.end()){ // if already visited.

return false;

}

if(C==D){

res = 1;

return true;

}

visited.insert(C);

for(int i =0; i< equations.size(); i++){

string A = equations[i][0], B = equations[i][1];

if(C == A){

auto tmp = dfs(equations, values, visited, B, D, res);

if(tmp){

res = values[i] * res;

return true;

}

}else if(C == B){

auto tmp = dfs(equations, values, visited, A, D, res);

if(tmp){

res = res / values[i];

return true;

}

}

}

visited.erase(C);

return false;

}

};

上面解法的弱点（不好看的点）就是需要检查C/D是否已经被发现。否则不容易分辨检查二者是否相等的情况

主要思路，就是递归找关系， 并把其结果乘积。下面的方法，并没有考虑 e /a. = 1, e/b = 1. 然后求a/b的。 所以时错误的

class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        vector<double> res;
        int N = equations.size();
        unordered_map<string, unordered_map<string, double>> map;
        for(int i =0;i<N;i++){
            string dividend = equations[i][0];
            string divisor =  equations[i][1];
            // include themselves
            map[dividend][dividend] = 1;
            map[divisor][divisor] = 1;
                       
            double value = values[i];
            map[dividend][divisor] = value;
            if(value != 0 ) // as equations can exist 0 / a = 0
                map[divisor][dividend] = 1.0 / value;
        }
        unordered_set<string> usedStrings;
        for(auto query : queries){
            res.push_back(dfs(query[0], query[1], map, usedStrings));
        }
        return res;
    }
private:
    double dfs(string a, string b, unordered_map<string, unordered_map<string, double>> &map, unordered_set<string> &usedStrings){
        if(usedStrings.find(a) != usedStrings.end()){
            return -1;
        }
        if(map[a].find(b) != map[a].end()){
            return map[a][b];
        }else{
            usedStrings.insert(a);
            double res = -1;
            auto iter = map[a].begin();
            while(iter!= map[a].end()){
                res = (iter->second) * dfs(iter->first, b, map, usedStrings);
                if(res != -1){
                    break;
                }
                iter++;
            }
            usedStrings.erase(a);
            return res;
        }
    }
};

Errors:

1:  map里由于我保存了 a->b    b -> a 这样会造成循环

2: 再就是double 给写成 long,  肏

----------第二遍----------- DFS。   每次只考虑  A >= B 的情况， 否则就inverse ---

但这样是不行的。 比如 e=2a, e = 3b

我们插入的就只有上面的。 query时，  无法倒回来通过e的关系

NOTE

     因为dfs的时候， 可能-1是来自于 不存在。 也可能是来自于正常的计算结果。 因此不能仅仅靠返回一个double值。 而是要返回bool,  结果保存在另一个参数里

565. Array Nesting -----------M

A zero-indexed array A of length N contains all integers from 0 to N-1. Find and return the longest length of set S, where S[i] = {A[i], A[A[i]], A[A[A[i]]], ... } subjected to the rule below.

Suppose the first element in S starts with the selection of element A[i] of index = i, the next element in S should be A[A[i]], and then A[A[A[i]]]… By that analogy, we stop adding right before a duplicate element occurs in S.

 

Example 1:

Input: A = [5,4,0,3,1,6,2]
Output: 4
Explanation: 
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

 

Note:

1. N is an integer within the range [1, 20,000].
2. The elements of A are all distinct.
3. Each element of A is an integer within the range [0, N-1].

 A:

关键在于， 会形成一个个彼此独立的circle,

Approach #2 Using Visited Array [Accepted]

Algorithm

In the last approach, we observed that in the worst case, all the elements of the $nums$ array are added to the sets corresponding to all the starting indices. But, all these sets correspond to the same set of elements only, leading to redundant calculations.

We consider a simple example and see how this problem can be resolved. From the figure below, we can see that the elements in the current nesting shown by arrows form a cycle. Thus, the same elements will be added to the current set irrespective of the first element chosen to be added to the set out of these marked elements.

Thus, when we add an element $nums[j]$ to a set corresponding to any of the indices, we mark its position as visited in a $visited$ array. This is done so that whenever this index is chosen as the starting index in the future, we do not go for redundant $count$ calculations, since we've already considered the elements linked with this index, which will be added to a new(duplicate) set.

By doing so, we ensure that the duplicate sets aren't considered again and again.

Further, we can also observe that no two elements at indices $i$ and $j$ will lead to a jump to the same index $k$, since it would require $nums[i] = nums[j] = k$, which isn't possible since all the elements are distinct. Also, because of the same reasoning, no element outside any cycle could lead to an element inside the cycle. Because of this, the use of $visited$ array goes correctly.

class Solution {
public:
    int arrayNesting(vector<int>& nums) {
        int N = nums.size();
        vector<bool> V(N,false); // vector of whether visited
        
        int maxLen = -1;
        for(int i =0;i<N;i++){
            int seed = i;
            if(V[seed]) // if already visited
                continue;
            int count = 0;
            while(not V[seed]){
                V[seed] = true;
                count++;
                seed = nums[seed];
            }
            maxLen = max(maxLen ,count);
        }
        return maxLen;
    }
};

979. Distribute Coins in Binary Tree -------M

 Given the root of a binary tree with N nodes, each node in the tree has node.val coins, and there are N coins total.

In one move, we may choose two adjacent nodes and move one coin from one node to another.  (The move may be from parent to child, or from child to parent.)

Return the number of moves required to make every node have exactly one coin.

 

Example 1:

Input: [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

Example 2:

Input: [0,3,0]
Output: 3
Explanation: From the left child of the root, we move two coins to the root [taking two moves].  Then, we move one coin from the root of the tree to the right child.

Example 3:

Input: [1,0,2]
Output: 2

Example 4:

Input: [1,0,0,null,3]
Output: 4

 

Note:

1. 1<= N <= 100
2. 0 <= node.val <= N

A:

就是递归调用

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int distributeCoins(TreeNode* root) {
        int res = 0;
        helper(root, res);
        return res;
    }
private:
    int helper(TreeNode* root, int & res){// return number of coins it returned to parent of root
        if(not root)
            return 0;
        int ll = helper(root->left, res);
        int rr = helper(root->right, res);
        int cur = root->val + ll + rr -1;
        res += abs(ll) + abs(rr);
        return cur;
    }
};