6395. Buy Two Chocolates
给你一个整数数组 prices ，它表示一个商店里若干巧克力的价格。同时给你一个整数 money ，表示你一开始拥有的钱数。
你必须购买 恰好 两块巧克力，而且剩余的钱数必须是 非负数 。同时你想最小化购买两块巧克力的总花费。
请你返回在购买两块巧克力后，最多能剩下多少钱。如果购买任意两块巧克力都超过了你拥有的钱，请你返回 money 。注意剩余钱数必须是非负数。
测试样例
输入：prices = [1,2,2], money = 3
输出：0
解释：分别购买价格为 1 和 2 的巧克力。你剩下 3 - 3 = 0 块钱。所以我们返回 0 。
解答：这道题目就是寻找数组中最小的2个数。竞赛偷懒直接使用了排序。
class Solution {
public int buyChoco(int[] prices, int money) {
Arrays.sort(prices);
int min = prices[0] + prices[1];
if (min > money) {
return money;
} else {
return money - min;
}
}
}6394. Extra Characters in a String
给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串，每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。
请你采取最优策略分割 s ，使剩下的字符 最少 。
测试样例：
输入：s = "leetscode", dictionary = ["leet","code","leetcode"]
输出：1
解释：
将 s 分成两个子字符串：下标从 0 到 3 的 "leet" 和下标从 5 到 8 的 "code" 。只有 1 个字符没有使用（下标为 4），所以我们返回 1 。
解答: 没想到什么好的方法。这道题目我利用了TrieTree和动态规划。利用动态规划记录s的某个位置，剩下的最小字符数。利用TrieTree快速定位哪些序列出现在dictionary中。
class Solution {
private class TrieNode{
boolean isEnd;
Map<Character, TrieNode> next;
public TrieNode(){
isEnd = false;
next = new HashMap<>();
}
}
private TrieNode root;
private String s;
private Integer[] dp;
public int minExtraChar(String s, String[] dictionary) {
root = new TrieNode();
for (String d : dictionary) {
TrieNode tmp = root;
for (int i = 0; i < d.length(); ++i) {
char c = d.charAt(i);
if (!tmp.next.containsKey(c)) {
tmp.next.put(c, new TrieNode());
}
tmp = tmp.next.get(c);
}
tmp.isEnd = true;
}
this.dp = new Integer[s.length()];
this.s = s;
return helper(0);
}
private int helper(int p) {
if (p >= s.length()) {
return 0;
}
if (dp[p] == null) {
dp[p] = 1 + helper(p + 1);
TrieNode tmp = root;
for (int i = p; i < s.length(); ++i) {
char c = s.charAt(i);
if (!tmp.next.containsKey(c)) {
break;
}
tmp = tmp.next.get(c);
if (tmp.isEnd) {
dp[p] = Math.min(dp[p], helper(i + 1));
}
}
}
return dp[p];
}
}6393. Maximum Strength of a Group
给你一个下标从 0 开始的整数数组 nums ，它表示一个班级中所有学生在一次考试中的成绩。老师想选出一部分同学组成一个 非空 小组，且这个小组的 实力值 最大，如果这个小组里的学生下标为 i0, i1, i2, ... , ik ，那么这个小组的实力值定义为 nums[i0] nums[i1] nums[i2] ... nums[ik] 。
请你返回老师创建的小组能得到的最大实力值为多少。
测试样例：
输入：nums = [3,-1,-5,2,5,-9]
输出：1350
解答: 这道题目的范围实在过小：1 <= nums.length <= 13。直接利用状态压缩暴力运算就行了。
class Solution {
public long maxStrength(int[] nums) {
long max = Long.MIN_VALUE;
int right = 1 << nums.length;
for (int i = 1; i < right; ++i) {
long tmp = 1;
for (int j = 0; j < nums.length; ++j) {
int o = (i >> j) & 1;
if (o == 1) {
tmp *= nums[j];
}
}
max = Math.max(max, tmp);
}
return max;
}
}6464. Greatest Common Divisor Traversal
给你一个下标从 0 开始的整数数组 nums ，你可以在一些下标之间遍历。对于两个下标 i 和 j（i != j），当且仅当 gcd(nums[i], nums[j]) > 1 时，我们可以在两个下标之间通行，其中 gcd 是两个数的 最大公约数 。
你需要判断 nums 数组中 任意 两个满足 i < j 的下标 i 和 j ，是否存在若干次通行可以从 i 遍历到 j 。
如果任意满足条件的下标对都可以遍历，那么返回 true ，否则返回 false 。
测试样例：
输入：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 。
解答: 这道题目需要完成对数字的质因数分解。利用HashMap记录每个质数第一个碰到的位置。利用UnionFind可以查看2点之间是否可达。
class Solution {
private class DSU{
int[] parent;
public DSU(int N) {
parent = new int[N];
for (int i = 0; i < N; ++i) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
parent[find(x)] = find(y);
}
}
public boolean canTraverseAllPairs(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
DSU uf = new DSU(nums.length);
for (int i = 0; i < nums.length; ++i) {
int t = nums[i];
for (int j = 2; j * j <= t; ++j) {
while (t % j == 0) {
t /= j;
if (!map.containsKey(j)) {
map.put(j, i);
} else {
uf.union(map.get(j), i);
}
}
}
if (t != 1) {
if (!map.containsKey(t)) {
map.put(t, i);
} else {
uf.union(map.get(t), i);
}
}
}
int f = uf.find(0);
for (int i = 0; i < nums.length; ++i) {
if (uf.find(i) != f) {
return false;
}
}
return true;
}
}