欢迎大家加QQ群：623375442。五一节放假还是两道Hard，这个是没想到的。
100659. Maximum Product of Two Digits
给定一个正整数 n。
返回 任意两位数字 相乘所得的 最大 乘积。
注意：如果某个数字在 n 中出现多次，你可以多次使用该数字。
测试样例：
输入：n = 31
输出：3
解释：n 的数字是 [3, 1]。任意两位数字相乘的结果为：3 * 1 = 3。最大乘积为 3。
解答：遍历整数 n 的每一位数字，维护两个最大的数字 max[0]（最大值）和 max[1]（第二大值）。对于当前提取的数字 tmp：
- 如果 tmp > max[0]，则更新 max[1]=max[0]，max[0]=tmp；
- 否则如果 tmp > max[1]，则更新 max[1]=tmp。
最终返回 max[0] * max[1] 即为所求最大乘积。
class Solution {
public int maxProduct(int n) {
// max[0] 存储最大的数字，max[1] 存储第二大的数字
int[] max = {0, 0};
// 逐位提取 n 的数字
while (n > 0) {
int tmp = n % 10; // 取出最低位
// 如果当前数字大于 max[0]，则更新最大值和第二大值
if (tmp > max[0]) {
max[1] = max[0];
max[0] = tmp;
}
// 否则如果大于第二大值，则更新第二大值
else if (tmp > max[1]) {
max[1] = tmp;
}
n /= 10; // 去掉最低位
}
// 返回最大的两个数字的乘积
return max[0] * max[1];
}
}100626. Fill a Special Grid
给你一个非负整数 N，表示一个 2^N x 2^N 的网格。你需要用从 0 到 2^(2^N) - 1 的整数填充网格，使其成为一个 特殊 网格。一个网格当且仅当满足以下 所有 条件时，才能称之为 特殊 网格：
- 右上角象限中的所有数字都小于右下角象限中的所有数字。
- 右下角象限中的所有数字都小于左下角象限中的所有数字。
- 左下角象限中的所有数字都小于左上角象限中的所有数字。
- 每个象限也都是一个特殊网格。
返回一个 2^N x 2^N 的特殊网格。
注意：任何 1x1 的网格都是特殊网格。
测试样例：
输入：N = 1
输出：[[3,0],[2,1]]
解释: 每个象限的数字如下：
- 右上角：0
- 右下角：1
- 左下角：2
- 左上角：3
由于 0 < 1 < 2 < 3，该网格满足给定的约束条件。
解答：对于大小为 2^N x 2^N 的网格，递归地将其分为四个象限，依次填充：
- 右上象限（起始数字 start 开始）；
- 右下象限（紧接上一区域）；
- 左下象限；
- 左上象限。
每个子象限也是大小减半的“特殊网格”，起始值累加遍历至完整填充。最终保证四个象限的数值区间依次递增。
class Solution {
public int[][] specialGrid(int N) {
int len = 1 << N; // 计算网格边长 2^N
int[][] res = new int[len][len];
// 从整个网格的 (0,0) 到 (len-1,len-1)，起始数字 0，开始填充
helper(0, 0, len - 1, len - 1, 0, res);
return res;
}
/**
* 递归填充子网格
* @param lx 子网格左上角 x 坐标
* @param ly 子网格左上角 y 坐标
* @param rx 子网格右下角 x 坐标
* @param ry 子网格右下角 y 坐标
* @param start 当前子网格填充的起始值
* @param res 最终结果网格
* @return 返回下一个子网格应使用的起始数字
*/
private int helper(int lx, int ly, int rx, int ry, int start, int[][] res) {
// 如果子网格为 1x1，直接填值
if (lx == rx && ly == ry) {
res[lx][ly] = start;
return start + 1;
} else {
// 计算中点，分成四个象限
int dx = (lx + rx) / 2, dy = (ly + ry) / 2;
// 1. 右上 (lx, dy+1) 到 (dx, ry)
start = helper(lx, dy + 1, dx, ry, start, res);
// 2. 右下 (dx+1, dy+1) 到 (rx, ry)
start = helper(dx + 1, dy + 1, rx, ry, start, res);
// 3. 左下 (dx+1, ly) 到 (rx, dy)
start = helper(dx + 1, ly, rx, dy, start, res);
// 4. 左上 (lx, ly) 到 (dx, dy)
return helper(lx, ly, dx, dy, start, res);
}
}
}100636. Merge Operations for Minimum Travel Time
给你一个长度为 l 公里的直路，一个整数 n，一个整数 k 和 两个 长度为 n 的整数数组 position 和 time 。
数组 position 列出了路标的位置（单位：公里），并且是 严格 升序排列的（其中 position[0] = 0 且 position[n - 1] = l）。
每个 time[i] 表示从 position[i] 到 position[i + 1] 之间行驶 1 公里所需的时间（单位：分钟）。
你 必须 执行 恰好 k 次合并操作。在一次合并中，你可以选择两个相邻的路标，下标为 i 和 i + 1（其中 i > 0 且 i + 1 < n），并且：
- 更新索引为 i + 1 的路标，使其时间变为 time[i] + time[i + 1]。
- 删除索引为 i 的路标。
返回经过 恰好 k 次合并后从 0 到 l 的 最小总旅行时间（单位：分钟）。
测试样例：
输入：l = 10, n = 4, k = 1, position = [0,3,8,10], time = [5,8,3,6]
输出：62
解释: 合并下标为 1 和 2 的路标。删除下标为 1 的路标，并将下标为 2 的路标的时间更新为 8 + 3 = 11。
合并后：position 数组：[0, 8, 10], time 数组：[5, 11, 6]
总旅行时间：40 + 22 = 62 ，这是执行 1 次合并后的最小时间。
解答：使用三维记忆化深度优先搜索（DFS + DP），状态为 (pos, remain, add)：
- pos：当前处理的路标索引；
- remain：剩余需要执行的合并次数；
- add：由于前面合并操作累积到当前区段的附加时间。
在位置 pos，尝试将它与后续某个位置 j 之间所有中间路标一次性合并，计算此段的行驶时间并递归到下一个未合并的路标 j。取所有方案的最小值。通过 dp[pos][remain][add] 进行剪枝和结果缓存。
class Solution {
private static final int MAX = Integer.MAX_VALUE / 2; // 避免溢出的“大”值
// 内部封装数据，加速访问
class Data {
int l, n, k;
int[] position, time;
int[] prefixTime; // time 前缀和，用于快速计算合并附加时间
Integer[][][] dp; // 记忆化 DP 表
public Data(int _l, int _n, int _k, int[] _position, int[] _time) {
l = _l; n = _n; k = _k;
position = _position;
time = _time;
prefixTime = new int[n + 1];
// 构建前缀和：prefixTime[i+1] = time[0] + ... + time[i]
for (int i = 0; i < n; i++) {
prefixTime[i + 1] = prefixTime[i] + time[i];
}
int sumTime = prefixTime[n];
// dp[pos][remain][add]，add 的最大可能值为 sumTime
dp = new Integer[n][k + 1][sumTime + 1];
}
}
public int minTravelTime(int l, int n, int k, int[] position, int[] time) {
Data data = new Data(l, n, k, position, time);
// 从第 0 个路标开始，还需合并 k 次，初始 add 为 0
return helper(0, k, 0, data);
}
/**
* @param pos 当前路标索引
* @param remain 剩余的合并次数
* @param add 累积附加的 time 值
* @param data 封装数据
* @return 最小旅行时间
*/
private int helper(int pos, int remain, int add, Data data) {
// 如果已经到达最后一个路标
if (pos == data.n - 1) {
// 合并次数正好用完，则后续无路段，时间为 0；否则返回“无效”大值
return (remain == 0 ? 0 : MAX);
}
// 记忆化剪枝
if (data.dp[pos][remain][add] == null) {
int best = MAX;
// 尝试将 pos 后面的若干标点一次性合并到 j
for (int j = pos + 1; j < data.n; j++) {
int used = j - pos - 1; // 需要用掉的合并次数
if (used > remain) break; // 超过剩余次数，不可行
// 计算 pos 到 j 这一段行驶距离与速率
int dist = data.position[j] - data.position[pos];
int rate = data.time[pos] + add; // 合并后当前路段速率
int costBlock = dist * rate; // 时间花费
// 计算下一段的 add 值：如果 used > 0，就要累加中间那些 time 值
int newAdd = (used > 0)
? data.prefixTime[j] - data.prefixTime[pos + 1]
: 0;
// 递归至 j，并扣除 used 次合并
int tmp = helper(j, remain - used, newAdd, data);
if (tmp < MAX) {
best = Math.min(best, costBlock + tmp);
}
}
data.dp[pos][remain][add] = best;
}
return data.dp[pos][remain][add];
}
}
100652. Find Sum of Array Product of Magical Sequences
给你两个整数 M 和 K，和一个整数数组 nums。
- seq 的序列长度为 M。
- 0 <= seq[i] < nums.length
- 2^seq[0] + 2^seq[1] + ... + 2^seq[M - 1] 的 二进制形式 有 K 个 置位。
这个序列的 数组乘积 定义为 prod(seq) = (nums[seq[0]] nums[seq[1]] ... * nums[seq[M - 1]])。
返回所有有效 魔法 序列的 数组乘积 的 总和 。
由于答案可能很大，返回结果对 10^9 + 7 取模。
置位 是指一个数字的二进制表示中值为 1 的位。
测试样例：
输入：M = 5, K = 5, nums = [1,10,100,10000,1000000]
输出：991600007
解释: 所有 [0, 1, 2, 3, 4] 的排列都是魔法序列，每个序列的数组乘积是 10^13。
解答：用四维记忆化 DFS，状态 (pos, um, uk, key)：
- pos：当前遍历到 nums 的索引；
- um：已选元素数目；
- uk：当前累计的二进制置位数（除最高位以外的低位）；
- key：当前二进制和的“剩余”值，用于逐步计算置位数。
在 pos 处，可选择不取或取若干次 nums[pos]，并用组合数 C(m-um, i) 枚举取 i 次的方案数，同时累积乘积和统计新产生的置位数。达到边界时，若正好选满 M 个且置位数为 K，则计为 1 种有效方案。所有方案乘积值合并并对 1_000_000_007 取模。
class Solution {
class Data {
Long[][][][] dp; // dp[pos][um][uk][key]
int[] nums;
int m, k;
public Data(int m, int k, int[] nums) {
this.nums = nums;
this.m = m;
this.k = k;
dp = new Long[nums.length][m + 1][k + 1][32];
}
}
private static int[][] combine;
private static final int mod = 1_000_000_007;
// 预处理组合数 C[n][k]
static {
combine = new int[31][31];
combine[0][0] = 1;
for (int i = 1; i <= 30; ++i) {
for (int j = 0; j <= i; ++j) {
if (j == 0 || j == i) {
combine[i][j] = 1;
} else {
combine[i][j] = (combine[i - 1][j - 1] + combine[i - 1][j]) % mod;
}
}
}
}
public int magicalSum(int m, int k, int[] nums) {
Data data = new Data(m, k, nums);
return (int) helper(0, 0, 0, 0, data);
}
/**
* @param pos 当前处理的 nums 索引
* @param um 已选元素总数
* @param uk 当前已统计的二进制置位数（低位部分）
* @param key 当前累计二进制和，用于统计置位
*/
private long helper(int pos, int um, int uk, int key, Data data) {
// 超出限制时无效，直接返回 0
if (um > data.m || uk > data.k) return 0;
// 遍历完 nums
if (pos == data.nums.length) {
// 恰好选满 m 且总置位数为 k 时，算作 1 种
if (um == data.m && uk + count(key) == data.k) {
return 1;
} else {
return 0;
}
}
if (data.dp[pos][um][uk][key] == null) {
long res = 0;
// 情况一：不取 nums[pos]，但要处理 key 的最低位置位数
res = helper(pos + 1, um, uk + (key % 2), key / 2, data);
// 情况二：取 i 次 nums[pos]，i 从 1 到 m-um
long mul = 1;
for (int i = 1; i <= data.m - um; ++i) {
mul = (mul * data.nums[pos]) % mod; // 当前选 i 次的乘积
int c = combine[data.m - um][i]; // 从剩余位置选 i 次的组合数
long ways = helper(
pos + 1,
um + i,
uk + ((key + i) % 2), // 新增的置位
(key + i) / 2, // 更新的 key
data
);
res = (res + mul * c % mod * ways % mod) % mod; // 累加各方案贡献
}
data.dp[pos][um][uk][key] = res;
}
return data.dp[pos][um][uk][key];
}
// 统计整数 key 的二进制中 1 的个数
private int count(int key) {
int cnt = 0;
while (key > 0) {
cnt += key & 1;
key >>= 1;
}
return cnt;
}
}