讨论/技术交流/🏆 第 230 场力扣周赛/
🏆 第 230 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛】

image.png

3 分 - 统计匹配检索规则的物品数量
4 分 - 最接近目标价格的甜点成本
5 分 - 通过最少操作次数使数组的和相等
7 分 - 车队 II

4
共 77 个回复

依旧只会第一题的加一
ORZ

25

第二题当时暴力过了,结果现在又加样例判超时,音响没了。我的心情出了点问题

2

第一次参加周赛,找了半天题在哪(就服自己),淦....orz,最后四分钟改了个数第二题通过了,满足了,看了看排行榜,果然大神就是多orz

2

第二题数据规模一开始看成10的4次方了 想半天不知道怎么做 剩半小时了仔细一看发现是10...

2

妈妈我出息了最后两分钟完成第二题

2

QAQ第二题直接卡死,一波动态规划把自己搞晕了呜呜呜

1

到点后一分钟找到bug第三题提交通过了,太淦了。。

1

我感觉我思路已经说的很细致了,用路程时间图把所有车的路程时间曲线都画出来(相交代表相遇即追上,追上之后因为是跟慢车行驶,所以后车的曲线到交点就不用延伸出去了)。然后很容易看出这个路程时间图的曲线都是凸的,可以单调栈来做,单调栈O(N)解决。需要注意的是,要逆序来做,从最后一辆车开始

1

题目2:最接近目标价格的甜点成本

思路:状态压缩

  • 由于所有配料都可以选择不添加或添加,所以需要遍历所有子集。因为最多不超过 1010 种配料,所以可以使用状态压缩,将 mm 种配料的选择与否对应到一个长度为 mm 的二进制数字。遍历所有 mm 位的二进制数字对应所有可能的选择搭配,第 ii 位数字为 11 说明本次选择加入了第 ii 种配料。
  • 由于所有配料都可以选择添加 11 份或 22 份,所以我们可以拆分为进行了 22 次选择,每次都选择某种配料不加入或者加入 11 份。所以需要嵌套循环,分别遍历两个长度为 mm 的二进制数。由于最多不超过 1010 种配料,所以可以在 2202^{20} 的复杂度内完成遍历。

代码:

class Solution {
    using ll = long long;
public:
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        int n = baseCosts.size(), m = toppingCosts.size();
        ll ret = baseCosts[0], cur = 0;
        
        // 选择第 i 种基料
        for(int i = 0; i < n; i++) {
            // 第一次选择
            for(int j = 0; j < (1 << m); j++) {
                // 第二次选择
                for(int k = j; k < (1 << m); k++) {
                    // 先加入第 i 种基料的成本
                    cur = baseCosts[i];
                    
                    // 遍历 m 种配料
                    for(int l = 0; l < m; l++) {
                        if(j & (1 << l)) cur += toppingCosts[l];
                        if(k & (1 << l)) cur += toppingCosts[l];
                    }
                    if(abs(ret - target) > abs(cur - target)) {
                        ret = cur;
                    } else if(abs(ret - target) == abs(cur - target)) {
                        // 选择成本较小的
                        ret = min(ret, cur);
                    }
                }
            }
        }
        return ret;
    }
};

复杂度分析:

  • 时间复杂度为 O(nm⋅4m)O(nm·4^m)。
  • 空间复杂度为 O(1)O(1)。

关注GTAlgorithm,专注周赛、面经题解分享,陪大家一起攻克算法难关~

算法干货汇总

字节跳动客户端二面面经(附答案)

字节跳动客户端三面面经(附答案)

3

加一