N-Gram 模型的假设

N-Gram 模型基于这样一种假设,第n个词的出现只与前面n-1个词相关,而与其它任何词都不相关,整句的概率就是各个词出现概率的乘积。在拼写检查里即是一个字母的出现概率只和前n-1个字母的出现概率相关,并且是前n-1个字母出现概率的乘积。

20世纪70年代之前,科学家们试图推断这个文字序列是否合乎文法、含义是否正确等。但这条路走不动。贾里尼克从另外一个角度来看待这个问题。用一个简单的统计语言模型非常美丽的搞定了它。贾里尼克的出发点非常easy:一个句子是否合理。就看看它的可能性大小怎样。至于可能性就用概率来衡量。第一个句子出现的概率最大,因此。第一个句子最有可能句子结构合理。这种方法更普通而严格的描写叙述是: 假定S表示某一个有意义的句子,由一连串特定顺序排列的词w1,w2,w3,…,wn组成。这里n是句子的长度。如今,我想知道S在文本中(语料库)出现的可能性,也就是数学上所说的S的概率P(S)。我们须要一个模型来估算概率。既然S=w1,w2,w3,…,wn。那么最好还是把P(S)展开表示: P(S)=P(w1,w2,w3,…,wn)

利用条件概率的公式。S这个序列出现的概率等于每个词出现的条件概率相乘,于是P(w1,…,wn)展开为:、
P(S)=P(W1,W2,W3,…,Wn)=P(W1)P(W2|W1)P(W3|W1,W2)…P(Wn|W1,W2,…,Wn-1)
当中P(w1)表示第一个词w1出现的概率;P(w2|w1)是已知第一个词的前提下。第二个词出现的概率;以此类推,词wn出现的概率取决于它前面全部的词。
可是这样的方法存在两个致命的缺陷:一个缺陷是參数空间过大(条件概率P(wn|w1,w2,…,wn-1)的可能性太多,无法估算),不可能有用处。另外一个缺陷是数据稀疏严重。
数据稀疏的解释:如果词表中有20000个词,如果是bigram model(二元模型)那么可能的2-gram就有400000000个,如果是trigram(3元模型),那么可能的3-gram就有8000000000000个!那么对于当中的非常多词对的组合,在语料库中都没有出现,依据最大似然估计得到的概率将会是0。这会造成非常大的麻烦,在算句子的概率时一旦当中的某项为0。那么整个句子的概率就会为0,最后的结果是,我们的模型仅仅能算可怜兮兮的几个句子,而大部分的句子算得的概率是0. 因此,我们要进行数据平滑(data Smoothing),数据平滑的目的有两个:一个是使全部的N-gram概率之和为1,使全部的N-gram概率都不为0,有关数据平滑处理的方法能够參考《数学之美》第33页的内容。

leetcode-137. Single Number II[很有意思的一道题目]

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题目链接:https://leetcode.com/problems/single-number-ii/

 

这道题目最直接的方法是使用哈希表来解决。

但是使用哈希表是文艺青年的做派。

对于追求极致的大牛来说,这显然还不够。

下面的解法思路是从其它大牛copy来的,简单分析一下:

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        one, two, three = 0, 0, 0
        for v in nums:
            two |= one & v
            one ^= v
            three = ~(one & two)
            one &= three
            two &= three
        return one
思路解析:
因为除了一个出现了一次的数,其它数都重复了3次。我们可以想到用
位运算来解决问题。
我们用one记录当前位置之前(包括当前位置)所有数字的各个二进制位
的总数模3等于1 ,同样用two记录当前位置之前(包括当前位置)所有数
字的各个二进制位的总数模3等于2
比如当前数字是3,前面有1与4,那么one会记录3,1,4第1至32位bit
中1出现的次数模3==1的结果,two会记录模3==2的结果。
one&two的结果的某个比特位==1,说明one中的该比特位与two中的
该比特位都是1,那么说明该比特位出现了3次,需要从当前结果中消掉
这些比特位。很简单,one&two按位取反表明不需要去掉的比特位,
那么one&(~(one&two))将one中的出现3次的比特位去掉。
最后剩下只出现一次的数的所有的比特位都在one中记录。那么one肯定
就是那个只出现一次的数。

leetcode-287. Find the Duplicate Number[Floyd算法-龟兔算法]

该题的另一种解法是环检测的方法。

http://keithschwarz.com/interesting/code/find-duplicate/FindDuplicate.python.html

以下为翻译:

这道题(据说)花费了计算机科学界的传奇人物Don Knuth 24小时才解出来。并且我只见过一个人(Keith Amling)用更短时间解出此题。

问题的第一部分 - 证明至少存在一个重复元素 - 是鸽笼原理的直接应用。如果元素的范围是[1, n],那么只存在n种不同的值。如果有n+1个元素,其中一个必然重复。

问题的第二部分 - 在给定约束条件下寻找重复元素 - 可就难多了。 要解决这个问题,我们需要敏锐的洞察力,使问题通过一列的转化,变为一个完全不同的问题。

解决本题需要的主要技巧就是要注意到:由于数组的n + 1个元素范围从1到n,我们可以将数组考虑成一个从集合{1, 2, ..., n}到其本身的函数f。这个函数的定义为f(i) = A[i]。基于这个设定,重复元素对应于一对下标i != j满足 f(i) = f(j)。我们的任务就变成了寻找一对(i, j)。一旦我们找到这个值对,只需通过f(i) = A[i]即可获得重复元素。

但是我们怎样寻找这个重复值呢?这变成了计算机科学界一个广为人知的“环检测”问题。问题的一般形式如下:给定一个函数f,序列x_i的定义为

    x_0     = k       (for some k)
    x_1     = f(x_0)
    x_2     = f(f(x_0))
    ...
    x_{n+1} = f(x_n)

假设函数f从定义域映射到它本身,此时会有3种情况。首先,如果定义域是无穷的,则序列是无限长并且没有循环的。例如,函数 f(n) = n + 1,在整数范围内满足这个性质 - 没有数字是重复的。 第二, 序列可能是一个闭合循环,这意味着存在一个i使得x_0 = x_i。在这个例子中,序列在一组值内无限循环。第三,序列有可能是的“ρ型的”,此时序列看起来像下面这样:

      x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j}
                         ^                       |
                         |                       |
                         +-----------------------+

也就是说,序列从一列链条型的元素开始进入一个环,然后无限循环。我们将环的起点称为环的“入口”。

对于从数组中寻找重复元素这个问题,考虑序列从位置n开始重复调用函数f。亦即从数组的最后一个元素开始,然后移动到其元素值对应的下标处,并且重复此过程。可以得到:此序列是ρ型的。要明白这一点,需要注意到其中一定有环,因为数组是有限的并且当访问n个元素时,一定会对某个元素访问两次。无论从数组的哪一个位置开始,这都是成立的。

另外,注意由于数组元素范围1到n,因此不存在值为0的元素。进而,从数组的第一个元素开始调用一次函数f之后,再也不会回到这里。这意味着第一个元素不会是环的一部分,但如果我们继续重复调用函数f,最终总会访问某个节点两次。从0节点开始的链条与环形相接,使得其形状一定是ρ型。

此外,考虑一下环的入口。由于节点位于环的入口,一定存在两个输入,其对应的函数f的输出值都等于入口元素下标。要使其成立,一定存在两个下标i != j,满足f(i) = f(j),亦即A[i] = A[j]。因而环的入口一定是重复值。

这是由Robert Floyd提出的一个著名算法,给定一个ρ型序列,在线性时间,只使用常数空间寻找环的起点。这个算法经常被称为“龟兔”算法,至于原因下面就明白了。
算法背后的思想是定义两个变量。首先,令c为进入环的链的长度,然后令l为环的长度。接下来,令l'为大于c的l的倍数的最小值。可以得出结论:对于上文定义的任意ρ型序列的l',都有
 
     x_{l'} = x_{2l'}
 
