感谢又给一次AK的机会，AK传送门
强密码检验器 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; } };
咒语和药水的成功对数
题目
思路
代码
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; } };
替换字符后匹配
题目
思路
代码
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; } };
补题学到的妙解
s u f 数组存储最终每个字符所有能转移到的状态
最终结果就是取 s u b中每个字符状态的并集
参考这位大佬
位运算加速，代码如下：
class Solution { public: static const int N = 5010; bitset<N> res, pre[128], suf[128]; bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) { for (int i = 0; i < 128; i++) pre[i].reset(); for (int i = 0; i < s.size(); i++) pre[s[i]].set(i); for (int i = 0; i < 128; i++) suf[i] = pre[i]; for (auto &mp: mappings) suf[mp[0]] |= pre[mp[1]]; res.set(); for (int i = 0; i < sub.size(); i++) res &= suf[sub[i]] >> i; return res.count(); } };
统计得分小于 K 的子数组数目
题目
思路
比较容易能发现一个性质，单调性， 即子数组越长，那么分数越高。
由此我们可以想到有双指针来解决，（应该可以吧hhhh
l , r 维护区间左右，当前区间表示一定满足分数
那么如何计算上每个状态的贡献呢？
我们可以定义，当前状态 ll,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; } };
