前言

忘记的名字还能记住，失去的记忆却无法挽回

VP 周赛

整体偏重字符串的考察，t4是道数学推理题。

1. 字符串中不同整数的数目

1805. 字符串中不同整数的数目

基础的字符串考察，尤其要注意大数

Java

import java.math.BigInteger;

class Solution {
    
    public int numDifferentIntegers(String word) {
        
        // 过滤掉字母
        String w = word.replaceAll("[a-zA-Z]", " ");
        
        // 单词切分，需要注意 前置/后置空格
        String[] terms = w.trim().split("\\s+");
        
        // 注意word里，没有数字的特例
        // 这里要用大数
        return Arrays.stream(terms).filter(x -> x.length() > 0)
            .map(BigInteger::new)
            .collect(Collectors.toSet()).size();
        
    }
    
}

注：这题易错

2. 还原排列的最少操作步数

1806. 还原排列的最少操作步数

这是道非常好的题，实际VP中，没找到规律，但感觉模拟次数有限，So Brute Force Algorithm。

正解在这篇文章单向回环判断 100%

Java

class Solution {
    
    public int reinitializePermutation(int n) {

        int[] orig = IntStream.range(0, n).toArray();

        int[] perm = IntStream.range(0, n).toArray();
        int[] arr = new int[n];
        
        int cnt = 0;
        while (cnt == 0 || (cnt != 0 && !Arrays.equals(perm, orig))) {
            
            // 复制+模拟
            for (int i = 0; i < n; i++) {
                if ((i % 2) == 0) {
                    arr[i] = perm[i / 2];
                } 
                else {
                    arr[i] = perm[n / 2 + (i - 1) / 2];
                }
            }
            
            // 交换
            int[] ts = arr;
            arr = perm;
            perm = ts;

            cnt++;

        } 
        
        return cnt;
        
    }
    
}

3. 替换字符串中的括号内容

1807. 替换字符串中的括号内容

模拟题吧，题意中明确把说，没有嵌套，格式正确，那处理起来就非常的容易了。

属于滑窗类型

Java

class Solution {
    
    public String evaluate(String s, List<List<String>> knowledge) {

        // 字典构建
        Map<String, String> dict = new HashMap<>();
        for (List<String> kv: knowledge) {
            dict.put(kv.get(0), kv.get(1));
        }
        
        char[] buf = s.toCharArray();
        
        StringBuilder sb = new StringBuilder();
        
        // 滑窗模拟
        int i = 0;
        while (i < buf.length) {
            char c = buf[i];
            if (c == '(') {
                int j = i + 1;
                while (j < buf.length && buf[j] != ')') {
                    j++;
                }
                String k = new String(buf, i + 1, j - i - 1);
                
                sb.append(dict.getOrDefault(k, "?"));
                i = j + 1;
            } else {
                sb.append(c);
                i = i + 1;
            }
        }
        
        return sb.toString();
        
    }
    
    
}

4. 好因子的最大数目

1808. 好因子的最大数目

其实这题有点脑筋急转弯，不是枚举数字，然后拆解因子，再判定是否满足，是否最大。

而是直接绕过质因子，直接构造最大的数。

正所谓，正难则反

该题可以等价于

$s_{.} t_{.}$ $a_{1}, a_{2}, ..., a_{n}$ 都是质数
$s_{.} t_{.}$ $b_{1} + b_{2} + ... + b_{n} = m$

求 $a_{1}^{b_{1}} * a_{2}^{b_{2}} * ... * a_{n}^{b_{n}}$ 最大化

写题思路，更像猜测，大概有三个

可能跟 $m$ 有点关系
最小因子, 拆的越小越好
最大因子，尽量保持最大

从给的case分析来看，更像最小因子，而且更倾向于3，而不是2.

所以给了一个猜测解，但是没证明

因为数比较大，特意用了快速幂，可能这是除数学外的唯一考点。

Java

class Solution {
    
    long mod = 10_0000_0007;
    
    long ksm(int base, int n) {
        long res = 1l;
        long m = base;
        while (n > 0) {
            if ((n & 0x01) == 0x01) {
                res = (res * m) % mod;
            }
            n >>= 1;
            m = (m * m) % mod;
        }
        return res;
    }
    
    // 正难则反？脑筋急转弯
    public int maxNiceDivisors(int primeFactors) {
        
        if (primeFactors == 1) return 1;
        if (primeFactors == 2) return 2;
        
        long ans = 1l;

        if (primeFactors % 3 == 0) {
            return (int)ksm(3, primeFactors / 3);
        } else if (primeFactors % 3 == 1) {
            // 需要借一个3，然后拆成2 * 2
            return (int)((ksm(3, primeFactors / 3 - 1) * 4) % mod);
        } else {
            return (int)((ksm(3, primeFactors / 3) * 2) % mod);
        }
        
    }
    
}

除了猜测，尝试，好像也没其他辙。

标答是数字拆分，真的没想到。