美团8.27笔试4A
[美团0827笔试]
第一题(100%)：字符串匹配，暴力破解
//
// Created by Harold on 2022/8/27/0027.
//
#include <iostream>
#include <string>
using namespace std;
class Solution{
private:
int n_S;
int m_s;
string S;
string s;
public:
void getInput(){
cin>>n_S>>m_s;
cin>>S>>s;
}
void getAns(){
int count = 0;
for(int i = 0; i < n_S; i++){
int index_S = i;
int index_s = 0;
while(index_s < m_s){
if(s[index_s] != '*'){
if(S[index_S] == s[index_s]){
index_S++;
index_s++;
}
else{
break;
}
}
else{
index_S++;
index_s++;
}
}
if(index_s >= m_s){
count++;
}
}
cout<<count;
}
void run(){
getInput();
getAns();
}
};
int main(){
Solution s;
s.run();
return 0;
} 第二题(100%)：使用链表模拟交换过程 //
// Created by Harold on 2022/8/27/0027.
//
#include <iostream>
#include <list>
#include <vector>
using namespace std;
class Solution{
private:
int n_num;
int m_opt;
vector<int> optList;
public:
void getInput(){
cin>>n_num>>m_opt;
vector<int> temp(m_opt);
for(int i = 0; i < m_opt; i++){
cin>>temp[i];
}
optList = temp;
}
void getAns(){
list<int> numsList;
for(int i = 1; i <= n_num; i++){
numsList.push_back(i);
}
for(int i = 0; i < m_opt; i++){
int index = optList[i];
auto realIndex = numsList.begin();
for(auto it = numsList.begin(); it != numsList.end(); it++){
if(*it == index){
realIndex = it;
break;
}
}
numsList.erase(realIndex);
numsList.push_front(index);
}
for(int item : numsList){
cout<<item<<" ";
}
}
void run(){
getInput();
getAns();
}
};
int main(){
Solution s;
s.run();
return 0;
} 第三题(100%)：分割字符串问题，整体使用回溯，使用map记录需要得到的子串并计数，每划分出符合的子串查一下map看计数是否还有剩余 //
// Created by Harold on 2022/8/27/0027.
//
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
class Solution{
private:
int n,m;
string S;
vector<int> length;
vector<string> subStr;
unordered_map<string,int> mp;
int count = 0;
public:
void getInput(){
cin>>n>>m;
cin>>S;
vector<int> l(m,0);
for(int i = 0; i < m; i++){
cin>>l[i];
}
length = l;
vector<string> s(m);
for(int i = 0; i < m; i++){
cin>>s[i];
}
subStr = s;
}
void getAns(){
for(int i = 0; i < m; i++){
mp[subStr[i]]++;
}
backtracking(0);
cout<<count;
}
void backtracking(int index){
if(index >= S.size()){
count++;
return;
}
for(int i = index; i < n; i++){
string sub = S.substr(index,i-index+1);
if(mp.find(sub) != mp.end()){
if(mp[sub] > 0){
mp[sub]--;
backtracking(i+1);
mp[sub]++;
}
}
}
}
void run(){
getInput();
getAns();
}
};
int main(){
Solution s;
s.run();
return 0;
} 第四题：没时间做了 第五题(100%)：贪心策略，每次碰见猫猫检查是否有玩具，有玩具的话先找出花费时间最小的玩具，再判断使用该玩具是否更省时间，没有玩具总时间加T
//
// Created by Harold on 2022/8/27/0027.
//
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n,k,T;
cin>>n>>k>>T;
vector<int> toys_time(k+1,0);
vector<int> hadToys;
for(int i = 1; i <= k; i++){
cin>>toys_time[i];
}
int count_time = 0;
for(int i = 0; i < n; i++){
int temp;
int getTime;
cin>>temp;
if(temp > 0){
getTime = toys_time[temp];
hadToys.push_back(getTime);
}
else{
if(hadToys.empty()){
count_time += T;
}
else{
int minIndex = 0;
for(int j = 0; j < hadToys.size(); j++){
if(hadToys[j] < hadToys[minIndex]){
minIndex = j;
}
}
int minCost = hadToys[minIndex];
if(minCost < T){
count_time += minCost;
hadToys.erase(hadToys.begin()+minIndex);
}
else{
count_time += T;
}
}
}
}
cout<<count_time;
return 0;
} 
