【LeetCode第 80 场双周赛】
感谢又给一次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; }};
咒语和药水的成功对数
题目
思路
计算 s p e l l s [ i ] ∗ p o t i o n s [ j ] > = s u c c e s s {spells[i] * potions[j] >= success} spells[i]∗potions[j]>=success ,每个 i {i} i 有多少个 j {j} j 满足。
转化为找到 s p e l l s [ i ] > = s u c c e s s / p o t i o n s [ j ] spells[i] >= success \ / \ potions[j] spells[i]>=success / potions[j],有多少个 j {j} j 满足。
那么此时我们可以新开数组 a [ j ] a[j] a[j] 用以表示 s u c c e s s / p o t i o n s [ j ] success \ / \ potions[j] success / potions[j]
由于在此是大于等于才满足条件(也即 a [ j ] < = s p e l l s [ i ] a[j]<=spells[i] a[j]<=spells[i]),那么我们将 a a a 数组存储上取整的值: ( s u c c e s s − 1 ) / p o t i o n s [ j ] + 1 (success-1) \ / \ potions[j] + 1 (success−1) / potions[j]+1。
相当于是找到 a [ j ] < s p e l l s [ i ] a[j] < spells[i] a[j]<spells[i] 的 j j j 的个数,此时我们将 a a a 数组升序排列,可以用二分查找临界位置。
- 最终结果: r e s [ i ] = u p p e r _ b o u n d ( a . b e g i n ( ) , a . e n d ( ) , s p e l l s [ i ] ) − a . b e g i n ( ) ; res[i]=upper\_bound(a.begin(), a.end(), spells[i]) - a.begin(); 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 5000 5000 的字符串长度 ,大概 n 2 n^2 n2 也就是 3 e 7 3e7 3e7,加上中间字符串的匹配操作,卡个极限时间能过。
- 从左向右遍历 s s s ,以每个位置 i i i 为起始,向后的 s u b . s i z e ( ) sub.size() sub.size() 长度的子串,去与 s u b sub sub 进行比对。
- 遍历 s u b sub sub,如果当前字符 s u b [ j ] sub[j] sub[j] 可以换为对应位的 s s s 的子串字符,直到所有 j j j 都满足,那么即可以将 s u b sub sub 变为 s s 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 l,r l,r 维护区间左右,当前区间表示一定满足分数 < k < k <k 的情况。
那么如何计算上每个状态的贡献呢?
- 我们可以定义,当前状态 l , r l, r l,r ,贡献值为:以 r r r 结尾的区间个数,并且区间起始是从 l l l 开始,形式化为 r − l + 1 r - l + 1 r−l+1
- 这样在 r r r 每次移动时,都对其计算贡献,显然每个状态都是不重的,并且对于答案这样是不会遗漏的。(r r r 会从起始移动到末尾)
误:一开始我对贡献计算是区间 l , r l, 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; }};
2022年6月12日01点06分