1、统计星号

1）题目描述

给你一个字符串 s ，每两个连续竖线'|' 为一对。换言之，第一个和第二个 '|' 为一对，第三个和第四个 '|' 为一对，以此类推。
请你返回 不在 竖线对之间，s 中 '*' 的数目。
注意，每个竖线 '|' 都会 恰好 属于一个对。

2）原题链接

LeetCode.6104：统计星号

3）思路解析

$(1)$ 先统计出所有*的个数，然后减去两两|之前的*的个数则是答案，使用List存下所有|的下标，进行两两遍历。

4）模板代码

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）算法与时间复杂度

??算法：模拟
??时间复杂度：遍历一次字符串，复杂度为 $O (n)$ 。

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

1）题目描述

给你一个整数 n，表示一张 无向图 中有 n 个节点，编号为 0到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条无向边。
请你返回 无法互相到达 的不同点对数目。

2）原题链接

LeetCode.6106：统计无向图中无法互相到达点对数

3）思路解析

$(1)$ 并查集的模板题，使用数组w保存额外信息，每个连通块的点的个数，对于每个连通块，所有预期不相连的点的个数为 $S$ ，这有：
$S = (l o n g) ((n ? w [i]) ? w [i]$
由于答案不考虑顺序，两个点只视为一种答案，所以最后答案会翻倍，我们需要把每个连通块得到的 $S$ 相加再除以 $2$ 。
$(2)$ 我们发现，确实本质就是求一下每个连通块的大小，所以我们无论用DFS还是BFS也都非常好写。

4）模板代码

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）算法与时间复杂度

??算法：并查集、BFS、DFS
??时间复杂度：不进行具体分析

3、操作后的最大异或和

1）题目描述

给你一个下标从 0 开始的整数数组 nums 。一次操作中，选择任意非负整数 x 和一个下标 i ，更新 nums[i] 为 nums[i] AND (nums[i] XOR x) 。
注意，AND 是逐位与运算，XOR 是逐位异或运算。
请你执行 任意次 更新操作，并返回 nums 中所有元素 最大 逐位异或和。

2）原题链接

LeetCode.6105:操作后的最大异或和

3）思路解析

$(1)$ 对于位运算操作，我们可知与其二进制有关，而二进制在数据范围内不会超过32位。二进制中位与位之间是相互独立互不影响的，为了发现规律我们去考虑每一位二进制位的情况。
$(2)$ 假设我们考虑第 $y$ 位，由于是二进制，所以 $y$ 的值只可能是 $0$ 或者 $1$ ，此时我们假设 $y$ 为0，那么则有 $0 A N D (0 X O R x)$ ，因为 $0$ 与上任何值都为 $0$ ，所以无论x为多少该位都只能是 $0$ ，如果假设 $y$ 为 $1$ ，则有 $1 A N D (0 X O R x)$ ，这种情况则需要进行讨论，如果 $x$ 为 $1$ ，这最后结果为 $1$ ，否则为 $0$ 。
$(3)$ 由此我们发现，当某个数的二进制的第 $y$ 位是 $0$ 时，它无法改变，当第 $y$ 位是 $1$ 时，它可以变成 $0$ 。对于数组内的所有数，如果存在某个数的第 $y$ 位为 $1$ ，那我们一定可以保证其他数的第 $y$ 位均是 $0$ 或者变成 $0$ 。使得所有数在异或后保证第 $y$ 位为 $1$ 。为了让值更大，就要保证更多的 $1$ ，我们去判断每个位是否都有 $1$ 即可，即将所有数或上即是答案。

4）模板代码

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）算法与时间复杂度

??算法：位运算
??时间复杂度：遍历一遍数组为 $O (n)$

4、不同骰子序列的数目

1）题目描述

给你一个整数 n 。你需要掷一个 6 面的骰子 n 次。请你在满足以下要求的前提下，求出不同骰子序列的数目：
1、序列中任意相邻数字的 最大公约数 为 1。
2、序列中相等的值之间，至少有 2 个其他值的数字。正式地，如果第 i 次掷骰子的值等于第 j 次的值，那么 abs(i - j) > 2 。
请你返回不同序列的 总数目 。由于答案可能很大，请你将答案对 $10^9+7$ 取余后返回。
如果两个序列中至少有一个元素不同，那么它们被视为不同的序列。

2）原题链接

LeetCode.6107:不同骰子序列的数目

3）思路解析

$(1)$ 一眼肯定是线性 $d p$ 问题，考虑到第 $i$ 次扔骰子被第 $i ? 1$ 和 $i ? 2$ 次有关，我们需要使用三维 $d p$ 存储状态方便转移。定义 $f [i] [k] [u]$ 为第 $i$ 次扔的点数为 $u$ ，第 $i ? 1$ 次为 $k$ 的方案数。
$(2)$ 我们可以先预处理出哪些点数是可以作为相邻的点的，对于第 $i$ 次丢筛子然后再去三重循环枚举 $j, k, u$ ，在判断符合的情况下，有转移方程:
$f [i] [j] [k] = (f [i] [j] [k] + f [i ? 1] [u] [j])$

4）模板代码

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