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 = 0
        mx2 = 0
        while n:
            x = n % 10
            if x > mx1:
                mx1, mx2 = x, mx1
            elif x > mx2:
                mx2 = x
            n //= 10
        return 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 = 0
        def dfs(x: int, y: int, d: int):
            if d == 1:
                nonlocal cnt
                grid[x][y] = cnt
                cnt += 1
                return
            dfs(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 | 7
        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 && 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:
        @cache
        def dfs(i: int, j: int, pre: int, cur: int)->int:
            if i == n - 1:
                return 0 if j == 0 else inf
            res = dfs(i + 1, j, cur, time[i+1]) + (position[i+1] - position[i]) * cur
            if i and j:
                res = min(res, dfs(i + 1, j - 1, pre, cur + time[i+1]) + (position[i+1] - position[i]) * pre)
            return res
        return 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])>>i
        auto 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;
    }
};