5508. 数的平方等于两数乘积的方法数 #模拟 #哈希表
题目链接
题意
给你两个整数数组nums1 和 nums2 ，请你返回根据以下规则形成的三元组的数目（类型 1 和类型 2 ）：
- 类型 1：三元组
(i, j, k)，如果nums1[i]2 == nums2[j] * nums2[k]其中0 <= i < nums1.length且0 <= j < k < nums2.length - 类型 2：三元组
(i, j, k)，如果nums2[i]2 == nums1[j] * nums1[k]其中0 <= i < nums2.length且0 <= j < k < nums1.length
分析
由于两数组的长度不超过1e3，直接将两数组内部的所有组合都枚举下来，并将其乘积存到map中。最后两数组每个元素进行平方，检查该结果是否在map标记过，若标记过，便累加。
typedef long long ll;
class Solution {
public:
int numTriplets(vector<int>& nums1, vector<int>& nums2) {
unordered_map<ll, int> map1, map2;
for(int i = 0; i < nums1.size(); i++){
for(int j = i + 1; j < nums1.size(); j++){
ll cur = 1ll * nums1[i] * nums1[j];
map1[cur]++;
}
}
for(int i = 0; i < nums2.size(); i++){
for(int j = i + 1; j < nums2.size(); j++){
ll cur = 1ll * nums2[i] * nums2[j];
map2[cur]++;
}
}
int ans = 0;
for(int i = 0; i < nums1.size(); i++){
ll cur = 1ll * nums1[i] * nums1[i];
if(map2[cur]) ans += map2[cur];
}
for(int i = 0; i < nums2.size(); i++){
ll cur = 1ll * nums2[i] * nums2[i];
if(map1[cur]) ans += map1[cur];
}
return ans;
}
};
5509. 避免重复字母的最小删除成本 #贪心
题目链接
题意
给定字符串 s 和整数数组 cost ，其中 cost[i] 是从s 中删除字符 i 的代价。
现要求将字符串任意相邻两个字母不相同的最小删除成本。
分析
若有若干个重复的字符，我们只能保留其中一个。为保证代价最小，显然应该留下代价最大的。我们一趟遍历，实时检查当前字符是否与上一字符相等，如果相等，便累加代价、更新字符最大代价。当遇到不相等字符时，更新答案，重新计数重复次数。
class Solution {
public:
int minCost(string s, vector<int>& cost) {
char last = '#'; //记录上一字符
int mymax = cost[0]; //重复字符中代价最大
int cnt = 1; //记录某个字符的重复次数
int i = 0, sum = 0, len = s.length();
int tmpsum = 0; //累加重复字符的代价之和
while(i < len){
if(last == s[i]){ //说明当前字符与上一相邻字母重复
mymax = max(mymax, cost[i]);
tmpsum += cost[i];
cnt++;
}
else if(last != s[i]){
if(cnt > 1) sum += (tmpsum - mymax);
mymax = tmpsum = cost[i];
cnt = 1;
last = s[i];
}
i++; //O(n)
}
if(cnt > 1) sum += (tmpsum - mymax); //边界情况
return sum;
}
};
5510. 保证图可完全遍历 #并查集 #最小生成树
题目链接
题意
有一n阶无向图，并有三种类型的边：
-
类型 1：只能由 Alice 遍历。
-
类型 2：只能由 Bob 遍历。
-
类型 3：Alice 和 Bob 都可以遍历。
给定数组 edges ，其中edges[i] = [typei, ui, vi]，表示节点 ui 和 vi 之间存在类型为 typei 的双向边。请你在保证图仍能够被 Alice和 Bob 完全遍历的前提下，找出可以删除的最大边数。（如果从任何节点开始，Alice 和 Bob 都可以到达所有其他节点，则认为图是可以完全遍历的。）如果 Alice 和 Bob 无法完全遍历图，则返回 -1 。
样例
分析
如果同一子集用公共边（对应类型3的边）就能够走完，那么同一子集中无需使用Alice或Bob的特殊边（对应类型1/2的边），删除公共边造成的影响会比删除特殊边更大。我们暂时只考虑类型3的边，利用并查集，构建一棵类型3组成的最小生成森林，此处之所以说是森林，是因为单凭类型3的边不能保证整个图是连通的。在搭建森林时，我们就已经将多余的类型3的边去除掉，只保留最少的类型3的边，因而在并查集合并时需要统计下合并的边数量tree3。
接下来我们要分别保证Alice和Bob能够完全遍历。即在原有的类型3的最小生成森林中，用类型2的边构建最小生成树，统计需要合并的类型2的边数量tree2，从而保证Bob在不多余边的情况下完全遍历；同理，原有的类型3的最小生成森林中构建类型1的边构建最小生成树，统计类型1的边tree1。最后计算edges.size() - (tree1 + tree2 + tree3)，统计最终要删除的边数总和
class Solution {
private:
int fa1[100005] = {0}, fa2[100005] = {0};
public:
int findSet(int x, int fa[]){
if(x != fa[x]) fa[x] = findSet(fa[x], fa);
return fa[x];
}
void Union(int x, int y, int fa[]){
fa[y] = x;
}
int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
int tree3 = 0, tree2 = 0, tree1 = 0;
for(int i = 1; i <= n; i++) fa1[i] = fa2[i] = i;
for(int i = 0; i < edges.size(); i++){
if(edges[i][0] != 3) continue;
int u = edges[i][1], v = edges[i][2];
int pu = findSet(u, fa1), pv = findSet(v, fa1);
if(pu != pv){
tree3++; Union(pu, pv, fa1);
}
}
for(int i = 1; i <= n; i++) fa2[i] = fa1[i];
for(int i = 0; i < edges.size(); i++){
if(edges[i][0] != 1) continue;
int u = edges[i][1], v = edges[i][2];
int pu = findSet(u, fa1), pv = findSet(v, fa1);
if(pu != pv){
tree1++; Union(pu, pv, fa1);
}
}
for(int i = 0; i < edges.size(); i++){
if(edges[i][0] != 2) continue;
int u = edges[i][1], v = edges[i][2];
int pu = findSet(u, fa2), pv = findSet(v, fa2);
if(pu != pv){
tree2++; Union(pu, pv, fa2);
}
}
int cnt1 = 0, cnt2 = 0;
for(int i = 1; i <= n; i++) {
if(fa1[i] == i) cnt1++;
if(fa2[i] == i) cnt2++;
}
if(cnt1 != 1 || cnt2 != 1) return -1;
return edges.size() - (tree1 + tree2 + tree3);
}
};