从一道算法题说去1

声明:算法学习来自,7月算法,面试&算法&机器学习&找工作就上七月算法

1. 今天学习的算法是 LCS,最长公共子序列,属于典型的动态规划基础题。

    十分钟搞定LCS 学习视频:http://julyedu.com/video/play/id/9

2. 实践代码:

/*
Algorithm LCS
*/
#include <stack>
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 50

// Get LCS
int GetLcs(int dp[][MAX], int path[][MAX], const string& strOne, const string& strTwo) {
	int strOneLength = strOne.length();
	int strTwoLength = strTwo.length();
	for (int i = 0; i < strOneLength; ++i) {
		dp[i][0] = 0;
	}
	for (int i = 0; i < strTwoLength; ++i) {
		dp[0][i] = 0;
	}
	for (int i = 0; i < strOneLength; ++i) {
		for (int j = 0; j < strTwoLength; ++j) {
			if (strOne[i] == strTwo[j]) {
				dp[i+1][j+1] = dp[i][j] + 1;
				path[i+1][j+1] = 0; //leftTop
			}
			else {
				if (dp[i][j+1] > dp[i+1][j]) {
					dp[i+1][j+1] = dp[i][j+1];
					path[i+1][j+1] = -1; //top
				}
				else {
					dp[i+1][j+1] = dp[i+1][j];
					path[i+1][j+1] = 1; //left
				}
			}
		}
	}
	return dp[strOneLength][strTwoLength];
}

// Print LCS string
string PrintLcs(int path[][MAX], const string& strOne, const string& strTwo) {
	stack <char> stk;
	int i = strOne.length();
	int j = strTwo.length();
	while ((i > 0) && (j > 0)) {
		if (path[i][j] == 0) {
			stk.push(strOne[i-1]);
			--i;
			--j;
		}
		else if (path[i][j] == 1) {
			--j;
		}
		else {
			--i;
		}
	}
	string lcsString = "";
	while (!stk.empty()) {
		lcsString = lcsString + stk.top();
		stk.pop();
	}
	return lcsString;
}

int main(int argc, char **argv) {
	string strOne = "bdcaba";
	string strTwo = "abcbdab";
	int dp[MAX][MAX], path[MAX][MAX];

	cout << GetLcs(dp, path, strOne, strTwo) << endl;
	cout << PrintLcs(path, strOne, strTwo) << endl;

	return 0;
}
时间: 2024-10-23 19:59:52

从一道算法题说去1的相关文章

从一道算法题说去2

今天的算法题是关于 字符串的最小编辑距离问题求解. 1. 什么是字符串编辑距离 编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数.许可的编辑操作包括将一个字符替换成另一个字符,添加一个字符,删除一个字符. 例如将kitten一字转成sitting: a. sitten (k→s)  b. sittin (e→i)  c. sitting (→g)  俄罗斯科学家Vladimir Levenshtein在1965年提出

求助一道算法题,关于数组算法

问题描述 求助一道算法题,关于数组算法 有一个字符串数组{"用户1,商品1,200","用户2,商品2,100","用户3,商品1,300","用户4,商品3,50","用户5,商品3,50"},写的方法需要返回的是{"用户2,商品2","用户3,商品1","用户4,商品3"}也就是说比较下每种商品的最高价格是谁,并返回谁买了,如果价格相同取最先买

一道算法题,看看大家的思路(续)

"一道算法题,看看大家的思路",看了众多的回复,本人愚钝,没有看明白其中的奥妙.在细细研究<编程之美>中的文章后,终于理解了这个算法的思路.现将这个算法的演算过程以及代码实现(VB2005)赋予其后,和各位交流. 现再将题目复述一遍: 题目描述:有31,-41,59,26,-53,58,97,-93,-23,84十个数.SUM(N,M)表示从第N个数到到第M个数的和.例如:SUM(2,3)=-41+59=18.问:最大的和是多少?对应的N和M是多少? 先不管N和M的计算,直

每日一道算法题-寻找丑数

题目:我们把只包含因子2.3和5的数称作丑数(Ugly Number).例如6.8都是丑数,但14不是,因为它包含因子7.习惯上我们把1当做是第一个丑数.求按从小到大的顺序的第1500个丑数. 分析:寻找一个数是不是满足某种数(质数,水仙数)等,最简单的方法就是遍历,对于任意一个丑数必定可以写成2^m*3^n*5^p,因而对于一个丑数,只含有2,3,5因子,也就意味着该数number%2==0:number%3==0:number%5==0,如果一个数能被2整除,我们就连续除以2:能被3整除,我

一道算法题,看看大家的思路

题目描述:有31,-41,59,26,-53,58,97,-93,-23,84十个数.SUM(N,M)表示从第N个数到到第M个数的和.例如:SUM(2,3)=-41+59=18.问:最大的和是多少?对应的N和M是多少? 这个题目并不难,实现的方法多种多样.最坏的算法,遍历所有的情况,求出最大和. 我在这儿提一个算法的思路,不是最优的,主要是讲解这个算法的. 模拟生物算法(谢谢装配脑袋指正,这应该是遗传算法). 根据题目,构造生物S,生物S有三个属性N.M.V.N表示开始的下标,M表示结束的下标,

求一道算法题的实现,谢谢了

问题描述 题目如下: 一个21位的整数,它的各个位数的21次方的和加起来等于它本身.要求:程序在三分钟内完成,Java语言实现.谢谢了! 问题补充:蔡华江 写道 解决方案 http://huajiang.iteye.com/blog/763764解决方案二:总算搞完了,2秒内可以求出结果.待会贴上思路解决方案三:估计要用数学方法,我只发现了一个规律,就是一个数的21次方的个位数还是这个数,继续关注~~~

设计-一道二重积分算法题,要求复杂度低于n^2

问题描述 一道二重积分算法题,要求复杂度低于n^2 对于x∈X{x0,x1,x2,...,xn-1},y∈Y{y0,y1,y2,...,yn-1},又已知一个矩阵C,C中的元素C(i,j)的值为p(xi,xj) 设计一个算法计算 假设这里log(.)属于基本算符,有没有让它的复杂度低于n^2的方法? 解决方案 每天一道算法题2 删除链表结点(时间复杂度为O(1)))

算法题——一道数字组合的题目的求解

题目:给定一个数字,和一个范围,产生所有在范围内的不重复的数字之和,和等于给定的数字. 举例:给数字12,范围3-6.可以产生以下5个组合: 1.3+3+3+3 2.3+3+6 3.3+4+5 4.4+4+4 5.6+6 要求给出最快实现,并且是非递归. 这是某人给我出的一道算法题.经过考虑,给出了解法.最快的谈不上(算法无止境.人外有人),没有用递归.   还是以题目的例子说明,数字12,范围3-6.给出了5种组合.将这5种组合改写一下 3+3+3+3=3*4+4*0+5*0+6*0 记作:(

算法题:uva 1330

题目链接: http://uva.onlinejudge.org/index.php? option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=4076 以前做过一道一维的,这题只是变成了二维的,其他方法都一样.HDU 1506  Largest Rectangle in a Histogram   题解 代码1: #include<cstdio> #include<cs