LeetCode --- 448 周赛

题目列表

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 的情况，此时应该返回 $dfs(0,k,0,time[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 来说，只要我们确定了它标定了几个 $nums[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 的个数就会大大减小，具体见代码

代码如下

// C++
constexpr int MOD = 1e9 + 7;
constexpr int MX = 31;
long long POW(long long x, long long y){long long res = 1;while(y){if(y & 1) res = res * x % MOD;x = x * x % MOD;y >>= 1;}return res;
}
vector<long long> F(MX), INV_F(MX);
int init = []{F[0] = 1;for(int i = 1; i < MX; i++){F[i] = F[i - 1] * i % MOD;}// 计算逆元INV_F.back() = POW(F.back(), MOD - 2);for(int i = MX - 1; i > 0; i--){INV_F[i - 1] = INV_F[i] * i % MOD;}return 0;
}();
class Solution {
public:int magicalSum(int m, int K, vector<int>& nums) {int n = nums.size();vector pow_(n, vector<int>(m + 1));for(int i = 0; i < n; i++){pow_[i][0] = 1;for(int j = 1; j <= m; j++){pow_[i][j] = 1LL * pow_[i][j-1] * nums[i] % MOD;}}vector memo(n, vector(m+1, vector(K+1, vector<int>(m/2+1, -1))));// i : 从低到高枚举二进制数位// j : 剩余要选的 seq 的元素个数// k : 剩余要得到的二进制 1 的个数// s : sum(2^seq[0...i])>>iauto dfs = [&](this auto&& dfs, int i, int j, int k, int s)->int{int c1 = popcount((unsigned) s);if(c1 + j < k){return 0;}if(i == n || j == 0 || k == 0){return j == 0 && c1 == k;}if(memo[i][j][k][s] != -1) return memo[i][j][k][s];int res = 0;for(int c = 0; c <= j; c++){res = (res + 1LL * dfs(i + 1, j - c, k - ((s + c) & 1), s + c >> 1) * pow_[i][c] % MOD * INV_F[c] % MOD) % MOD;}return memo[i][j][k][s] = res;};return F[m] * dfs(0, m, K, 0) % MOD;}
};