证明实际上非常直观并且具有自明性 - 这是计算机科学中我最喜欢的证明之一。思路就是由于l'至少为c,它一定包含在环内。同时,由于l'是环长度的倍数,我们可以将其写作ml,其中m为常数。如果我们从位置x_{l'}开始(其在环内),然后再走l'步到达x_{2l'},则我们恰好绕环m次,正好回到起点。

Floyd算法的一个关键点就是即使我们不明确知道c的值,依然可以在O(l')时间内找到值l'。思路如下。我们追踪两个值"slow"和"fast",均从x_0开始。然后迭代计算
 
     slow = f(slow)
     fast = f(f(fast))
 
我们重复此步骤直到slow与fast彼此相等。此时,我们可知存在j满足slow = x_j,并且fast = x_{2j}。 由于x_j = x_{2j},可知j一定至少为c,因为此时已经在环中。另外,可知j一定是l的倍数,因为x_j = x_{2j}意味着在环内再走j步会得到同样的结果。最后,j一定是大于c的l的最小倍数,因为如果存在一个更小的大于c的l的倍数,我们一定会在到达j之前到达那里。所以,我们一定有j = l',意味着我们可以在不知道环的长度或者形状的情况下找到l'。

要完成整个过程,我们需要明白如何使用l'来找到环的入口(记为x_c)。要做到这一步,我们再用最后一个变量,记为"finder",从x_0出发。然后迭代重复执行过程:

 
    finder = f(finder)
    slow   = f(slow)
 
直到finder = slow为止。
我们可知:
(1) 两者一定会相遇 
(2) 它们会在环的入口相遇。 
要理解这两点,我们注意由于slow位于x_{l'},如果我们向前走c步,那么slow会到达位置x_{l' + c}。由于l'是环长度的倍数,相当于向前走了c步,然后绕环几圈回到原位。换言之,x_{l' + c} = x_c。另外,考虑finder变量在行进c步之后的位置。 它由x_0出发,因此c步之后会到达x_c。这证明了(1)和(2),由此我们已经证明两者最终会相遇,并且相遇点就是环的入口。

算法的美妙之处在于它只用O(1)的额外存储空间来记录两个不同的指针 - slow指针和fast指针(第一部分),以及finder指针(第二部分)。但是在此之上,运行时间是O(n)的。要明白这一点,注意slow指针追上fast指针的时间是O(l')。由于l'是大于c的l的最小倍数,有两种情况需要考虑。首先,如果l > c,那么就是l。 否则,如果l < c,那么我们可知一定存在l的倍数介于c与2c之间。要证明这一点,注意在范围c到2c内,有c个不同的值,由于l < c,其中一定有值对l取模运算等于0。最后,寻找环起点的时间为O(c)。这给出了总的运行时间至多为O(c + max{l, 2c})。所有这些值至多为n,因此算法的运行时间复杂度为O(n)。

Python程序如下:
class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        fast = 0
        slow = 0

        while True:
            fast = nums[nums[fast]]
            slow = nums[slow]
            if slow == fast:
                break

        fast = 0
        while fast != slow:
            fast = nums[fast]
            slow = nums[slow]

        return fast

leetcode-287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

  1. You must not modify the array (assume the array is read only).
  2. You must use only constant, O(1) extra space.
  3. Your runtime complexity should be less than
    O(n<sup>2</sup>)

    .

  4. There is only one duplicate number in the array, but it could be repeated more than once.

题目描述:

给定长度为n+1的整形数组,该数组的每一个整数均在[1,n]之间。

假设只有一个重复的数字,请找出该重复数字。

注意:

1.不能修改数组(假设数组只读)

2.空间复杂度为O(1)

3.时间复杂度小于O(n^2)

4.数组中只有一个重复数字,但是它可能重复不止一次。

 

思路:

根据抽屉原理,如果数组中不超过n/2的元素的数目大于n/2,那么重复数字肯定出现在前半段。反之出现在后半段。导致这种结果的原因在于数组只有一个数字是重复的,也就是说n个数字不重复。超过一半的数字处于平均值之下,那么重复数字 只可能在前半部分。

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        right = len(nums)-1
        left = 1


        while left < right:
            mid = left + (right-left)/2
            counter = 0
            for num in nums:
                if num <= mid:
                    counter += 1
            if counter > mid:
                right = mid-1
            else:
                left = mid+1
        return left

leetcode-41.First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given

[1,2,0]

return

3

,
and

[3,4,-1,1]

return

2

.

Your algorithm should run in O(n) time and uses constant space.

题目描述:

给出无序的整数数组,找出第一个缺失的正数。

例如,

[1,2,0] 返回 3

[3,4,-1,1]返回2

算法的时间复杂度不超过O(n)并且使用常量空间。

思路:

题目要求是找到缺失的第一个正数,那么我们只把数组中是正数的元素交换到其在数组中其元素值的位置,比如a[5] = 3,那么将a[5]与a[2]交换。

这样正数都会被放置在其应该处于的位置,而负数以及元素值超过数组长度的数跳过。最后所有的有效正数都会被放置在其对应的位置。

等全部交换完成后从头开始查找第一个元素其元素值与位置不符,返回该元素位置。

Python代码示例:

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        while i < len(nums):
            if nums[i] != i+1 and nums[i] < len(nums) and nums[i] >= 1 and nums[i] != nums[nums[i]-1]:
                tmp = nums[i]
                nums[i] = nums[tmp-1]
                nums[tmp-1] = tmp
            else:
                i += 1
        print nums
        for i in xrange(len(nums)):
            if i+1 != nums[i]:
                return i+1
        return len(nums)+1

约瑟夫环

普通的解法:构建环然后循环去除元素

int JosephuseCircle(unsigned int n,unsigned int m){
if(n<1||m<1) return -1;
unsigned int i=0;
list<int> l;
for(i=0;i<n;++i)
l.push_back(i);
list<int>::iterator cur = l.begin();
while(l.size()>1){
for(int i=1;i<m;++i){
cur++;
if(cur == l.end())
cur = l.begin();
}
list<int>::iterator next = ++cur;
if(next == l.end())
next = l.begin();
–cur;
l.erase(cur);
cur = next;
}
return *(cur);
}

更高效的解决方法:构建递推公式

  1.  定义关于数据长度n和删除步进m的方程F(n,m),表示在n个数字0,1,…,n-1中每次删除第m个数字后最后剩下的一个数字。
  2. 在n的数字中,第一个被删除的是(m-1)%n,简记为k。那么剩下的n-1个数字是0,1,…,k-1,k+1,…,n-1.并且下一次删除从k+1开始。
  3. 在第二次删除时,数字序列是 k+1,k+2,…,n-1,0,1,…k-1。
  4. 此时的函数F(n,m)的数字序列发生了变化,为了适应该变化我们将此时的F(n,m)记为F'(n-1,m)
  5. 由于F与F’的结果都是最后一个数字,那么F(n,m)=F'(n-1,n)
  6. 然后对第二次的数字序列做映射:

k+1              ===>                       0

k+2              ===>                       1

n-1              ===>                       n-1-k-1=n-k-2

0                  ===>                       n-k-1

1                   ===>                      n-k

k-1                ===>                       n-2

7.从上面得出映射 p(x) = (x-k-1)%n,表示当前映射数字x实际上是F(n,m)中的第(x-k-1)%n个数字。逆映射p^-1(x) = (x+k+1)%n;

8.由于映射后的序列与最初的序列都具有同样的形式即都从0开始,那么仍然可以F(n-1,m)表示。可以得出

F'(n-1,m) = p^-1(F(n-1,m))=映射之前剩下的最后一个数字=[F(n-1,m)+k+1]%n

把k = (m-1)%n带入,那么F(n,m) = F'(n-1,m)=[F(n-1,m)+m]%n

9:上面的公式可以归纳为以下公式:

F(n,m)=0 if  n=1 else [F(n-1,m)+m]%n 

这是一个递归的求解过程,因为最后n=1时有具体的结果不会再继续递归下去。
int JosephuseCircle2(unsigned int n,unsigned int m){
if(n<1||m<1)
return -1;
int last = 0;
for(int i=2;i<=n;++i){
last = (last+m)%i;
}
return last;
}

leetCode-319. Bulb Switcher

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

Example:

Given n = 3. 
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off]. 
So you should return 1, because there is only one bulb is on.

继续阅读“leetCode-319. Bulb Switcher”

动态规划算法解决查找最长回文问题

class Solution {
public:
string longestPalindrome(string s) {
//BOTTOM-TOP 动态规划实现查找最长回文串
//初始化备忘矩阵
const int sz = s.size();
bool**q = new bool*[sz];
for (int i = 0; i < sz; ++i){
q[i] = new bool[sz];
for (int j = 0; j < sz; ++j){
q[i][j] = false;
}
}
//开始自底部向顶部动态规划
//首先初始化回文串起始终止位置
int pstart = -1, pend = pstart;
for (int i = sz – 1; i >= 0; –i){
for (int j = i; j < sz; ++j){
//如果子串的首尾字符相同,并且其距离不大于2或者首尾之间的子子串在备忘中是true的,
//该字串肯定是一个回文
//cout << i << “->” << j<<“|”;
if (s[i] == s[j] && (j – i <= 2 || q[i+1][j-1])==true){
q[i][j] = true;
if ((j – i+1)>(pend – pstart)) {
pstart = i;
pend = j;
//cout << i << “->” << j << endl;
}
}
}//end for

}//enf for
delete[] q;
return s.substr(pstart, pend – pstart + 1);
}

};

leetcode9 [Palindrome Number] [Easy,C++]

题目来源:

https://leetcode.com/problems/palindrome-number/

题目描述:

Determine whether an integer is a palindrome. Do this without extra space.

Some hints:Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

中文描述:

判断一个int是不是对称数。

限制计算空间。

解题思路:

根据对称数的判定特点,首先将int按中点截为2个子段。

然后对字段进行判断。

对字段的判断有多种方法,可以将其中一个逆转然后比较两个数的大小。这种方法要比下面的方法效率更高。

也可以按位判断,从一个段的正序与另一个段的逆序按位判断。

我的AC:

<1>正逆序按位比较法     100ms

bool isPalindrome(int x) {
if (x < 0) return false;
if (x == 0) return true;
unsigned pdlen = 0, half=0;
int jlen = x,header=0,tailer=0,prefix=0;
while (jlen){//首先求出int长度
++pdlen;
jlen /= 10;
}
half = pdlen / 2;//分割数据
prefix = pow(10, half);
header = pdlen & 0x1 ? x / pow(10, half + 1) : x / pow(10, half);
tailer = x – x / prefix*prefix;

while (half){//按位判断
int div = pow(10, half – 1);
int htop = header / div;
header -= htop*div;

int tbot = tailer % 10;
tailer /= 10;
if (htop != tbot) return false;
–half;
}
return true;
}

<2>单一逆序比较法   76ms

bool isPalindrome(int x) {
if (x < 0) return false;
if (x == 0) return true;
unsigned pdlen = 0, half=0;
int jlen = x,header=0,tailer=0,prefix=0;
while (jlen){
++pdlen;
jlen /= 10;
}
half = pdlen / 2;
prefix = pow(10, half);
header = pdlen & 0x1 ? x / pow(10, half + 1) : x / pow(10, half);
tailer = x – x / prefix*prefix;

//上面先求出数据长度

//下面将header逆转与tailer比较大小

//不逆转tailer的原因在于像00000012这样的tailer逆序的话不会算成21000000,而是21.而header逆转不会有这个问题。

int reverse_header = 0;
while (header){
int mod = header % 10;
header /= 10;
reverse_header = reverse_header * 10 + mod;
}
if (reverse_header != tailer) return false;
return true;
}

leetcode8 [String to Integer (atoi)] [Easy,C++]

题目来源:

https://leetcode.com/problems/string-to-integer-atoi/

题目描述:

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Update (2015-02-10):
The signature of the

C++

function had been updated. If you still see your function signature accepts a

const char *

argument, please click the reload button to reset your code definition.

spoilers alert… click to show requirements for atoi.

Requirements for atoi:The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

中文描述:

实现atoi方法以将string转为一个int。

atoi的实现要求:

略过字符串开始的空格,直到遇到第一个非空格字符。

对从该非空格字符开始直到下一个空格或字符串结尾之间的子字符串进行处理。

在子字符串中从头开始捕获尽可能长的连续数字字符串。

如果没有该模式的字符串,返回0。

如果数字范围超过了int所能表示的范围,超过上界返回INT_MAX,低于下界返回INT_MIN.

解题思路:

本题考查对特殊情况的处理。

<1>int上下界的处理方法,比如要用long long类型的变量接收总和。并在总和计算循环中对上下界进行比较,防止最后的总和越过long long范围的情况发生。

<2>对于首个非空格字符为+ -两个字符的特殊考虑。

<3>对于字符开始的连续空格与计数开始之后出现的空格的处理

我的AC:

int myAtoi(string str) {
long long sum = 0;//用long long类型的变量接收总和,以防止可能的溢出。
const int max = 0x7fffffff, min = 0x80000000;//设置int的上下界
int flag = 1,sflag=0;
string::iterator is = str.begin();
while (is != str.end()){
char curChar = *is;
if (isdigit(curChar)){
if (curChar==’0’&&sum==0) ++is;//如果是字符是0,并且sum=0,那么这个0前面没有别的数字,跳过该0往后计算
else {
sum = sum * 10 + curChar – ‘0’;//否则计算sum
if (sum*flag > max) return max;//及时判断是否越界
if (sum*flag < min) return min;
++is;
}
sflag = 1;
}
else if (isspace(curChar)){//对空格的处理
if (sflag) break;//如果空格出现在计数数字之后,停止循环
++is;//如果空格出现在字符串最前面,继续循环
}
else if (curChar == ‘-‘ || curChar == ‘+’){//对+-号的处理
string::iterator is_tail = is + 1;
if (is_tail != str.end()){
if (isdigit(*is_tail)) {
if (curChar==’-‘) flag = -1;
}
else break;
}
++is;
}
else break;
}

return sum*flag;
}