“This is the ninth day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Look a hundred times beauty, beauty is not necessarily yours. But if you run the algorithm a hundred times, the knowledge is yours

Who can have nine floors? No need to get up!

Title address

The title

Given an array of string equations representing relationships between variables, each equation [I] is of length 4 and takes one of two different forms: “A ==b” or” A! = b “. In this case, a and b are lowercase (not necessarily different) letters that represent single-letter variable names.

Return true only if an integer can be assigned to a variable name so that all given equations are satisfied, false otherwise.

Example 1:

Input: ["a==b","b!=a"] Output: false Explanation: If we specify a= 1 and b = 1, then the first equation can be satisfied, but not the second equation. There's no way to assign variables that satisfy both of these equations.Copy the code

Example 2:

Input: ["b==a","a==b"] Output: true Explanation: We can specify a= 1 and b= 1 to satisfy both equations.Copy the code

Example 3:

Input: ["a==b","b==c","a==c"] Output: trueCopy the code

Example 4:

Input: ["a==b","b!=c","c==a"] Output: falseCopy the code

Example 5:

Input: ["c==c","b==d","x!=z"] Output: trueCopy the code

Tip:

  1. 1 <= equations.length <= 500
  2. equations[i].length == 4
  3. equations[i][0] 和 equations[i][3]It’s lowercase
  4. equations[i][1]either'=', either'! '
  5. equations[i][2] 是 '='

Their thinking

  • We need to hand write one and look it up.

  • Iterate over the array of equations passed in. In the process of iterate, we need to pay attention to:

    • Each equation iterated is a string
    • The first and third terms of the string are the letters we need to compare
    • The second term of the string can be considered to determine whether the equation is= =The key to
    • jsThe method of converting letters to numbers ischarCodeAt

  • Using and looking up sets we’re going to start by categorizing the equal ones

  • So let’s iterate the equation! If it is already classified in the equation, return false

  • Otherwise return true

A brief introduction to how to write a set and look up

  • Make: Creates an arraybossStores information about the connected components of each variable
  • Find: Returns a representativeiThe node of the set, usually returns the root node of the set of x
  • Merge: Used to merge two identical collections

The problem solving code

var equationsPossible = function(equations) {
    let union = new Union(26)
    for(let eq of equations){
        if(eq[1] = ='='){
            union.merge(eq.charCodeAt(0) - "a".charCodeAt(), eq.charCodeAt(3) - "a".charCodeAt()) 
        }
    }
   
     for(let eq of equations){
        if(eq[1] = ='! ') {if(union.find(eq.charCodeAt(0) - "a".charCodeAt())==union.find(eq.charCodeAt(3) - "a".charCodeAt())){
                return false}}}return true
};

class Union {
    constructor(n){
        this.boss = new Array(n).fill(0).map((v,i) = > i)
    }
    find(i){
        if(this.boss[i] ==i) return i
        return this.find(this.boss[i])
    }
    merge(a,b){
        let fa = this.find(a)
        let fb = this.find(b)
        if(fa==fb) return
        this.boss[fa] = fb
    }
}
Copy the code

If you have any questions or suggestions, please leave a comment!