Catalog

Leetcode And check the problem summary

1. What is juxtaposition

1.1 And look up the search set

1.2 And the merging of search sets

2.Leetcode Select and do the combined search questions

2.1 547. Circle of friends

2.2 399. Divide and evaluate

2.3  Interview questions 17.07. Baby's name

Leetcode And check the problem summary

Today, I decided to completely understand the collection of search .

1. What is juxtaposition

In some cases N In the application of set of elements , We usually start with each element forming a single set of elements , Then merge the set of elements belonging to the same group in a certain order , In the meantime, we need to repeatedly find out which set an element is in . This kind of topic is characterized by seemingly uncomplicated , But the amount of data is huge , If it is described by normal data structure , Often too large in space , The computer can't afford it ; Even in space , The running time complexity is also high , It is simply impossible to calculate the results required by the test questions within the specified running time of the competition , Only a new abstract special data structure can be used —— Union checking set .

And the search set is similar to a forest , Each node has a father[x] To express x The father node of .

Initialize collection x, There is only x An element , take x The root node of is set to itself , So the label of each set = The label of the root node .

public void init(int x){
    father[x]=x;
}

Next, let's take a look at two important operations of join search ： Find and merge .

1.1 And look up the search set

lookup , That is to find elements x Where the collection is , Find out x The label of the root node of .

Pictured , If we want to know the elements 3 Where the collection is , We can know father[3]=2,father[2]=1, We can get it , Elements 3 The set is 1. And we can find Look for the element x The number of operations in the set = Elements x At the depth of .

The search here has an optimization of path compression , Or get 3 The set where the set is located is 1 when , You can directly father[3] Set to 1, And looking for 3 Find when 2, There may be other elements , Put the... Of these elements father All are set to 1, such , Next time find 3 When our descendants gather , In the above example , The search times are shortened 1. When looking for 3 When our ancestors gathered , The number of searches is only 1 了 . After path compression, the set becomes :

We can write code like this ：

// Returns the element x The set label where it is located 
public int find(int x){
    // If x Not root node 
    if(x!=father[x]){
       father[x]=find(father[x]);// Path compression 
    }
    return father[x];
}

When backtracking, all recursive elements father[] Are set as the set root node . This optimization is the advantage of the join search set .

1.2 And the merging of search sets

union(x,y) The combined x and y The two sets , We only need to set the root node of one set as the child of the root node of the other set .

Suppose now 1,2,3 Three nodes , Their initialization is three sets that contain only themselves .

Merge 1 and 2, It can be ：

The effect of these two cases is the same , But if you and 3 Merge , It can be ：

  These two situations will lead to finding elements 3 When you gather , The search times of the former is 2, The search times of the latter is 1, The latter is more efficient . therefore There is an optimization of heuristic merging in the merging of joint search sets , That is, record the depth of each set , When you want to merge two sets , Hang the set with smaller depth under the set with larger depth .（ This optimization effect is not very obvious , Not much , Sometimes it is troublesome to discuss the situation in this way , You can also directly put y Hang up x above ）.

We can write code like this ：

// Merge x and y Where the collection is 
public void union(int x, int y)
{
    int fx = find(x);// find x Where the collection is , namely x The root node 
    int fy = find(y);// find y In the collection , namely y The root node 
    if (fx == fy) return;
    if (rank[fx] > rank[fy]) //y  Merge into  x
    {
        father[fy] = fx;
        if(rank[fy]+1>rank[fx])// If you hang up fy Then the depth increases 
        {
            rank[fx]=rank[fy]+1;// The rank here is depth 
        }
    }
    else
    {           
        father[fx] = fy;
        if(rank[fx]+1>rank[fy]) rank[fy]=rank[fx]+1;
    }
}

Concurrent set lookup is applicable to the merging and searching of all sets , It can also be extended to some operations in graph theory to judge whether two elements belong to the same connected block . Due to the use of heuristic merging and path compression techniques , The time complexity of the joint search set can be approximately regarded as O(1), The space complexity is O(N), In this way, a large-scale problem will be transformed into a small space 、 Very fast and simple operation .

2.Leetcode Select and do the combined search questions

