阿里笔试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;
}
#阿里笔试##阿里巴巴##笔试题目##实习##笔经#
全部评论
大佬nb,我只在完成了第一题minchange()部分,-1情况还没考虑清楚就没时间了
1 回复
分享
发布于 2020-03-28 19:00
第一题不是应该先输有几个字符串吗?不是固定只能输两个字符串吧
点赞 回复
分享
发布于 2020-03-28 21:03
小红书
校招火热招聘中
官网直投
第二题精度要求好像是e-6
点赞 回复
分享
发布于 2020-03-28 21:09
第二题样例大佬你的也没通过,应该是1.8333333
点赞 回复
分享
发布于 2020-03-28 21:34
这是要逼死我们哈~~~建议在下一场前3小时发,否则估计又要连夜换题:)
点赞 回复
分享
发布于 2020-03-29 22:18
你第一题做的有问题,如果字符串B的第一个字符在字符串A的末尾,你的程序就完蛋了,找最大匹配长度不能从头开始查,应该在字符串B的每一个字符开始都要查找一次,留最大相同次序
点赞 回复
分享
发布于 2020-03-30 15:22
def calp(index,l,r): 计算所有区间都大于等于index的概率     pi=1     for i in range(len(l)):         lennums=r[i]-l[i]+1         if r[i]<index:             return 0          elif index<l[i]:             pass         else:             temp=(r[i]-index+1)/lennums              pi*=temp     return pi def cal_index_p(index,l,r): 计算index为最小值的概率     return (calp(index,l,r)-calp(index+1,l,r)) def cal_e(n,l,r):     min_num=min(l)     max_num=max(r)     res=0     for i in range(min_num,max_num+1):         res+=cal_index_p(i,l,r)*i     return res
点赞 回复
分享
发布于 2020-03-30 16:48

相关推荐

4 38 评论
分享
牛客网
牛客企业服务