Category: 编程之美

编程之美3.3 计算字符串的相似度 (编辑距离)

Part 1： 题目描述 许多程序会大量使用字符串。对于不同的字符串，我们希望能够有办法判断其相似程序。我们定义一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为： 1.修改一个字符（如把“a”替换为“b”）; 2.增加一个字符（如把“abdd”变为“aebdd”）; 3.删除一个字符（如把“travelling”变为“traveling”）; 比如，对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g”的方式来达到目的。上面的两种方案，都仅需要一 次 。把这个操作所需要的次数定义为两个字符串的距离，而相似度等于“距离+1”的倒数。也就是说，“abcdefg”和“abcdef”的距离为1，相似度 为1/2=0.5。 给定任意两个字符串，你是否能写出一个算法来计算它们的相似度呢？ Part 2：分析 书中给出的解法是通过递归来做的。其实有更快更简便的方法——动态规划。 此题其实就是算法中的求“最短编辑距离”。 编辑距离定义：计算两个字符串的距离，完全相同的字符串距离为0，可以通过修改一个字符、增加一个字符或删除一个字符三种方式来使两个字符串相同，但这些方式会使得距离加1。 假设现在有两个字符串A和B A：David B：Taisy 用二维数组d[i][j]表示A中取前i个字符到B中取前j个字符的最短编辑距离。比如d[2][1]就代表从”Da”到”T”的最短编辑距离。这里为2（即把D换成T，去掉A 或者去掉D，把a换成T）。 首先我们作出初始化d[0][j] = j（字符串A子串长度为0，字符串B子串有多少个字符，就作多少次增加操作；于是同理，作删除操作，可得d[i][0] = i） 其中d[i][j]只有3个来源： 1). 来自d[i – i][j – 1]，即 “A的前i-1个字符组成的子串” 到 “B的前j-1个字符组成的子串” 的编辑距离，此时如果A[i] = B[j]，则最短编辑距离不变，否则最短编辑距离加1（即把A[i]变为B[j] ），所以d[i][j] = d[i – 1][j – 1] + (A[i] == B[j] ?  0 : 1) […]

POJ 2453 解题报告

题目意思：给定正整数x，求出在二进制表示中与他有相同个数的‘1’，且比他大的最小的数。 可以把此题当成求二进制中1的个数来做。而该算法在我的其他帖子（点击这里）中已经有详细说明。 代码： [cpp] #include <iostream> using namespace std; int Count (int); int main() { int x, num; while(cin >> x) { if(!x) break; num = Count(x); while(x++) if(Count(x) == num) { cout << x << endl; break; } } return 0; } int Count(int x) { x = (x & 0x55555555) + ((x >> […]

寻找发帖“水王”

编程之美第2.3题————寻找发帖“水王” 题目描述： Tango是微软亚洲研究院的一个试验项目。研究院的员工和实习生们都很喜欢在Tango上面交流灌水。传说，Tango有一大“水王”，他不但喜欢发贴，还会回复其他ID发的每个帖子。坊间风闻该“水王”发帖数目超过了帖子总数的一半。如果你有一个当前论坛上所有帖子（包括回帖）的列表，其中帖子作者的ID也在表中，你能快速找出这个传说中的Tango水王吗？ 首先，我们可以假设有这样一个数据结构来表示帖子 [cpp] type struct post { char* title; char* content; int uid; }post_t; [/cpp] 题目告诉我们已知所有帖子的列表，也就是说我们知道了所有帖子的链表 post_t*　post_list，或者是所有帖子的数组post_array[num]。然后让我们找到出现次数最多的uid是多少，并且该uid一定超过了总和的一半。为了叙述方便，下面用数组举例。最容易就想到的方法，就是遍历整个数组，记录每一个uid出现的次数，然后再比较一下，求出最大的。 其实，这个问题就可以等价于：求数组中出现次数大于一半的那个数 解法一 对数组排序，然后遍历排好序的数组，统计各ID出现的次数，找到超过一半的那个即可。代码如下： [cpp] int Find (int* post, int len) { sort(post, post + len); int num = 1; for(int i = 0; i < len; i++) { if(post[i] == post[i + 1]) num++; else num […]

求二进制数中1的个数

编程之美第2.1题————求二进制数中1的个数 题目描述：对于一个字节（8bit）的无符号整形变量，求其中的二进制表示中“1”的个数，要求算法的执行效率尽可能的高。 书中由浅入深地给出了几种解法。 解法一 也是最容易想到的，因为对于无符号整数，若采取对2取余操作，结果只有两种，奇数余1，偶数余0，而奇数的二进制最后一位为1，偶数的二进制最后一位为0。这样我们就可以通过奇偶判断来得到结果，以二进制数1011和1100举例： 1011 对2取余，余数为1，二进制末尾为1，即含有一个1 1100 对2取余，余数为0，二进制末尾为0，即含有一个0 不管这个二进制数的高位有多少个0或者多少个1，对2取余的操作只与最低位相关。所以，如果能够把所有的位都作为最低位，对2取余一次，然后将结果相加，即可得到该题答案。而二进制数中，右移操作，就相当于除以2，所以有了以下解法。 [c] unsigned int Count (unsigned int x) { unsigned int num = 0; // the result while(x) // end of loop when x is 0 { if(x % 2 == 1) // to judge whether the last bit is ‘1’ { num++; } x = […]