设为首页收藏本站

LUPA开源社区

 找回密码
 注册
文章 帖子 博客
LUPA开源社区 首页 业界资讯 技术文摘 查看内容

程序员编程艺术第二十八~二十九章:最大连续乘积子串、字符串编辑距离 ...

2013-3-28 14:32| 发布者: 红黑魂| 查看: 3842| 评论: 0|原作者: v_JULY_v|来自: CSDN博客

摘要: 前言    时间转瞬即逝,一转眼,又有4个多月没来更新blog了,过去4个月都在干啥呢?对的,今2013年元旦和朋友利用业余时间一起搭了个方便朋友们找工作的编程面试算法论坛:为学论坛http://www.51weixue.com/。最近 ...

变种

  此外,此题还有另外的一个变种形式,即给定一个长度为N的整数数组,只允许用乘法,不能用除法,计算任意(N-1)个数的组合中乘积最大的一组,并写出算法的时间复杂度。

  我们可以把所有可能的(N-1)个数的组合找出来,分别计算它们的乘积,并比较大小。由于总共有N个(N-1)个数的组合,总的时间复杂度为O(N2),显然这不是最好的解法。
  OK,以下解答来自编程之美
    解法1

    
解法2
  
  此外,还可以通过分析,进一步减少解答问题的计算量。假设N个整数的乘积为P,针对P的正负性进行如下分析(其中,AN-1表示N-1个数的组合,PN-1表示N-1个数的组合的乘积)。
1.P为0

          那么,数组中至少包含有一个0。假设除去一个0之外,其他N-1个数的乘积为Q,根据Q的正负性进行讨论:
Q为0
说明数组中至少有两个0,那么N-1个数的乘积只能为0,返回0;
Q为正数
返回Q,因为如果以0替换此时AN-1中的任一个数,所得到的PN-1为0,必然小于Q
Q为负数
如果以0替换此时AN-1中的任一个数,所得到的PN-1为0,大于Q,乘积最大值为0。

     2.    P为负数

根据“负负得正”的乘法性质,自然想到从N个整数中去掉一个负数,使得PN-1为一个正数。而要使这个正数最大,这个被去掉的负数的绝对值必须是数组中最小的。我们只需要扫描一遍数组,把绝对值最小的负数给去掉就可以了。

      3.    P为正数

    类似地,如果数组中存在正数值,那么应该去掉最小的正数值,否则去掉绝对值最大的负数值。
    上面的解法采用了直接求N个整数的乘积P,进而判断P的正负性的办法,但是直接求乘积在编译环境下往往会有溢出的危险(这也就是本题要求不使用除法的潜在用意),事实上可做一个小的转变,不需要直接求乘积,而是求出数组中正数(+)、负数(-)和0的个数,从而判断P的正负性,其余部分与以上面的解法相同。

    在时间复杂度方面,由于只需要遍历数组一次,在遍历数组的同时就可得到数组中正数(+)、负数(-)和0的个数,以及数组中绝对值最小的正数和负数,时间复杂度为O(N)。


第二十九章、字符串编辑距离


题目描述:给定一个源串和目标串,能够对源串进行如下操作:
   1.在给定位置上插入一个字符
   2.替换任意字符
   3.删除任意字符
写一个程序,返回最小操作数,使得对源串进行这些操作后等于目标串,源串和目标串的长度都小于2000。

提醒:上文前言中已经说过了,此题反复出现,最近考的最多的是百度和Google的笔试面试经常考察。下图则是2013年Google的校招试题原景重现:


解答

    解法一、    此题跟上面的最大连续乘积子串类似,常见的思路是动态规划,下面是简单的DP状态方程:

  1. //动态规划:    
  2.     
  3. //f[i,j]表示s[0...i]与t[0...j]的最小编辑距离。    
  4. f[i,j] = min { f[i-1,j]+1,  f[i,j-1]+1,  f[i-1,j-1]+(s[i]==t[j]?0:1) }    
  5.     
  6. //分别表示:添加1个,删除1个,替换1个(相同就不用替换)。   

    解法二、本解法来自为学论坛:http://www.51weixue.com/thread-482-1-1.html

     编辑距离的定义和计算方法如下:
Given two strings A and B, edit A to B with the minimum number of edit operations:

  • a) .Replace a letter with another letter
  • b) .Insert a letter
  • c) .Delete a letter
    E.g.
A = interestingly    _i__nterestingly
B = bioinformatics   bioinformatics__
                     1011011011001111
Edit distance = 11
    Instead of minimizing the number of edge operations, we can associate a cost function to the
operations and minimize the total cost. Such cost is called edit distance. Instead of using string edit, in computational biology, people like to use string alignment.We use similarity function, instead of cost function, to evaluate the goodness of the alignment.
    E.g. of similarity function: match – 2, mismatch, insert, delete – -1.
Consider two strings ACAATCC and AGCATGC.
One of their alignment is

In the above alignment, space (‘_’) is introduced to both strings. There are 5 matches, 1
mismatch, 1 insert, and 1 delete.The alignment has similarity score 7.
    A_CAATCC
    AGCA_TGC
    Note that the above alignment has the maximum score.Such alignment is called optimal
alignment.String alignment problem tries to find the alignment with the maximum similarity
score!String alignment problem is also called global alignment problem.
Needleman-Wunsch algorithm
    Consider two strings S[1..n] and T[1..m].Define V(i, j) be the score of the optimal alignment
