leetcode biweekly contes 105 比较蛋疼的题目，各种 corn case 太恶心了，t3 竟然给了那么少的数目，太想吐槽了。
6395. 购买两块巧克力 给你一个整数数组 prices ，它表示一个商店里若干巧克力的价格。同时给你一个整数 money ，表示你一开始拥有的钱数。
你必须购买 恰好 两块巧克力，而且剩余的钱数必须是 非负数 。同时你想最小化购买两块巧克力的总花费。
请你返回在购买两块巧克力后，最多能剩下多少钱。如果购买任意两块巧克力都超过了你拥有的钱，请你返回 money 。注意剩余钱数必须是非负数。
示例 1：
输入：prices = [1,2,2], money = 3 输出：0 解释：分别购买价格为 1 和 2 的巧克力。你剩下 3 - 3 = 0 块钱。所以我们返回 0 。
示例 2：
输入：prices = [3,2,3], money = 3 输出：3 解释：购买任意 2 块巧克力都会超过你拥有的钱数，所以我们返回 3 。
提示：
2 <= prices.length <= 501 <= prices[i] <= 1001 <= money <= 100
地址 https://leetcode.cn/contest/biweekly-contest-105/problems/buy-two-chocolates/
题意 排序
思路
直接取最小的两个值即可，比较最小两个值之和与 money 的之间的关系即可
复杂度分析：
时间复杂度：$O(n \log n)$，$n$ 表示数组的长度。
空间复杂度：$O(\log n)$, $n$ 表示数组的长度。
代码 class Solution {public : int buyChoco (vector<int >& prices, int money) sort (prices.begin (), prices.end ()); int tot = prices[0 ] + prices[1 ]; if (money >= tot) { return money - tot; } return money; } };
6394. 字符串中的额外字符 给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串，每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。
请你采取最优策略分割 s ，使剩下的字符 最少 。
示例 1：
输入：s = "leetscode", dictionary = ["leet","code","leetcode"] 输出：1 解释：将 s 分成两个子字符串：下标从 0 到 3 的 "leet" 和下标从 5 到 8 的 "code" 。只有 1 个字符没有使用（下标为 4），所以我们返回 1 。
示例 2：
输入：s = "sayhelloworld", dictionary = ["hello","world"] 输出：3 解释：将 s 分成两个子字符串：下标从 3 到 7 的 "hello" 和下标从 8 到 12 的 "world" 。下标为 0 ，1 和 2 的字符没有使用，所以我们返回 3 。
提示：
1 <= s.length <= 501 <= dictionary.length <= 501 <= dictionary[i].length <= 50dictionary[i] 和 s 只包含小写英文字母。dictionary 中的单词互不相同。
地址 https://leetcode.cn/contest/weekly-contest-346/problems/lexicographically-smallest-palindrome/
题意 动态规划
思路
简单题目即可，设 $dp[i]$ 表示前 $i$ 个字符进行有效分割后剩余的最少字符数目，此时可以得到如下递推公式：
如果当前的子串 $s[j\cdots i]$ 可以被分割，此时可以知道 $dp[i] = \min(dp[i], dp[j - 1])$;
如果当前不存在任何的以 $i$ 为结尾的子串进行分割，此时 $s[i]$ 肯定被剩下，可以得到 $dp[i] = dp[i - 1] + 1$；
依次按照上述的递推关系进行检测，即可得到整个字符串剩余的字符的最小值；
复杂度分析：
时间复杂度：$O(n^2 \times m)$，其中 $n$ 为字符串 $s$ 的长度, $m$ 表示给定字典的最大长度。
空间复杂度：$O(Cm)$。
代码 class Solution {public : int minExtraChar (string s, vector<string>& dictionary) int n = s.size (); unordered_set<string> cnt (dictionary.begin(), dictionary.end()) ; vector<int > dp (n + 1 , INT_MAX) ; dp[0 ] = 0 ; for (int i = 1 ; i <= n; i++) { dp[i] = dp[i - 1 ] + 1 ; for (int j = 1 ; j <= i; j++) { if (cnt.count (s.substr (i - j, j))) { dp[i] = min (dp[i], dp[i - j]); } } } return dp[n]; } };
6393. 一个小组的最大实力值 给你一个下标从 0 开始的整数数组 nums ，它表示一个班级中所有学生在一次考试中的成绩。老师想选出一部分同学组成一个 非空 小组，且这个小组的 实力值 最大，如果这个小组里的学生下标为 i0, i1, i2, … , ik ，那么这个小组的实力值定义为 nums[i0] * nums[i1] * nums[i2] * ... * nums[ik] 。
请你返回老师创建的小组能得到的最大实力值为多少。
示例 1：
输入：nums = [3,-1,-5,2,5,-9] 输出：1350 解释：一种构成最大实力值小组的方案是选择下标为 [0,2,3,4,5] 的学生。实力值为 3 * (-5) * 2 * 5 * (-9) = 1350 ，这是可以得到的最大实力值。
示例 2：
输入：nums = [-4,-5,-4] 输出：20 解释：选择下标为 [0, 1] 的学生。得到的实力值为 20 。我们没法得到更大的实力值。
提示：
1 <= nums.length <= 13-9 <= nums[i] <= 9
地址 https://leetcode.cn/contest/biweekly-contest-105/problems/maximum-strength-of-a-group/
题意
贪心
思路
题目给的数据太少了，直接暴力完全可以搞定，也可以用贪心解法来面对；
所有的整数全部取，负数只取偶数个最小的负数；
如果全部为 $0$ 或者 只有一个负数其余全部为 $0$，则直接返回 $0$;
如果只有一个数且为负数，则只能返回该负数；
复杂度分析：
时间复杂度：$O(n \log n)$，其中 $n$ 为数组的长度, 实际时间复杂度可以优化到 $n$；
空间复杂度：$O(n)$，其中 $n$ 为数组的长度；
代码 class Solution {public : long long maxStrength (vector<int >& nums) vector<int > neg; long long ans = 1 ; int n = nums.size (); int zero = 0 ; for (auto v : nums) { if (v > 0 ) { ans = ans * v; } else if (v < 0 ) { neg.emplace_back (v); } else { zero++; } } if (n == 1 ) { return nums[0 ]; } if (zero == n || (zero == n - 1 && neg.size () == 1 )) { return 0 ; } sort (neg.begin (), neg.end ()); if (neg.size () % 2 == 0 ) { for (auto v : neg) { ans = ans * v; } } else { for (int i = 0 ; i < neg.size () - 1 ; i++) { ans = ans * neg[i]; } } return ans; } };
6464. 最大公约数遍历 给你一个下标从 0 开始的整数数组 nums ，你可以在一些下标之间遍历。对于两个下标 i 和 j（i != j），当且仅当 gcd(nums[i], nums[j]) > 1 时，我们可以在两个下标之间通行，其中 gcd 是两个数的 最大公约数 。
你需要判断 nums 数组中 任意 两个满足 i < j 的下标 i 和 j ，是否存在若干次通行可以从 i 遍历到 j 。
如果任意满足条件的下标对都可以遍历，那么返回 true ，否则返回 false 。
示例 1：
输入：nums = [2,3,6] 输出：true 解释：这个例子中，总共有 3 个下标对：(0, 1) ，(0, 2) 和 (1, 2) 。 从下标 0 到下标 1 ，我们可以遍历 0 -> 2 -> 1 ，我们可以从下标 0 到 2 是因为 gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1 ，从下标 2 到 1 是因为 gcd(nums[2], nums[1]) = gcd(6, 3) = 3 > 1 。 从下标 0 到下标 2 ，我们可以直接遍历，因为 gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1 。同理，我们也可以从下标 1 到 2 因为 gcd(nums[1], nums[2]) = gcd(3, 6) = 3 > 1 。
示例 2：
输入：nums = [3,9,5] 输出：false 解释：我们没法从下标 0 到 2 ，所以返回 false 。
示例 3：
输入：nums = [4,3,12,8] 输出：true 解释：总共有 6 个下标对：(0, 1) ，(0, 2) ，(0, 3) ，(1, 2) ，(1, 3) 和 (2, 3) 。所有下标对之间都存在可行的遍历，所以返回 true 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 105
地址 https://leetcode.cn/contest/weekly-contest-346/problems/modify-graph-edge-weights/
题意
并查集
思路
拿到这个题目第一想到的就是并查集，即如果两个数 $nums[i], nums[j]$ 满足 $\gcd(nums[i],nums[j]) > 1$ 时，此时可以将 $i,j$ 看成存在一条边连接，我们可以采用欧拉素数筛查的办法，如果两个数存在相同的质因子则我们将其进行合并；
模仿欧拉线性筛选质数的方法，每次筛选时，将数组中含有相同质因子的数进行合并即可；
最终我们检测是否数组中所有的元素都在一个集合中；
比较坑的是最后一个 case, 竟然出现了单个数 $[1]$ 也算是连通，想了好久才过了这个 case;
复杂度分析：
时间复杂度：$O((U + n)\alpha(n))$，其中 $n$ 为给定的数组的长度,$U$ 表示数组中的最大值;
空间复杂度：$O(U)$，其中 $U$ 为给定的数组中的最大值；
代码 class UnionFind {public : UnionFind (int n) { parent = vector <int >(n); rank = vector <int >(n); sz = vector <int >(n); for (int i = 0 ; i < n; i++) { parent[i] = i; sz[i] = 1 ; } } void uni (int x, int y) int rootx = find (x); int rooty = find (y); if (rootx != rooty) { if (rank[rootx] > rank[rooty]) { parent[rooty] = rootx; sz[rootx] += sz[rooty]; } else if (rank[rootx] < rank[rooty]) { parent[rootx] = rooty; sz[rooty] += sz[rootx]; } else { parent[rooty] = rootx; rank[rootx]++; sz[rootx] += sz[rooty]; } } } int find (int x) if (parent[x] != x) { parent[x] = find (parent[x]); } return parent[x]; } int size (int x) return sz[find (x)]; } bool connect (int x, int y) return find (x) == find (y); } private : vector<int > parent; vector<int > rank; vector<int > sz; }; class Solution {public : bool canTraverseAllPairs (vector<int >& nums) sort (nums.begin (), nums.end ()); int maxVal = *max_element (nums.begin (), nums.end ()); int n = nums.size (); UnionFind uf (n) ; vector<bool > vis (maxVal + 1 , false ) ; vector<vector<int >> arr (maxVal + 1 ); if (n == 1 ) { return true ; } for (int i = 0 ; i < nums.size (); i++) { if (nums[i] == 1 ) return false ; arr[nums[i]].emplace_back (i); } for (int i = 2 ; i <= maxVal; i++) { if (!vis[i]) { vector<int > curr; for (int j = i; j <= maxVal; j += i) { for (auto v : arr[j]) { curr.emplace_back (v); } vis[j] = true ; } if (curr.size () > 1 ) { int x = curr[0 ]; for (auto v : curr) { uf.uni (x, v); } } } } int tot = uf.size (uf.find (0 )); return tot == n; } };
欢迎关注和打赏，感谢支持！
