Problem List
- [1] 强密码检验器 II
- [2] 咒语和药水的成功对数
- [3] 替换字符后匹配
- [4] 统计得分小于 K 的子数组数目
1. 强密码检验器 II
1.1 题目描述
如果一个密码满足以下所有条件，我们称它是一个 强 密码：
- 它有至少 8 个字符。
- 至少包含 一个小写英文 字母。
- 至少包含 一个大写英文 字母。
- 至少包含 一个数字 。
- 至少包含 一个特殊字符 。特殊字符为：
"!@#$%^&*()-+"中的一个。 - 它 不 包含
2个连续相同的字符（比方说"aab"不符合该条件，但是"aba"符合该条件）。
给你一个字符串 password ，如果它是一个 强 密码，返回 true，否则返回 false 。
示例1：
输入： password = “IloveLe3tcode!”
输出： true
解释： 密码满足所有的要求，所以我们返回 true 。示例2：
输入： password = “Me+You—IsMyDream”
输出： false
解释： 密码不包含数字，且包含 2 个连续相同的字符。所以我们返回 false 。示例3：
输入： password = “1aB!”
输出： false
解释： 密码不符合长度要求。所以我们返回 false 。
1.2 思路
直接模拟，首先检测长度是否大于等于8，如果不满足则直接返回false，然后设置多个bool类型变量用于表示第1到第5个要求是否满足，遍历整个字符串，检测前后字符是否存在相邻两个字符一样的情况，若是则返回false；否则将对应的bool变量置为true,最后如果满足中间四个要求则返回true，如果其中若干个没满足要求则返回false。
class Solution {
set<char> s;
public:
bool strongPasswordCheckerII(string password) {
// 检查长度是否满足要求
if(password.length() < 8) return false;
// 将特殊字符应映射到哈希表中
string str = "!@#$%^&*()-+";
for(char ch: str){
s.insert(ch);
}
// 依次为大小字母、小写字母、数字、特殊字符
bool upper = false, lower = false, num = false, flag = false;
for(int i = 0; i < password.length(); ++i){
// 检查相邻是否存在一样的字符
if(i > 0 && password[i] == password[i-1]){
return false;
}
if(password[i] >= 'A' && password[i] <= 'Z'){
upper = true;
}else if(password[i] >= 'a' && password[i] <= 'z'){
lower = true;
}else if(password[i] >= '0' && password[i] <= '9'){
num = true;
}else if(s.count(password[i])){
flag = true;
}
}
// 只有满足全部要求才返回true
return upper&&lower&&num&&flag;
}
}; 2. 咒语和药水的成功对数
2.1 题目描述
给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。
同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。
请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。
示例1：
输入： spells = [5,1,3], potions = [1,2,3,4,5], success = 7
输出： [4, 0, 3]
解释：
- 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
- 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
- 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
所以返回 [4,0,3] 。
示例2：
输入： spells = [3,1,2], potions = [8,5,8], success = 16
输出： [2, 0, 2]
解释：
- 第 0 个咒语：3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
- 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
- 第 2 个咒语：2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。
所以返回 [2,0,2] 。
2.2 思路
对potions数组进行升序排序，然后遍历spells数组，在potions数组中找到第一个大于等于ceil(success / spells[i])的下标，即找到可以与spells[i]配对成功的药水数。
class Solution {
public:
vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
sort(potions.begin(), potions.end());
vector<int> res(spells.size());
for(int i = 0; i < spells.size(); ++i){
long long target = success / spells[i];
if(success % (long long)spells[i] != 0){
target += 1;
}
res[i] = potions.end() - lower_bound(potions.begin(),potions.end(),target);
}
return res;
}
}; 3. 替换字符后匹配
3.1 题目描述
给你两个字符串 s 和 sub 。同时给你一个二维字符数组 mappings ，其中 mappings[i] = [oldi, newi] 表示你可以替换 sub 中任意数目的 oldi 字符，替换成 newi 。sub 中每个字符 不能 被替换超过一次。
如果使用 mappings 替换 0 个或者若干个字符，可以将 sub 变成 s 的一个子字符串，请你返回 true，否则返回 false 。
一个 子字符串 是字符串中连续非空的字符序列。
示例1：
输入： s = “fool3e7bar”, sub = “leet”, mappings = [[“e”,”3”],[“t”,”7”],[“t”,”8”]]
输出： true
解释： 将 sub 中第一个 ‘e’ 用 ‘3’ 替换，将 ‘t’ 用 ‘7’ 替换。
现在 sub = “l3e7” ，它是 s 的子字符串，所以我们返回 true 。
示例2：
输入： s = “fooleetbar”, sub = “f00l”, mappings = [[“o”,”0”]]
输出： false
解释： 字符串 “f00l” 不是 s 的子串且没有可以进行的修改。
注意我们不能用 ‘o’ 替换 ‘0’ 。
示例2：
输入： s = “Fool33tbaR”, sub = “leetd”, mappings = [[“e”,”3”],[“t”,”7”],[“t”,”8”],[“d”,”b”],[“p”,”b”]]
输出： true
解释： 将 sub 里第一个和第二个 ‘e’ 用 ‘3’ 替换，用 ‘b’ 替换 sub 里的 ‘d’ 。
得到 sub = “l33tb” ，它是 s 的子字符串，所以我们返回 true 。
3.2 思路
class Solution {
public:
bool matchReplacement(string s, string sub, vector<vector<char>>& mappings) {
int len1 = s.length(), len2 = sub.length();
bool hash[128][128] = {0};
for(auto it: mappings){
hash[(int)it[0]][(int)it[1]] = true; // 实现mappings中的映射，为true则有从old转到new的
}
int left = 0; // 窗口左端点
while(left <= len1-len2){
int i = 0;
for(; i < len2; ++i){ // 遍历sub
if(s[i+left] == sub[i]){ // 字符一致不用管
continue;
}
if(!hash[(int)sub[i]][(int)s[i+left]]){ // 字符不一致就看mappings中有没有可以将sub[i]
break; // 改为s[i+left],没有则将窗口右移
}
}
if(i == len2){ // 窗口中的字符可以通过修改后匹配
return true;
}
++left;
}
return false;
}
}; 4. 统计得分小于 K 的子数组数目
4.1 题目描述
一个数字的 分数 定义为数组之和 乘以 数组的长度。
比方说，[1, 2, 3, 4, 5] 的分数为 (1 + 2 + 3 + 4 + 5) * 5 = 75 。
给你一个正整数数组 nums 和一个整数 k ，请你返回 nums 中分数 严格小于 k 的 非空整数子数组数目。
子数组 是数组中的一个连续元素序列。
示例1：
输入： nums = [2,1,4,3,5], k = 10
输出： 6
解释：
有 6 个子数组的分数小于 10 ：
- [2] 分数为 2 * 1 = 2 。
- [1] 分数为 1 * 1 = 1 。
- [4] 分数为 4 * 1 = 4 。
- [3] 分数为 3 * 1 = 3 。
- [5] 分数为 5 * 1 = 5 。
- [2,1] 分数为 (2 + 1) * 2 = 6 。
注意，子数组 [1,4] 和 [4,3,5] 不符合要求，因为它们的分数分别为 10 和 36，但我们要求子数组的分数严格小于 10 。示例2：
输入： nums = [1,1,1], k = 5
输出： 5
解释：
除了 [1,1,1] 以外每个子数组分数都小于 5 。
[1,1,1] 分数为 (1 + 1 + 1) * 3 = 9 ，大于 5 。
所以总共有 5 个子数组得分小于 5 。
4.2 思路
滑动窗口。根据数组得分定义为数组的加和与长度的乘积，因而可以转换为求滑动窗口中数字的加和与窗口长度的乘积严格小于k，当满足这个条件时则窗口右端点右移，否则说明以窗口左端点为起始点且满足数组得分小于k的子数组个数为right - left - 1(从left开始窗长依次递增直至右端点在right的前一个位置，递增次数即为子数组个数)，然后左端点右移一位，继续循环。当right已经移动到最后一个位置时，直接将当前窗口中的所有子数组个数((right-left-1)*(right-left)/2)加到答案并返回。
class Solution {
public:
long long countSubarrays(vector<int>& nums, long long k) {
int n = nums.size();
vector<long> vec(n+1, 0);
for(int i = 0; i < n; ++i){
vec[i+1] = (long)vec[i] + nums[i];
}
long long ans = 0;
int left = 0, right = 1;
while(right <= n){
while(right <= n && ((long long)(vec[right] - vec[left]))*(right - left) < k){
++right;
}
if(right == n+1){
return ans + ((long long)(right - left - 1))*(right - left)/2;
}
ans += right - left - 1;
left++;
}
return ans;
}
};
