2582. 递枕头
n 个人站成一排，按从 1 到 n 编号。
最初，排在队首的第一个人拿着一个枕头。每秒钟，拿着枕头的人会将枕头传递给队伍中的下一个人。一旦枕头到达队首或队尾，传递方向就会改变，队伍会继续沿相反方向传递枕头。
例如，当枕头到达第 n 个人时，TA 会将枕头传递给第 n - 1 个人，然后传递给第 n - 2 个人，依此类推。
给你两个正整数 n 和 time ，返回 time 秒后拿着枕头的人的编号。
示例 1：
输入：n = 4, time = 5
输出：2
解释：队伍中枕头的传递情况为：1 -> 2 -> 3 -> 4 -> 3 -> 2 。
5 秒后，枕头传递到第 2 个人手中。
示例 2：
输入：n = 3, time = 2
输出：3
解释：队伍中枕头的传递情况为：1 -> 2 -> 3 。
2 秒后，枕头传递到第 3 个人手中。
提示：
2 <= n <= 1000
1 <= time <= 1000解答：
class Solution {
public int passThePillow(int n, int time) {
// 定义变量记录当前拿着枕头的人的编号，初始值为 1，代表队首
int curr = 1;
// 定义变量记录枕头传递的方向，初始值为 1，代表向右传递
int direction = 1;
// 模拟枕头传递的过程
for (int i = 1; i <= time; i++) {
// 如果当前拿着枕头的人在队尾，需要改变传递方向
if (curr == n) {
direction = -1;
}
// 如果当前拿着枕头的人在队首，需要改变传递方向
if (curr == 1) {
direction = 1;
}
// 更新拿着枕头的人的编号
curr += direction;
}
// 返回拿着枕头的人的编号
return curr;
}
}
2583. 二叉树中的第 K 大层和
给你一棵二叉树的根节点 root 和一个正整数 k 。
树中的 层和 是指 同一层 上节点值的总和。
返回树中第 k 大的层和（不一定不同）。如果树少于 k 层，则返回 -1 。
注意，如果两个节点与根节点的距离相同，则认为它们在同一层。
示例 1：
输入：root = [5,8,9,2,1,3,7,4,6], k = 2
输出：13
解释：树中每一层的层和分别是：
- Level 1: 5
- Level 2: 8 + 9 = 17
- Level 3: 2 + 1 + 3 + 7 = 13
- Level 4: 4 + 6 = 10
第 2 大的层和等于 13 。
示例 2：
输入：root = [1,2,null,3], k = 1
输出：3
解释：最大的层和是 3 。
提示：
树中的节点数为 n
2 <= n <= 10^5
1 <= Node.val <= 10^6
1 <= k <= n解答：哈希表+dfs
class Solution {
int maxLevel = 0;
public long kthLargestLevelSum(TreeNode root, int k) {
if (root == null) {
return -1;
}
// 使用哈希表存储每个层的节点值的总和
Map<Integer, Long> map = new HashMap<>();
dfs(root, 1, map);
// 将哈希表中的值存储到列表中并排序
List<Long> list = new ArrayList<>(map.values());
Collections.sort(list, Collections.reverseOrder());
// 返回第k大的值，如果树少于k层则返回-1
return list.size() >= k ? list.get(k - 1) : -1L;
}
private void dfs(TreeNode node, int level, Map<Integer, Long> map) {
if (node == null) {
return;
}
// 更新当前层的节点值的总和
long sum = map.getOrDefault(level, 0L);
map.put(level, sum + node.val);
maxLevel = Math.max(maxLevel, level);
// 递归处理左右子树
dfs(node.left, level + 1, map);
dfs(node.right, level + 1, map);
}
}2584. 分割数组使乘积互质
给你一个长度为 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 的最大公约数。
示例 1：
输入：nums = [4,7,8,15,3,5]
输出：2
解释：上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。
唯一一个有效分割位于下标 2 。
示例 2：
输入：nums = [4,7,15,8,3,5]
输出：-1
解释：上表展示了每个下标 i 处的前 i + 1 个元素的乘积、剩余元素的乘积和它们的最大公约数的值。
不存在有效分割。
提示：
n == nums.length
1 <= n <= 10^4
1 <= nums[i] <= 10^6解答：质因子分解
class Solution {
public int findValidSplit(int[] nums) {
int n = nums.length;
var left = new HashMap<Integer, Integer>(); // left[p] 表示质数 p 首次出现的下标
var right = new int[n]; // right[i] 表示左端点为 i 的区间的右端点的最大值
for (int i = 0; i < n; i++) {
int x = nums[i];
for (int d = 2; d * d <= x; ++d) // 分解质因数
if (x % d == 0) {
if (left.containsKey(d))
right[left.get(d)] = i; // 记录左端点对应的右端点的最大值
else
left.put(d, i); // 第一次遇到质数 d
for (x /= d; x % d == 0; x /= d) ;
}
if (x > 1)
if (left.containsKey(x))
right[left.get(x)] = i;
else
left.put(x, i);
}
for (int l = 0, maxR = 0; l < n; l++) {
if (l > maxR) // 最远可以遇到 maxR
return maxR; // 也可以写 l-1
maxR = Math.max(maxR, right[l]);
}
return -1;
}
}2585. 获得分数的方法数
考试中有 n 种类型的题目。给你一个整数 target 和一个下标从 0 开始的二维整数数组 types ，其中 types[i] = [counti, marksi] 表示第 i 种类型的题目有 counti 道，每道题目对应 marksi 分。
返回你在考试中恰好得到 target 分的方法数。由于答案可能很大，结果需要对 109 +7 取余。
注意，同类型题目无法区分。
比如说，如果有 3 道同类型题目，那么解答第 1 和第 2 道题目与解答第 1 和第 3 道题目或者第 2 和第 3 道题目是相同的。
示例 1：
输入：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
示例 2：
输入：target = 5, types = [[50,1],[50,2],[50,5]]
输出：4
解释：要获得 5 分，你可以选择以下四种方法之一：
- 解决 5 道第 0 种类型的题目：1 + 1 + 1 + 1 + 1 = 5
- 解决 3 道第 0 种类型的题目和 1 道第 1 种类型的题目：1 + 1 + 1 + 2 = 5
- 解决 1 道第 0 种类型的题目和 2 道第 1 种类型的题目：1 + 2 + 2 = 5
- 解决 1 道第 2 种类型的题目：5
示例 3：
输入：target = 18, types = [[6,1],[3,2],[2,3]]
输出：1
解释：只有回答所有题目才能获得 18 分。
提示：
1 <= target <= 1000
n == types.length
1 <= n <= 50
types[i].length == 2
1 <= counti, marksi <= 50解答：动态规划
class Solution {
private static final int MOD = 1000000007;
public int waysToReachTarget(int target, int[][] types) {
// 获取数组 types 的长度
int n = types.length;
// 定义一个二维数组 dp，表示达到每个目标值所需要的方案数
int[][] dp = new int[n + 1][target + 1];
// 初始化 dp[0][0] 为 1，表示达到目标值为 0 时有一种方案
dp[0][0] = 1;
// 遍历 types 数组
for (int i = 1; i <= n; i++) {
// 获取当前物品的个数和标记值
int count = types[i - 1][0];
int marks = types[i - 1][1];
// 遍历所有的目标值
for (int j = 0; j <= target; j++) {
// 遍历当前物品能够选择的个数
for (int k = 0; k <= count && k * marks <= j; k++) {
// 计算当前目标值 j 能够使用当前物品 i 的 k 个，以及之前物品能够达到的目标值 j-k*marks 的方案数之和
dp[i][j] = (dp[i][j] + dp[i - 1][j - k * marks]) % MOD;
}
}
}
// 返回达到目标值 target 的方案数
return dp[n][target];
}
}
