399. Evaluate Division ---------------M ~~~~~~~~！！！！

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 answer does not exist, return -1.0.

Example:
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 ].

The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.

According to the example above:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 

 

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

A:

再一次，VS上的结果是对的。LC结果不对。 哎。不管了

主要思路，就是递归找关系， 并把其结果乘积。

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,  肏

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;
    }
};

554. Brick Wall -------------M

There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the top to the bottom and cross the least bricks.

The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right.

If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks.

You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.

 

Example:

Input: [[1,2,2,1],
        [3,1,2],
        [1,3,2],
        [2,4],
        [3,1,2],
        [1,3,1,1]]

Output: 2

Explanation: 

 

Note:

1. The width sum of bricks in different rows are the same and won't exceed INT_MAX.
2. The number of bricks in each row is in range [1,10,000]. The height of wall is in range [1,10,000]. Total number of bricks of the wall won't exceed 20,000.

 

A:

就是记录每个edge的距离，然后找到最多的距离即可。

class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        int total = -1;
        unordered_map<int,int> map;
        for(auto row: wall){
            int curTotal = 0;
            for(auto brick : row){
                curTotal += brick;
                map[curTotal]++;
            }
            if(total<0){
                total = curTotal;
            }
        }
        int maxCount = 0;
        auto iter = map.begin();
        while(iter != map.end()){
            if(iter->first != total)
                maxCount = max(maxCount, iter->second);
            iter++;
        }
        return wall.size() - maxCount;
    }
};

875. Koko Eating Bananas ------------M ~~~~

Koko loves to eat bananas.  There are N piles of bananas, the i-th pile has piles[i] bananas.  The guards have gone and will come back in H hours.

Koko can decide her bananas-per-hour eating speed of K.  Each hour, she chooses some pile of bananas, and eats K bananas from that pile.  If the pile has less than K bananas, she eats all of them instead, and won't eat any more bananas during this hour.

Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.

Return the minimum integer K such that she can eat all the bananas within H hours.

 

Example 1:

Input: piles = [3,6,7,11], H = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], H = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], H = 6
Output: 23

 

Constraints:

• 1 <= piles.length <= 10^4
• piles.length <= H <= 10^9
• 1 <= piles[i] <= 10^9

 A:

就是binary search找到k个值

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int H) {
        int N = piles.size();
        int start = 1;
        int end = pow(10,9);
        while(start<=end){
            double mid = start + (end-start)/2;
            int count = 0;
            bool canFinish = true;            
            for(auto p : piles){
                count += ceil(p/mid);
                if(count > H){
                    canFinish = false;
                    break;
                }
            }
            if (canFinish) {
                end = mid - 1;
            }
            else {
                start = mid + 1;
            }
        }
        return start;
    }
};

我一开始在canFinish的时候，if else 里颠倒了

547. Friend Circles ------------M ~~~~~~~~~~~!!!

 There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are direct friends with each other, otherwise not. And you have to output the total number of friend circles among all the students.

Example 1:

Input: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle. 
The 2nd student himself is in a friend circle. So return 2.

 

Example 2:

Input: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends, 
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.

 

Constraints:

• 1 <= N <= 200
• M[i][i] == 1
• M[i][j] == M[j][i]

A:

这个的transitive 比较巧妙，我一开始想成 dfs了.  其实下面用的是是BFS

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int N = M.size();
        int res = 0;
        for(int i =0; i<N;i++){
            if(M[i][i] != 1) // this number already been visited
                continue;
            res++;
            stack<int> row2check;
            row2check.push(i);
            while(not row2check.empty()){
                int row = row2check.top();
                M[row][row] = -1;
                row2check.pop();                
                for(int j = 0;j<N;j++){
                    if(M[row][j]==1){
                        M[row][j] = -1;
                        row2check.push(j);
                    }
                }
            }
        }
        return res;
    }
};

其实DFS也是可以的。就是找到一个新的数字以后，要dfs 其每一条line

567. Permutation in String -----------M

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

 

Example 1:

Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input:s1= "ab" s2 = "eidboaoo"
Output: False

 

Constraints:

• The input strings only contain lower case letters.
• The length of both given strings is in range [1, 10,000].

A: 

就是一个个对比啊。记录每个char的数量

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        vector<int> V1(26,0);
        vector<int> V2(26,0);
        int n1 = s1.length(), n2 = s2.length();
        if(n2<n1)
            return false;
        for(int i =0;i<n1;i++){
            V1[s1[i]-'a']++;
            V2[s2[i]-'a']++;
        }
        if(helper(V1,V2))
            return true;
        for(int i =n1;i<n2;i++){
            V2[s2[i]-'a']++;
            V2[s2[i-n1]-'a']--;
            if(helper(V1,V2))
                return true;
        }
        return false;
    }
private:
    bool helper(vector<int> & V1, vector<int> & V2){
        for(int i =0;i<26;i++)
            if(V1[i] != V2[i])
                return false;
        return true;
    }
};