玖的数学&算法录
0%

第282场周赛解答

发表于
本文字数： 4.5k 阅读时长 ≈ 4 分钟

第282场周赛

链接↓

第282场周赛

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

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

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

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

示例 1：

1
2
3
输入：words = ["pay","attention","practice","attend"], pref = "at"
输出：2
解释：以 "at" 作为前缀的字符串有两个，分别是："attention" 和 "attend" 。

示例 2：

1
2
3
输入：words = ["leetcode","win","loops","success"], pref = "code"
输出：0
解释：不存在以 "code" 作为前缀的字符串。

提示：

  • 1 <= words.length <= 100
  • 1 <= words[i].length, pref.length <= 100
  • words[i] 和 pref 由小写英文字母组成

分析：根据题目意思

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int prefixCount(vector<string>& words, string p) {
    int ans=0;
    string res;
    for(int i=0;i<words.size();i++)
        res+=(words[i]+" ");
    istringstream ss(res);
    string str;
    for (int i = 1; ss >> str; i ++)
            if (str.find(p) == 0) ans++;
        return ans;
    }
};

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

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

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

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

示例 1：

1
2
3
4
5
6
7
8
输入：s = "leetcode", t = "coats"
输出：7
解释：
- 执行 2 步操作，将 "as" 追加到 s = "leetcode" 中，得到 s = "leetcodeas" 。
- 执行 5 步操作，将 "leede" 追加到 t = "coats" 中，得到 t = "coatsleede" 。
"leetcodeas" 和 "coatsleede" 互为字母异位词。
总共用去 2 + 5 = 7 步。
可以证明，无法用少于 7 步操作使这两个字符串互为字母异位词。

示例 2：

1
2
3
输入：s = "night", t = "thing"
输出：0
解释：给出的字符串已经互为字母异位词。因此，不需要任何进一步操作。

提示：

  • 1 <= s.length, t.length <= 2 * 105
  • s 和 t 由小写英文字符组成

分析：

首先约定same为s字符串与t字符串的公共部分，

那么我们需要使用哈希表去计录s与t中元素出现的次数，

遍历一遍字母，去求两个字符串中出现同样的字母中字符串较少的数量。

根据题意我们知道s字符串是可以拆分成自己本身有的和公共same的，同样t字符串也是可以拆分成自己本身有的和公共same的，因此我们结果返回

$$result=s.size()+t.size()-2*same$$

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int minSteps(string s, string t) {
    int same=0;
    unordered_map<int,int> a,b;
    for(auto x:s) a[x]++;
    for(auto x:t) b[x]++;
    for(int i='a';i<='z';i++) same+=min(a[i],b[i]);
    return s.size()+t.size()-2*same;
    }
};

6010.完成旅途的最少时间

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

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

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

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：time = [1,2,3], totalTrips = 5
输出：3
解释：
- 时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。
  已完成的总旅途数为 1 + 0 + 0 = 1 。
- 时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。
  已完成的总旅途数为 2 + 1 + 0 = 3 。
- 时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。
  已完成的总旅途数为 3 + 1 + 1 = 5 。
所以总共完成至少 5 趟旅途的最少时间为 3 。

示例 2：

1
2
3
4
5
输入：time = [2], totalTrips = 1
输出：2
解释：
只有一辆公交车，它将在时刻 t = 2 完成第一趟旅途。
所以完成 1 趟旅途的最少时间为 2 。

提示：

  • 1 <= time.length <= 105
  • 1 <= time[i], totalTrips <= 107

分析：

由于每趟公交车之间是相互独立的，且time是单调递增的，因此如果需要时间尽可能少，那么我们考虑使用二分（左侧模板）。

特别注意

由于time[i]与totalTrips的上界是1e7，考虑最极端情况，若只有一趟车，每跑一趟需要1e7，需要1e7次，那么跑完需要时间1e14。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define ll long long
class Solution {
public:
        bool check(vector<int>& time,int k,ll m){
            ll cur=0;
            for(auto t:time){
                cur+=m/t;
                if(cur>=k) return true;
            }
            return cur>=k;
        }
        long long minimumTime(vector<int>& time, int k) {
            ll l=0,r=1e14;//<14都会被卡
            while(l<r){
                ll mid=l+r >> 1;
                if(check(time,k,mid)) r=mid;
                else l=mid+1;
            }
            return l;
    }
};

6011.完成比赛的最少时间

给你一个下标从 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 秒 换成 任意一种轮胎（也可以换成当前种类的新轮胎）。

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

示例 1：

1
2
3
4
5
6
7
8
9
输入：tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4
输出：21
解释：
第 1 圈：使用轮胎 0 ，耗时 2 秒。
第 2 圈：继续使用轮胎 0 ，耗时 2 * 3 = 6 秒。
第 3 圈：耗费 5 秒换一条新的轮胎 0 ，然后耗时 2 秒完成这一圈。
第 4 圈：继续使用轮胎 0 ，耗时 2 * 3 = 6 秒。
总耗时 = 2 + 6 + 5 + 2 + 6 = 21 秒。
完成比赛的最少时间为 21 秒。

示例 2：

1
2
3
4
5
6
7
8
9
10
输入：tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5
输出：25
解释：
第 1 圈：使用轮胎 1 ，耗时 2 秒。
第 2 圈：继续使用轮胎 1 ，耗时 2 * 2 = 4 秒。
第 3 圈：耗时 6 秒换一条新的轮胎 1 ，然后耗时 2 秒完成这一圈。
第 4 圈：继续使用轮胎 1 ，耗时 2 * 2 = 4 秒。
第 5 圈：耗时 6 秒换成轮胎 0 ，然后耗时 1 秒完成这一圈。
总耗时 = 2 + 4 + 6 + 2 + 4 + 6 + 1 = 25 秒。
完成比赛的最少时间为 25 秒。

提示：

  • 1 <= tires.length <= 105
  • tires[i].length == 2
  • 1 <= fi, changeTime <= 105
  • 2 <= ri <= 105
  • 1 <= numLaps <= 1000

分析：

通过遍历去统计最少花费多少时间， 用每一个轮胎去试试看，看一圈的最少时间。

后半段相当于完全背包问题，a表示物品，f表示价值

最后计算的时候由于第一次换轮胎是不需要时间的，因此减去一次换轮胎的时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#define ll long long
class Solution {
    int a[1001],f[1001];
public:
    int minimumFinishTime(vector<vector<int>>& tires, int c, int nn) {
        int n=tires.size();
        memset(a,127,sizeof(a));
        for(int i=0;i<n;i++){
            ll cur=tires[i][0],res=cur;
            for(int j=1;j<=20;j++){
                a[j]=min(1LL*a[j],res);
                cur*=tires[i][1];
                res+=cur;
                if(res>=1<<30) break;
            }
        }
        memset(f,127,sizeof(f));
        f[0]=0;
        for(int i=1;i<=20;i++){
            if(a[i]<1<<30)
                for(int j=0;j+i<=nn;j++){
                    if(f[j]<1<<30)
                        f[j+i]=min(f[j+i],f[j]+a[i]+c);
                }
        }
        return f[nn]-c;
    }
};