力扣第157场双周赛

1. 最大质数子字符串之和

给定一个字符串 s，找出可以由其 子字符串 组成的 3个最大的不同质数 的和。

返回这些质数的 总和 ，如果少于 3 个不同的质数，则返回 所有 不同质数的和。

质数是大于 1 且只有两个因数的自然数：1和它本身。

子字符串 是字符串中的一个连续字符序列。 

注意：每个质数即使出现在 多个 子字符串中，也只能计算 一次 。此外，将子字符串转换为整数时，忽略任何前导零。

示例 1：

输入： s = "12234"

输出： 1469

解释：

由 "12234" 的子字符串形成的不同质数为 2 ，3 ，23 ，223 和 1223。
最大的 3 个质数是 1223、223 和 23。它们的和是 1469。
示例 2：

输入： s = "111"

输出： 11

解释：

由 "111" 的子字符串形成的不同质数是 11。
由于只有一个质数，所以结果是 11。
 

提示：

1 <= s.length <= 10
s 仅由数字组成。 

解题思路：字符串的长度只有10，注意字符串转 int -> [-10^9,10^9]时会超, 其他就是简单模拟即可

class Solution {
public:bool solve(long long num){if(num<2) return false;for(long long i=2;i*i<=num;i++){if(num%i==0) return false;}return true;}long long sumOfLargestPrimes(string s) {set<long long> a;int n=s.size();for(int i=0;i<n;i++){string tmp="";for(int j=i;j<n;j++){tmp+=s[j];         long long v=stoll(tmp);if(solve(v)){a.insert(v);}}}vector<long long> b(a.begin(),a.end()); sort(b.begin(),b.end()); int n_b=b.size(); long long sum=0;if(n_b>=3) return b[n_b-1]+b[n_b-2]+b[n_b-3];else{sum=accumulate(b.begin(),b.end(),0LL);}return sum;}
};

 2. 不相交子字符串的最大数量

给你一个字符串 word。

返回以 首尾字母相同 且 长度至少为 4 的 不相交子字符串 的最大数量。

子字符串 是字符串中连续的 非空 字符序列。

 

示例 1：

输入： word = "abcdeafdef"

输出： 2

解释：

两个子字符串是 "abcdea" 和 "fdef"。

示例 2：

输入： word = "bcdaaaab"

输出： 1

解释：

唯一的子字符串是 "aaaa"。注意我们 不能 同时选择 "bcdaaaab"，因为它和另一个子字符串有重叠。

 

提示：

1 <= word.length <= 2 * 10^5
word 仅由小写英文字母组成。

解题思路：

f[i]=max(f[i-1],f[j-1]+1)
f(i): 从前i个字符中最多能选出多少个符合条件的子串 

class Solution {
public:int maxSubstrings(string word) {int n=word.size();vector<int> pre(26),a(n+1);for(int i=1;i<=n;i++){a[i]=pre[word[i-1]-'a'];pre[word[i-1]-'a']=i;}vector<int> f(n+1);f[0]=0;for(int i=1;i<=n;i++){f[i]=f[i-1];int j=a[i];while(j>0&&i-j<3) j=a[j];if(j>0){f[i]=max(f[i],f[j-1]+1);}}return f[n];}
};

 3. 给边赋权值的方案数 I

给你一棵 n 个节点的无向树，节点从 1 到 n 编号，树以节点 1 为根。树由一个长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示在节点 ui 和 vi 之间有一条边。
一开始，所有边的权重为 0。你可以将每条边的权重设为 1 或 2。

两个节点 u 和 v 之间路径的 代价 是连接它们路径上所有边的权重之和。

选择任意一个 深度最大 的节点 x。返回从节点 1 到 x 的路径中，边权重之和为 奇数 的赋值方式数量。

由于答案可能很大，返回它对 10^9 + 7 取模的结果。

注意： 忽略从节点 1 到节点 x 的路径外的所有边。

解题思路： 每条边的边权只能是1或者2，保证边上的边权和是奇数，保证有奇数个1即可，

实现上我们先求出最大深度x, 然后从x条边种选出1,3,5个1，其他为2

