提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

LeetCode周赛324，官方的福利场，老梁点赞，非常推荐萌新一刷

2023-02-18 16:38:01 时间

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

今天是周一，我们来看下昨天的LeetCode周赛。

这一场是LeetCode周赛第324场，同样是LeetCode官方的福利场，提供极客防疫口罩以及LeetPoker等奖品。并且只要通过一题就可以获得LeetCode专属福利。

虽然是福利场，也有很多大佬都在评论区表示刷新了排名。但我个人做下来感觉这场的赛题还是有一定难度的，尤其是对于缺少解题技巧以及完整解题思维的新手来说。很多推导和思考不是那么顺理成章，可能会卡上一会。

但题目的质量我个人感觉是非常不错的，还挺适合初学者作为入门练习的，不论你是出于什么目的打开的LeetCode，都希望你能从本场的赛题当中获得乐趣。

统计相似字符串对的数目

给你一个下标从 0 开始的字符串数组 words 。

如果两个字符串由相同的字符组成，则认为这两个字符串 相似 。

  • 例如，"abca" 和 "cba" 相似，因为它们都由字符 'a'、'b'、'c' 组成。
  • 然而，"abacba" 和 "bcfd" 不相似，因为它们不是相同字符组成的。

请你找出满足字符串 words[i] 和 words[j] 相似的下标对 (i, j) ，并返回下标对的数目，其中 0 <= i < j <= word.length - 1 。

题解

周赛的第一题一般都是签到题，但今天这题值得好好说一说。

在本题当中我们要判断两个字符串的字符构成是否一样，比较容易想到可以使用set等数据结构进行去重。除此之外我们还可以使用bitmask的思想，利用int中的32个二进制位来表示26个英文字母是否出现过。很多新手可能不知道这种技巧，因此这里特别提一下。

首先，我们将二十六个字母转化成0-26的数字。接着使用位运算操作，1 << x表示将1左移x位，对应第x位二进制位为1的整数。我们在某个数上加上这个数就相当于将它的第x位标记成了1。

通过这个技巧，我们只需要使用整数就可以表示一个字符串的构成。那么我们在使用一个map来统计一下每个构成出现的次数，就可以很轻松地得到答案。

class Solution {
public:
    int similarPairs(vector<string>& words) {
        map<int, int> mp;
        for (auto & w: words) {
            // 将字符串构成转化成整数
            int tmp = 0;
            for (auto c : w) {
                tmp |= (1 << (c - 'a'));
            }
            mp[tmp]++;
        }
        int ret = 0;
        for (auto it : mp) {
            if (it.second > 1) {
                // 假设某一个构成出现x次，那么对应的字符串对数量为C(x, 2)，即x(x-1)/2
                ret += (it.second * (it.second - 1)) / 2;
            }
        }
        return ret;
    }
};

使用质因数之和替换后可以取到的最小值

给你一个正整数 n 。

请你将 n 的值替换为 n 的 质因数 之和，重复这一过程。

  • 注意，如果 n 能够被某个质因数多次整除，则在求和时，应当包含这个质因数同样次数。

返回 n 可以取到的最小值。

题解

我刚拿到这题的时候有一点懵，感觉这不像是第二题的难度，有一点出乎我意料。

这题当中有两个难点，第一个难点是质因数分解，在数学题当中这很容易，但是在编程里则困难很多。其次是本题的循环条件不明，我们无从确定按照题意进行质因数替换会不会陷入无限循环。对于一些萌新来说，可能会被唬住，他们可能会担心这样实现会不会陷入无限循环。

我们先来回答第二个问题，答案是不会。对于输入的

n

来说，首先很容易发现当

n

为质数时，它替换之后的结果为它自身。

我们假设它分解质因数之后的结果为

n = p_1^{k_1}*p_2^{k_2}\cdots p_m^{k_m}

。那么进行替换之后的下一个

n = \sum_{i=1}^m k_ip_i

。其中

p_i

是质数，也就是说大于2。我们知道在大于1的情况下，

mn > m+n

。所以必然有

\sum_{i=1}^m k_ip_i < p_1^{k_1}*p_2^{k_2}\cdots p_m^{k_m}

