高质量DP压轴，非常精彩的比赛。LeetCode周赛第282场

TechFlow-承志

发布于 2022-09-21 16:08:55

4350

文章被收录于专栏：TechFlowTechFlow

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

我们来看LeetCode周赛。赞助者是GrapeCity 西安，比赛奖励如下：

看完了奖品之后，我们来看题。

统计包含给定前缀的字符串

难度：零星

给你一个字符串数组 words 和一个字符串 pref 。

返回 words 中以 pref 作为前缀的字符串的数目。

字符串 s 的前缀就是 s 的任一前导连续字符串。

解法

模拟题，要判断是否包含给定的前缀，很简单，我们直接从匹配串中取出对应长度的子串，然后比较一下子串和需要匹配的前缀是否相等即可。

比赛的时候偷了下懒，用了Python，操作字符串比较方便，其实用C++的substr也是一样的。

class Solution:
    def prefixCount(self, words: List[str], pref: str) -> int:
        ret = 0
        m = len(pref)
        for w in words:
            if w[:m] == pref:
                ret+=1
        return ret

使两字符串互为字母异位词的最少步骤数

难度：☆

给你两个字符串 s 和 t 。在一步操作中，你可以给 s 或者 t 追加任一字符。

返回使 s 和 t 互为字母异位词所需的最少步骤数。

字母异位词指字母相同但是顺序不同（或者相同）的字符串。

解法

题目描述说的花里胡哨，其实意思就是说让两个字符串变得构成一致，最少需要添加几个字符。

我们只需要统计一下每个字符串当中a-z的数量，将数量少的那个补齐一致即可。统计一下需要补齐的数量即是答案。

也可以对两个字符串进行排序之后再比对，稍微麻烦一些，一样是可行的。

class Solution {
public:
    int minSteps(string s, string t) {
        vector<int> p(30, 0), r(30, 0);
        for (int i = 0; i < s.length(); i++) {
            p[s[i] - 'a'] ++;
        }
        for (int i = 0; i < t.length(); i++) {
            r[t[i] - 'a'] ++;
        }
        
        int ret = 0;
        for (int i = 0; i < 26; i++) {
            ret += abs(p[i] - r[i]);
        }
        return ret;
    }
};

完成旅途的最少时间

难度：☆☆

给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 **一趟 **旅途所需要花费的时间。

每辆公交车可以连续完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车独立运行，也就是说可以同时有多辆公交车在运行且互不影响。

给你一个整数 totalTrips ，表示所有公交车总共需要完成的旅途数目。请你返回完成至少 totalTrips 趟旅途需要花费的最少时间。

解法

首先我们观察一下数据范围，会发现这题的数据范围很大，无论是公交车的数量还是需要的旅程数规模都不小。所以我们暴力枚举一定是不行的。

但如果不暴力枚举，也很难办，因为时间的延长会对所有的车辆都有影响。我们要统计对所有车辆的影响就一定会要全部遍历一遍，那么因此带来的开销就非常大了。

那怎么办呢？这里用到一个非常关键的诀窍，即从解决问题转变到验证问题上来。我们都知道在算法当中有一个NP问题的概念，指的是在多项式时间复杂度内没有可行解，但是可以在多项式时间复杂度内验证的问题。这道题就有点NP问题的意思，我们想要算出来这样的答案是非常困难的，时间复杂度很高。但我们验证一个答案是不是满足条件则要简单很多，我们只需要遍历一下每一辆车，算一下总和就行了。

既然我们求解答案容易，验证答案简单，我们就可以从这个角度入手，思考通过快速验证的方式找到答案。

想到这里基本上就呼之欲出了，我们可以通过二分法来找最小满足条件的答案。因为时间和所有车辆的旅程数之间是一个正比关系，时间越长，旅程数一定越多。既然存在这样的正比关系，那么使用二分法就是顺理成章的事情了。

我们来看下二分的上下界，我们要找满足条件的最小值，可以采用左开右闭区间。下界自然就是0，上界是什么呢？上界是min(time) * totalTrips，也就是速度最快的车辆的耗时乘上旅程数。我们要做的就是在这个范围内，使用二分法找到满足条件的最小答案。

注意，这道题的范围会超过int，所以需要使用long long类型。

代码本身并不复杂，主要是思维相对比较巧妙。

class Solution {
public:
    long long minimumTime(vector<int>& time, int totalTrips) {
        int n = time.size();
        sort(time.begin(), time.end());
        long long l = 0, r = (long long)time[0] * (long long)totalTrips;
        while (l+1 < r) {
            long long m = (l + r) >> 1;
            long long cur = 0;
            for (int i = 0; i < n; i++) {
                cur += m / (long long) time[i];
            }
            if (cur < totalTrips) l = m;
            else r = m;
        }
        return r;
    }
};

完成比赛的最小时间

难度：☆☆☆☆

