[weekly replay] the 81st biweekly match of leetcode

1、 Statistical asterisk

1） Title Description

Give you a string s , Every time Two Continuous vertical line '|' by a pair . In other words , The first and the second '|' It's a couple , The third and the fourth '|' It's a couple , And so on .
Please return be not in Between vertical line pairs ,s in '*' Number of .
Be careful , Each vertical line '|' Metropolis just Belong to a pair .

2） Original link

LeetCode.6104： Statistical asterisk

3） Thinking analysis

• $(1)$ First count out all * The number of , Then subtract two liang | Previous * The number of is the answer , Use List Save all | The subscript , Go through it in pairs .

4） Template code

class Solution {
    
    public int countAsterisks(String s) {
    
        int n=s.length();
        char[] c=s.toCharArray();
        int ans=0;
        List<Integer> list=new ArrayList<>();
        for (int i=0;i<n;++i){
    
            char g=c[i];
            if (g=='|') list.add(i);
            if (g=='*') ans++;
        }
        int len=list.size();
        int gg=0;
        for (int i = 0; i <len; i+=2) {
    
            int l=list.get(i);
            int r=list.get(i+1);
            for (int j = l+1; j <r; j++) {
    
                if (c[j]=='*') gg++;
            }
        }
        return ans-gg;
    }
}

5） Algorithm and time complexity

   Algorithm ： simulation
   Time complexity ： Traverse the string once , The complexity is $O(n)$.

2、 Count the logarithm of points that cannot reach each other in an undirected graph

1） Title Description

Give you an integer n, Means a sheet of Undirected graph There is n Nodes , The number is 0 To n - 1 . And give you a two-dimensional array of integers edges , among edges[i] = [ai, bi] Representation node ai and bi There is a Undirected edge .
Please return Unable to reach each other Different Number of pairs .

2） Original link

LeetCode.6106： Count the logarithm of points that cannot reach each other in an undirected graph

3） Thinking analysis