，也就是说随着我们的替换，这个数必然是递减的，直到某一次替换之后的结果为质数为止。

所以我们不用担心这样的替换操作会无限进行，它必然是有尽头的。其次是第一个问题，怎么进行质因数分解。这应该不是我们第一次遇到了，答案也很简单，我们可以使用埃拉托斯特尼筛法，也叫素数筛法来在

O(n)

的复杂度内筛选出范围内所有的素数。由于我用习惯了

O(n \log n)

的模板，所以我的代码可能也不是最快的，大家感兴趣可以网上搜索一下其他大佬讲解筛法的博客。

class Solution {
public:
    int smallestValue(int n) {
        vector<bool> is_prime(100050, 1);
        vector<int> prime;
        
        // 筛法，筛选出1e5范围内的所有素数
        const int N = 100001;
        for (int i = 2; i < N; i++) {
            if (is_prime[i]) {
                prime.push_back(i);
                for (int j = i * 2; j < N; j+=i) {
                    is_prime[j] = 0;
                }
            }
        }
        
        int ret = n;
        int tmp = 0;
        // n不再发生变化时退出
        while (true) {
            tmp = 0;
            // 记录之前的n
            int cur = n;
            while (n > 1) {
                for (auto x : prime) {
                    while (n % x == 0) {
                        n = n / x;
                        tmp += x;
                    }
                }
            }
            // 如果变化前后一样，则break
            if (cur == tmp) break;
            n = tmp;
            ret = min(ret, tmp);
        }
        return ret;
    }
};

添加边使所有节点度数都为偶数

给你一个有 n 个节点的 无向 图，节点编号为 1 到 n 。再给你整数 n 和一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条边。图不一定连通。

你可以给图中添加 至多 两条额外的边（也可以一条边都不添加），使得图中没有重边也没有自环。

如果添加额外的边后，可以使得图中所有点的度数都是偶数，返回 true ，否则返回 false 。

点的度数是连接一个点的边的数目。

题解

不知道多少同学被这题的几张图吓住的，其实这道题的题面有唬人的成分，对图论没有信心的萌新尤其容易被吓住。

为什么这么说呢，因为题目中说了至多添加两条额外的边要求图中所有点的度数为偶数。也就是说无非四种情况，第一种一条边不用添加，第二种添加一条边能满足题意，第三种添加两条边能满足题意，最后一种不能满足题意。

接着我们再来看看添加一条边意味着什么，如果有学过图论或者了解过数学里面七桥问题的同学应该对此很敏感。在图中添加一条边意味着会改变两个点的度数的奇偶性。这个也很直观，假设我们在(u, v)两个点之间加了一条边，那么它们的度数都增加了1，奇偶性同时发生变化。

到这里，应该就很清晰了，既然最终的目标是让所有的点的度数都是偶数，那么我们自然需要想办法把度数是奇数的点变成偶数。接着我们把所有点按照度数的奇偶性分成两组。奇数的一组，偶数的一组。我们尽量不动偶数的部分，只改变奇数的部分满足题意。

首先，如果奇数组内点的数量大于4，那么一定无解。因为我们最多只能加两条边，一条边最理想也就能让两个点从奇变偶。所以超过4个奇数点一定无解。其次，分析一下会发现一个或者三个奇数点也无解，因为一条边会同时改变两个点的奇偶性，不论怎么加，最终能改变的点的数量是偶数，所以无法让一个点或者三个点从奇变偶。

如此一来我们真正需要考虑的就只剩下了两个奇数点和四个奇数点的情况。

其中两个点的情况又非常简单，我们要做的就是想办法在它们之间连一条边。但我们不知道它们之间是否已经存在一条边了，如果没有边相连，那么我们直接加上一条边连通即可。注意，如果已经有边了，也并不意味着无解，因为还有一种方案是两个点都连接到第三个点上。这样这个点的度数增加了2，而它们的度数各增加了1，还是有解。所以我们还要判断一下是否能够找到一个这两个点都不连通的第三个点。

四个点的情况也类似，无非是四个点的配对组合会多一些，一共有3种。所以我们要枚举一下这三种组合，判断一下它们之间是否已经有边相连即可，只要有一种组合有解即为有解。