然后我们套用组合数公式Cn1+Cn3+...=2^(n-1) 

class Solution {
public:int mx=0;const int M=1e9+7; vector<vector<int>> g; void dfs(int i, int fa , int d){for(int x: g[i]){if(x!=fa){dfs(x,i,d+1);}}  mx=max(mx,d);}int assignEdgeWeights(vector<vector<int>>& edges){int n=edges.size()+1;g.resize(n+1);for(int i=0;i<n-1;i++){int x=edges[i][0],y=edges[i][1];g[x].push_back(y); g[y].push_back(x);}vector<int> p(n+1);p[0]=1;for(int i=1;i<=n;i++) p[i]=p[i-1]*2%M;dfs(1,0,0);return p[mx-1];}
};

 4. 给边赋权值的方案数 II

给你一棵有 n 个节点的无向树，节点从 1 到 n 编号，树以节点 1 为根。树由一个长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示在节点 ui 和 vi 之间有一条边。

一开始，所有边的权重为 0。你可以将每条边的权重设为 1 或 2。

两个节点 u 和 v 之间路径的 代价 是连接它们路径上所有边的权重之和。

给定一个二维整数数组 queries。对于每个 queries[i] = [ui, vi]，计算从节点 ui 到 vi 的路径中，使得路径代价为 奇数 的权重分配方式数量。

返回一个数组 answer，其中 answer[i] 表示第 i 个查询的合法赋值方式数量。

由于答案可能很大，请对每个 answer[i] 取模 10^9 + 7。

注意： 对于每个查询，仅考虑 ui 到 vi 路径上的边，忽略其他边。

解题思路：相比上题多了一个query的操作，变成ui -> vi 的路径权重和为奇数的方案数, 和上场周赛最后一题(可以直接点开我主页力扣栏查看即可), 类似,  

注：到底是比赛谁套个板子, 还有脸发到某站当比赛实录啊

const int M=1e9+7;
class LCA_solve {
public:vector<int> depth, to_root_minD;vector<vector<int>> pa;LCA_solve(vector<vector<int>>& edges) {int n = edges.size() + 1;int m = bit_width(edges.size() + 1); vector<vector<int>> g(n);for (auto& e : edges) {int x = e[0]-1, y = e[1]-1;g[x].push_back(y);g[y].push_back(x);}depth.resize(n);pa.resize(n, vector<int>(m, -1));auto dfs = [&](this auto&& dfs, int x, int fa) -> void {pa[x][0] = fa;for (auto& y : g[x]) {if (y != fa) {depth[y] = depth[x] + 1;dfs(y, x);}}};dfs(0, -1);for (int i = 0; i < m - 1; i++) {for (int x = 0; x < n; x++) {if (int p = pa[x][i]; p != -1) {pa[x][i + 1] = pa[p][i];}}}}int get_kth_ancestor(int node, int k) {for (; k; k &= k - 1) {node = pa[node][countr_zero((unsigned)k)];}return node;}int get_lca(int x, int y) {if (depth[x] > depth[y]) {swap(x, y);}y = get_kth_ancestor(y, depth[y] - depth[x]);if (y == x) {return x;}for (int i = pa[x].size() - 1; i >= 0; i--) {int px = pa[x][i], py = pa[y][i];if (px != py) {x = px;y = py;}}return pa[x][0];}int twoPoits_dis(int x, int y) {return depth[x] + depth[y] - depth[get_lca(x, y)] * 2;}
};
class Solution {
public:vector<int> assignEdgeWeights(vector<vector<int>>& edges, vector<vector<int>>& queries) {int n=edges.size(); vector<int> p(n+1);p[0]=1;for(int i=1;i<=n;i++) p[i]=p[i-1]*2%M;LCA_solve g(edges);vector<int> ans(queries.size());for (int i=0;i<queries.size();i++) {int x=queries[i][0]-1;int y=queries[i][1]-1;if (x!=y){ans[i]=p[g.twoPoits_dis(x, y) - 1];}}return ans;}
};

感谢大家的点赞和关注，你们的支持是我创作的动力！(其他细节，有时间再补充...)