[数据结构与算法]LeetCode 力扣周赛 282

周赛传送门

个人感觉第四题好有难度，写的我直头晕。

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

思路：std::string::find

时间复杂度：$O(n)$

空间复杂度：$O(1)$

std::string::find 是 std::string 的成员函数，可用来获取子串在母串中的位置，其返回值有两种情况：

• 存在子串：返回第一次出现的第一个字符的下标。
• 不存在：返回 std::string::npos。

因此，可根据返回值是否为 0 来判断是否包含给定前缀。

class Solution {
public:
    int prefixCount(vector<string>& words, string pref) {
        int cnt = 0;
        for (const auto &w : words) {
            if (w.find(pref) == 0) {
                cnt++;
            }
        }
        return cnt;
    }
};

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

思路：统计数量

时间复杂度：$O(|s|+|t|+|\sum |)$

空间复杂度：$O(|\sum |)$

对于每一种字符 $c$，统计在两个字符串中的数量差记为 $d$，并向较少的那个字符串添加 $d$ 个 $c$ 即可。因此将 $abs(d)$ 累加起来即为答案。

class Solution {
public:
    int minSteps(string s, string t) {
        int cnt[2][26] = {0};
        for (auto c : s) { cnt[0][c-'a']++; }
        for (auto c : t) { cnt[1][c-'a']++; }
        int anw = 0;
        for (int i = 0; i < 26; i++) {
            anw += abs(cnt[0][i] - cnt[1][i]);
        }
        return anw;
    }
};

完成旅途的最少时间

思路：二分

时间复杂度：$O(n\ln t)$。$t$ 为答案上限，由数据范围可知，取 $1e14$ 即可。

空间复杂度：$O(1)$。

设有函数 $f(c)$ 如下：
$$f(c)=\sum _{i=0}^{n?1}?(\frac{c}{tim{e}_i})?$$

$c$ 为花费时间，$f(c)$ 即为每辆车能完成旅途数的总和。显然，随着 $c$ 的增大，$f(c)$ 必然是单调递增的。又有题目的数据范围可知，答案必在 $[1,1e14]$ 内。因此在该范围内二分 $c$ 即可。

class Solution {
public:
    bool check(int64_t l, const vector<int> &time, int64_t t) {
        int64_t cnt = 0;
        for (auto tt : time) {
            cnt += (l/tt);
            if (cnt >= t) return true;
        }
        return cnt >= t;
    }
    long long minimumTime(vector<int>& time, int totalTrips) {
        int64_t L = 0, R = 100000000000000L;
        while (L <= R) {
            int64_t mid = (L+R)>>1;
            if (check(mid, time, totalTrips)) {
                R = mid-1;
            } else {
                L = mid+1;
            }
        }
        return R+1;
    }
};

完成比赛的最少时间

思路：动态规划，贪心

时间复杂度：$O((T+L)?c)$，$T$ 为轮胎种数，$L$ 为圈数，$c$ 为单个轮胎的圈数上限。

空间复杂度：$O(L+n)$

设有一维数组 $dp$，$d{p}_i$ 表示 跑完第 $i$ 圈的最短时间，则有：
$$d{p}_i=\underset{j=0}{\overset{i?1}{\min }}(d{p}_j+changeTime+op{t}_{i?j});$$

$op{t}_c$ 表示连续跑完 $c$ 圈不换胎的最短时间。考虑到 $changeTime$ 的取值上限为 $1e5$，$r$ 的最小取值为 $2$。又有 $2^{1}8>1e5$，因此 $c$ 的上限可取 18。

另外，需要注意计算过程中由圈数过大引起的溢出问题，对于超出 int32_t 的情形，可通通用 INT_MAX 代替。因为 $changeTime$ 远小于该值，这种情形一定不会比其他换胎的策略更优。

class Solution {
public:
    int64_t dp[1001] = {0};

    bool check(int f, int r, int64_t x, int c, int64_t now) {
        int64_t v = c;
        for (int i = 1; i <= x; i++) {
            int64_t s = f;
            for (int j = 1; j < i; j++) {
                if (v+s >= now) return false;
                s *= r;
            }
            v += s;
            if (v >= now) return false;
        }
        return v < now;
    }

    int64_t cal(int f, int r, int x) {
        int64_t v = 0;
        for (int i = 1; i <= x; i++) {
            int64_t s = f;
            for (int j = 1; j < i; j++) {
                s *= r;
                if (s > INT_MAX) { return INT_MAX; }
            }
            v += s;
            if (v > INT_MAX) { return INT_MAX; }
        }
        return v;
    }

    int minimumFinishTime(vector<vector<int>>& tires, int changeTime, int numLaps) {
        int opt[18] = {0};
        for (int i = 1; i < 18; i++) {
            int o = 0;
            for (int j = 0; j < tires.size(); j++) {
                int64_t a = cal(tires[j][0], tires[j][1], i);
                int64_t b = cal(tires[o][0], tires[o][1], i);
                if (a < b) {
                    o = j;
                }
            }
            opt[i] = o;
        }
        memset(dp, -1, sizeof(dp));
        dp[0] = -changeTime;
        for (int i = 0; i <= numLaps; i++) {
            for (int j = 1; j < 18; j++) {
                if (i+j <= numLaps) {
                    if (dp[i+j] == -1 || check(tires[opt[j]][0], tires[opt[j]][1], j, changeTime+dp[i], dp[i+j])) {
                        dp[i+j] = dp[i] + changeTime + cal(tires[opt[j]][0], tires[opt[j]][1], j);
                    }
                }
            }
        }
        return dp[numLaps];
    }
};