6337. Count Distinct Numbers on Board
给你一个正整数 n ，开始时，它放在桌面上。在 109 天内，每天都要执行下述步骤：
- 对于出现在桌面上的每个数字 x ，找出符合 1 <= i <= n 且满足 x % i == 1 的所有数字 i 。
- 然后，将这些数字放在桌面上。
返回在 10^9 天之后，出现在桌面上的 不同 整数的数目。注意：
- 一旦数字放在桌面上，则会一直保留直到结束。
- % 表示取余运算。例如，14 % 3 等于 2 。
测试样例
输入：n = 5
输出：4
解释：
最开始，5 在桌面上。 第二天，2 和 4 也出现在桌面上，因为 5 % 2 == 1 且 5 % 4 == 1 。 再过一天 3 也出现在桌面上，因为 4 % 3 == 1 。 在十亿天结束时，桌面上的不同数字有 2 、3 、4 、5 。
解答：这题关键条件是
- 找出符合 1 <= i <= n
- 1 <= n <= 100
暴力计算即可
class Solution {
public int distinctIntegers(int n) {
boolean[] isAdd = new boolean[101];
isAdd[n] = true;
Queue<Integer> queue = new LinkedList<>();
queue.add(n);
int res = 1;
while (!queue.isEmpty()) {
int tmp = queue.poll();
for (int i = 1; i <= tmp; ++i) {
if (tmp % i == 1 && !isAdd[i]) {
isAdd[i] = true;
queue.add(i);
res += 1;
}
}
}
return res;
}
}6338. Count Collisions of Monkeys on a Polygon
现在有一个正凸多边形，其上共有 n 个顶点。顶点按顺时针方向从 0 到 n - 1 依次编号。每个顶点上 正好有一只猴子 。下图中是一个 6 个顶点的凸多边形。
每个猴子同时移动到相邻的顶点。顶点 i 的相邻顶点可以是：
- 顺时针方向的顶点 (i + 1) % n ，或
- 逆时针方向的顶点 (i - 1 + n) % n 。
如果移动后至少有两个猴子位于同一顶点，则会发生 碰撞 。返回猴子至少发生 一次碰撞 的移动方法数。由于答案可能非常大，请返回对 10^9+7 取余后的结果。
注意，每只猴子只能移动一次。
测试样例：
输入：n = 3
输出：6
解答: 这道题本质考的是快速幂。如果猴子想要不发生任何碰撞，只有2种可能，即猴子同时顺时针移动或者逆时针一动。
所以答案就是所有可能 - 2
class Solution {
private static final int mod = 1_000_000_007;
public int monkeyMove(int n) {
long all = mul(n);
return (int)((all + mod - 2) % mod);
}
private long mul(int n) {
if (n == 0) {
return 1;
} else {
long tmp = mul(n / 2);
long cur = 1;
if (n % 2 == 1) {
cur = 2;
}
return (tmp * tmp * cur) % mod;
}
}
}6339. Put Marbles in Bags
你有 k 个背包。给你一个下标从 0 开始的整数数组 weights ，其中 weights[i] 是第 i 个珠子的重量。同时给你整数 k 。
请你按照如下规则将所有的珠子放进 k 个背包。
- 没有背包是空的。
- 如果第 i 个珠子和第 j 个珠子在同一个背包里，那么下标在 i 到 j 之间的所有珠子都必须在这同一个背包中。
- 如果一个背包有下标从 i 到 j 的所有珠子，那么这个背包的价格是 weights[i] + weights[j] 。
一个珠子分配方案的 分数 是所有 k 个背包的价格之和。请你返回所有分配方案中，最大分数 与 最小分数 的 差值 为多少。
测试样例
输入：weights = [1,3,5,1], k = 2
输出：2
解答：这题是脑筋急转弯题。一开始会以为使用动态规划，但是直接超时，所以需要换个思路。
由于每个背包，可以认为是一次数组的切分。那么经过一次切分之后，切切分在i位置，则增加的分数是nums[i] + nums[i + 1]。那么最小分数和最大分数就是寻找最大的K - 1个切分位和最小的K - 1个切分位置。
class Solution {
public long putMarbles(int[] weights, int k) {
List<Long> list = new ArrayList<>();
for (int i = 0; i + 1 < weights.length; ++i) {
long tmp = weights[i];
tmp += weights[i + 1];
list.add(tmp);
}
Collections.sort(list);
long res = 0;
for (int i = 0; i < k - 1; ++i) {
res -= list.get(i);
res += list.get(list.size() - 1 - i);
}
return res;
}
}6340. Count Increasing Quadruplets
给你一个长度为 n 下标从 0 开始的整数数组 nums ，它包含 1 到 n 的所有数字，请你返回上升四元组的数目。
如果一个四元组 (i, j, k, l) 满足以下条件，我们称它是上升的：
- 0 <= i < j < k < l < n 且
- nums[i] < nums[k] < nums[j] < nums[l] 。
测试样例
输入：nums = [1,3,2,4,5]
输出：2
解答：这种寻找3个或者4个关键数字的题目基本有个套路 - 从中间的一个/两个数字下手，分为前半和后半部分。
以这道题目为例子，我们从j,k入手。则我们需要寻找比nums[k]小，且i < j的个数和寻找比nums[j]大，且n > l的个数。以此转化为2个二维前缀和就能获得答案。
class Solution {
public long countQuadruplets(int[] nums) {
int len = nums.length;
int[][] countLarge = new int[len][len];
for (int i = 0; i < len; ++i) {
int tmp = 0;
for (int j = len - 1; j > i; --j) {
if (nums[j] < nums[i]) {
countLarge[i][j] = tmp;
} else if (nums[j] > nums[i]) {
tmp += 1;
}
}
}
long res = 0;
for (int i = 0; i < len; ++i) {
long tmp = 0;
for (int j = 0; j < i; ++j) {
if (nums[j] > nums[i]) {
res += tmp * countLarge[j][i];
} else if (nums[j] < nums[i]) {
++tmp;
}
}
}
return res;
}
}