目录
一，3162. 优质数对的总数 I
二，3163. 压缩字符串 III
三，3164. 优质数对的总数 II
四， 3165. 不包含相邻元素的子序列的最大和
一，3162. 优质数对的总数 I
假设 x 是 nums1 数组中的值，y 是 nums2 数组中值，我们要求的就是有几个 (x，y) 满足
x % (y * k) == 0，可以直接暴力
代码如下：
class Solution {
public int numberOfPairs(int[] nums1, int[] nums2, int k) {
int ans = 0;
for(int x : nums1){
for(int y : nums2){
if(x%(y*k)==0) ans++;
}
}
return ans;
}
}二，3163. 压缩字符串 III
本题是一道模拟题，遍历word字符串，将相邻且字符相同的子字符串，写成数字+字符的形式，比如 "aaabbc"，写成 "3a2b1c"，注意，数字最大是9，也就是说如果遇到比如12个连续的'a'，我们要写成 "9a3a"。
代码如下：
class Solution {
public String compressedString(String word) {
int cnt = 1;
char[] ch = word.toCharArray();
StringBuilder res = new StringBuilder();
for(int i=1; i<ch.length; i++){
if(ch[i] == ch[i-1] && cnt < 9){
cnt++;
}else{
res.append(cnt);
res.append(ch[i-1]);
cnt = 1;
}
}
if(cnt > 0){
res.append(cnt);
res.append(ch[ch.length-1]);
}
return res.toString();
}
}三，3164. 优质数对的总数 II
1. 预处理被除数：
- 要求满足 x % (y * k) == 0 的数对（x，y），可以先枚举nums1数组，使用哈希表统计出 x / k 的所有因子及其对应的数量，再枚举 nums2 数组，看 y 是否是x/k的因子（即是否在哈希表中），如果存在，加上对应的值。最终得出答案
2.预处理除数
- 除了上述做法，我们还可以先枚举nums1数组，使用哈希表统计出 x / k 及其对应的数量，枚举nums2数组，枚举 y 的倍数及其数量，看是否在哈希表中，如果存在，加上对应的值。最终得出答案
代码如下：
class Solution {
//预处理被除数x
public long numberOfPairs(int[] nums1, int[] nums2, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int x : nums1){//统计 <x/k 的因子, 对应的数量>
if(x%k == 0){
for(int i=1; i<=Math.sqrt(x/k); i++){
if(x/k%i == 0){
map.merge(i, 1, Integer::sum);
if(i < x/k/i)
map.merge(x/k/i, 1, Integer::sum);
}
}
}
}
long ans = 0;
for(int y : nums2){
ans += map.getOrDefault(y, 0);
}
return ans;
}
}
class Solution {
//预处理除数y
public long numberOfPairs(int[] nums1, int[] nums2, int k) {
//O(n+m+(mx/k)logm)
Map<Integer, Integer> map1 = new HashMap<>();
long mx = 0;
for(int x : nums1){//统计 <x/k,x/k的数量>
if(x%k == 0){
map1.merge(x/k, 1, Integer::sum);
mx = Math.max(mx, x/k);
}
}
Map<Integer, Integer> map2 = new HashMap<>();
for(int y : nums2){
map2.merge(y, 1, Integer::sum);
}
long ans = 0;
for(int y : map2.keySet()){
int s = 0;
for(int j=y; j<=mx; j+=y){//枚举 y 的倍数
s += map1.getOrDefault(j, 0);
}
ans += (long) s * map2.get(y);
}
return ans;
}
}四， 3165. 不包含相邻元素的子序列的最大和
本题一看就是一道标准的打家劫舍问题，直接上代码：
class Solution {
public int maximumSumSubsequence(int[] nums, int[][] queries) {
int MOD = (int)1e9 + 7;
int n = nums.length;
int[] f = new int[n];
int ans = 0;
for(int[] q : queries){
nums[q[0]] = q[1];
f[0] = Math.max(0, nums[0]);
for(int i=1; i<n; i++){
f[i] = Math.max(f[i-1], (i>1?f[i-2]:0)+nums[i]);
}
System.out.println(f[n-1]);
ans = (ans+f[n-1])%MOD;
}
return ans;
}
}但是上述做法会超时，需要换一种做法，这题实际上需要使用线段树动态维护[0，n-1]的最大值，就是将 [l，r] = [l，mid] + [mid+1，r]，不断的分治，但是由于题目要求不包含相邻元素，也就是说mid 和 mid+1这两个点最多只能取一个，而只靠一维数组无法维护，所以需要一个二维数组f[n][4]，这里先用f00，f01，f10，f11表示一下它们的状态：
- f00:表示[l,r]l,r都不选的合法最大值
- f01:表示[l,r]l不选的合法最大值(r可选可不选)
- f10:表示[l,r]r不选的合法最大值(l可选可不选)
- f11:表示[l,r]都可以选的合法最大值(l,r可选可不选)
它们之间的递推关系：
- f00 = max(f01+f00, f00+f10)
- f01 = max(f00+f11, f01+f01)
- f10 = max(f10+f10, f11+f00)
- f11 = max(f10+f11, f11+f01)
画个图来理解一下：
剩下的基本都是线段树基本方法，没什么变化，代码如下：
class Solution {
//f00:表示[l,r]l,r都不选的合法最大值
//f01:表示[l,r]l不选的合法最大值(r可选可不选)
//f10:表示[l,r]r不选的合法最大值(l可选可不选)
//f11:表示[l,r]都可以选的合法最大值(l,r可选可不选)
//[l, r] = [l, mid] + [mid+1, r]
// 00 01 10 11
//f00 = max(f01+f00, f00+f10)
//f01 = max(f00+f11, f01+f01)
//f10 = max(f10+f10, f11+f00)
//f11 = max(f10+f11, f11+f01)
int[][] f;
int[] a;
void maintain(int i){
f[i][0] = Math.max(f[i<<1][1]+f[i<<1|1][0], f[i<<1][0]+f[i<<1|1][2]);
f[i][1] = Math.max(f[i<<1][0]+f[i<<1|1][3], f[i<<1][1]+f[i<<1|1][1]);
f[i][2] = Math.max(f[i<<1][2]+f[i<<1|1][2], f[i<<1][3]+f[i<<1|1][0]);
f[i][3] = Math.max(f[i<<1][2]+f[i<<1|1][3], f[i<<1][3]+f[i<<1|1][1]);
}
void build(int l, int r, int i){
if(l == r){
f[i][3] = Math.max(0, a[l]);
}else{
int mid = (l + r) / 2;
build(l, mid, i<<1);
build(mid+1, r, i<<1|1);
maintain(i);
}
}
void update(int l, int r, int i, int R, int val){
if(l == r){
f[i][3] = Math.max(0, val);
return;
}
int mid = (l + r) / 2;
if(R <= mid){
update(l, mid, i<<1, R, val);
}else{
update(mid+1, r, i<<1|1, R, val);
}
maintain(i);
}
int query(int l, int r, int i){
return f[i][3];
}
public int maximumSumSubsequence(int[] nums, int[][] queries) {
int MOD = (int)1e9 + 7;
int n = nums.length;
f = new int[n<<2][4];
a = nums;
build(0, n-1, 1);
int ans = 0;
for(int[] q : queries){
update(0, n-1, 1, q[0], q[1]);
ans = (ans + query(0, n-1, 1))%MOD;
}
return ans%MOD;
}
}
