当前位置：首页 > news >正文

LeetCode --- 448 周赛

news 来源：原创 2025/7/29 4:39:07

题目列表

3536. 两个数字的最大乘积
3537. 填充特殊网格
3538. 合并得到最小旅行时间
3539. 魔法序列的数组乘积之和

一、两个数字的最大乘积

在这里插入图片描述
由于数据都是正数，所以乘积最大的两个数，本质就是找数组中最大的两个数即可，可以排序后直接找到，也可以通过遍历找到，代码如下

// C++
// 遍历
class Solution {
public:int maxProduct(int n) {int mx1 = 0, mx2 = 0;while(n){int x = n % 10;if(x > mx1) mx2 = mx1, mx1 = x;else if(x > mx2) mx2 = x;n /= 10;}return mx1 * mx2;}
};

# Python
class Solution:def maxProduct(self, n: int) -> int:mx1 = 0mx2 = 0while n:x = n % 10if x > mx1:mx1, mx2 = x, mx1elif x > mx2:mx2 = xn //= 10return mx1 * mx2

二、填充特殊网格

在这里插入图片描述
这是个很经典的分治题，根据题目描述，对于一个网格图，可以将它划分成四个象限，即四个小网格图，而对于每一个小网格图，我们又能划分成四个象限，很显然，这是规模更小的子问题，可以用递归来解决，代码如下

