【携程】20250313 携程笔试

1. 字符串 100%

2. 贪心+排序 100%

每次选择数字应该选择最大的数字，这样确保了在挑选的数字个数相同的情况下，挑选的数字中的最小值就会尽可能地大。

那么就先排序，依次选择最大的数字，然后遍历得到最大的结果

3. 素数筛+滑动窗口 100%

优化计算权值：先找到所有的质数（题目规定数字最大是 10^4），用埃氏素数筛优化，然后用所有的质数去找到所有数字的质因数，这样就减少了迭代的次数

优化计算子数组之和：滑动窗口法，计算区间内的权值之和，这样就得到了剩下数字的权值之和

4. 并查集 100%

其实就是找路径上所有节点都是偶数，那么他们的最大公因数肯定是偶数，至少是 2

这里我一开始使用递归的方式，递归每一种情况，结果超时了，对了 78%

后来我转念一想，既然权值为奇数的节点是不能继续递归下去的，那么相当于这棵树被权值为奇数的节点分成了很多个子树

每个子树的情况可以单独考虑：假设有一颗有 n 个节点的树（节点权值都是偶数），那么每个节点都能到达剩下的 n-1 个节点，也就是说，总共有 n*(n-1)/2+n 条唯一的路径（+n 是因为自己到自己也算路径）

这不就是并查集吗！

构建逻辑：如果两个节点相连，并且两个节点的权值都是偶数，那么就 Merge

计算每个子树路径数：只要在构建之后用哈希表获得 map<父节点（意指并查集节点的最高父节点），每个集合的大小>，然后判断最高父节点的权值是不是偶数，如果是奇数这就不是一个合法的子树，否则就让 res += (n*(n-1))/2 + n