【leetcode周赛总结】LeetCode第 81 场双周赛（6.25）

周赛链接：竞赛 - 力扣 (LeetCode)81场双周赛

题目1 2315. 统计星号

思路：

简单题目直接遍历，用一个变量标识是否在竖线对之内

代码：

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

题目2 统计无向图中无法互相到达点对数

思路：

并查集，并查集的参考模板见【算法笔记】重点总结并查集_Let it beSun的博客-CSDN博客

主要求每个连通分量的大小

一开始TLE（超时）的思路：求出每个连通分量的大小之后直接用乘法计算

例如：

此时几个联通分量的大小分别为{4，2，1}此时计算 ans = 4*2+4*1+2*1 = 14

但是时间复杂度O(n^2)超时；

计算方法一

所以考虑对于每一个节点，计算节点i不联通的点对数，因为每一个节点分别计算存在重复，所以答案就是求和再除以2。

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

计算方法二

可以考虑对于所有的点对数 n*(n-1)/2 ,减去各个联通分量内部的节点对数 a*(a-1)/2

代码：

对应计算方法一：

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

对应计算方法二：

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

题目3  2317. 操作后的最大异或和

思路

  就是统计这个数组中每一位是否出现1，对于所有二进制位，只要这一位在数组中出现过 1，那么答案里这一位也是 1。

因此答案就是所有数按位或的结果。复杂度 O(n)。

代码

方法一：直接统计

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

 方法二：按位或

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