6307. Pass the Pillow
n 个人站成一排，按从 1 到 n 编号。
最初，排在队首的第一个人拿着一个枕头。每秒钟，拿着枕头的人会将枕头传递给队伍中的下一个人。一旦枕头到达队首或队尾，传递方向就会改变，队伍会继续沿相反方向传递枕头。
- 例如，当枕头到达第 n 个人时，TA 会将枕头传递给第 n - 1 个人，然后传递给第 n - 2 个人，依此类推。
给你两个正整数 n 和 time ，返回 time 秒后拿着枕头的人的编号。
测试样例
输入：n = 4, time = 5
输出：2
解释：
队伍中枕头的传递情况为：1 -> 2 -> 3 -> 4 -> 3 -> 2 。
5 秒后，枕头传递到第 2 个人手中。
解答：存在提示：1 <= time <= 1000，直接暴力计算即可
class Solution {
public int passThePillow(int n, int time) {
int cur = 1, dir = 1;
for (int i = 0; i < time; ++i) {
if (cur + dir > n) {
dir = -1;
} else if (cur + dir <= 0) {
dir = 1;
}
cur += dir;
}
return cur;
}
}6308. Kth Largest Sum in a Binary Tree
给你一棵二叉树的根节点 root 和一个正整数 k 。
树中的 层和 是指 同一层 上节点值的总和。
返回树中第 k 大的层和（不一定不同）。如果树少于 k 层，则返回 -1 。
注意，如果两个节点与根节点的距离相同，则认为它们在同一层。
测试样例：
输入：root = [5,8,9,2,1,3,7,4,6], k = 2
输出：13
解答: 层次遍历，然后优先队列排序就能获得答案
class Solution {
public long kthLargestLevelSum(TreeNode root, int k) {
PriorityQueue<Long> queue = new PriorityQueue<>();
List<TreeNode> level = new ArrayList<>();
level.add(root);
while (!level.isEmpty()) {
List<TreeNode> nextLevel = new ArrayList<>();
long sum = 0;
for (TreeNode n : level) {
sum += n.val;
if (n.left != null) {
nextLevel.add(n.left);
}
if (n.right != null) {
nextLevel.add(n.right);
}
}
queue.add(sum);
if (queue.size() > k) {
queue.poll();
}
level = nextLevel;
}
return queue.size() == k ? queue.poll() : -1;
}
}6309. Split the Array to Make Coprime Products
给你一个长度为 n 的整数数组 nums ，下标从 0 开始。
如果在下标 i 处 分割 数组，其中 0 <= i <= n - 2 ，使前 i + 1 个元素的乘积和剩余元素的乘积互质，则认为该分割 有效 。
- 例如，如果 nums = [2, 3, 3] ，那么在下标 i = 0 处的分割有效，因为 2 和 9 互质，而在下标 i = 1 处的分割无效，因为 6 和 3 不互质。在下标 i = 2 处的分割也无效，因为 i == n - 1 。
返回可以有效分割数组的最小下标 i ，如果不存在有效分割，则返回 -1 。
当且仅当 gcd(val1, val2) == 1 成立时，val1 和 val2 这两个值才是互质的，其中 gcd(val1, val2) 表示 val1 和 val2 的最大公约数。
测试样例
输入：nums = [4,7,8,15,3,5]
输出：2
解释：
上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。
唯一一个有效分割位于下标 2 。
解答：这道题目不能直接暴力乘法，然后利用gcd计算。乘法很容易导致结果超过long或者int上限。
这道题目考察的是区间融合。如果质数分解之后，一个质数覆盖的范围和另一个质数有重叠，就需要融合。
还需要考虑一些特殊情况。如果n=1, 那么返回-1。还有开头和结尾存在1的情况。
class Solution {
public int findValidSplit(int[] nums) {
Map<Integer, List<Integer>> primes = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
int tmp = nums[i];
for (int n = 2; n * n <= tmp; ++n) {
if (tmp % n == 0) {
if (!primes.containsKey(n)) {
primes.put(n, new ArrayList<>());
}
primes.get(n).add(i);
}
while (tmp % n == 0) {
tmp /= n;
}
}
if (tmp != 1) {
if (!primes.containsKey(tmp)) {
primes.put(tmp, new ArrayList<>());
}
primes.get(tmp).add(i);
}
}
List<List<Integer>> primeLoc = new ArrayList<>();
for (Map.Entry<Integer, List<Integer>> kv : primes.entrySet()) {
primeLoc.add(kv.getValue());
}
Collections.sort(primeLoc, (a, b) -> (a.get(0).compareTo(b.get(0))));
int max = 0;
for (List<Integer> l : primeLoc) {
if (l.get(0) > max) {
return max;
} else {
max = Math.max(max, l.get(l.size() - 1));
}
}
return max < nums.length - 1 ? max : -1;
}
}6310. Number of Ways to Earn Points
考试中有 n 种类型的题目。给你一个整数 target 和一个下标从 0 开始的二维整数数组 types ，其中 types[i] = [counti, marksi] 表示第 i 种类型的题目有 counti 道，每道题目对应 marksi 分。
返回你在考试中恰好得到 target 分的方法数。由于答案可能很大，结果需要对 10^9 +7 取余。
注意，同类型题目无法区分。
比如说，如果有 3 道同类型题目，那么解答第 1 和第 2 道题目与解答第 1 和第 3 道题目或者第 2 和第 3 道题目是相同的。
测试样例
输入：target = 6, types = [[6,1],[3,2],[2,3]]
输出：7
解释：
要获得 6 分，你可以选择以下七种方法之一：
- 解决 6 道第 0 种类型的题目：1 + 1 + 1 + 1 + 1 + 1 = 6
- 解决 4 道第 0 种类型的题目和 1 道第 1 种类型的题目：1 + 1 + 1 + 1 + 2 = 6
- 解决 2 道第 0 种类型的题目和 2 道第 1 种类型的题目：1 + 1 + 2 + 2 = 6
- 解决 3 道第 0 种类型的题目和 1 道第 2 种类型的题目：1 + 1 + 1 + 3 = 6
- 解决 1 道第 0 种类型的题目、1 道第 1 种类型的题目和 1 道第 2 种类型的题目：1 + 2 + 3 = 6
- 解决 3 道第 1 种类型的题目：2 + 2 + 2 = 6
- 解决 2 道第 2 种类型的题目：3 + 3 = 6
解答：利用动态规划可以获得结果。注意不要乱用动态规划，导致从组合变成排列的情况。
class Solution {
private static final int mod = 1_000_000_007;
public int waysToReachTarget(int target, int[][] types) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int[] t : types) {
int[] tmp = duplicate(dp);
for (int i = 0; i < t[0]; ++i) {
int[] next = new int[target + 1];
for (int j = target; j >= t[1]; --j) {
next[j] = tmp[j - t[1]];
dp[j] = (dp[j] + next[j]) % mod;
}
tmp = next;
}
}
return dp[target];
}
private int[] duplicate(int[] dp) {
int[] res = new int[dp.length];
for (int i = 0; i < dp.length; ++i) {
res[i] = dp[i];
}
return res;
}
}