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标记过，若标记过，便累加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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 的代价。

现要求将字符串任意相邻两个字母不相同的最小删除成本。

分析

若有若干个重复的字符，我们只能保留其中一个。为保证代价最小，显然应该留下代价最大的。我们一趟遍历，实时检查当前字符是否与上一字符相等，如果相等，便累加代价、更新字符最大代价。当遇到不相等字符时，更新答案，重新计数重复次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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)，统计最终要删除的边数总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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);
    }
};