虽然最后写的代码量不少，但编码难度并不高。

class Solution {
public:
    bool isPossible(int n, vector<vector<int>>& edges) {
        // 邻接表建图
        vector<int> graph[n+1];
        for (auto &vt: edges) {
            int u = vt[0], v = vt[1];
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
        
        // 根据点的度数划分奇偶
        // 邻接表建图之后可以直接得到每个点的度数
        vector<int> even, odd;
        for (int i = 1; i <= n; i++) {
            if (graph[i].size() % 2) {
                odd.push_back(i);
            }else {
                even.push_back(i);
            }
        }
        
        if (odd.size() == 0) return true;
        if (odd.size() == 2) {
            int u = odd[0], v = odd[1];
            // 如果u和v不相连，返回true
            bool flag = true;
            for (auto x: graph[u]) if (x == v) flag = false;
            if (flag) return true;
            
            // 维护u和v所有连接的点
            set<int> nodes;
            for (auto x: graph[u]) nodes.insert(x);
            for (auto x: graph[v]) nodes.insert(x);
            
            nodes.insert(u);
            nodes.insert(v);
            
            // 如果存在一个点和u、v都不相连，则可以让u、v都连上
            return nodes.size() < n;
        }
        if (odd.size() == 4) {
            auto check_comb = [&](int u1, int u2, int v1, int v2) -> bool {
                u1 = odd[u1], u2 = odd[u2];
                v1 = odd[v1], v2 = odd[v2];
                // 判断u1-u2, v1-v2是否相连
                bool flag = true;
                for (auto x: graph[u1]) if (x == u2) return false;
                for (auto x: graph[v1]) if (x == v2) return false;
                return true;
            };
            return check_comb(0, 1, 2, 3) || check_comb(0, 2, 1, 3) || check_comb(0, 3, 1, 2);
        }
        return false;
    }
};

查询树中环的长度

给你一个整数 n ，表示你有一棵含有 2n - 1 个节点的 完全二叉树 。根节点的编号是 1 ，树中编号在[1, 2n - 1 - 1] 之间，编号为 val 的节点都有两个子节点，满足：

  • 左子节点的编号为 2 * val
  • 右子节点的编号为 2 * val + 1

给你一个长度为 m 的查询数组 queries ，它是一个二维整数数组，其中 queries[i] = [ai, bi] 。对于每个查询，求出以下问题的解：

  1. 在节点编号为 ai 和 bi 之间添加一条边。
  2. 求出图中环的长度。
  3. 删除节点编号为 ai 和 bi 之间新添加的边。

注意：

  • 环 是开始和结束于同一节点的一条路径，路径中每条边都只会被访问一次。
  • 环的长度是环中边的数目。
  • 在树中添加额外的边后，两个点之间可能会有多条边。

请你返回一个长度为 m 的数组 answer ，其中 answer[i] 是第 i 个查询的结果。

题解

这道题同样很唬人，看着就很复杂，但实际上题目内核并不难。

很容易想到对于query [a, b]来说，由于它们都是一棵完美二叉树上的点。那么a和b一定存在公共祖先，我们将ab相连得到的环，本质上就是它们到公共祖先的路径围成的。

所以我们要做的就是找到它们的公共祖先，计算一下路径长度再+1即可。

寻找公共祖先的方法也非常简单，我们从这两点出发往上遍历。根据完美二叉树的性质，从儿子节点遍历到父亲节点，只需要将序号除以2取整即可，这个步骤我们可以使用位运算右移一位来代替。

class Solution {
public:
    vector<int> cycleLengthQueries(int n, vector<vector<int>>& queries) {
        vector<int> ret;
        
        for (auto &q: queries) {
            int u = q[0], v = q[1];
            // 分别记录u、v的路径长度
            int l = 0, r = 0;
            while (u != v) {
                if (u > v) {
                    u = u >> 1;
                    l++;
                }else {
                    v = v >> 1;
                    r++;
                }
            }
            // 答案为l+r+1
            ret.push_back(l+r+1);
        }
        return ret;
    }
};

关于这一次周赛的赛题就聊到这里，不知道大家对于这场比赛感受怎样呢？

不论你有什么想法，都欢迎在评论区与我分享。

相关文章