Probability
array
a.fill(0);
右值引用
今天看了DTW，http://en.wikipedia.org/wiki/Dynamic_time_warping
目的是匹配两个长度不等，但是轮廓相同的序列的相似度的匹配算法。具体的例子
就是两个人说一个单词，但是语速不同，导致长度不同，因此匹配的位置也不同，因此需要允许扭曲序列，也就是存在偏移的匹配。
int DTWDistance(s: array [1..n], t: array [1..m]) {
DTW := array [0..n, 0..m]
for i := 1 to n
DTW[i, 0] := infinity
for i := 1 to m
DTW[0, i] := infinity
DTW[0, 0] := 0
for i := 1 to n
for j := 1 to m
cost:= d(s[i], t[j])
DTW[i, j] := cost + minimum(DTW[i-1, j ], // insertion
DTW[i , j-1], // deletion
DTW[i-1, j-1]) // match
return DTW[n, m]
}
加上偏移量限制的算法，也就是对于每个i，都是j是从i-w 到i+w计算，其他的不匹配，考虑到i-w可能下越界，因此max(1, i-w), 考虑到i+w上越界，因此min(m, i+w)
今天做RepeatDNASeq 的时候，每个DNA都编码一次，O(10n)，肖哥说可以用位运算，这样可以后面的不用遍历整个dna序列，复杂度降到O(n),
那么每次val都左移2位，然后再取低位的20位，然后累加新来的一个数的值
val<<=2;
val&=m;
val+=GetIndex(s[i+9]);
整个代码如下：
class Solution {
public:
int GetIndex(char s)
{
if(s=='A') return 0;
if(s=='T') return 1;
if(s=='G') return 2;
if(s=='C') return 3;
}
vector<string> findRepeatedDnaSequences(string s) {
int n=s.size();
unordered_map<int, pair<int, int>> myhash;
string dna=s.substr(0, 10);
int val=0;
for(auto e: dna)
val=val*4+GetIndex(e);
myhash[val].fi++;myhash[val].se=i;
int m=0x000fffff;
for(int i=1;i+9<n;i++)
{
val<<=2;
val&=m;
val+=GetIndex(s[i+9]);
myhash[val].fi++;myhash[val].se=i;
}
vector<string> ans;
for(auto e: myhash)
{
if(e.se.fi>1) ans.push_back(s.substr(e.se.se, 10));
}
return ans;
}
};
优化之后，我的代码在飞~
今天一个朋友问到一道概率题，我已经很生疏了。
2012年5月，10000个乘客里面在美联航出现延误航班的人数是0.81
问后面的10000人里面，有0个，至少一个和至少两个延误航班的概率。
一开始直接以为是二项分布，事件发生概率是0.81/10000, 然后二项分布搞搞，
但是答案是在Possion分布里面，主要是因为里面有2012年5月这个时间段里，给定的10000个人里面。
搜到著名博主ruanyifeng的一篇博客，
http://www.ruanyifeng.com/blog/2013/01/poisson_distribution.html
里面提到了泊松分布的三个条件
（1）顾客购买水果罐头是小概率事件。
（2）购买水果罐头的顾客是独立的，不会互相影响。
（3）顾客购买水果罐头的概率是稳定的。
但是感觉最重要的单位时间或者单位面积没有提及。
那么上面的题目lamda就是0.81， 带入公式即可
另外这道题目 似乎第二问没看懂 promoter是谁
Darwin Head, a 35-year-old sawmill worker, won
$1 million and a Chevrolet Malibu Hybrid by scoring
15 goals within 24 seconds at the Vancouver Canucks
National Hockey League game (B. Ziemer, “Darwin evolves
into an Instant Millionaire,” Vancouver Sun, February 28,
2008, p. 1). Head said he would use the money to pay off
his mortgage and provide for his children, and he had no
plans to quit his job. The contest was part of the Chevrolet
Malibu Million Dollar Shootout, sponsored by General
Motors Canadian Division. Did GM-Canada risk the
$1 million? No! GM-Canada purchased event insurance from
a company specializing in promotions at sporting events such
as a half-court basketball shot or a hole-in-one giveaway at
the local charity golf outing. The event insurance company
estimates the probability of a contestant winning the contest,
and for a modest charge, insures the event. The promoters pay
the insurance premium but take on no added risk as the in-
surance company will make the large payout in the unlikely
event that a contestant wins. To see how it works, suppose
that the insurance company estimates that the probability a
contestant would win a Million Dollar Shootout is 0.001, and
that the insurance company charges $4,000.
a. Calculate the expected value of the profit made by the
insurance company.
b. Many call this kind of situation a win–win opportunity
for the insurance company and the promoter. Do you
agree? explain.
题目出自 statics for managers using microsoft excel, 感觉国外教材的题目和国内教材风格不同。