2185. 统计包含给定前缀的字符串
题意
返回 words 中以 pref 作为 前缀 的字符串的数目。
思路
words的数据范围为100，遍历words里的每个字符串，用substr函数判断前缀是否跟pref相等即可。时间复杂度O ( n )
代码
class Solution { public: int prefixCount(vector<string>& words, string pref) { int ans=0; for(string t:words){ int len=pref.size(); if(t.size()>=len){ //cout<<t.substr(0,len)<<endl; if(t.substr(0,len)==pref) ans++; } } return ans; } };
2186. 使两字符串互为字母异位词的最少步骤数
题意
给你两个字符串 s 和 t 。在一步操作中，你可以给 s 或者 t 追加 任一字符 。
返回使 s 和 t 互为 字母异位词 所需的最少步骤数。字母异位词 指字母相同但是顺序不同（或者相同）的字符串
字符串长度为2e5，且都由小写字母构成
思路
考虑到只有26个小写字符，可以先用数组分别记录s,t中每个字母出现的次数，然后再遍历26个字母，两者的差值就是使得s,t里该字母个数相同的最小次数，因为再增加多的也没有意义了。
时间复杂度就是O(n)
代码
class Solution { public: int minSteps(string s, string t) { int ans=0; int mps[30],mpt[30]; for(int i=0;i<30;i++) mps[i]=mpt[i]=0; for(int i=0;i<s.size();i++) mps[s[i]-'a']++; for(int i=0;i<t.size();i++) mpt[t[i]-'a']++; for(int i=0;i<26;i++){ ans=ans+abs(mps[i]-mpt[i]); } return ans; } };
2187. 完成旅途的最少时间
题意
给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。
每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。
给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。
1 <= time.length <= 1e5
1 <= time[i], totalTrips <= 1e7
思路
首先，答案是具有单调性的。如果当前时间可行的话，那么更长时间也可以完成旅途，短时间就不会完成旅途。所以可以对答案进行二分。
二分的上界为旅行的趟数乘以旅途时间的最小值。
二分的check函数：遍历每辆公交车，二分的是花费的时间，对于第i辆公交车来说，完成旅途的次数就是m i d / t i m e i，然后累计和，判断是否大于等于给出的旅途次数就可以了。中间for循环就可以进行判断，算是一个小优化。
过程中会爆int，所以要随时注意转成long long
代码
class Solution { public: bool check(long long mid,vector<int>time,int totalTrips){ long long res=0; for(int t:time){ res=res+mid/(1ll*t); if(res>=totalTrips) return true; } return res>=totalTrips; } long long minimumTime(vector<int>& time, int totalTrips) { sort(time.begin(),time.end()); long long l=0ll,r=1ll*totalTrips*time[0],ans=0; while(l<=r){ long long mid=(l+r)/(2ll); //cout<<l<<" "<<r<<" "<<mid<<endl; if(check(mid,time,totalTrips)){ ans=mid;//还可以更少 r=mid-1; } else{ l=mid+1; } } return ans; } }; /* [10000] 10000000 */
2188. 完成比赛的最少时间
题意
给你一个下标从 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 秒 换成 任意一种轮胎（也可以换成当前种类的新轮胎）。
请你返回完成比赛需要耗费的 最少 时间。
思路
知道是dp但是没想出上界。
记n u m [ i ]表示同一个轮胎连续跑i圈的最小耗时，遍历每个轮胎，计算出来当前轮胎连续跑i圈的最小耗时，然后跟n u m [ i ]取m i n。
定义d p [ i ]为跑i圈的最小耗时，初始化就是d p [ 0 ] = 0 ，表示跑0圈的时间为0.
然后枚举最后一个轮胎连续跑了j圈，根据上文分析，j的最大值为m i n ( i , 17 )。那么之前的轮胎的耗时就是d p [ i − j ]，最后一个轮胎耗时为n u m [ j ]，更换轮胎的花费为c h a n g e T i m e。
转移为d p [ i ] = m i n ( d p [ i ] , d p [ i − j ] + n u m [ j ] + c h a n g e T i m e ) ;
最后的答案为d p [ n u m s L a p s ] − c h a n g e T i m e，因为第一个轮胎实际上是不换的。
时间复杂度为O ( n )
代码
class Solution { public: int minimumFinishTime(vector<vector<int>>& tires, int changeTime, int numLaps) { int n=tires.size(); int num[20]; memset(num,0x3f/2,sizeof num); for(auto now:tires){ long long f=1ll*now[0]; int idx=1,sum=0; while(f<=changeTime+now[0]){ sum=sum+f; num[idx]=min(num[idx],sum); f=f*now[1]; idx++; } } int dp[numLaps+1]; memset(dp,0x3f,sizeof dp); dp[0]=0; for(int i=1;i<=numLaps;i++){ for(int j=1;j<=min(i,17);j++){ dp[i]=min(dp[i],dp[i-j]+num[j]+changeTime); } } return dp[numLaps]-changeTime; } };
