唐山如何做百度的网站,网站后台登入模板,装修网网站建设,网页设计基础图片题目列表
3334. 数组的最大因子得分
3335. 字符串转换后的长度 I
3336. 最大公约数相等的子序列数量
3337. 字符串转换后的长度 II
一、数组的最大因子得分 数据范围足够小#xff0c;可以用暴力枚举移除的数字#xff0c;得到答案#xff0c;时间复杂度为O(n^2)#…题目列表
3334. 数组的最大因子得分
3335. 字符串转换后的长度 I
3336. 最大公约数相等的子序列数量
3337. 字符串转换后的长度 II
一、数组的最大因子得分 数据范围足够小可以用暴力枚举移除的数字得到答案时间复杂度为O(n^2)代码如下
class Solution {
public:long long maxScore(vectorint nums) {int n nums.size();auto get [](int i)-long long{// gcd(0, x) x, lcm(1, x) xlong long x 0; // 计算 gcdlong long y 1; // 计算 lcmfor(int j 0; j n; j){if(i j) continue;x gcd(x, nums[j]);y lcm(y, nums[j]);}return x * y;};long long ans get(-1); // 不去除任何数字for(int i 0; i n; i){ans max(ans, get(i));}return ans;}
};
有没有更快的做法我们同样枚举被移除的数字有没有方法能更加快速的算出剩余数字的 LCM 和 GCD有的只要我们提前算出左右两个部分的 LCM 和 GCD就能直接计算得出剩余部分的LCM 和 GCD即进行前后缀分解时间复杂度为O(n)代码如下
注意上面的时间复杂度默认 LCM 和 GCD 是O(1)但实际上 GCD/LCM 的时间复杂度为O(logn)
class Solution {
public:long long maxScore(vectorint nums) {int n nums.size();vectorlong long suf_gcd(n 1), suf_lcm(n 1, 1);// gcd(0, x) x, lcm(1, x) xfor(int i n - 1; i 0; i--){suf_gcd[i] gcd(suf_gcd[i 1], nums[i]);suf_lcm[i] lcm(suf_lcm[i 1], nums[i]);}long long ans suf_gcd[0] * suf_lcm[0]; // 不去除任何数long long pre_gcd 0, pre_lcm 1;for(int i 0; i n; i){ // 同时计算 ans 和 前缀gcd/lcmans max(ans, gcd(pre_gcd, suf_gcd[i 1]) * lcm(pre_lcm, suf_lcm[i1]));pre_gcd gcd(pre_gcd, nums[i]);pre_lcm lcm(pre_lcm, nums[i]);}return ans;}
};
二、字符串转换后的长度 I 这题的数据范围比较小我们可以模拟 t 次转换的过程。对于任意一个字母它的转换规则是一样的所以我们先统计出 26 个字母出现的次数然后根据规则进行转换即可代码如下
class Solution {const int MOD 1e9 7;
public:int lengthAfterTransformations(string s, int t) {vectorint cnt(26);for(auto e : s) cnt[e - a];while(t--){vectorinttmp(26);for(int i 0; i 26; i)tmp[i] cnt[(i-126)%26]; // 如a的出现次数变成b的出现次数// z 不仅能变成 a , 还能变成 btmp[1] (tmp[1] cnt[25]) % MOD;swap(tmp, cnt);}int ans 0;for(int i 0; i 26; i) ans (ans cnt[i]) % MOD;return ans;}
};
但是一旦 t 的范围过大就会超时有没什么更快的方法由于每个字母的转移方式是固定的所以只要给定一个字母和操作次数就能得到一个长度问题是如何加速这个计算过程
假设f[i][j]表示字母 i (用0-25表示) 经过 j 次操作的长度我们有如下方程 代码如下
class Solution {const int MOD 1e9 7;// 矩阵快速幂vectorvectorint POW(vectorvectorint a, int n){int m a.size();vectorvectorint res(m, vectorint(m));for(int i 0; i m; i) res[i][i] 1;while(n){if(n 1) res mul(res, a);a mul(a, a);n 1;}return res;}// 矩阵相乘vectorvectorint mul(const vectorvectorint a, const vectorvectorint b){int n a.size(), m b[0].size();vectorvectorint c(n, vectorint(m));for(int i 0; i n; i){for(int k 0; k n; k){if(a[i][k] 0) continue;for(int j 0; j m; j){c[i][j] (c[i][j] 1LL * a[i][k] * b[k][j]) % MOD;}}}return c;}
public:int lengthAfterTransformations(string s, int t) {int n s.size();vectorvectorint mtx(26, vectorint(26));for(int i 0; i 26; i){mtx[i][(i1)%26] 1;}mtx[25][1] 1;auto f POW(mtx, t); // 矩阵的t次幂vectorint cnt(26);for(auto e : s) cnt[e - a];long long ans 0;for(int i 0; i 26; i){ans reduce(f[i].begin(), f[i].end(), 0LL) * cnt[i];}return ans % MOD;}
};
三、最大公约数相等的子序列数量 对于每一个数都有三种可能要么在seq1要么在seq2要么不选一旦我们选择完一个数对于剩下的数我们依旧可以用相同的方法进行处理大问题被划分为一个个小问题进行解决。
设dfs(ijk)表示当seq1的gcdjseq2的gcdk时从前 i 个数中进行选择能得到的合法方案数
对于 nums[i]
1、不选方案数为 dfs(i-1jk)2、选入seq1方案数为 dfs(i-1gcd(jnums[i])k)3、选入seq2方案数为 dfs(i-1jgcd(knums[i]))
故状态转换方程为
dfs(ijk) dfs(i-1jk) dfs(i-1gcd(jnums[i])k) dfs(i-1jgcd(knums[i]))
边界条件当 i 0 时返回 j k表示将所有的数都进行分配后如果seq1的gcd seq2的gcd则为一种合法方案数
代码如下
class Solution {const int MOD 1e9 7;
public:int subsequencePairCount(vectorint nums) {int n nums.size();int memo[n][201][201];memset(memo, -1, sizeof(memo));functionint(int,int,int) dfs [](int i, int j, int k)-int{if(i 0) return j k;if(memo[i][j][k] ! -1) return memo[i][j][k];int res dfs(i - 1, j, k); // 不选res (res dfs(i - 1, gcd(j, nums[i]), k)) % MOD;res (res dfs(i - 1, j, gcd(k, nums[i]))) % MOD;return memo[i][j][k] res;};// 注意我们的dfs会包含一种seq1和seq2都为空的方案需要被减去// 由于取模操作 dfs(n - 1, 0, 0) - 1 可能为负数所以要 MOD) % MODreturn (dfs(n - 1, 0, 0) - 1 MOD) % MOD;}
};
四、字符串转换后的长度 II 这题的思路同第二题只是计算的矩阵不同具体代码如下
class Solution {const int MOD 1e9 7;// 矩阵快速幂vectorvectorint POW(vectorvectorint a, int n){int m a.size();vectorvectorint res(m, vectorint(m));for(int i 0; i m; i) res[i][i] 1;while(n){if(n 1) res mul(res, a);a mul(a, a);n 1;}return res;}// 矩阵相乘vectorvectorint mul(const vectorvectorint a, const vectorvectorint b){int n a.size(), m b[0].size();vectorvectorint c(n, vectorint(m));for(int i 0; i n; i){for(int k 0; k n; k){if(a[i][k] 0) continue;for(int j 0; j m; j){c[i][j] (c[i][j] 1LL * a[i][k] * b[k][j]) % MOD;}}}return c;}
public:int lengthAfterTransformations(string s, int t, vectorint nums) {int n s.size();vectorvectorint mtx(26, vectorint(26));for(int i 0; i 26; i){for(int j i 1; j i nums[i]; j){mtx[i][j%26] 1;}}auto f POW(mtx, t);vectorint cnt(26);for(auto e : s) cnt[e - a];long long ans 0;for(int i 0; i 26; i){ans reduce(f[i].begin(), f[i].end(), 0LL) * cnt[i];}return ans % MOD;}
};