给你一个下标从 0 开始的二维整数数组 tires ，其中 tires[i] = [fi, ri] 表示第 i 种轮胎如果连续使用，第 x 圈需要耗时 fi * ri(x-1) 秒。

比方说，如果 fi = 3 且 ri = 2 ，且一直使用这种类型的同一条轮胎，那么该轮胎完成第 1 圈赛道耗时 3 秒，完成第 2 圈耗时 3 * 2 = 6 秒，完成第 3 圈耗时 3 * 22 = 12 秒，依次类推。

同时给你一个整数 changeTime 和一个整数 numLaps 。

比赛总共包含 numLaps 圈，你可以选择任意一种轮胎开始比赛。每一种轮胎都有无数条。每一圈后，你可以选择耗费 changeTime 秒换成任意一种轮胎（也可以换成当前种类的新轮胎）。

请你返回完成比赛需要耗费的最少时间。

解法

这题难度比较大，难点主要在于数据规模。

轮胎的数量有1e5，并且每个轮胎可以开动的时间也是不确定的，再考虑到一共要开最多1000圈，所以组合下来就有非常多的可能性。

如果不考虑规模，我们可以使用动态规划的方法来求解。我们使用dp[i][j]表示跑完i圈使用轮胎j的开销。不难写出转移代码：

int m = tires.size();
for (int i = 0; i < numLaps; i++) {
    for (int j = 0; j < m; j++) {
        for (int k = 0; k < m; k++) {
            dp[i][j] = min(dp[i][j], dp[i-1][k] + cost);
        }
    }
}

但是这段代码当中有两个难点，第一个难点是复杂度太大，我们用了三重循环，显然是一定会超时的。别说三重循环，就连两重循环都无法接受。第二个难点是cost的计算，我们在中途是不知道之前轮胎已经跑了几圈的，这会影响之后轮胎的开销。

第二个问题不难解决，我们只需要在dp数组当中多维护一个轮胎当前已经跑的圈数即可。所以真正核心的是第一个问题，这也是本题的最大难点。

怎么解决呢？还是需要分析问题，我们观察一下会发现changeTime最大是1e5，而轮胎的耗时是以指数级增长的。也就是说在最优情况下，一个轮胎能够开的圈数是非常有限的。当r最小为2时，也不会超过20。我们可以将轮胎和它自己比，求出不换胎的情况下最多能够行驶的圈数。什么情况下是极限呢？当下一轮不换胎的耗时大于换胎就是极限了。

接着我们再把这些轮胎之间横向比较，我们可以找到只行驶一圈、两圈、三圈最短的耗时。前面分析过了，在不换轮胎的情况下，最长行驶的圈数不会超过20。也就是说我们把问题转换成了一个完全背包问题，连续行驶的圈数是体积，所花费的时间是开销，我们需要找到填满背包最小的开销。并且我们已经知道商品的种数不会超过20。

那么这个动态规划的规模就从

O(nm^2)

下降到了

O(n)

。

更多细节查看代码注释。

class Solution {
public:
    int minimumFinishTime(vector<vector<int>>& tires, int ct, int numLaps) {
        typedef pair<int, int> pii;
        long long mark = 0x3f3f3f3f3f3f3f3f;
        // 存储连续跑圈最短耗时
        vector<long long> nt(numLaps+2, mark);
        
        int n = tires.size();
        for (int i = 0; i < n; i++) {
            // s表示总时间，t表示当前一圈需要的时间
            long long s = tires[i][0];
            long long t = tires[i][0];
            long long r = tires[i][1];
            int rnd = 1;
            // 当跑一圈的耗时大于换新胎跑一圈时，就没必要再连续跑了
            while (t <= (long long) (ct + tires[i][0])) {
                // 如果当前轮胎更优，更新nt
                if (rnd <= numLaps && s < nt[rnd]) nt[rnd] = s;
                rnd++;
                t *= r;
                s += t;
            }
        }
        
        // 找到最多能跑的圈数，即商品数
        for (int i = 1; i <= numLaps+1; i++) {
            if (nt[i] == mark) {
                n = i;
                break;
            }
        }
        
        vector<long long> dp(numLaps+1, mark);
        dp[0] = 0;
        
        // 完全背包问题，i枚举体积，j枚举商品
        for (int i = 0; i < numLaps; i++) {
            for (int j = 1; j < n; j++) {
                // 0时刻自带轮胎出发， 不需要额外换胎时间
                if (i + j <= numLaps) dp[i+j] = min(dp[i+j], dp[i] + nt[j] + (i == 0 ? 0 : ct));
            }
        }
        return dp[numLaps];
    }
};

这场比赛的前三题难度还行，最后一题难度比较大，很考验思维，总的来说，难度的阶梯和区分度做的很不错，大家有空不妨都练习练习。

好了，关于这场周赛就聊到这里，感谢大家的阅读。

喜欢本文的话不要忘记三连~

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-02-28，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 Coder梁微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度