每日算法题：Day 18（概率统计）
作者：TeddyZhang，公众号：算法工程师之路
Day 18, 概率统计知识点走起~
1
编程题
【剑指Offer】数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007 输入描述: 题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4 对于%75的数据,size<=10^5 对于%100的数据,size<=2*10^5
思路： 此答案只能通过50%，待解决！！！使用归并排序，在合并的同时确定逆序对的个数。大佬帮帮忙解决下！
class Solution {
public:
long long merge(vector<int>& list, long long L, long long mid, long long R){
vector<int> help(R-L+);
long long i = , p1 = L, p2 = mid+, res = ;
while(p1 <= mid && p2 <= R){
res += list[p1] > list[p2] ? (mid-p1+) : ;
help[i++] = list[p1] < list[p2] ? list[p1++] : list[p2++];
}
while(p1 <= mid){
help[i++] = list[p1++];
}
while(p2 <= R){
help[i++] = list[p2++];
}
for(i = ;i < help.size(); i++){
list[L+i] = help[i];
}
res %= ;
return res;
}
long long sortProcess(vector<int>& list, long long L, long long R){
if(L == R) return ;
long long mid = L + (R-L)/;
return sortProcess(list, L, mid) +
sortProcess(list, mid+, R) +
merge(list, L, mid, R);
}
int InversePairs(vector<int> data) {
if(data.size() < ) return ;
int res = sortProcess(data, , data.size()-1);
return res;
}
};
【剑指Offer】两个单链表的第一个公共节点
输入两个链表，找出它们的第一个公共结点。（单向无环）
思路： 第一个思路，使用hash_set作为辅助空间，首先遍历第一个链表，将链表每个地址保存到hash_set中，然后再遍历第二个链表，边遍历边查找，如果找到，则返回该节点，否则返回nullptr.
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
if(pHead1 == nullptr || pHead2 == nullptr) return nullptr;
ListNode* cur = pHead1;
unordered_set<ListNode*> hash_set;
while(cur != nullptr){
hash_set.insert(cur);
cur = cur->next;
}
cur = pHead2;
while(cur != nullptr){
if(hash_set.find(cur) != hash_set.end()){
return cur;
}
cur = cur->next;
}
return nullptr;
}
};
第二种思路是不使用额外的辅助空间，直接进行遍历，假设当较短的链表这阵p1遍历完成后，将指针移到长链表的头节点pHead2，等p2也遍历完成后，指向pHead1，此时p1和p2之间的节点数正好两个链表节点数量的差，然后两个指针齐头并进，如果相交，则一定可以找到p1==p2的节点，并返回，否则返回nullptr。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
ListNode *p1 = pHead1;
ListNode *p2 = pHead2;
while(p1!=p2){
p1 = (p1==NULL ? pHead2 : p1->next);
p2 = (p2==NULL ? pHead1 : p2->next);
}
return p1;
}
};2
概念题
【概率统计】两个人抛硬币，规定第一个抛出正面的人必须穿女装，请问先抛的人穿女装的概率多大？
假设1表示正面，0表示反面，则两个抛置硬币的情况可以如下所示： 00 / 01 / 10 / 11 其中有人穿女装的有三种情况01、10、11, 在这三种情况下其中10、11为先抛的人穿女装，因此其概率为2/3.
【概率统计】将7723810的各位数字打乱排序,可组成的不同的7位自然数的个数是?
首先我们对7个数进行全排列，但是其中7重复了一次，因此，实际中的个数为7!/2。但是由于数字中有零的存在，因此需要减去首位为零的情况，即7!/2-6! = 2160
【概率统计】若串S=′software′,其子串的数目是多少？
注意：有一个大坑，空串也是一个字符串的字串 假设一个字符串的字符数量为n，那么每个字串的数目为n+n-1+…+1=n(n+1)/2。将n=8带入后得到总数为36，不要忘记加上空字符串，最后得到总数为37.
【概率统计】某地每天有流星雨的概率是相等的，一个人每天晚上都去观察，发现一个月能够看到流星的概率是91%，请问半个月中能够看到流星的概率是多少？
利用反向思维，如果半个月都看到流星的概率为p, 则没有看到的概率就是1-p，同时一个月都没有看到流星的概率为1-p, 从而1-(1-p)(1-p) = 91%, 则最后得到p=70%.