[summary of leetcode weekly competition] the 81st fortnight competition of leetcode (6.25)

Weekly Links ： competition - Power button (LeetCode)81 A fortnight game

subject 1 2315. Statistical asterisk

Ideas ：

Direct traversal of simple topics , Use a variable to identify whether it is within the vertical line pair

Code ：

class Solution {
  public int countAsterisks(String s) {
        int count = 0;
        int d = 0;
        for(char c:s.toCharArray()){
            if(d==1){
                if(c=='|'){
                    d = 0;
                }
            }else{
                if(c=='|'){
                    d = 1;
                }
                if(c=='*'){
                    count++;
                }
            }
        }
        return count;
    }
}

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

Ideas ：

Union checking set , See 【 Algorithm notes 】 Focus on summary and collection _Let it beSun The blog of -CSDN Blog

Mainly find the size of each connected component

In limine TLE（ Overtime ） The idea of ： Calculate the size of each connected component directly by multiplication

for example ：

At this time, the sizes of several connected components are {4,2,1} Now calculate ans = 4*2+4*1+2*1 = 14

But time complexity O(n^2) Overtime ;

Calculation method 1

So consider for each node , Computing node i The number of disconnected points , Because there is repetition in the calculation of each node , So the answer is to sum and divide by 2.

 for(int i=0;i<n;i++){
            ans += (long)(n-sz[find(i)]);
        }
return ans/2;

Calculation method 2

You can consider the logarithm of all points n*(n-1)/2 , Subtract the number of nodes inside each connected component a*(a-1)/2

Code ：

Corresponding calculation method 1 ：

class Solution {
    int[] f = new int[100005];
    int[] sz = new int[100005];
    public int find(int x){
        if(f[x]==x) return x;
        return f[x] = find(f[x]);
    }
    public void unite(int x,int y){
        int fx = find(x);
        int fy = find(y);
        if(fx!=fy){
            f[fx] = fy;
            sz[fy] += sz[fx];
            sz[fx] = 0;
        }
    }
    public long countPairs(int n, int[][] edges) {
        for(int i=0;i<n;i++){
            f[i] = i;
            sz[i] = 1;
        }
        long ans = 0;
        for(int i=0;i<edges.length;i++){
            int a = edges[i][0];
            int b = edges[i][1];
            unite(a,b);
        }
        for(int i=0;i<n;i++){
            ans += (long)(n-sz[find(i)]);
        }
        return ans/2;
    }
}

Corresponding calculation method 2 ：

class Solution {
    int[] f = new int[100005];
    int[] sz = new int[100005];
    public int find(int x){
        if(f[x]==-1) return x;
        return f[x] = find(f[x]);
    }
    public void unite(int x,int y){
        int fx = find(x);
        int fy = find(y);
        if(fx!=fy){
            f[fx] = fy;
            sz[fy] += sz[fx];
            sz[fx] = 0;
        }
    }
    public long countPairs(int n, int[][] edges) {
        for(int i=0;i<n;i++){
            f[i] = -1;
            sz[i] = 1;
        }
        long ans = 0;
        for(int i=0;i<edges.length;i++){
            int a = edges[i][0];
            int b = edges[i][1];
            unite(a,b);
        }
        for(int i=0;i<n;i++){
            if(f[i]==-1){
                ans += (long)sz[i]*(sz[i]-1)/2;
            }
        }
        return (long)n*(n-1)/2-ans;
    }
}

subject 3  2317. Maximum XOR and after operation

Ideas

  It is to count whether each bit in this array appears 1, For all binary bits , As long as this bit appears in the array  1, So this one in the answer is also  1.

So the answer is the result of bitwise or of all numbers . Complexity O(n).

Code

Method 1 ： Direct statistics

class Solution {
    public int maximumXOR(int[] nums) {
        int[] bit = new int[32];
        for(int i=0;i<32;i++){
            for(int num:nums){
                if( ((num>>i)&1) == 1){
                    bit[i]++;
                    break;
                }
            }
        }
        int res = 0;
        int t = 1;
        for(int i=0;i<32;i++){
            if(i!=0){
                t = t*2;
            }
            res += bit[i]==0?0:t;
        }
        return res;
    }
}

  Method 2 ： Press bit or

  public int maximumXOR(int[] nums) {
        int ans = 0;
        for (int num : nums) ans |= num;
        return ans;
    }