变种 此外,此题还有另外的一个变种形式,即给定一个长度为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状态方程: -
-
-
- 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) }
-
-
解法二、本解法来自为学论坛: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__nterestinglyB = bioinformatics bioinformatics__ 1011011011001111Edit distance = 11 Instead of minimizing the number of edge operations, we can associate a cost function to theoperations 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 : 

下面是代码,测试数据比较少,若有问题请指正: -
-
-
- #pragma once
- #include <string>
- class CStrEditDistance
- {
- public:
- CStrEditDistance(std::string& vStrRow, std::string& vStrColumn);
- ~CStrEditDistance(void);
- int getScore() { return m_Score; }
- int getEditDis() { return m_EditDis; }
- void setEditDis(int vDis) { m_EditDis = vDis; }
- void setScore(int vScore) { m_Score = vScore; }
- private:
- void process(const std::string& vStrRow, const std::string& vStrColumn);
- int getMaxValue(int a, int b, int c)
- {
- if (a < b){ if (b < c) return c; return b; }
- else { if (b > c) return a; return a < c ? c : a; }
- }
- private:
- int m_EditDis;
- int m_Score;
- };
-
- #include "StrEditDistance.h"
- #include <iostream>
- #include <iomanip>
- #define MATCH 2
- #define MISS_MATCH -1
- #define INSERT -1
- #define DELETE -1
- CStrEditDistance::CStrEditDistance(std::string& vStrRow, std::string& vStrColumn)
- {
- process(vStrRow, vStrColumn);
- }
- CStrEditDistance::~CStrEditDistance(void)
- {
- }
-
- void CStrEditDistance::process(const std::string& vStrRow, const std::string& vStrColumn)
- {
- int editDis = 0;
- int row = vStrColumn.length();
- int column = vStrRow.length();
- const int sizeR = row + 1;
- const int sizeC = column + 1;
-
- int **pScore = new int*[sizeR];
- for (int i = 0; i <= row; i++)
- pScore = new int[sizeC];
-
-
- for (int c = 0; c <= column; c++)
- pScore[0][c] = 0 - c;
- for (int r = 0; r <= row; r++)
- pScore[r][0] = 0 - r;
-
-
- for (int c = 1; c <= column; c++)
- {
- for (int r = 1; r <= row; r++)
- {
-
- int valueMatch;
- if (vStrColumn[r-1] == vStrRow[c-1])
- valueMatch = MATCH;
- else
- valueMatch = MISS_MATCH;
- int A = pScore[r-1][c] + INSERT;
- int B = pScore[r][c-1] + DELETE;
- int C = pScore[r-1][c-1] + valueMatch;
- pScore[r][c] = getMaxValue(A, B, C);
- }
- }
-
-
- int r = row, c = column;
- while(r > 0 && c > 0)
- {
- if (pScore[r][c]+1 == pScore[r-1][c]) { editDis++; r--; continue; }
- else if (pScore[r][c]+1 == pScore[r][c-1]) { editDis++; c--; continue; }
- else if (pScore[r][c]+1 == pScore[r-1][c-1]){ editDis++; r--; c--; continue; }
- else { r--; c--; }
- }
- if (r > 0 && c == 0) editDis += r;
- else if (c > 0 && r == 0) editDis += c;
-
- std::cout << std::endl;
-
-
- for (int i = 0; i <= row; i++)
- {
- for (int j = 0; j <= column; j++)
- std::cout << std::setw(2) << pScore[j] << " ";
- std::cout << std::endl;
- }
- std::cout << std::endl;
-
-
- setEditDis(editDis);
- setScore(pScore[row][column]);
-
- for (int i = 0; i <= row; i++)
- {
- delete pScore;
- pScore = NULL;
- }
- delete[] pScore;
- }
|