题目列表
3162. 优质数对的总数 I
3163. 压缩字符串 III
3164. 优质数对的总数 II
3165. 不包含相邻元素的子序列的最大和
一、优质数对的总数I
这里由于数据范围比较小，我们可以直接暴力枚举，代码如下
class Solution {
public:
int numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
int ans = 0;
for(auto x:nums1){
for(auto y:nums2){
ans += x%(y*k)==0;
}
}
return ans;
}
};二、压缩字符串III
这题也是简单的模拟题，只要统计连续出现的字符个数，将它们拼接称字符串即可，但是要注意一旦连续出现的次数大于十，我们就需要将它进行拆分，比如有20个连续的a，拼接的字符串不能是20a，而应该是9a9a2a，代码如下
class Solution {
public:
string compressedString(string word) {
string ans;
int i = 0, n = word.size();
while(i < n){
int j = i++;
while(i < n && word[j] == word[i])
i++;
int m = i - j; // 字符word[j]连续出现的个数
while(m >= 10){
ans += '9';
ans += word[j];
m -= 9;
}
if(m) ans += to_string(m) + word[j];
}
return ans;
}
};三、优质数对的总数II
题目和第一题相同，但是数据范围被扩大了，不能暴力枚举了，该如何做？
题目要求nums1[i]%k*nums2[j]==0的数对个数，我们有两种思路：
1、枚举统计nums1数组元素的因子有哪些，然后遍历统计nums2[j]*k占了多少
2、枚举统计nums2数组元素*k的倍数有哪些，然后统计nums1数组元素占了多少
两种方法都可以，在代码中我们会算它们的时间复杂度
代码如下
class Solution {
// 1、枚举统计nums1数组元素的因子有哪些，然后遍历统计nums2[j]*k占了多少
public:
// 时间复杂度 O(n*sqrt(U/k) + m) U = max(nums1)
long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
unordered_map<int,int> mp;
// O(n*sqrt(U/k)) U = max(nums1)
for(auto x:nums1){
if(x%k) continue; // 首先必须是k的倍数
x /= k;
for(int i = 1; i*i <= x; i++){
if(x%i) continue;
mp[i]++;
if(i*i!=x) mp[x/i]++;
}
}
// O(m)
long long ans = 0;
for(auto x:nums2){
ans += mp.count(x)?mp[x]:0;
}
return ans;
}
};
class Solution {
// 2、枚举统计nums2数组元素*k的倍数有哪些，然后遍历统计nums1[i]占了多少
public:
// 时间复杂度 O(n+m+U*logm) U = max(nums1)
long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
unordered_map<int,int> cnt1, cnt2, mp;
int u = INT_MIN;
for(auto x:nums1){
u = max(u, x);
if(x%k) continue;
cnt1[x/k]++;
}
if(cnt1.empty()) return 0;
for(auto x:nums2){
cnt2[x]++;
}
// 看着像是O(n^2)的时间复杂度
// 最坏的情况是nums2的元素全都不重复
// 为1,2,3,....,mx 共有m个数
// U/1 + U/2 + U/3 + ... + U/mx
//= U*(1+1/2+1/3+...+1/mx)
//= U*logm
// 1+1/2+1/3+...+1/mx 调和级数的极限，可以直接求1/x的积分，为logx
// O(U*logm)
long long ans = 0;
for(auto [x,c]:cnt2){
int s = 0;
for(int i = x; i <= u;i += x){
s += cnt1.count(i)?cnt1[i]:0;
}
ans += (long long)s*c;
}
return ans;
}
};四、不包含相邻元素的子序列的最大和
这题单独只看求不相邻元素的子序列最大和，是一道标准的打家劫舍问题，建议没写过的先去写一写，如果写过的话，其实很容易想到它可以用动态规划来做，然后你就会开始想如何进行优化，代码如下
class Solution {
const int MOD = 1e9+7;
public:
int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& q) {
int n = nums.size(), m = q.size();
int ans = 0;
vector<long long> dp(n+2);
for(int i=0;i<n;i++){
dp[i+2] = max(dp[i]+nums[i],dp[i+1]);
}
for(auto v:q){
int pos = v[0], x = v[1];
nums[pos] = x;
bool flag = false;
for(int i=pos;i<n;i++){
dp[i+2] = max(dp[i]+nums[i],dp[i+1]);
}
ans = (ans%MOD + dp.back()%MOD)%MOD;
}
return ans;
}
};但实际上这题用动态规划来写是不行的，会超时，可以去试试(java的除外，java给的时间比较宽松，官方应该会调整，这里暂且不论)。
那么这题该如何去做呢？注意，题目进行的是单点更新，区间查询的操作，显然很适合用线段树来做，那么能不能呢？这里就需要考虑一个问题：打家劫舍问题能不能用分治来做？思路如下
代码如下
// 线段树
class Solution {
const int MOD = 1e9 + 7;
vector<array<unsigned int,4>> t;
// f00,f01,f10,f11
// 0, 1, 2, 3
void maintain(int o){
auto& a = t[o<<1], b = t[o<<1|1];
t[o] = {
max(a[0]+b[2], a[1]+b[0]), // 00 = max 00+10 01+00
max(a[0]+b[3], a[1]+b[1]), // 01 = max 00+11 01+01
max(a[2]+b[2], a[3]+b[0]), // 10 = max 10+10 11+00
max(a[2]+b[3], a[3]+b[1]) // 11 = max 10+11 11+01
};
}
void build(vector<int>&nums,int o,int l,int r){
if(l == r){
// 当只有一个元素时，根据状态定义，只有f11是可以进行选择的为max(0,nums[l])，其余都无法选择为0
t[o][3] = max(0,nums[l]);
return;
}
int mid = (l+r)>>1;
build(nums, o<<1, l, mid);
build(nums, o<<1|1, mid + 1, r);
maintain(o);
}
void update(int o,int l,int r,int i,int val){
if(l == r){
t[o][3] = max(val,0);
return;
}
int mid = (l+r)>>1;
if(i<=mid){
update(o<<1,l,mid,i,val);
}else{
update(o<<1|1,mid+1,r,i,val);
}
maintain(o);
}
public:
int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
t.resize(2<<(32 - __builtin_clz(n)));
build(nums, 1, 0, n - 1);
long long ans = 0;
for(auto&q:queries){
update(1, 0, n - 1, q[0], q[1]);
ans += t[1][3];
}
return ans%MOD;
}
};