• $(1)$ And look up the set of template questions , Using arrays w Save additional information , The number of points in each connected block , For each connected block , The number of all expected unconnected points is $S$, There are ：
  $$S=(long)((n-w[i])\ast w[i]$$
  Because the answer doesn't consider the order , Two points are only one answer , So the final answer will double , We need to take each connected block to get $S$ Add and divide $2$.
• $(2)$ We found that , Indeed, the essence is to find the size of each connected block , So whatever we use DFS still BFS Also very easy to write .

4） Template code

class Solution {
    
    int N=100010;
    int[] q=new int[N];
    int[] w=new int[N];
    public long countPairs(int n, int[][] edges) {
    
        for (int i = 0; i < n; i++) {
    
            q[i]=i;
            w[i]=1;
        }
        for (int[] g:edges){
    
            int a=g[0];
            int b=g[1];
            a=find(a);
            b=find(b);
            if (a!=b){
    
                q[a]=b;
                w[b]+=w[a];
            }
        }
        long ans=0;
         Set<Integer> set=new HashSet<>();
         for (int i = 0; i < n; i++) {
    
            int a=find(i);
            if (set.contains(a)) continue;
            ans+= (long)(n -w[a]) *w[a];
            set.add(a);
        }
        return ans/2;
    }
    int find(int x){
    
        if (q[x]!=x) q[x]=find(q[x]);
        return q[x];
    }
}

5） Algorithm and time complexity

   Algorithm ： Union checking set 、BFS、DFS
   Time complexity ： No specific analysis

3、 Maximum XOR and after operation

1） Title Description

I'll give you a subscript from 0 The starting array of integers nums . In one operation , choice arbitrarily Non-negative integer x And a subscript i , to update nums[i] by nums[i] AND (nums[i] XOR x) .
Be careful ,AND It's a bit by bit sum operation ,XOR Is a bitwise XOR operation .
Please execute Any time update operation , And back to nums All elements in Maximum Bitwise XOR and .

2） Original link

LeetCode.6105: Maximum XOR and after operation

3） Thinking analysis

• $(1)$ For bit operations , We know that it has something to do with binary , And binary will not exceed... In the data range 32 position . Binary median and bit are independent of each other , In order to find the rule, we consider the case of each binary bit .
• $(2)$ Suppose we consider the second $y$ position , Because it's binary , therefore $y$ The value of can only be $0$ perhaps $1$, Now let's assume $y$ by 0, Then there are $0AND(0XORx)$, because $0$ And any value above is $0$, So no matter x The number of this bit can only be $0$, If we assume $y$ by $1$, Then there are $1AND(0XORx)$, This situation needs to be discussed , If $x$ by $1$, The final result is $1$, Otherwise $0$.
• $(3)$ So we found that , When the binary number of a number is $y$ Is it $0$ when , It cannot change , When the first $y$ Is it $1$ when , It can become $0$. For all numbers in the array , If there is a number of th $y$ Position as $1$, Then we can guarantee the number of others $y$ All of them are $0$ Or become $0$. Make all numbers guarantee the th after XOR $y$ Position as $1$. In order to make the value bigger , It is necessary to guarantee more $1$, Let's decide whether every bit has $1$ that will do , That is to say, all numbers or above are the answer .

4） Template code

class Solution {
    
   public int maximumXOR(int[] nums) {
      
       int n=nums.length;
       int g=nums[0];
       for(int i=1;i<n;++i) g|=nums[i];
       return g;
    }
}

5） Algorithm and time complexity

   Algorithm ： An operation
   Time complexity ： Traversing the array is $O(n)$

4、 The number of different die sequences

1） Title Description

Give you an integer n . You need to roll one 6 Face dice n Time . Please meet the following requirements , Find out Different The number of dice in a sequence ：
1、 Any in the sequence adjacent Digital greatest common divisor by 1.
2、 In sequence equal Between the values of , There are at least 2 A number of other values . Formally , If the first i The value of a roll of dice be equal to The first j The second is worth , that abs(i - j) > 2 .
Please return different sequences of The total number . Because the answer can be big , Please correct the answer $10^9+7$ Remainder After the return .
If at least one element of two sequences is different , Then they are treated as different sequences .

2） Original link

LeetCode.6107: The number of different die sequences

3） Thinking analysis

• $(1)$ It must be linear at a glance $dp$ problem , Considering the $i$ Throw dice for the first time $i-1$ and $i-2$ Secondary related , We need to use 3D $dp$ Storage state is easy to transfer . Definition $f[i][k][u]$ For the first time $i$ The number of points thrown is $u$, The first $i-1$ Next is $k$ Number of alternatives .
• $(2)$ We can preprocess which points can be used as adjacent points , For the first $i$ Throw the sieve again, and then go to the triple loop enumeration $j,k,u$, If it is judged to be true , There's a transfer equation :
  $$f[i][j][k]=(f[i][j][k]+f[i-1][u][j])$$

4） Template code

class Solution {
    
    int N=10010;
    int[][][] f=new int[N][7][7];
    boolean[][] st=new boolean[7][7];
    int mod=1000000007;
   public int distinctSequences(int n) {
    
       if (n==1) return 6;
       for (int i = 1; i <=6; i++) {
    
           for (int j = 1; j <=6; j++) {
    
               if (i!=j&&gcd(i,j)==1){
    
                   f[2][i][j]=1;
                   st[i][j]=true;
               }
           }
       }
       for (int i = 3; i <=n; i++) {
    
           for (int j = 1; j <=6; j++) {
    
               for (int k = 1; k <=6; k++) {
    
                   if (st[j][k]&&j!=k){
    
                       for (int u = 1; u <=6; u++) {
    
                           if (st[u][j]&&k!=u&&j!=u){
    
                               f[i][j][k] = (f[i][j][k] + f[i-1][u][j]) % mod;
                           }
                       }
                   }
               }
           }
       }
       int res=0;
       for (int i = 1; i <=6; i++) {
    
           for (int j = 1; j <=6; j++) {
    
               res=(res+f[n][i][j])%mod;
           }
       }
       return res;
   }
   int gcd(int a,int b){
    
       return b==0?a:gcd(b,a%b);
   }
}

5） Algorithm and time complexity

   Algorithm ：dp
   Time complexity ：$O(n{m}^3)$, Office $m$ by 6, Because the sieve only has 6 Face to face .

5、 Weekly summary

   The third question can not be analyzed by bit operation , The fourth question does not write three-dimensional $dp$, I am a $sb$.