感谢又给一次AK的机会

文章目录

• 强密码检验器 II
• 咒语和药水的成功对数
• 替换字符后匹配
• 统计得分小于 K 的子数组数目

强密码检验器 II

题目

思路

• 根据题意模拟即可

代码

class Solution {public:    bool strongPasswordCheckerII(string p) { int n = p.size(); if(n < 8) return false; string s = "!@#$%^&*()-+"; bool o1 = true, o2 = true, o3 = true, o4 = true, o5 = true; for (int i = 0; i < n; i++) {     if(p[i] <= 'z' && p[i] >= 'a') o1 = false;     if(p[i] <= 'Z' && p[i] >= 'A') o2 = false;     if(p[i] <= '9' && p[i] >= '0') o3 = false;     for (int j = 0; j < s.size(); j++) if(s[j] == p[i]) o4 = false;     if(i && p[i] == p[i - 1]) o5 = false; } return !o1 && !o2 && !o3 && !o4 && o5;    }};

咒语和药水的成功对数

题目

思路

计算 $spells[i]\ast potions[j]>=success$ ，每个 $i$ 有多少个 $j$ 满足。

转化为找到 $spells[i]>=success/potions[j]$，有多少个 $j$ 满足。

那么此时我们可以新开数组 $a[j]$ 用以表示 $success/potions[j]$

由于在此是大于等于才满足条件（也即 $a[j]<=spells[i]$），那么我们将 $a$ 数组存储上取整的值：$(success-1)/potions[j]+1$。

相当于是找到 $a[j]<spells[i]$ 的 $j$ 的个数，此时我们将 $a$ 数组升序排列，可以用二分查找临界位置。

• 最终结果： $res[i]=upper\_bound(a.begin(),a.end(),spells[i])-a.begin();$

代码

class Solution {public:    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) { vector<int> res; vector<long long> a; for (int i = 0; i < potions.size(); i++) {     a.push_back(1ll * (success - 1) / potions[i] + 1); } sort(a.begin(), a.end()); for (int i = 0; i < spells.size(); i++) {     int id = upper_bound(a.begin(), a.end(), spells[i]) - a.begin();     res.push_back(id); } return res;    }};

替换字符后匹配

题目

思路

• 比赛的时候想歪了，以为是一道难的算法题，还想着怎么建边搜。

其实我们看数据发现，$5000$ 的字符串长度 ，大概 n 2 n^2 n2 也就是 $3e7$，加上中间字符串的匹配操作，卡个极限时间能过。

• 从左向右遍历 $s$ ，以每个位置 $i$ 为起始，向后的 $sub.size()$ 长度的子串，去与 $sub$ 进行比对。
• 遍历 $sub$，如果当前字符 $sub[j]$ 可以换为对应位的 $s$ 的子串字符，直到所有 $j$ 都满足，那么即可以将 $sub$ 变为 $s$ 的子串

细节详见代码部分

代码

class Solution {public:    map<char, map<char, bool>> mp; bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) { int n = s.size(), m = sub.size(); if(m > n) return false; for (int i = 0; i < mappings.size(); i++) {     char a = mappings[i][0], b = mappings[i][1];     mp[a][b] = true; }  for (int i = 0; i < n - m + 1; i++) {     string pre = s.substr(i, m);     bool o = true;     for (int j = 0; j < m; j++) {  if(!mp[sub[j]][pre[j]] && sub[j] != pre[j]) o = false;  if(!o) break;     }     if(o) return true; } return false;    }};

统计得分小于 K 的子数组数目

题目

思路

• 比较容易能发现一个性质，单调性， 即子数组越长，那么分数越高。

由此我们可以想到有双指针来解决，（应该可以吧hhh

• $l,r$ 维护区间左右，当前区间表示一定满足分数 $<k$ 的情况。

那么如何计算上每个状态的贡献呢？

• 我们可以定义，当前状态 $l,r$ ，贡献值为：以 $r$ 结尾的区间个数，并且区间起始是从 $l$ 开始，形式化为 $r-l+1$
• 这样在 $r$ 每次移动时，都对其计算贡献，显然每个状态都是不重的，并且对于答案这样是不会遗漏的。（$r$ 会从起始移动到末尾）

误：一开始我对贡献计算是区间 $l,r$ 之间所有区间数，显然这样会有大量的重复区间的计算，读者可自行思考。

代码

class Solution {public:    #define ll long long    long long countSubarrays(vector<int>& nums, long long k) { int r = 0, n = nums.size(); ll now = 0, len = 0, res = 0; for (int i = 0; i < n; i++) {     while(r < n && ((now + nums[r])) * (len + 1) < k) {  now += nums[r];  len ++;  res += (r - i + 1);  r++;     }     now -= nums[i];     len--; } return res;    }};