每日算法题:Day 11

admin 2019-8-11 15:33 115人围观 C++相关

点击上方“算法工程师之路”，选择“星标”公众号

重磅干货，第一时间送达

作者：TeddyZhang，公众号：算法工程师之路

Day 11, 概率统计知识点走起~

编程题
【剑指Offer】栈的压入，弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

思路：
在这个题目中由于是判断压入序列和弹出序列是不是一个堆栈真正的过程，那么思路就很简单了，使用一个堆栈去模拟这个过程不就好了！

首先遍历pushV,堆栈tmp压入每一个元素，在压入的同时需要判断需不需要将这个元素弹出呢？判断方法为：tmp的栈顶和popV数组中的元素是否一样，如果一样就弹出，注意这个弹出过程需要进行循环判断（可能一次弹出多个数）！最后通过判断tmp栈是否为空即可得到结果！

class Solution {
public:
    bool IsPopOrder(vector<int> pushV, vector<int> popV) {
        if(pushV.size() == 0) return false;
        stack<int> tmp;
        int j = 0;    // popV的索引
        for(auto i: pushV){
            tmp.push(i);
            // 判断栈顶是否
            while(j < popV.size() && tmp.top() == popV[j]){
                tmp.pop();
                j++;
            }
        }
        return  tmp.empty();
    }
};

【剑指Offer】从上到下打印二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

思路：
此题目实为层次遍历，二叉树的遍历除了层次遍历外，还有先序，中序，后序遍历，之前的文章中讲的很详细了！

层次遍历需要队列来进行数据的储存！！！并且层次遍历的迭代版非常容易实现，自行看代码吧。

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<int> res;

         if(!root)
            return res;      //如果为空，则需要返回空vector
        queue<TreeNode *> tmp;
        tmp.push(root);

        while(!tmp.empty()){
            TreeNode* node = tmp.front();
            res.push_back(node->val);    //取出队头数据
            tmp.pop();
            if(node->left)
                tmp.push(node->left);
            if(node->right)
                tmp.push(node->right);
        }
        return res;
    }
};

2概念题
【概率统计】一个英雄基础攻击力为100，携带了三件暴击武器，武器A有40%的概率打出2倍攻击，武器B有20%的概率打出4倍攻击，武器C有10%概率打出6倍攻击，各暴击效果触发是独立事件，但是多个暴击效果在一次攻击中同时触发时只有后面武器的暴击真正生效，例如一次攻击中武器A判定不暴击，武器B和武器C都判定触发暴击，那么这次攻击实际是600攻击力。那么这个英雄攻击力的数学期望是？

使用武器C：600 * 10%
使用武器B：保证武器C不使用：400 * 90% * 20%
使用武器A：保证武器B和C不使用：200 * 90% * 80% * 40%
什么武器都不用：100 * 60% * 80% * 90%
相加后得到最终的攻击期望为：232.8

【概率统计】假设某个广告展现后被点击的概率是1/3（实际远小于这个数，只是为方便计算），那该广告3次展现，被点击次数少于2次的概率是?

点击0次：C(3,0)(2/3)^3=8/27
点击1次：C(3,1)(2/3)^2*(1/3) = 12/27
相加之和为20/27，约为0.74

【概率统计】某单位组织党员参加党史，党风廉政建设，科学发展观和业务能力四项培训，要求每名党员参加且只能参加其中的两项，无论如何安排，都至少有 5 名党员参加的培训完全相同，请问该单位至少有多少名党员？

4门课程，每人选2门，有6中选法；此时根据抽屉原理，将这6中选法想象为6个抽屉，在每个抽屉中放入4个党员，则有24名党员；此时，再多来一名党员，则无论将其安排在哪个抽屉，6个抽屉中都必有一个里面装的是5名党员。所以，该机关至少有24+1=25名党员

【概率统计】如果在高速公路上30分钟内看到车开过的几率是0.95，那么在10分钟内看到车开过的几率是多少?

泊松分布是单位时间内独立事件发生次数的概率分布，主要用途是：

某人一天收到的微信数量
来到某公共汽车站的乘客数
某放射性物质发出的粒子
显微镜下某区域中的白血球

指数分布是独立事件的时间间隔的概率分布，主要应用为：

旅客进机场的时间间隔
中文维基百科新条目出现的时间间隔
在排队论中，一个顾客接受服务的时间长短

因此这个题目可以使用泊松分布求解，t=30时，1-P(N(30)=0)=0.95，求出1-P(N(10)=0)=0.6316。
也可以用另外一种假设的方法，假设十分中内没有看到车的几率是X，则30分钟都没有看到车的几率是X^3,求得X，然后得到最后结果！
3

资源分享

欢迎关注我的个人公众号（算法工程师之路），公众号内有大量视频资料和电子书资料以及算法笔记，回复关键字即可获取！

公众号简介：分享算法工程师必备技能，谈谈那些有深度有意思的算法，主要范围：C++数据结构与算法/深度学习（CV），立志成为Offer收割机！坚持分享算法题目和解题思路（Day By Day)

号外，算法刷题群已经建立，但由于人数超出限制，无法扫码添加，可以加号主微信（Leopard7319538）说明来意，可以加入到算法刷题群，每天2道编程题3道概念题，晚9点打卡，我们一起坚持下去！！！已经300人加入啦~

完

▼ 更多精彩推荐，请关注我们 ▼

长按二维码关注算法工程师之路

算法工程师

我们一起努力，For World!

undefined

在看点这里

----------------------------------------------------------------------------------------------------------------------
我们尊重原创，也注重分享，文章来源于微信公众号：算法工程师之路，建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------