2.1 547. Circle of friends

 There is... In the class  N  Famous student . Some of them are friends , Some are not . Their friendship is transitive . If known  A  yes  B  Friend, ,B  yes  C  Friend, , Then we can think that  A  It's also  C  Friend, . The so-called circle of friends , A collection of friends .

 Given a  N * N  Matrix  M, It means the friendship between the middle school students in the class . If M[i][j] = 1, It means that we have known the  i  And  j  The students are friends with each other , Otherwise, I don't know . You have to output the total number of known circles of friends among all students .

 

 Example  1：

 Input ：
[[1,1,0],
 [1,1,0],
 [0,0,1]]
 Output ：2 
 explain ： Known students  0  And students  1  Be friends with each other , They are in a circle of friends .
 The first 2 A student is in a circle of friends . So back  2 .
 Example  2：

 Input ：
[[1,1,0],
 [1,1,1],
 [0,1,1]]
 Output ：1
 explain ： Known students  0  And students  1  Be friends with each other , Student  1  And students  2  Be friends with each other , So students  0  And students  2  It's also a friend , So the three of them are in a circle of friends , return  1 .
 

 Tips ：

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

 source ： Power button （LeetCode）
 link ：https://leetcode-cn.com/problems/friend-circles
 Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

This is the most typical 、 The simplest joint search set problem , You can directly use and search sets to solve .

// Typical joint search set problem 
// We use father[N*N] Array to record the parent node ,father[i] Express i Parent node 
// There must have been N A circle of friends is everyone themselves , Every merge , The number of circles of friends will be reduced once 
class Solution {
    public int[] father;
    public int res;
    public int findCircleNum(int[][] M) {
        int N=M.length;
        if(N<=0) return 0;
        res=N;
        father=new int[N*N];
        // First give father Array full assignment -1
        for(int i=0;i<N*N;i++)
            father[i]=-1;
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
                if(M[i][j]==1) union(i,j);// Merge sets 
        return res;
    }
    // lookup x The parent node 
    public int find(int x){
        if(father[x]==-1 || father[x]==x){
            father[x]=x;// The initial parent node is itself 
            return x;
        }
        else{
            father[x]=find(father[x]);// Trace back to the root node , Path compression 
        }
        return father[x];
    }
    // Merge sets 
    public void union(int x,int y){
        int fx=find(x);
        int fy=find(y);
        if(fx==fy) return ;
        else{
            res--;// Reduce your circle of friends by one 
            father[fx]=fy;
        }
    }
}

2.2 399. Divide and evaluate

 Give the equation  A / B = k,  among  A  and  B  Are variables represented by strings , k  Is a floating point number . Solving problems according to known equations , And return the calculation results . If the result does not exist , Then return to  -1.0.

 Input is always valid . You can assume that there is no divisor in the division operation  0  The situation of , And there is no contradictory result .

 

 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]
 explain ：
 Given ：a / b = 2.0, b / c = 3.0
 problem ：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
 return ：[6.0, 0.5, -1.0, 1.0, -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]
 

 Tips ：

1 <= equations.length <= 20
equations[i].length == 2
1 <= equations[i][0].length, equations[i][1].length <= 5
values.length == equations.length
0.0 < values[i] <= 20.0
1 <= queries.length <= 20
queries[i].length == 2
1 <= queries[i][0].length, queries[i][1].length <= 5
equations[i][0], equations[i][1], queries[i][0], queries[i][1]  It consists of small letters and numbers 

 source ： Power button （LeetCode）
 link ：https://leetcode-cn.com/problems/evaluate-division
 Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

answer ：