// C++
class Solution {
public:vector<vector<int>> specialGrid(int n) {int cnt = 0;vector grid(1 << n, vector<int>(1 << n));auto dfs = [&](this auto&& dfs, int x, int y, int d){ // 根据左上角坐标和边长就能确定一个网格图if(d == 1){grid[x][y] = cnt++;return;}int new_d = d / 2;// 按照这样的顺序，网格中的数字从小到大依次增长// 右上象限dfs(x, y + new_d, new_d);// 右下象限dfs(x + new_d, y + new_d, new_d);// 左下象限dfs(x + new_d, y, new_d);// 左上象限dfs(x, y, new_d);};dfs(0, 0, 1 << n);return grid;}
};

# Python
class Solution:def specialGrid(self, n: int) -> List[List[int]]:grid = [[0] * (1 << n) for _ in range(1 << n)]cnt = 0def dfs(x: int, y: int, d: int):if d == 1:nonlocal cntgrid[x][y] = cntcnt += 1returndfs(x, y + d // 2, d // 2)dfs(x + d // 2, y + d // 2, d // 2)dfs(x + d // 2, y, d // 2)dfs(x, y, d // 2)dfs(0, 0, 1 << n)return grid

三、合并得到最小旅行时间

在这里插入图片描述
本题可以用选或不选的思想，对于每一个索引 i，我们都可以考虑是否删除它，如果删除，则下一段路程的 next_time = time[i] + time[i+1]，同时，我们还需要记录上一段路程的 pre_time 来计算出当前这段路程需要花费的时间
对于任意一段 position[i] ~ position[i+1] 路程来说，它所需要的时间只和当前索引 i 对应的 time 有关，一旦确定了是否删除当前索引，就能计算出这段路程需要花费的时间

故我们有如下定义

$dfs(i,j,pre\_time,cur\_time)$ 表示当前路程 time = cur_time，上一段路程 time = pre_time，剩余可删除索引为 j 个时，position[i] ~ position[n-1] 时所需的最少时间
- 如果选择不删除当前索引，则 $dfs(i,j,pre\_time,cur\_time)=dfs(i+1,j,cur\_time,time[i+1])+(position[i+1]-position[i])\times cur\_time$
- 如果选择删除当前索引，则 $dfs(i,j,pre\_time,cur\_time)=dfs(i+1,j-1,pre\_time,cur\_time+time[i+1])+(position[i+1]-position[i])\times pre\_time$
- 上诉两种情况去 min 返回
当 i == n - 1 时，到达终点，返回 0
答案返回 $dfs(1,k,time[0],time[1])+(position[1]-position[0])\times time[0]$ ，因为 i = 0 的索引不能被删除，可以单独计算(或者也可以放入 dfs 中写一个逻辑处理 i = 0 的情况，此时应该返回 $df s (0, k, 0, t im e [0])$ )

代码如下

// C++
class Solution {
public:int minTravelTime(int l, int n, int k, vector<int>& position, vector<int>& time) {// 6 | 4 | 7 | 7// 这里用哈希进行记忆化，分别计算出 i、j、pre、cur 所需要的比特位，将他们拼接成 int 当作 key 来使用unordered_map<int,int> memo;auto dfs = [&](this auto&& dfs, int i, int j, int pre, int cur)->int{if(i == n - 1){return j == 0 ? 0 : INT_MAX / 2;}int mask = i << 18 | j << 14 | pre << 7 | cur;if(memo.count(mask)) return memo[mask];int res = dfs(i + 1, j, cur, time[i+1]) + cur * (position[i + 1] - position[i]);if(j){res = min(res, dfs(i + 1, j - 1, pre, cur + time[i+1]) + pre * (position[i + 1] - position[i]));}return memo[mask] = res;};// 将 i = 0 的逻辑放在外面return dfs(1, k, time[0], time[1]) + time[0] * (position[1] - position[0]);}
};class Solution {
public:int minTravelTime(int l, int n, int k, vector<int>& position, vector<int>& time) {// 6 | 4 | 7 | 7unordered_map<int,int> memo;auto dfs = [&](this auto&& dfs, int i, int j, int pre, int cur)->int{if(i == n - 1){return j == 0 ? 0 : INT_MAX / 2;}int mask = i << 18 | j << 14 | pre << 7 | cur;if(memo.count(mask)) return memo[mask];int res = dfs(i + 1, j, cur, time[i+1]) + cur * (position[i + 1] - position[i]);if(j && i){ // 将 i = 0 的逻辑放在里面res = min(res, dfs(i + 1, j - 1, pre, cur + time[i+1]) + pre * (position[i + 1] - position[i]));}return memo[mask] = res;};return dfs(0, k, 0, time[0]);}
};

# Python
class Solution:def minTravelTime(self, l: int, n: int, k: int, position: List[int], time: List[int]) -> int:@cachedef dfs(i: int, j: int, pre: int, cur: int)->int:if i == n - 1:return 0 if j == 0 else infres = dfs(i + 1, j, cur, time[i+1]) + (position[i+1] - position[i]) * curif i and j:res = min(res, dfs(i + 1, j - 1, pre, cur + time[i+1]) + (position[i+1] - position[i]) * pre)return resreturn dfs(0, k, 0, time[0])

四、魔法序列的数组乘积之和

在这里插入图片描述
思路：

给定一个 seq 序列，如何计算出它对答案的贡献？
- 假设给定 seq = [0,0,0,1,1,2,2,2]
- 根据题目要求，它对答案的贡献为 $nums[0]^3 \times nums[1]^2\times nums[2]^3$
- 同时，由于 seq 序列的数据顺序不同，被认定为不同的序列，根据排列组合，则包含这些元素的 seq 序列对于答案的贡献为 $\frac{8!}{3! \times 2! \times 3!}\times nums[0]^3 \times nums[1]^2\times nums[2]^3=8!\times \frac{nums[0]^3}{3!}\times \frac{nums[1]^3}{2!} \times \frac{nums[2]^3}{3!}$
- 也就是说，我们可以单独计算每一个 $\frac{nums[i]^c}{c!}$ ，然后将它们相乘得到答案
- 故对于 seq 来说，只要我们确定了它标定了几个 $n u m s [i]$ ，就能计算出它的贡献
考虑如何得到序列 seq，使得 popcount(sum(2^seq[i])) == K ?
- 难点在于，相同二进制位置的 1 相加会产生进位，我们无法只通过一个参数来直接确定还需要多少二进制数位的 1
- 如果我们直接暴力计算出 s = sum(2^seq[i])，然后在选完所有 seq 序列的数字后，求 popcount(s)，进行判断，就会爆内存，因为 s 很大
- 如何做？
  - 性质：只要我们从低到高枚举二级制数位的 1 进行选择，就会发现 +Nx2^i 不会影响低位的二进制数位的 1 的数量
  - 所以我们只要关心统计从二进制数位 i 开始往后的高位上的二级制数即可，这样我们记录的 s 的个数就会大大减小，具体见代码