首页 > 笔经面经 > 阿里笔试(更新到3.30)附全5场笔试代码

阿里笔试(更新到3.30)附全5场笔试代码

头像
卖报人 #阿里笔试#
编辑于 2020-04-01 22:02:49 APP内打开
赞 14 | 收藏 102 | 回复5 | 浏览5009
前情提要:自己参加了3.23场,其他场次根据讨论区的描述写的代码,如果题目理解有误或者有其他方面的指导,请各位留言指导,我也会更新优化~
附每一场的代码:
3.20场:
3.23场:
3.25场:
3.27场:
微软3.25场:(这个题思路上还希望有人能以一起讨论一下)
————————————————————————————————————————
3.30场,同样是参考了讨论区的题目和方法,以下代码思路应该没问题,但由于不知道数据的具体要求和输入要求,如有问题还请指正,谢谢~
第一题:N个养鸡场,每个鸡场有Ni只鸡,每天每个鸡场增加K只鸡,每天结束时卖掉鸡最多的那个场的所有鸡的一半,求M天后剩余鸡总数:
/*
 第1题:模拟,采用优先队列来执行整个过程,时间复杂度O(mlogn)
 首先构造优先队列(大顶堆),维护M次即可。
 注意:每次我们只需要维护队头元素,而不需要对所有元素都在每次循环中都更新数据
 每次队头元素出队,值改为(当前值-当前是第几天*每天的增长量)/2(实际上这个更新是相对大小的更新)
 */

#include<iostream>
#include<queue>
using namespace std;

int resud(priority_queue<int, vector<int>, less<int> > pq, int n, int m, int k) {
    int i, tmp;
    int res = 0;
    for(i = 0; i < m; i++) {
        tmp = (pq.top() - (i+1)*k);
        if(tmp < 0 && tmp%2 != 0) {
            tmp = tmp/2 - 1;
        }
        else {
            tmp = tmp/2;
        }
        pq.pop();
        pq.push(tmp);
    }
    
    for(i = 0; i < n; i++) {
        res = res + pq.top();
        pq.pop();
    }
    return res + n*m*k;
}

int main() {
    int n,m,k;
    cin>>n>>m>>k;
    priority_queue<int, vector<int>, less<int> > pq;
    
    int i;
    int tmp;
    
    for(i = 0; i < n; i++) {
        cin>>tmp;
        pq.push(tmp);
    }
    cout<<resud(pq, n, m, k)<<endl;
    return 0;
}
第二题:对一个数字串,等概率取任意一段连续子串,求取出的子串的最大值的期望。
/*
问题转化为计算每个连续子串中的最大值,用栈的方法,时间、空间均O(n)复杂度
dp[i]:标明所有以v[i]为串尾的子串的最大值的和 (简单可知,dp[i]是i+1个子串最大值的和)
用栈来记录情况如下:
   对于v[i],我们让栈元素依次弹出,直到找到比v[i]大的元素:
   如果栈空了,证明v[i]为串尾的所有串的最大值都是v[i],所以dp[i] = (i+1)*v[i];
   如果栈没空,假设此时栈顶元素对应v[j],则对串k~i,如果k<=j,则这些串的最大值的和和dp[j]一致;
   如果k>j,则这些串的最大值为v[i],加起来即可
串总数是(1+n)*n/2,只要把所有dp加起来除以总数就可以了
*/

#include<iostream>
#include<iomanip>
#include<stack>
#include<vector>
using namespace std;

struct prs {
    int val;
    int ord;
};

double calE (vector<int> v) {
    if(v.empty()) {
        return 0;
    }
    
    stack<prs> s;
    prs ptmp;
    ptmp.val = v[0];
    ptmp.ord = 0;
    s.push(ptmp);
    
    double dp[v.size()];
    dp[0] = v[0];
    int i;
    double res = v[0];
    
    for(i = 1; i < v.size(); i++) {
        while(!s.empty() && v[i] >= s.top().val) {
            s.pop();
        }
        if(s.empty()) {
            dp[i] = (i+1)*v[i];
        }
        else {
            dp[i] = (i - s.top().ord)*v[i] + dp[s.top().ord];
        }
        res = res + dp[i];
        
        ptmp.val = v[i];
        ptmp.ord = i;
        s.push(ptmp);
    }
    return res/double((v.size()+1)*v.size()/2);
}

int main() {
    int n;
    cin>>n;
    vector<int> v;
    
    int i, tmp;
    for(i = 0; i < n; i++) {
        cin>>tmp;
        v.push_back(tmp);
    }
    
    cout.setf(ios::fixed);
    cout<<fixed<<setprecision(6)<<calE(v)<<endl;
    return 0;
}

5条回帖

回帖
加载中...
话题 回帖

推荐话题

相关热帖

笔经面经近期热帖

近期精华帖

热门推荐