// In essence, it is a weighted union search set problem 
// We can use a hash table father Record the parent node of each node 
// Then use another hash table values Record the distance from the node to the parent node 
// then x,y The solution of the equation , Also is to use x The distance to the root node divided by y The distance to the root node 
class Solution {
    public HashMap<String,String> father=new HashMap();
    public HashMap<String,Double> values=new HashMap();
    public double[] calcEquation(List<List<String>> e, double[] v, List<List<String>> q) {
        // Go through the equation first , Merge sets by the way 
        for(int i=0;i<e.size();i++){
            List<String> temp=e.get(i);
            String x=temp.get(0);
            String y=temp.get(1);
            // because x,y It must be in the same set , So merge the two sets 
            union(x,y,v[i]);
        }
        // Find the result 
        double[] res=new double[q.size()];
        for(int i=0;i<q.size();i++){
            List<String> temp=q.get(i);
            String x=temp.get(0);
            String y=temp.get(1);
            if(!father.containsKey(x) || !father.containsKey(y)){// The element of the equation to be solved does not 
                res[i]=-1;
                continue;
            }
            String fx=find(x);// look for x Parent node 
            String fy=find(y);// look for y Parent node 
            if(!fx.equals(fy)) res[i]=-1;// If x,y Not in a collection , The equation is unsolved 
            else res[i]=values.get(x)/values.get(y);// Otherwise solution x The distance to the root node divided by y The distance to the root node 
        }
        return res;
    }
    // lookup x Parent node 
    public String find(String x){
        String fx=father.getOrDefault(x,x);// If x No parent node , That is itself , At this point, it is the root node 
        String fx2=new String(fx);// Remember its parent node one level above 
        double vx=values.getOrDefault(x,1.0);
        if(!fx.equals(x)){// If it's not the root node , Just keep going back 
            fx=find(fx);// Path compression 
            vx=vx*values.get(fx2);//x The distance to the root node 
        } 
        father.put(x,fx);
        values.put(x,vx);
        return fx;
    }
    // Merge two nodes 
    public void union(String x,String y,double vi){
        String fx=find(x);// look for x Parent node 
        String fy=find(y);// look for y Parent node 
        double vx=values.getOrDefault(x,1.0);
        double vy=values.getOrDefault(y,1.0);
        if(fx.equals(fy)) return ;// The two nodes have been set together 
        father.put(fx,fy);// Set up fy by fx Parent node 
        values.put(fx,vy*vi/vx);
    }
}

2.3  Interview questions 17.07. Baby's name

 Every year, , The government publishes 10000 of the most common baby names and how often they appear , That's the number of babies with the same name . Some names have multiple spellings , for example ,John  and  Jon  Essentially the same name , But it was published as two names .
 Given two lists , One is the name and the corresponding frequency , The other is essentially the same name for . Design an algorithm to print out the actual frequency of each real name . Be careful , If  John  and  Jon  It's the same , also  Jon  and  Johnny  identical , be  John  And  Johnny  Also the same , That is, they have transitivity and symmetry .

 In the results list , Choose the name with the lowest dictionary order as the real name .

 Example ：

 Input ：names = ["John(15)","Jon(12)","Chris(13)","Kris(4)","Christopher(19)"], synonyms = ["(Jon,John)","(John,Johnny)","(Chris,Kris)","(Chris,Christopher)"]
 Output ：["John(27)","Chris(36)"]
 Tips ：

names.length <= 100000

class Solution {
    public String[] trulyMostPopular(String[] names, String[] synonyms) {
        Map<String, Integer> map = new HashMap<>();
        Map<String, String> father = new HashMap<>();     // Union checking set , key( descendants )->value( Ancestors )
        for (String name : names) {     // Statistical frequency 
            int idx1 = name.indexOf('(');
            int idx2 = name.indexOf(')');
            int frequency = Integer.valueOf(name.substring(idx1 + 1, idx2));
            map.put(name.substring(0, idx1), frequency);
        }
        for (String pair : synonyms) {  //union A synonym for 
            int idx = pair.indexOf(',');
            String name1 = pair.substring(1, idx);
            String name2 = pair.substring(idx + 1, pair.length() - 1);
            while (father.containsKey(name1)) {   // look for name1 Ancestors 
                name1 = father.get(name1);
            }
            while (father.containsKey(name2)) {   // look for name2 Ancestors 
                name2 = father.get(name2);
            }
            if(!name1.equals(name2)){   // Ancestors are different , To merge 
                int frequency = map.getOrDefault(name1, 0) + map.getOrDefault(name2, 0);    // The number of occurrences is the sum of the two 
                String trulyName = name1.compareTo(name2) < 0 ? name1 : name2;
                String nickName = name1.compareTo(name2) < 0 ? name2 : name1;
                father.put(nickName, trulyName);      // Nickname as a branch of big name , That is, big name is the ancestor of small name 
                map.remove(nickName);       // Update the data 
                map.put(trulyName, frequency);
            }
        }
        String[] res = new String[map.size()];
        int index = 0;
        for (String name : map.keySet()) {
            StringBuilder sb = new StringBuilder(name);
            sb.append('(');
            sb.append(map.get(name));
            sb.append(')');
            res[index++] = sb.toString();
        }
        return res;
    }
}