力扣11.22

44. 通配符匹配

给你一个输入字符串 (s) 和一个字符模式 § ，请你实现一个支持 ‘?’ 和 ‘*’ 匹配规则的通配符匹配：

• ‘?’ 可以匹配任何单个字符。
• ‘*’ 可以匹配任意字符序列（包括空字符序列）。
  判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

数据范围

• 0 <= s.length, p.length <= 2000
• s 仅由小写英文字母组成
• p 仅由小写英文字母、'?' 或 '*' 组成

分析

令$dp[i][j]$表示$p$的前$i$个是否能匹配$s$的前$j$个，状态转移如下

• 若$p[i]==s[j]$，此时$dp[i][j]=dp[i-1][j-1]$
• 若KaTeX parse error: Expected 'EOF', got '&' at position 11: p[i]!=s[j]&̲&p[i]!='?'&&p[i…，此时$dp[i][j]=false$
• 若$p[i]={=}^{\prime }{?}^{\prime }$，此时$dp[i][j]=dp[i-1][j-1]$
• 若$p[i]={=}^{\prime }{\ast }^{\prime }$，此时由于 *可以匹配任意字符串，因此若$dp[i-1][0],dp[i-1][1]...dp[i-1][j]$中有成立的，$dp[i][j]$就成立，反之不成立，为了优化复杂度，可以使用一个$pre[i][j]$数组表示$p$的前$i$个匹配$s$的至多前$j$个字符是否成功，这样$dp[i][j]=pre[i-1][j]$

代码

class Solution {
public:
    const static int N = 2005;
    bool dp[N][N];
    bool pre[N][N];
    bool isMatch(string s, string p) {
        if(s == "") {
            for(int j = 0; j < p.size(); j ++ ) {
                if(p[j] != '*') return false;
            }
            return true;
        }
        int n = s.size(), m = p.size();
        dp[0][0] = true;
        pre[0][0] = true;
        for(int i = 0; i < m; i ++ ) {
            if(i == 0 && p[i] == '*') {
                dp[i + 1][0] = true;
                pre[i + 1][0] = true;
                for(int j = 0; j < n; j ++ ) {
                    dp[i + 1][j + 1] = true;
                    pre[i + 1][j + 1] = true;
                }
                continue;
            } else if(i != 0 && p[i] == '*') {
                dp[i + 1][0] = dp[i][0];
                pre[i + 1][0] = dp[i + 1][0];
            }
            cout << dp[i + 1][0] << " ";
            for(int j = 0; j < n; j ++ ) {
                if(p[i] == s[j]) dp[i + 1][j + 1] = dp[i][j];
                else if(p[i] == '?') dp[i + 1][j + 1] = dp[i][j];
                else if(p[i] == '*') {
                    dp[i + 1][j + 1] = pre[i][j + 1];
                }
                else dp[i + 1][j + 1] = false;
                pre[i + 1][j + 1] = (dp[i + 1][j + 1] || pre[i + 1][j]);
                // cout << dp[i + 1][j + 1] << " ";
            }
            // cout << endl;
        }
        return dp[m][n];
    }
};

3233. 统计不是特殊数字的数字数量

给你两个 正整数 l 和 r。对于任何数字 x，x 的所有正因数（除了 x 本身）被称为 x 的 真因数。

如果一个数字恰好仅有两个 真因数，则称该数字为 特殊数字。例如：

• 数字 4 是 特殊数字，因为它的真因数为 1 和 2。
• 数字 6 不是 特殊数字，因为它的真因数为 1、2 和 3。
  返回区间 [l, r] 内 不是 特殊数字 的数字数量。

数据范围

• 1 <= l <= r <= 109

分析

可以发现，若是特殊数字，必须满足它是一个质数的完全平方，因此先使用欧拉筛获得全部质数，然后看看l到r中有多少个质数的平方即可

代码

class Solution {
public:
    const static int N =  1e5 + 5;
    int prime[N], cnt = 0;
    bool vis[N];
    void init(int n ) {
        vis[1] = true;
        for(int i = 2; i <= n; i ++ ) {
            if(!vis[i]) prime[++ cnt ] = i;
            for(int j = 1; prime[j] * i <= n; j ++ ) {
                vis[i * prime[j]] = true;
                if(i % prime[j] == 0) break;
            }
        }
    }
    int nonSpecialCount(int l, int r) {
        init(N - 5);
        int res = 0;
        for(int i = 1; i <= cnt; i ++ ) {
            if(prime[i] > sqrt(r)) break;
            if(prime[i] * prime[i] >= l && prime[i] * prime[i] <= r) {
                res ++ ;
            }
        }
        return r - l + 1 - res;
    }
};