Leetcode第282次周赛解题报告

老样子 动态规划继续卡

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

知识点：模拟
效率：$O(n^2)$Search效率，如果自己写匹配可以降低到$O(n)$
按照题意，只需要搜索一下有几个单词前缀为目标单词

/**
 * @param {string[]} words
 * @param {string} pref
 * @return {number}
 */
var prefixCount = function(words, pref) {
    let ans = 0
    words.forEach((x)=>ans+=(x.search(pref)==0))
    return ans
};

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

知识点：模拟
效率：$O(n)$
根据题意，统计两个字符串不同的字符的个数

class Solution {
public:
    int minSteps(string s, string t) {
        vector<int> cnt('z'-'a'+2,0);
        vector<int> cnt1('z'-'a'+2,0);
        for(auto i:s) cnt[i-'a']++;
        for(auto i:t) cnt1[i-'a']++;
        int ans = 0;
        for(int i = 'a';i <= 'z';i++) {
            int idx = i-'a';
            ans += abs(cnt[idx]-cnt1[idx]);
        }
        return ans;
    }
}

6010. 完成旅途的最少时间

知识点：二分
效率：$O(nlogn)$
这个题的坑点是不知道到底右区间是多少，因此采用级数扩大的方式查找右区间。
赛场上拍了一个小时，以为是方法做错了，结果发现是取值范围的问题。

他让找最小满足的数，一般找最小满足的都可以用二分。
让l在不满足的一侧，r在满足的一侧，然后通过不断求值的方式进行更新即可，最小满足条件的点即为二分查找的结果。

class Solution {
public:
    long long minimumTime(vector<int>& time, int totalTrips) {
        if(totalTrips == 0) return 0;
        sort(time.begin(),time.end());
        vector<pair<long long,long long>> stat;
        pair<long long,long long> last = {time[0],0};
        for(auto i : time){
            if(last.first==i) last.second++;
            else{
                stat.push_back(last);
                last = {i,1};
            }
        }
        stat.push_back(last);
        auto cal = [&stat](long long time)->long long{
            long long ans = 0;
            for(auto &[v,n] : stat) {
                if(v > time) break;
                ans += n*(time/v);
            }
            return ans;
        };
        long long l = 0,r = last.first;
       // cout << l << " " << r << endl;
        bool flag = false;
        bool flag1 = false;
        while(true) {
            while(!flag) {
                long long rr = cal(r);
                  if(rr < totalTrips) {
                    l=r,r *= 10;
                    continue;
                }
                else flag = true;
            }
            
            //cout << l << " " << r << endl;
            long long m = (l+r) / 2;
            long long mm = cal(m);
            cout << l << " " << r << " " << m << " "<< mm << endl;
            if(mm < totalTrips){
                l = m + 1;
            }else { // mm >= 
                r = m - 1;
            }
            if(l >= r) {
                if(cal(l)>= totalTrips) return l;
                if(cal(l+1)>= totalTrips) return l+1;
            }
        }
        return r;
    }
};

6011. 完成比赛的最少时间

知识点：动态规划、枚举
效率：$O(n)$
这个题最重要的是枚举，即预处理状态。
我在比赛的时候是没有想到要预处理状态的，最核心的问题是没有看到轮胎可以重复选的设定。
枚举：跑[1,20]圈内最少需要的时间，把所有的轮胎拿过来计算cost，取min即可。
枚举边界的确定：因为2^20就已经非常大了，所以可以非常确定的说，枚举肯定在20圈以内，是一个常数级。
假如能够理解枚举，那剩下的就很简单了，无非是怎么选的问题，是一个裸的动态规划。
可惜我没想到要枚举。

class Solution {
public:
    int minimumFinishTime(vector<vector<int>>& tires, int changeTime, int numLaps) {
        vector<long long> dp(max(21,numLaps+1),1e10);
        vector<long long> minTrie(21,1e10);
        minTrie[0] = 0;
        for(auto i : tires) {
            long long now = 0;
            for(long long j = 1;j <= 19;j++) {
                long long x = i[0] * pow(i[1],j-1);
                now += x;
                if(now > 1e10) break;
                minTrie[j] = min(minTrie[j],now);
            }
        }
        dp[0] = 0;
        for(int i = 1;i <= 19;i++) {
            cout << minTrie[i] << " ";
        }
        cout << endl;
        for(int i = 1;i <= numLaps;i++) {
            for(int j = 1;j <= 19;j++) {
                //cout << i << " " << j << endl;
                if(i-j > 0) {
                    dp[i] = min(dp[i],dp[i-j]+minTrie[j]+changeTime);
                } else if(i-j == 0) {
                    dp[i] = min(dp[i],dp[i-j]+minTrie[j]);
                }
            }
            //cout <<dp[i] << " ";
        }
        //cout << endl;
        //2 6 14 18 25

        return dp[numLaps];
    }
};