第一题
代码语言：javascript复制class Solution {
public:
int findLucky(vector<int>& arr) {
sort(arr.begin(),arr.end());
int times = 1;
int num = arr[0];
int ans=-1;
int anstime = 0;
for(int i=1;i<arr.size();i )
{
if(arr[i]!=arr[i-1])
{
if(times == num)
{
if(anstime <= times)
{
anstime = times;
ans = num;
}
}
times = 1;
num = arr[i];
}
else
{
times ;
}
}
if(times == num)
{
if(anstime <= times)
{
anstime = times;
ans = num;
}
}
return ans;
}
};第二题
代码语言：javascript复制class Solution {
public:
int dp[205];
int numTeams(vector<int>& rating) {
for(int i=0;i<rating.size();i )
{
dp[i]=0;
for(int j=i-1;j>=0;j--)
{
if(rating[i]>rating[j])
dp[i] ;
}
}
int ans=0;
for(int i=0;i<rating.size();i )
{
for(int j=i-1;j>=0;j--)
{
if(rating[i]>rating[j])
{
if(dp[j]!=0)
{
ans =dp[j];
}
}
}
}
for(int i=0;i<rating.size();i )
{
dp[i]=0;
for(int j=i-1;j>=0;j--)
{
if(rating[i]<rating[j])
dp[i] ;
}
}
for(int i=0;i<rating.size();i )
{
for(int j=i-1;j>=0;j--)
{
if(rating[i]<rating[j])
{
if(dp[j]!=0)
{
ans =dp[j];
}
}
}
}
return ans;
}
};第三题
代码语言：javascript复制class UndergroundSystem {
public:
map<string,int> m;
map<int,int> m2;
map<int,int> m3;
map<pair<int,int>,double>m4;
map<pair<int,int>,int> m5;
int pos=1;
UndergroundSystem() {
m.clear();
m2.clear();
m3.clear();
m4.clear();
m5.clear();
}
void checkIn(int id, string stationName, int t) {
if(!m[stationName])
{
m[stationName] = pos ;
}
m2[id] = m[stationName];
m3[id] = t;
}
void checkOut(int id, string stationName, int t) {
int startStation = m2[id];
int startTime = m3[id];
if(!m[stationName])
{
m[stationName] = pos ;
}
int endStation = m[stationName];
pair<int,int> p = make_pair(startStation,endStation);
double sum = m4[p] * m5[p];
m4[p] = (sum 1.0*(t-startTime))/(m5[p] 1);
m5[p] ;
}
double getAverageTime(string startStation, string endStation) {
int start = m[startStation];
int end = m[endStation];
return m4[make_pair(start,end)];
}
};
/**
* Your UndergroundSystem object will be instantiated and called as such:
* UndergroundSystem* obj = new UndergroundSystem();
* obj->checkIn(id,stationName,t);
* obj->checkOut(id,stationName,t);
* double param_3 = obj->getAverageTime(startStation,endStation);
*/第四题
数位DP，之前没有接触过，这次学了一下数位DP
代码语言：javascript复制#define MAX (int)(1e9 7)
class Solution {
public:
long long dp[505][55];
int next[55];
int digit[505];
string evil2;
int findGoodStrings(int n, string s1, string s2, string evil) {
evil2 = evil;
KMP(evil);
long long ans1 = DigitDP(s2);
long long ans2 = DigitDP(s1);
long long ans = (((ans1-ans2)%MAX) MAX)%MAX;
if (s1.find(evil) == std::string::npos)
return ans 1;
else
return ans;
}
void KMP(string evil)
{
next[0]=0;
for(int i=1;i<evil.length();i )
{
int k = next[i-1];
while(k!=0 && evil[i]!=evil[k])
{
k = next[k-1];
}
if(evil[i]==evil[k])
next[i]=k 1;
else
next[i]=0;
}
}
long long DigitDP(string s)
{
memset(digit,0,sizeof(digit));
memset(dp,0,sizeof(dp));
for(int i=0;i<s.length();i )
{
digit[s.length()-i-1] = s[i]-'a';
}
return dfs(s.length()-1,0,1);
}
long long dfs(int pos,int state,int op)
{
if(state==evil2.length())
return 0;
if(pos==-1) return 1;
if(!op && dp[pos][state]) return dp[pos][state];
int maxx = op?digit[pos]:25;
long long res=0;
for(int i=0;i<=maxx;i )
{
int k= state;
while(k && i!=evil2[k]-'a')
{
k = next[k-1];
}
if(i==evil2[k]-'a')
k = k 1;
else
k = 0;
res = dfs(pos-1,k,op && i==maxx);
}
res %= MAX;
if(!op)
dp[pos][state]=res;
return res;
}
};
