阿里笔试3.27场（附两题代码和前三场代码链接）
前情提要：自己参加了3.23场，其他场次根据讨论区的描述写的代码，如果题目理解有误或者有其他方面的指导，请各位留言指导，我也会更新优化~
附每一场的代码：
3.20场：
3.23场：
3.25场：
附微软3.25场讨论（这个题思路上还希望有人能以一起讨论一下）：
——————————————————————————————————————————————————
3.27场：
继续是从讨论区看题目，自己写代码，因此不了解具体输入输出要求和数据范围，也不保证AC，只供讨论：
第一题：给定字符串s1,s2，求从s1变为s2的最小移动次数（要求每一次只能从s1选取任意一个字符放到s1最后）
/*
参考了讨论区大佬的思路，这道题实质上是求s1中能匹配s2的最长前缀，
剩下未匹配的字符只需要按照s2的顺序依次移动即可
时间复杂度：O(n)
*/
#include<iostream>
#include<string>
using namespace std;
//检查s1是否可以变为s2
bool check(string s1, string s2) {
if(s1.length() != s2.length()) {
return 0;
}
long long rec[26] = {0};
long long i;
for(i = 0; i < s1.length(); i++) {
rec[s1[i] - 'a']++;
}
for(i = 0; i < s2.length(); i++) {
rec[s2[i] - 'a']--;
if(rec[s2[i] - 'a'] < 0) {
return 0;
}
}
return 1;
}
long long minchange(string s1, string s2) {
if(check(s1,s2) == 0) {
return -1;
}
long long i, cc = 0;
for(i = 0; i < s1.length(); i++) {
if(s1[i] == s2[cc]) {
cc++;
}
}
return s2.length() - cc;
}
int main() {
string sori, star;
cin>>sori;
cin>>star;
cout<<minchange(sori, star)<<endl;
return 0;
} (更新：按照题目的输入要求做了更新，方法不变）
第二题：给定N个区间（范围1~2000），每个区间包含左右范围（1<=L<=R<=2000），每次从所有区间范围内选择一个整数，求所有选出的数的最小值的期望。 #include<iostream>
#include<iomanip>
#include<vector>
#include<math.h>
using namespace std;
struct prs {
int l;
int r;
};
void range(vector<prs> &v, int &rangel, int &ranger) {
int i;
rangel = 2000;
ranger = 2000;
for(i = 0; i < v.size(); i++) {
ranger = min(ranger, v[i].r);
}
i = 0;
while(i < v.size()) {
if(v[i].l > ranger) {
v.erase(v.begin()+i, v.begin()+i+1);
}
else {
rangel = min(rangel, v[i].l);
i++;
}
}
return;
}
vector<double> ps(vector<prs> &v, int rangel, int ranger) {
vector<double> p;
int i, j;
double tmp = 1;
vector<double> vlen;
for(j = 0; j < v.size(); j++) {
vlen.push_back(double(v[j].r - v[j].l + 1));
}
for(i = ranger; i >= rangel; i--) {
for(j = 0; j < v.size(); j++) {
if(v[j].l < i) {
tmp = tmp * double((v[j].r - i + 1))/vlen[j];
}
}
p.push_back(tmp);
tmp = 1;
}
for(i = int(p.size()-1); i > 0; i--){
p[i] = p[i] - p[i-1];
}
return p;
}
double calE(vector<double> &p, int rangel, int ranger) {
int i;
double E = 0;
for(i = 0; i < p.size(); i++) {
E = E + (ranger - i)*p[i];
}
return E;
}
int main() {
int N;
cin>>N;
prs tmp;
vector<prs> v;
int rangel, ranger;
int i;
vector<double> p;
//按照实际题目的要求，更新了一下
/*
for(i = 0; i < N; i++) {
cin>>tmp.l>>tmp.r;
v.push_back(tmp);
}
*/
for(i = 0; i < N; i++) {
cin>>tmp.l;
v.push_back(tmp);
}
for(i = 0; i < N; i++) {
cin>>v[i].r;
}
range(v, rangel, ranger);
p = ps(v, rangel, ranger);
cout.setf(ios::fixed);
cout<<fixed<<setprecision(6)<<calE(p, rangel, ranger)<<endl;
return 0;
} 
查看30道真题和解析
