A 检查按位或是否存在尾随零
枚举：枚举两个元素的组合即可
class Solution {
public:
bool hasTrailingZeros(vector<int> &nums) {
int n = nums.size();
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
if ((nums[i] | nums[j]) % 2 == 0)
return true;
return false;
}
};
B 找出出现至少三次的最长特殊子字符串 I
同C …
class Solution {
public:
int maximumLength(string s) {
int n = s.size();
vector<vector<int>> li(26);
for (int i = 0, j = 0; i < n; i = ++j) {
while (j + 1 < n && s[j + 1] == s[j])
j++;
li[s[i] - 'a'].push_back(j - i + 1);
}
int l = 0, r = n;
auto can = [&](int len) {
for (auto &v: li) {
int cnt = 0;
for (auto blk: v)
if (blk >= len)
cnt += blk - len + 1;
if (cnt >= 3)
return true;
}
return false;
};
while (l < r) {
int mid = (l + r + 1) / 2;
if (can(mid))
l = mid;
else
r = mid - 1;
}
return l != 0 ? l : -1;
}
};
C 找出出现至少三次的最长特殊子字符串 II
二分：首先将 s s s 划分成若干特殊子字符串，然后二分枚举答案，判断当前枚举值是否满足条件
class Solution {
public:
int maximumLength(string s) {
int n = s.size();
vector<vector<int>> li(26);
for (int i = 0, j = 0; i < n; i = ++j) {
while (j + 1 < n && s[j + 1] == s[j])
j++;
li[s[i] - 'a'].push_back(j - i + 1);
}
int l = 0, r = n;
auto can = [&](int len) {//判断是否存在出现至少三次长为len的特殊子字符串
for (auto &v: li) {
int cnt = 0;
for (auto blk: v)
if (blk >= len)
cnt += blk - len + 1;
if (cnt >= 3)
return true;
}
return false;
};
while (l < r) {
int mid = (l + r + 1) / 2;
if (can(mid))
l = mid;
else
r = mid - 1;
}
return l != 0 ? l : -1;
}
};
D 回文串重新排列查询
字符串哈希 + 分类讨论：每次查询对应两个区间 [ s 1 , e 1 ] [s1,e1] [s1,e1] 和 [ s 2 , e 2 ] [s2,e2] [s2,e2] ，两个区间的位置关系可以分为：
- 两个区间不相交
- 两个区间相交
- 一个区间包含另一个区间
- 两个区间都不包含另一个区间
class Solution {
public:
using ll = long long;
vector<bool> canMakePalindromeQueries(string s, vector<vector<int>> &queries) {
string sl = s.substr(0, s.size() / 2), sr = s.substr(s.size() / 2, s.size() / 2);
reverse(sr.begin(), sr.end());//反转s后半段
srand(time(0));
ll e_ = 2333 + rand() % 10;
ll mod_ = 1e9 + rand() % 10;
shash hl(sl, e_, mod_), hr(sr, e_, mod_);
int n = sl.size();
vector<vector<int>> psl(26, vector<int>(n + 1)), psr(26, vector<int>(n + 1));//各个字符出现数目的前缀和
auto cmp_ps = [&](string &s, vector<vector<int>> &ps) {//计算psl、psr
for (int i = 0; i < 26; i++)
ps[i][0] = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < 26; j++)
ps[j][i + 1] = s[i] - 'a' == j ? ps[j][i] + 1 : ps[j][i];
};
cmp_ps(sl, psl);
cmp_ps(sr, psr);
auto eql = [&](int l, int r) {//判断 sl[l,r] 和 sr[l,r] 中各字符数目是否都相等
for (int i = 0; i < 26; i++)
if (psl[i][r + 1] - psr[i][l] != psr[i][r + 1] - psr[i][l])
return false;
return true;
};
auto ge = [&](int s1, int e1, int s2, int e2) {//判断 sl[s1,e1] 中各字符数目是否都不小于 sr[s2,e2] 中对应字符数目
for (int i = 0; i < 26; i++)
if (psl[i][e1 + 1] - psr[i][s1] < psr[i][e2 + 1] - psr[i][s2])
return false;
return true;
};
auto le = [&](int s1, int e1, int s2, int e2) {//判断 sl[s1,e1] 中各字符数目是否都不大于 sr[s2,e2] 中对应字符数目
for (int i = 0; i < 26; i++)
if (psl[i][e1 + 1] - psr[i][s1] > psr[i][e2 + 1] - psr[i][s2])
return false;
return true;
};
vector<bool> res(queries.size(), false);
for (int ind = 0; ind < queries.size(); ind++) {
int s1 = queries[ind][0], e1 = queries[ind][1], s2 = n * 2 - 1 - queries[ind][3], e2 = n * 2 - 1 - queries[ind][2];
if (e1 < s2 || e2 < s1) {//两个区间不相交
if (e2 < s1) {
swap(s1, s2);
swap(e1, e2);
}
if (s1 != 0 && hl(0, s1 - 1) != hr(0, s1 - 1))
continue;
if (e1 + 1 < s2 && hl(e1 + 1, s2 - 1) != hr(e1 + 1, s2 - 1))
continue;
if (e2 != n - 1 && hl(e2 + 1, n - 1) != hr(e2 + 1, n - 1))
continue;
if (!eql(s1, e1) || !eql(s2, e2))
continue;
} else {//两个区间相交
if (s1 <= s2 && e1 >= e2) {//[s1,e1] 包含 [s2,e2]
if (s1 != 0 && hl(0, s1 - 1) != hr(0, s1 - 1) || e1 != n - 1 && hl(e1 + 1, n - 1) != hr(e1 + 1, n - 1))
continue;
if (!eql(s1, e1))
continue;
} else if (s2 <= s1 && e2 >= e1) {[s2,e2] 包含 [s1,e1]
if (s2 != 0 && hl(0, s2 - 1) != hr(0, s2 - 1) || e2 != n - 1 && hl(e2 + 1, n - 1) != hr(e2 + 1, n - 1))
continue;
if (!eql(s2, e2))
continue;
} else {//两个区间相交,且任意一个都不包含另一个
if (s1 < s2) {// s1<s2<=e1<=e2
if (s1 != 0 && hl(0, s1 - 1) != hr(0, s1 - 1) || e2 != n - 1 && hl(e2 + 1, n - 1) != hr(e2 + 1, n - 1))
continue;
if (!ge(s1, e1, s1, s2 - 1) || !le(e1 + 1, e2, s2, e2) || !eql(s1, e2))
continue;
} else {//s2<s1<=e2<=s1
if (s2 != 0 && hl(0, s2 - 1) != hr(0, s2 - 1) || e1 != n - 1 && hl(e1 + 1, n - 1) != hr(e1 + 1, n - 1))
continue;
if (!le(s2, s1 - 1, s2, e2) || !ge(s1, e1, e2 + 1, e1) || !eql(s2, e1))
continue;
}
}
}
res[ind] = true;
}
return res;
}
class shash {//字符串哈希模板
public:
vector<ll> pres;
vector<ll> epow;
ll e, p;
shash(string &s, ll e, ll p) {
int n = s.size();
this->e = e;
this->p = p;
pres = vector<ll>(n + 1);
epow = vector<ll>(n + 1);
epow[0] = 1;
for (int i = 0; i < n; i++) {
pres[i + 1] = (pres[i] * e + s[i]) % p;
epow[i + 1] = (epow[i] * e) % p;
}
}
ll operator()(int l, int r) {
ll res = (pres[r + 1] - pres[l] * epow[r - l + 1] % p) % p;
return (res + p) % p;
}
};
};