between S[1..i] and T[1..j].
Basis:
V(0, 0) = 0
V(0, j) = V(0, j-1) + d(_, T[j]):Insert j times
V(i, 0) = V(i-1, 0) + d(S, _):Delete i times
that is:

Example :


下面是代码,测试数据比较少,若有问题请指正:

  1. //copyright@ peng_weida  
  2. //实现代码如下:  
  3. //头文件StrEditDistance.h  
  4. #pragma once  
  5. #include <string>  
  6. class CStrEditDistance  
  7. {  
  8. public:  
  9.     CStrEditDistance(std::string& vStrRow, std::string& vStrColumn);  
  10.     ~CStrEditDistance(void);  
  11.     int  getScore()    { return m_Score;   }  
  12.     int  getEditDis()  { return m_EditDis; }  
  13.     void setEditDis(int vDis) { m_EditDis = vDis; }  
  14.     void setScore(int vScore) { m_Score = vScore; }  
  15. private:  
  16.     void process(const std::string& vStrRow, const std::string& vStrColumn);  
  17.     int getMaxValue(int a, int b, int c)  
  18.     {  
  19.         if (a < b){ if (b < c) return c; return b; }  
  20.         else { if (b > c) return a; return a < c ? c : a; }  
  21.     }  
  22. private:  
  23.     int   m_EditDis;  
  24.     int   m_Score;  
  25. };  
  26. //源文件StrEditDistance.cpp  
  27. #include "StrEditDistance.h"  
  28. #include <iostream>  
  29. #include <iomanip>  
  30. #define MATCH        2  
  31. #define MISS_MATCH   -1  
  32. #define INSERT       -1  
  33. #define DELETE       -1  
  34. CStrEditDistance::CStrEditDistance(std::string& vStrRow, std::string& vStrColumn)  
  35. {  
  36.     process(vStrRow, vStrColumn);  
  37. }  
  38. CStrEditDistance::~CStrEditDistance(void)  
  39. {  
  40. }  
  41. //FUNCTION:  
  42. void CStrEditDistance::process(const std::string& vStrRow, const std::string& vStrColumn)  
  43. {  
  44.     int editDis = 0;     //编辑距离  
  45.     int row = vStrColumn.length();    
  46.     int column = vStrRow.length();  
  47.     const int sizeR = row + 1;  
  48.     const int sizeC = column + 1;  
  49.    
  50.     int **pScore = new int*[sizeR];  //二维指针  
  51.     for (int i = 0; i <= row; i++)  
  52.     pScore = new int[sizeC];  
  53.    
  54.     //初始化第一行和第一列  
  55.     for (int c = 0; c <= column; c++)  
  56.         pScore[0][c] = 0 - c;  
  57.     for (int r = 0; r <= row; r++)  
  58.         pScore[r][0] = 0 - r;  
  59.    
  60.     //从v(1,1)开始每列计算  
  61.     for (int c = 1; c <= column; c++)  
  62.     {  
  63.         for (int r = 1; r <= row; r++)  
  64.         {  
  65.           //计算v(i,j)  
  66.           int valueMatch;  
  67.           if (vStrColumn[r-1] == vStrRow[c-1])  
  68.               valueMatch = MATCH;  
  69.           else  
  70.               valueMatch = MISS_MATCH;    
  71.           int A = pScore[r-1][c] + INSERT;  
  72.           int B = pScore[r][c-1] + DELETE;  
  73.           int C = pScore[r-1][c-1] + valueMatch;  
  74.           pScore[r][c] = getMaxValue(A, B, C);  
  75.         }  
  76.     }  
  77.    
  78.     //计算编辑距离  
  79.     int r = row, c = column;  
  80.     while(r > 0 && c > 0)  
  81.     {  
  82.         if (pScore[r][c]+1 == pScore[r-1][c])      { editDis++; r--; continue; }  
  83.         else if (pScore[r][c]+1 == pScore[r][c-1]) { editDis++; c--; continue; }  
  84.         else if (pScore[r][c]+1 == pScore[r-1][c-1]){ editDis++; r--; c--; continue; }  
  85.         else { r--; c--; }  
  86.     }  
  87.     if (r > 0 && c == 0)  editDis += r;  
  88.     else if (c > 0 && r == 0) editDis += c;  
  89.    
  90.     std::cout << std::endl;  
  91.     //----------------DEBUG-------------------//  
  92.     //打印数据  
  93.     for (int i = 0; i <= row; i++)  
  94.     {  
  95.          for (int j = 0; j <= column; j++)  
  96.          std::cout << std::setw(2) << pScore[j] << "  ";  
  97.          std::cout << std::endl;  
  98.     }  
  99.     std::cout << std::endl;  
  100.    
  101.     //设置编辑距离和得分  
  102.     setEditDis(editDis);  
  103.     setScore(pScore[row][column]);  
  104.    
  105.     for (int i = 0; i <= row; i++)   //释放内存  
  106.     {  
  107.         delete pScore;  
  108.         pScore = NULL;  
  109.     }  
  110.     delete[] pScore;  
  111. }  


酷毙

雷人

鲜花

鸡蛋

漂亮
  • 快毕业了,没工作经验,
    找份工作好难啊?
    赶紧去人才芯片公司磨练吧!!

最新评论

关于LUPA|人才芯片工程|人才招聘|LUPA认证|LUPA教育|LUPA开源社区 ( 浙B2-20090187 浙公网安备 33010602006705号   

返回顶部